Post

确定与不确定性推理

Posted
By lreverse
11 min read
确定与不确定性推理

1. 推理

逻辑与推理是人工智能的核心问题

  • 推理就是按照某种策略从已有事实和知识推出结论的过程

按推理的逻辑基础分类

演绎推理

  • 从已知的一般性知识出发，推理出适合于某种个别情况的结论过程
  • 一般到个别
  • 常用形式：三段论法（大前提, 小前提, 结论）
  • 不能增殖新知识

归纳推理

  • 从大量特殊事例出发，归纳出一般性结论的推理过程
  • 个别到一般
  • 增殖新知识

按所用知识的确定性分类

确定性推理

  • 推理时所用的知识和证据都是确定的，推出的结论也是确定的

不确定性推理

  • 推理时所用的知识和证据不都是确定的，推出的结论也不确定

按推理中所用知识是否具有启发性分类

启发式推理

  • 推理过程中应用与问题有关的启发性知识，即解决问题的的策略、技巧及经验，以加快推理过程，提高搜索效率

非启发式推理

  • 在推理过程中，不运用启发性知识，只按照一般的控制逻辑进行推理
  • 这种方法缺乏对求解问题的针对性，所以推理效率较低，容易出现“组合爆炸”问题

2. 自然演绎推理

从一组已知为真的事实出发，直接运用命题逻辑或谓词逻辑中的推理规则推出结论的过程

基本的推理规则

  • 假言三段论
    • $P\rightarrow Q, Q\rightarrow R \Rightarrow P\rightarrow R$
  • 假言推理
    • $P, P\rightarrow Q为真 \Rightarrow Q为真$
  • 拒取式
    • $P\rightarrow Q, \neg Q \Rightarrow \neg P$
1
2
3
4

如果一个人大学毕业，则他就具有独立生活的能力
如果一个人具有独立生活的能力，则他就可以离开父母
P→Q, Q→R ⇒ P→R
如果一个人大学毕业，则他就可以离开父母

3. 归结演绎推理

归结演绎推理是一种基于鲁滨逊归结原理的机器推理技术。
鲁滨逊归结原理亦称为消解原理，是一种基于逻辑的“反证法”。就是把永真性的证明转化为关于不可满足性的证明

鲁滨逊归结原理

  • 关键点
    1. 子句集的子句之间是合取关系。所以，子句集中只要有一个子句为不可满足，则整个子句集就是不可满足的
    2. 空子句是不可满足的。所以，一个子句集中如果包含空子句，则该子句集就一定是不可满足的
  • 基本思想
    1. 把欲证明问题的结论否定，并加入子句集，得到一个扩充的子句集S’
    2. 设法检验子句集S’是否含有空子句。若含有空子句，则表明S’是不可满足的；若不含有空子句，则继续使用归结法，在子句集中选择合适的子句进行归结，直至导出空子句或不能继续归结为止
  • 包括
    • 命题逻辑归结原理
    • 谓词逻辑归结原理

命题逻辑归结原理

  • 互补文字：$P$与$\neg P$
  • 归结式：$C_1$ 和$C_2$ 是子句集中的任意两个子句，如果$C_1$ 中的文字$L_1$ 与$C_2$ 中的文字$L_2$ 互补，那么可从$C_1$ 和$C_2$ 中分别消去$L_1$ 和$L_2$ ，并将$C_1$ 和$C_2$ 中余下的部分按析取关系构成一个新的子句$C_{12}$
  • $examples$：
    • $C_1 =﹁P ∨Q$ ，$C_2 =﹁ Q$，$C_3 =P$，求$C_1$ 、$C_2$ 、$C_3$ 的归结式$C_{123}$
      • 先对$C_1$、$C_2$归结：$C_{12} =﹁P$
      • 再对$C_{12}$和$C_3$归结：$C_{123} =NIL$
  • 归结原理：$F$为已知前提，$G$为欲证明的结论，归结原理把证明$G$为$F$的逻辑结论转化为证明$F\wedge \neg G$为不可满足
  • 反演过程
    1. 否定目标公式$G$，得$\neg G$
    2. 把$\neg G$并入到公式集F中，得到${F, \neg G}$
    3. 把${F, \neg G}$化为子句集$S$
    4. 应用归结原理对子句集$S$中的子句进行归并，并把每次得到的归结式并入$S$中。如此反复进行，若出现空子句，则停止归结，此时就证明了$G$为真

谓词逻辑归结原理

在谓词逻辑中，由于子句集中的谓词一般都含有变元，因此不能像命题逻辑那样直接消去互补文字。而需要先用一个合一对变元进行代换，然后才能进行归结

4. 知识图谱推理

归纳学习-FOIL(First Order Inductive Learner)

  • 归纳逻辑程序设计(ILP)算法
  • 从一般到特殊，逐步给目标谓词添加前提约束谓词，直到所构成的推理规则不覆盖任何反例

5. 贝叶斯网络推理（因果推理）

  • 辛普森悖论
    • 总体样本上成立的某种关系却在分组样本里恰好相反
    • 在某些情况下，忽略潜在的“第三个变量”，可能会改变已有的结论，而我们常常却一无所知
  • 结构因果模型（因果模型）
  • 因果图（DAGO）：一般是有向无环图
  • 贝叶斯网络
    • 描述变量联合分布或数据生成机制的模型（可用DAG描述）

概述

  • 概率模型
    • 观测变量（证据）：智能体获取的世界状态的某些信息
    • 未知变量：智能体需要推理得出其他信息
    • 模型：已知变量与未知变量之间的关系
  • 一个概率模型是一组随机变量的联合分布
    1. 有定义域的变量
    2. 随机变量赋值之后被称为“实例”
    3. 联合概率：描述每一个“实例”的概率大小
    4. 归一化：所有“实例”的概率之和等于1
  • 概率推理
    • 已知某些概率的情况下计算出一个未知的目标概率
    • 普遍形式：条件概率的求解
  • 链式法则
    • $P(x_1, x_2, …, x_n)=\prod_{i}^{n}{P(x_i \mid x_1…x_i-1)}$
    • 例：$P(x_1, x_2, x_3)=P(x_1)P(x_2 \mid x_1)P(x_3 \mid x_1, x_2)$
  • 贝叶斯法则
    • $P(x \mid y)=\frac{P(x)P(y \mid x)}{P(y)}$
    • 可以基于观测或统计的条件概率，求出相反的条件下事件发生的概率
    • 是很多AI系统的基础

贝叶斯网络

也称概率图模型
是一种使用简单的局部概率分布来描述复杂联合概率分布的技术
原因：对于一般问题来说，联合概率表太大；根据经验，同时学习多个变量的概率分布很困难

  • 相互独立性
    • $\forall x,y: P(x, y)=P(x)P(y)$
    • 记作：$Ｘ \perp!!!!\perp Y$
    • 用于模型简化
      • 通常来说，相互独立性的假设往往是基于经验性的假设
  • 条件独立性
    • $\forall x,y,z: P(x, y \mid z)=P(x \mid z)P(y \mid z)$
    • 记作：$Ｘ \perp!!!!\perp Y \mid Z$
  • 表示方法
    • 拓扑结构（图）+ 局部条件概率
    • 节点：每个节点是一个条件概率，代表了一个变量
      • 每个条件概率以父节点取值的组合为条件$P(X \mid a_1 … a_n)$
    • 弧：变量间的相互作用
      • 编码条件独立性
    • 隐式地编码了联合概率分布
  • D-分离
    • 用于判断任意两个节点的相关性和独立性
    • 类型表示说明
      因果链$P(x, y, z)=P(x)P(y\vert x)P(z\vert y)$给定Y时，X和Z条件独立
      分连（共同原因Y）$P(x, y, z)=P(y)P(x\vert y)P(z\vert y)$给定Y时，X和Z条件独立
      汇连（共同结果Y）$P(x, y, z)=P(y)P(x\vert y)P(z\vert y)$X和Z是条件独立的；但在给定Y或Y的后代时，X和Z是相关的
  • 计算后验概率
    • 枚举法：利用联合概率推理
    • 变量消除法：交替进行合并和消除隐藏变量
  • 采样
    • 从概率分布S中抽取N个样本
    • 计算近似后验概率（证明其可以收敛到真实概率P）
Course, 人工智能导论
This post is licensed under CC BY 4.0 by the author.