人工智能导论【三】

一、经典推理逻辑


人们对各种事物进行分析、综合并最后作出决策时,通常从已知事实出发,通过运用已掌握的知识,找出其中蕴含的事实,或归结出新的事实,这一过程称为推理。

1、推理分类

2、推理的控制策略

推理的控制策略:推理过程是一个思维过程,即求解问题的过程,求解问题的质量和效率不仅依赖于所采用的求解方法,而且还依赖于求解问题的策略,即推理的控制策略。

推理的控制策略主要包括:推理方向、搜索策略、冲突消解策略、求解策略及限制策略等。

推理方向:正向、逆向、混合、双向

3、模式匹配

模式匹配:是指对两个知识模式(如两个谓词公式、两个框架片断或两个语义网络片断等)的比较与耦合,即检查这两个知识模式是否完全一致或近似一致。如果两者完全一致,或虽不完全一致但其相似程度落在指定的限度内,就称它们是可匹配的,否则为不可匹配。

(1)变量代换

因为代换的目的是使某些变元被另外的变元、常量或函数取代,使之不 再在公式中出现,而{g(y)/x,f(x)/y}在x与y之间出现了循环代换的情况,它既没有消去x,也没有消去y.

前代后。

(2)复合

1589961710053

(3)合一

(5)冲突消解策略

1.按针对性排序——本策略是优先选用针对性较强的产生式规则。

2.按已知事实的新鲜性排序——把数据库中后生成的事实称为新鲜的事实。

3.按匹配度排序 ——匹配度大的知识优先选用。

4.根据领域问题的特点排序

5.按上下文限制排序

6.按冗余限制排序

7.按条件个数排序

4、自然演绎推理

自然演绎推理:从一组已知为真的事实出发,直接运用经典逻辑的推理规则推出结论的过程称为自然演绎推理。

5、归结演绎推理

(1)子句

例子:

6、归结演绎推理

(1)海伯伦定理

(2)鲁宾逊归结原理

这两个推论告诉我们:为要证明子句集S的不可满足性,只要对其中可进行归结的子句进行归结,并把归结式加入子句集S,或者用归结式替换它的亲本子句,然后对新子句集证明不可满足性就可以了。如果经过归结能得到空子句,根据空子句的不可满足性,立即可得到原子句集S是不可满足的结论。这就是用归结原理证明子句集不可满足的基本思想。

在命题逻辑中,对不可满足的子句集S,归结原理是完备的。即,若子句集不可满足,则必然存在一个从S到空子句的归结演绎;若存在一个从S到空子句的归结演绎,则S一定是不可满足的。

对于可满足的子句集,用归结原理得不到任何结果。

(3)归结反演

(4)归结策略

归结策略大致可分为两大类:

删除策略:通过删除某些无用的子句来缩小归结的范围;

限制策略:通过对参加归结的子句进行种种限制,尽可能减小归结的盲目性,使其尽快的归结出空子句。

①归结的一般过程
删除策略
  • 纯文字删除法。

    • 纯文字:如果某文字L在子句集中不存在可与之互补的文字
      ¬L,则称该文字为纯文字。
    • 在归结时纯文字不可能被消去,因而用包含它的子句进行归结时不可能得到空子句,即这样的子句对归结是无意义的,所以可把它所在的子句从子句集中删去,这样不会影响子句集的可满足性。
  • 重言式删除法

    • 重言式:如果一个子句同时包含互补文字对,则称该子句为重言式。

      例如:P(x)⋁¬P(x),P(x)⋁Q(x)⋁¬P(x) ,重言式是真值为真的子句。

    • 对于一个子句集来说,不管增加或者删去一个真值为真的子句都不会影响它的不可满足性,因而可从子句集中删去重言式。

  • 包孕删除法

限制策略
  • 支持集策略(完备的)

    • 支持集策略:对参加归结的子句作出如下限制:每一次归结时,亲本子句至少应有一个是由目标公式的否定所得到的子句,或者是它们的后裔。
  • 线性输入策略(不完备的)

    • 参加归结的两个子句必须至少有一个是初始子句集中的子句。所谓初始子句集是指初始时要求进行归结的那个子句集。例如在归结反演中,初始子句集就是由已知前提及结论的否定化来的子句集。
    • 它是不完备的
  • 单文字子句策略(不完备的)

    • 如果一个子句只包含一个文字,则称它为单文字子句。单文字子句策略要求参加归结的两个子句必须至少有一个是单文字子句。
  • 祖先过滤形策略(完备的)

7、搜索策略

搜索分为盲目搜索和启发式搜索。

盲目搜索——按预定的控制策略进行搜索,在搜索过程中获得的中间信息不用来改进控制策略。这种搜索具有盲目性,效率不高,不便于复杂问题的求解。

启发式搜索——在搜索中加入了与问题有关的启发性信息,用以指导搜索朝着最有希望的方向前进,加速问题的求解过程并找到最优解。

显然,启发式搜索优于盲目搜索。但由于启发式搜索需要具有与问题本身特性相关的信息,而这并非对每一类问题都可以方便地抽取出来,因而盲目搜索仍不失为一种应用较多的搜索策略。

用搜索策略求解问题,首先要解决的问题是:用什么样的形式把问题表示出来。

通常有两种方法:状态空间表示法、与/或树表示法(不作介绍)

(1)状态空间表示法

  • “状态”——用以描述问题求解过程中不同时刻的状况;
  • “算符”——表示对状态的操作,算符的每一次使用就使问题由一种状态变换为另一种状态;
  • “解” —— 当到达目标状态时,由初始状态到目标状态所用算符的序列就是问题的一个解。

(2)状态空间的一般搜索过程

①给出初始状态(初始节点);

②选择适用的算符对其进行操作,生成一组子状态(或称后继状态、后继节点、子节点);

③检查目标状态是否在所生成的子状态中出现。若出现,则搜索成功,找到了问题的解;若不出现,则按某种搜索策略从已生成的状态中再选一个状态作为当前状态;

④重复第2和第3步,直到目标状态出现或者不再有可供操作的状态及算符时为止。

  • 状态空间法搜索策略
    • 盲目搜索策略
      • 广度优先搜索
      • 深度优先搜索
      • 有界深度优先搜索
      • 代价树的广度优先搜索
      • 代价树的深度优先搜索
    • 启发式搜索
      • 局部择优搜索
      • 全局择优搜索
-----------------------本文结束 感谢阅读-----------------------
坚持原创技术分享,您的支持将鼓励我继续创作!恰饭^.^~