第三章 确定性推理方法

第三章 确定性推理方法思维导图，关于人工智能导论课本的一些简单总结，可以帮助学习者理解和记忆。

第三章 确定性推理方法

• 推理的基本概念
  • 推理的定义
  • 推理方式及其分类
    • 1
      • 演绎推理
        • 由一般到特殊（三段论式）
      • 归纳推理
        • 由个别到一般
          • 完全归纳推理（必然性推理）
          • 不完全归纳推理（非必然性推理）
      • 默认推理
        • 知识不完全的情况下假设某些条件已经具备所进行的推理
    • 2
      • 确定性推理
        • 推理时所用的知识与证据都是确定的，推出的结论也是确定的，其真值或者为真或者为假。
      • 不确定性推理
        • 推理时所用的知识与证据不都是确定的，推出的结论也是不确定的。
          • 似然推理
          • 近似推理或模糊推理
    • 3
      • 单调推理
        • 随着推理向前推进及新知识的加入，推出的结论越来越接近最终目标。
      • 非单调推理
        • 由于新知识的加入，不仅没有加强已推出的结论，反而要否定它，使推理退回到前面的某一步，重新开始。
    • 4
      • 启发式推理
        • 启发性知识：与问题有关且能加快推理过程、提高搜索效率的知识。
      • 非启发式推理
  • 推理的方向
    • 正向推理（事实推动推理）
      • 已知事实→结论
    • 逆向推理（目标驱动推理）
      • 从某一假定目标开始
    • 混合推理
      • 先正向后逆向：先进行正向推理，帮助选择某个目标，即从已知事实演绎出部分结果，然后再用逆向推理证实该目标或提高其可信度
      • 先逆向后正向：先假设一个目标进行逆向推理，然后再利用逆向推理中得到的信息进行正向推理，以推出更多的结论。
    • 双向推理
      • 正向推理与逆向推理同时进行，在某一位置“碰头”的一种推理
  • 冲突消解策略
    • 匹配情况
      • 恰好匹配成功（一对一）； 不能匹配成功； 多种匹配成功（一对多、多对一、多对多）
    • 多种冲突消解策略
      • 按针对性排序 按已知事实的新鲜性排序 按匹配度排序 按条件个数排序 按上下文限制排序 按冗余限制排序 根据领域问题的特点排序
• 自然演绎推理
  • 定义
    • 从一组已知为真的事实出发，运用经典逻辑的推理规则推出结论的过程
  • 推理规则
    • P规则，T规则，假言推理，拒取式推理
  • 优点
    • 表达定理证明过程自然易理解 拥有丰富的推理规则，推理过程灵活 便于嵌入领域启发式知识
  • 缺点
    • 易产生组合爆炸，得到的中间结论一般呈指数形式递增
• 谓词公式化为子句集的方法
  • 反证法：P⥤Q，当且仅当P∧┐Q⇔F，即q为p的逻辑结论当且仅当P∧┐Q是不可满足的
  • 原子谓词公式： 一个不能再分解的命题。 文字：原子谓词公式及其否定。 P ：正文字，┐P：负文字。 子句：任何文字的析取式。任何文字本身也都是子句。 空子句：不包含任何文字的子句。 子句集：由子句构成的集合。
  • 为此，公式不可满足的充要条件是其子聚集不可满足
• 海伯伦定理
  • H域
    • 设 S 为子句集，则按下述方法构造的域H∞称为海伯伦域，简记为 H 域。 （1）令 H0 是 S 中所有个体常量的集合，若 S 中不包含个体常量，则令H0＝{α}，其中α为 任意指定的一个个体常量。 （2）令Hi＋1＝Hi∪{ S 中所有 n 元函数f（x1，…，xn） 是 H 中的元素}，其中i＝0，1，2，… 。
  • 基子句：用H 域中的元素代换子句中的变元后所得的子句，其中的谓词称为基原子。
  • 原子集：子句集中所有基原子构成的集合。
  • 子句集在 H 域上的解释：对子句集中出现的常量、函数及谓词取值，一次取值就是一个解释。
  • 定理：子句集不可满足的充要条件是存在一个有限的不可满足的基子句集 。
• 鲁滨逊归结原理
  • 子句集中子句之间是合取关系，只要有一个子句不可满足， 则子句集就不可满足。
  • 基本思想：检查子句及s中是否包含空子句，若包含则s不可满足。若不包含在s中选择合适的子句进行归结，一旦归结出空子句，则说明s是不可满足的
  • 基子句的归结：设C1与C2是子句集中的任意两个子句，如果 C1中的文字L1与 C2中的文字L2互补，那么从C1和 C2中分别消去L1和L2，并将二个子句中余下的部分析取，构成一个新子句C12 。
  • 定理：归结式C12是其亲本子句C1与C2的逻辑结论。即如果 C1与C2为真，则C12为真。
  • 推论：设C1与C2是子句集S中的两个子句，C12是它们的归结式，若用C12代替C1与C2后得到新子句集S1，则由S1不可满足性可推出原子句集S的不可满足性，即：S1的不可满足性⇔S的不可满足性
  • 推论：设C1与C2是子句集S中的两个子句，C12是它们的归结式，若C12 加入原子句集S，得到新子句集S1，则S与S1在不可满足的意义上是等价的，即：S1的不可满足性⇔S的不可满足性
  • 谓词逻辑中的归结原理（含有变量的子句的归结）
    • 设是 C1与C2 两个没有相同变元的子句，L1和 L2分别是C1与C2 中的文字，若 б是L1 和┐L2的最一般合一，则称C12＝（C1б-{L1б}∨（C2б-{L2б}） 为 C1和C2 的二元归结式。
  • 对于谓词逻辑，归结式是其亲本子句的逻辑结论。 对于一阶谓词逻辑，即若子句集是不可满足的，则必存在一个从该子句集到空子句的归结演绎；若从子句集存在一个到空子句的演绎，则该子句集是不可满足的。 如果没有归结出空子句，则既不能说 S 不可满足，也不能说 S 是可满足的。
• 归结反演
  • 应用归结原理证明定理的过程
  • 用归结反演证明的步骤是： （1）将已知前提表示为谓词公式F。 （2）将待证明的结论表示为谓词公式Q，并否定得到﹁ Q 。 （3）把谓词公式集{F，┐ Q} 化为子句集S。 （4）应用归结原理对子句集S中的子句进行归结，并把每次 归结得到的归结式都并入到S中。如此反复进行，若出 现了空子句，则停止归结，此时就证明了Q为真。
• 应用归结反演求解问题
  • 应用归结原理求解问题的步骤： （1）已知前提 F 用谓词公式表示，并化为子句集 S ； （2）把待求解的问题 Q 用谓词公式表示，并否定 Q，再与 ANSWER 构成析取式（﹁ Q ∨ ANSWER ） （3）把（﹁ Q∨ ANSWER） 化为子句集，并入到子句集 S中，得到子句集 S' ； （4）对S'应用归结原理进行归结； （5）若得到归结式 ANSWER ，则答案就在 ANSWER 中。