人工智能导论：第二章逻辑与推理

一、命题逻辑

1.1 命题逻辑的定义

命题逻辑(proposition logic)是应用一套形式化规则对以符号表示的描述性陈述进行推理的系统。
在命题逻辑中，一个或真或假的描述性陈述被称为原子命题，对原子命题的内部结构不做任何解析。
若干原子命题可通过逻辑运算符来构成复合命题。

如：

p: 北京是中国的首都

r : x<8

p为真命题，q为假命题，r不是命题，因为无法判断真假。

1.2 命题联结词

五个联结词：

联结词的真值表：

对于条件和双向条件两个联结词：

“如果p那么q(p⟶q)”定义的是一种蕴涵关系（即充分条件），也就是命题q 包含着命题p （ p是q的子集）。p不成立相当于p是一个空集，空集可被其他所有集合所包含，因此当p不成立时，“如果p那么q”永远为真，真值表对于为 True。

1.3 逻辑等价

定义：给定命题p和命题q，如果p和q在所有情况下都具有同样真假结果，那么p和q在逻辑上等价，一般用≡来表示，即p≡q。

1.4 推理规则

1.5 命题范式

有限个简单合取式构成的析取式称为析取范式
有限个简单析取式构成的合取式称为合取范式
析取范式和合取范式统称为范式（normal form）

性质：

一个析取范式是不成立的，当且仅当它的每个简单合取式都不成立。
一个合取范式是成立的，当且仅当它的每个简单析取式都是成立的。
任一命题公式都存在着与之等值的析取范式与合取范式（注意：命题公式的析取范式与合取范式不是唯一的）

二、谓词逻辑

2.1 定义

命题逻辑的局限性：在命题逻辑中，每个陈述句是最基本的单位(即原子命题)，无法对原子命题进行分解。因此在命题逻辑中，不能表达局部与整体、一般与个别的关系。

在谓词逻辑中，将原子命题进一步细化，分解出个体、谓词和量词，来表达个体与总体的内在联系和数量关系，这就是谓词逻辑研究内容。其中，个体、谓词（predicate）和量词（quantifier）为三个核心概念。

个体：所研究领域中可以独立存在的具体或抽象的概念。
谓词：用来刻画个体属性，或者个体间关系的存在性的元素，值为真或假，有几个参数就是几元谓词。
全称量词：全称量词用符号∀表示，表示一切的、凡是的、所有的、每一个等。 ∀x表示定义域中的所有个体， (∀x)P(x)表示定义域中的所有个体具有性质P
存在量词：存在量词用符号∃表示，表示存在、有一个、某些等。 ∃x表示定义域中存在一个或若干个个体，(∃x)P(x)表示定义域中存在一个个体或若干个体具有性质P

2.2 全称量词与存在量词之间的组合

(∀x)¬P(x)≡(¬∃x)P(x)
(¬∀x)P(x)≡(∃x)¬P(x)
(∀x)P(x)≡(¬∃x)¬P(x)
(∃x)P(x)≡ (¬∀x)¬P(x)

2.3 合式公式：

命题常项、命题变项、原子谓词（不存在任何量词与联结词）是合式公式。
如果A和B是合式公式，那么¬A、 A∧B、 A∨B、 A→B 、 A⟷B 都是合式公式
如果A是合式公式， x是个体变元，则∃xA(x) 和∀xA(x)也是合式公式
有限次地使用上述规则求得公式是合式公式

2.4 推理规则：

全称量词消去(Universal Instantiation, UI): (∀x)A(x)→A(y)

全称量词引入(Universal Generalization, UG): A(y)→(∀x)A(x)

存在量词消去(Existential Instantiation, EI): (∃x)A(x)→A(c)

存在量词引入(Existential Generalization, EG): A(c)→(∃x)A(x)

2.5 自然语言的形式化：

前提：1) 每驾飞机或者停在地面或者飞在天空；2) 并非每驾飞机都飞在天空

结论：有些飞机停在地面

形式化：plane(x): x是飞机；in_ground(x): x停在地面；on_fly(x): x飞在天空

已知：

(∀x)(plane(x)→in_ground(x)∨on_fly(x)), (¬∀x)(plane(x)→on_fly(x))

请证明：

(∃x)(plane(x)∧in_ground(x))

三、知识图谱推理

3.1概念

3.1.1 知识图谱的定义

知识图谱可视为包含多种关系的图。在图中，每个节点是一个实体（如人名、地名、事件和活动等），任意两个节点之间的边表示这两个节点之间存在的关系。一般而言，可将知识图谱中任意两个相连节点及其连接边表示成一个三元组（triplet）, 即 (left_node, relation, right_node) ，例：(水利工程, is an, 工程)。下图所示的知识图谱中，已知三峡大坝和葛洲坝为水利工程且位于同一流域，两者之间具有反调节的关系，于是知识图谱通过推理规则可以得知，同属于哥伦比亚河的达拉斯水坝和大古力水坝也具有反调节的关系。这种通过机器学习等方式对知识图谱所蕴含的关系进行挖掘的方法称为知识图谱推理。

3.1.2 构成

概念：层次化组织

实体：概念的示例化描述

属性：对概念或实体的描述信息

关系：概念或实体之间的关联

推理规则：可产生语义网络中上述新的元素

在实际中，知识图谱一般可以通过标注多关系图（labeled multi-relational graph）来表示，如下图就是一个知识图谱。

3.2 归纳学习

归纳逻辑程序设计 (inductive logic programming，ILP)算法，是机器学习和逻辑程序设计交叉领域的研究内容。ILP使用一阶谓词逻辑进行知识表示，通过修改和扩充逻辑表达式对现有知识归纳，完成推理任务。作为ILP的代表性方法，FOIL（First Order Inductive Learner）通过序贯覆盖实现规则推理。

可利用一阶谓词来表达刻画知识图谱中节点之间存在的关系，如图中形如<James,Couple,David>的关系可用一阶逻辑的形式来描述，即Couple(James, David)。

Couple(x, y)是一阶谓词，Couple是图中实体之间具有的关系，x和y是谓词变量

从图中已有关系可推知David和Ann具有父女关系，但这一关系在图中初始图(无红线)中并不存在，是需要推理的目标。用数学语言描述父女的关系就是：(∀x)(∀y)(∀z)(Mother(z, y)∧ Couple(x,z)→Father(x, y))，那么如何通过归纳学习推理得到这条规则呢？

下面用FOIL来进行推理：

FOIL算法推理手段：正例反例背景知识=>目标谓词

3.2.1 一些概念

目标谓词：Father(x, y)，此例中目标谓词只有一个正例Father(David, Mike)。

反例在知识图谱中一般不会显式给出，但可从知识图谱中构造出来。如从知识图谱中已经知道Couple(David, James)成立，则Father(David, James)可作为目标谓词P的一个反例，记为¬Father (David, James)。只能在已知两个实体的关系且确定其关系与目标谓词相悖时，才能将这两个实体用于构建目标谓词的反例，而不能在不知两个实体是否满足目标谓词前提下将它们来构造目标谓词的反例。

背景知识：知识图谱中目标谓词以外的其他谓词实例化结果，如Sibling(Ann, Mike)。

推理思路：从一般到特殊，逐步给目标谓词添加前提约束谓词，直到所构成的推理规则不覆盖任何反例。

从一般到特殊：对目标谓词或前提约束谓词中的变量赋予具体值，如将(∀x)(∀y)(∀z)(Mother(z, y)∧ Couple(x,z)→Father(x, y))这一推理规则所包含的目标谓词Father(x, y)中x和y分别赋值为David和Ann，进而进行推理。

FOIL中信息增益值(information gain)：评判一个前提约束谓词引入的价值，计算公式为：

3.2.2 具体流程

首先找出待加入的前提约束谓词和目标样例集合。

然后依次将谓词加入到推理规则中作为前提约束谓词，并计算所得到新推理规则的FOIL增益值。基于计算所得FOIL增益值来选择最佳前提约束谓词。可以得到下面的计算结果，找到最优的（FOIL增益最大的）加入。

例如将Mother(x, y)作为前提约束谓词加入，可得到推理规则Mother(x, y)→Father(x, y)，在背景知识中，Mother(x, y)有两个实例Mother(James, Ann)和Mother(James, Mike)。对于Mother(James, Mike)这一实例， x= James，y = Mike，将x和y代入Father(x, y)得到Father(James, Mike)，可知在训练样本中Father(James, Mike)是一个反例。覆盖正例和反例数量分别为0和2，算出收益以为负无穷，记为NA，依次计算，发现是最优的前提约束谓词。

将Couple(x,z)加入到推理规则，得到Couple(x,z)→Father(x, y)新推理规则将训练样例中与该推理规则不符的样例去掉。这里不符指当Couple(x,z)中x取值为David时，与Father(David, )或¬Father(David, )无法匹配的实例。训练样本集中只有正例Father(David, Mike)和负例¬Father(David, James)两个实例。

继续计算信息增益量，发现mother(z,y) 最大，将Mother(z, y)加入，得到新推理规则Mother(z, y)∧ Couple(x,z)→Father(x, y) 当x=David、y=Mike、z=James时，该推理规则覆盖训练样本集合中正例Father(David, Mike)且不覆盖任意反例，因此算法学习结束。
总结：给定目标谓词，FOIL算法从实例（正例、反例、背景样例）出发，不断测试所得到推理规则是否还包含反例，一旦不包含负例，则学习结束，展示了 “归纳学习”能力。

3.3 路径排序

与FOIL算法不同，路径排序推理算法（PRA）的基本思想是将实体之间的关联路径作为特征，来学习目标关系的分类器。

路径排序算法的工作流程主要分为三步：

(1) 特征抽取：生成并选择路径特征集合。生成路径的方式有随机游走（random walk）、广度优先搜索、深度优先搜索等。

(2) 特征计算：计算每个训练样例的特征值P(s rightarrow t;pi_j)。该特征值可以表示从实体节点s出发，通过关系路径pi_j到达实体节点t的概率；也可以表示为布尔值，表示实体s到实体t之间是否存在路径π_j；还可以是实体s和实体t之间路径出现频次、频率等。

(3) 分类器训练：根据训练样例的特征值，为目标关系训练分类器。当训练好分类器后，即可将该分类器用于推理两个实体之间是否存在目标关系。

四、因果推理

4.1 因果推理概述

4.1.1 辛普森悖论

定义：辛普森悖论表明，在某些情况下，忽略潜在的“第三个变量”，可能会改变已有的结论，而我们常常却一无所知。从观测结果中寻找引发结果的原因、考虑数据生成的过程，由果溯因，就是因果推理。

4.1.2 因果推理主要模型：

结构因果模型(structural causal model, SCM)：也被称为因果模型（causal model）或Neyman–Rubin因果模型。
因果图（causal diagram）：Judea Pearl 1995年提出。每个结构因果模型M都与一个因果图G相对应。
关系：每个结构因果模型M都对应一个因果图G相对应

4.1.3 因果推理的层级：

4.1.4 有向无环图

定义：

一般而言，因果图是有向无环图(directed acyclic graphs, DAG)。有向无环图刻画了图中所有节点之间的依赖关系。DAG 可用于描述数据的生成机制。这样描述变量联合分布或者数据生成机制的模型，被称为 “贝叶斯网络”（Bayesian network）。对于任意的有向无环图模型，模型中d个变量的联合概率分布由每个节点与其父节点之间的条件概率 P(child|parents)的乘积给出：

P(x_1,x_2,…,x_d) = displaystyleprod^d_{j = 1}P(x_j|x_{pa(j)})，x_{pa(j)} 表示节点x_j的父节点集合。

DAG可被视为因果过程：父辈节点“促成”了孩子几点的取值，如下图的联合分布例子：