确定性推理.ppt
《确定性推理.ppt》由会员分享,可在线阅读,更多相关《确定性推理.ppt(120页珍藏版)》请在三一文库上搜索。
1、1,第3章 确定性推理,智能系统的推理过程实际上就是一种思维过程。按照推理过程所用知识的确定性,推理可分为确定性推理和不确定性推理。对于推理的这两种不同类型,本章重点讨论前一种,不确定性推理放到下一章讨论。 3.1 推理的基本概念 3.2 推理的逻辑基础 3.3 自然演绎推理 3.4 归结演绎推理 3.5 基于规则的演绎推理,2,3.1 推理的基本概念,3.1.1 什么是推理 3.1.2 推理方法及其分类 3.1.3 推理的控制策略及其分类 3.1.4 正向推理 3.1.5 逆向推理 3.1.6 混合推理,3,3.1.1 什么是推理,推理的概念 是指按照某种策略从已知事实出发去推出结论的过程。
2、 推理所用的事实: 初始证据:推理前用户提供的 中间结论:推理过程中所得到的 推理过程:由推理机来完成,所谓推理机就是智能系统中用来实现推理的那些程序。 例如,医疗专家系统,专家知识保存在知识库中。推理开始时,先把病人的症状和检查结果放到综合数据库中,然后再从综合数据库的初始证据出发,按照某种策略在知识库中寻找,并使用知识,直到推出最终结论为止。 推理的两个基本问题 推理的方法:解决前提和结论的逻辑关系,不确定性传递 推理的控制策略:解决推理方向,冲突消解策略,4,3.1.2 推理方法及其分类 1. 按推理的逻辑基础分类(1/4),可分为演绎推理、归纳推理等 演绎推理 演绎推理是从已知的一般性
3、知识出发,去推出蕴含在这些已知知识中的适合于某种个别情况的结论。是一种由一般到个别的推理方法,其核心是三段论,如假言推理、拒取式和假言三段论。 例: 假言三段论 AB,BC AC 常用的三段论是由一个大前提、一个小前提和一个结论这三部分组成的。其中,大前提是已知的一般性知识或推理过程得到的判断;小前提是关于某种具体情况或某个具体实例的判断;结论是由大前提推出的,并且适合于小前提的判断。 例如,有如下三个判断: 计算机系的学生都会编程序; (一般性知识) 程强是计算机系的一位学生; (具体情况) 程强会编程序。 (结论) 这是一个三段论推理。其中,是大前提,是小前提;是经演绎推出来的结论。 可见
4、,其结论是蕴含在大前提中的。,5,3.1.2 推理方法及其分类 1. 按推理的逻辑基础分类(2/4),归纳推理 是一种由个别到一般的推理方法。归纳推理的类型 按照所选事例的广泛性可分为完全归纳推理和不完全归纳推理 按照推理所使用的方法可分为枚举、类比、统计和差异归纳推理等 完全归纳推理 是指在进行归纳时需要考察相应事物的全部对象,并根据这些对象是否都具有某种属性,推出该类事物是否具有此属性。如,计算机质量检验。 不完全归纳推理 是指在进行归纳时只考察了相应事物的部分对象,就得出了关于该事物的结论。例如,计算机,随机抽查。 枚举归纳推理 是指在进行归纳时,如果已知某类事物的有限可数个具体事物都具
5、有某种属性,则可推出该类事物都具有此种属性。 例如,设有如下事例: 王强是计算机系学生,他会编程序; 高华是计算机系学生,她会编程序; 当这些具体事例足够多时,就可归纳出一个一般性的知识: 凡是计算机系的学生,就一定会编程序。,6,3.1.2 推理方法及其分类 1. 按推理的逻辑基础分类(3/4),类比归纳推理 是指在两个或两类事物有许多属性都相同或相似的基础上,推出它们在其他属性上也相同或相似的一种归纳推理。 设A、B分别是两类事物的集合: A=a1,a2, B=b1,b2, 并设ai与bi总是成对出现,且当ai有属性P时,bi就有属性Q与此对应,即 P(ai)Q(bi) i=1,2, 则当
6、A与B中有一新的元素对出现时,若已知a有属性P,b有属性Q,即 P(a)Q(b) 类比归纳推理的基础是相似原理,其可靠程度取决于两个或两类事物的相似程度以及这两个或两类事物的相同属性与推出的那个属性之间的相关程度。,7,3.1.2 推理方法及其分类 1. 按推理的逻辑基础分类(4/4),演绎推理与归纳推理的区别 演绎推理是在已知领域内的一般性知识的前提下,通过演绎求解一个具体问题或者证明一个结论的正确性。它所得出的结论实际上早已蕴含在一般性知识的前提中,演绎推理只不过是将已有事实揭露出来,因此它不能增殖新知识。 归纳推理所推出的结论是没有包含在前提内容中的。这种由个别事物或现象推出一般性知识的
7、过程,是增殖新知识的过程。 例如,一位计算机维修员,从书本知识,到通过大量实例积累经验,是一种归纳推理方式。运用这些一般性知识知识去维修计算机的过程则是演绎推理。,8,3.1.3 推理的控制策略及其分类,推理的控制策略 推理过程不仅依赖于所用的推方法,同时也依赖于推理的控制策略。 推理的控制策略是指如何使用领域知识使推理过程尽快达到目标的策略。 控制策略的分类 由于智能系统的推理过程一般表现为一种搜索过程,因此,推理的控制策略又可分为推理策略和搜索策略。 推理策略 主要解决推理方向、冲突消解等问题,如推理方向控制策略、求解策略、限制策略、冲突消解策略等 推理方向控制策略用于确定推理的控制方向,
8、可分为正向推理、逆向推理、混合推理及双向推理。 求解策略是指仅求一个解,还是求所有解或最优解等。 限制策略是指对推理的深度、宽度、时间、空间等进行的限制。 冲突消解策略是指当推理过程有多条知识可用时,如何从这多条可用知识中选出一条最佳知识用于推理的策略。 搜索策略 主要解决推理线路、推理效果、推理效率等问题。 本章主要讨论推理策略,至于搜索策略将放到第4章单独讨论。,9,3.1.4 正向推理 推理算法,从已知事实出发、正向使用推理规则,亦称为数据驱动推理或前向链推理。 算法描述 (1) 把用户提供的初始证据放入综合数据库; (2) 检查综合数据库中是否包含了问题的解,若已包含,则求解结束,并成
9、功推出;否则执行下一步; (3) 检查知识库中是否有可用知识,若有,形成当前可用知识集,执行下一步;否则转(5)。 (4) 按照某种冲突消解策略,从当前可用知识集中选出一条规则进行推理,并将推出的新事实加入综合数据库种,然后转(2)。 (5) 询问用户是否可以进一步补充新的事实,若可补充,则将补充的新事实加入综合数据库中,然后转(3);否则表示无解,失败退出。 至于如何根据综合数据库中的事实到知识库中选取可用知识,当知识库中有多条知识可用时应该先使用那一条知识等。这些问题涉及到了知识的匹配方法和冲突消解策略,以后将会分别讨论。 其流程图如下:,10,把初始证据放入DB,DB中有解吗?,KB中有
10、可用知识吗?,形成可用知识集,可用知识集空吗?,按照冲突消解策略从该知识 集中选出一条知识进行推理,推出的是新事实吗?,将新事实加入到DB,把用户补充的新事 实加入到DB中,用户可补充新事实吗?,失败退出,成功退出,Y,N,N,Y,N,N,N,Y,Y,Y,11,3.1.4 正向推理 推理例子,例3.1请用正向推理完成以下问题的求解 假设知识库中包含有以下2条规则: r1: IF B THEN C r2: IF A THEN B 已知初始证据A,求证目标C。 解:本例的推理过程如下: 推理开始前,综合数据库为空。 推理开始后,先把A放入综合数据库,然后检查综合数据库中是否含有该问题的解,回答为“
11、N”。 接着检查知识库中是否有可用知识,显然r2可用,形成仅含r2的知识集。从该知识集中取出r2,推出新的实事B,将B加入综合数据库,检查综合数据库中是否含有目标C,回答为“N”。 再检查知识库中是否有可用知识,此时由于B的加入使得r1为可用,形成仅含r1的知识集。从该知识集中取出r1,推出新的实事C,将C加入综合数据库,检查综合数据库中是否含有目标C,回答为“Y”。 它说明综合数据库中已经含有问题的解,推理成功结束,目标C得证。,12,3.1.4 正向推理 优缺点,正向推理的主要优点 比较直观,允许用户主动提供有用的事实信息,适合于诊断、设计、预测、监控等领域的问题求解。 正向推理的主要缺点
12、 推理无明确目标,求解问题是可能会执行许多与解无关的操作,导致推理效率较低。,13,3.1.5 逆向推理 推理算法,从某个假设目标出发,逆向使用规则,亦称为目标驱动推理或逆向链推理。 算法描述: (1) 将要求证的目标(称为假设)构成一个假设集; (2) 从假设集中选出一个假设,检查该假设是否在综合数据库中,若在,则该假设成立,此时,若假设集为空,则成功退出,否则仍执行(2);若该假设不在数据库中,则执行下一步; (3) 检查该假设是否可由知识库的某个知识导出,若不能由某个知识导出,则询问用户该假设是否为可由用户证实的原始事实,若是,该假设成立,并将其放入综合数据库,再重新寻找新的假设,若不是
13、,则转(5);若能由某个知识导出,则执行下一步; (4) 将知识库中可以导出该假设的所有知识构成一个可用知识集; (5) 检查可用知识集是否为空,若是,失败退出;否则执行下一步; (6) 按冲突消解策略从可用知识集中取出一个知识,继续; (7) 将该知识的前提中的每个子条件都作为新的假设放入假设集,然后转(2)。 其流程图如下:,14,初始化DB和假设集,该假设是DB中的事实吗?,该假设能被KB中的知识导出吗?,从假设集中取出一个假设,可用知识集空吗?,按照冲突消解策略从该知识集中选出一条知识,将该知识前提中的每个子条件作为新的假设加入假设集,该假设成立 并放入DB,还有新的假设吗?,失败退出
14、,成功退出,Y,N,Y,Y,N,N,N,N,Y,将KB中所有能导出此假设的知识构成一个可用知识集,询问用户有此事实吗?,该假设 成立,Y,15,3.1.5 逆向推理 推理例子,对上例,采用逆向推理,其推理过程如下: 推理开始前,综合数据库和假设集均为空。 推理开始后,先将初始证据A和目标C分别放入综合数据库和假设集,然后从假设集中取出一个假设C,查找C是否为综合数据库中的已知事实,回答为“N”。 再检查C是否能被知识库中的知识所导出,发现C可由r1导出,于是r1被放入可用知识集。由于知识库中只有r1可用,故可用知识集中仅含r1。 接着从可用知识集中取出r1,将其前提条件B作为新的假设放入假设集
15、。从假设集中取出B,检查B是否为综合数据库中的实事,回答为“N”。再检查B是否能被知识库中的知识所导出,发现B可由r2导出,于是r2被放入可用知识集。由于知识库中只有r2可用,故可用知识集中仅含r2。 从可用知识集中取出r2,将其前提条件A作为新的假设放入假设集。然后从假设集中取出A,检查A是否为综合数据库中的实事,回答为“Y”。 他说明该假设成立,由于无新的假设,故推理过程成功结束,于是目标C得证。,16,3.1.5 逆向推理 优缺点,逆向推理的主要优点 不必寻找和使用那些与假设目标无关的信息和知识 推理过程的目标明确 也有利于向用户提供解释,在诊断性专家系统中较为有效。 逆向推理的主要缺点
16、 当用户对解的情况认识不请时,由系统自主选择假设目标的盲目性比较大,若选择不好,可能需要多次提出假设,会影响系统效率。,17,3.1.6 混合推理,混合推理的概念 把正向推理和逆向推理结合起来所进行的推理称为混合推理。是一种解决较复杂问题的方法。 混合推理的方法 1. 先正向后逆向 这种方法先进行正向推理,从已知事实出发推出部分结果,然后再用逆向推理对这些结果进行证实或提高它们的可信度。 2. 先逆向后正向 这种方法先进行逆向推理,从假设目标出发推出一些中间假设,然后再用正向推理对这些中间假设进行证实。 3. 双向混合 是指正向推理和逆向推理同时进行,使推理过程在中间的某一步结合起来。 对于这
17、些方法我不再详细讨论。,18,第3章 确定性推理,3.1 推理的基本概念 3.2 推理的逻辑基础 3.3 自然演绎推理 3.4 归结演绎推理 3.5 基于规则的演绎推理,19,3.2 推理的逻辑基础,3.2.1 谓词公式的解释 3.2.2 谓词公式的永真性和可满足性 3.2.3 谓词公式的等价性和永真蕴含性 3.2.4 谓词公式的范式 3.2.5 置换与合一,20,3.2.1 谓词公式的解释 概念,命题公式的解释 在命题逻辑中,命题公式的一个解释就是对该命题公式中各个命题变元的一次真值指派。 有了命题公式的解释,就可据此求出该命题公式的真值。 谓词公式的解释 由于谓词公式中可能包含由个体常量、
18、变元或函数,因此,必须先考虑这些个体常量和函数在个体域上的取值,然后才能根据它们的具体取值为谓词分别指派真值。 定义3.1 设D是谓词公式P的非空个体域,若对P中的个体常量、函数和谓词按如下规定赋值: (1) 为每个个体常量指派D中的一个元素; (2) 为每个n元函数指派一个从Dn到D的一个映射,其中 Dn =(x1, x2, , xn)| x1, x2, , xnD (3) 为每个n元谓词指派一个从Dn到F,T的映射。 则称这些指派为P在D上的一个解释I,21,3.2.1 谓词公式的解释 例子一(1/2),例3.2 设个体域D=1, 2,求公式A=(x)( y)P(x, y)在D上的解释,并
19、指出在每一种解释下公式A的真值。 解:由于公式A中没有包含个体常量和函数,故可直接为谓词指派真值,设有 这就是公式A 在D 上的一个解释。从这个解释可以看出: 当x=1、y=1时,有P(x,y)的真值为T; 当x=2、y=1时,有P(x,y)的真值为T; 即对x在D上的任意取值,都存在y=1使P(x,y)的真值为T。因此,在此解释下公式A的真值为T。,22,3.2.1 谓词公式的解释 例子一(2/2),说明:一个谓词公式在其个体域上的解释不是唯一的。例如,对公式A,若给出另一组真值指派 这也是公式A 在D 上的一个解释。从这个解释可以看出: 当x=1、y=1时,有P(x,y)的真值为T; 当x
20、=2、y=1时,有P(x,y)的真值为F; 即对x在D上的任意取值,不存在一个y使得P(x,y)的真值为T。因此,在此解释下公式A的真值为F。 实际上,A在D上共有16种解释,这里就不在一一列举。,23,3.2.1 谓词公式的解释 例子二,例3.3 设个体域D=1, 2,求公式B=(x)P(f(x), a)在D上的解释,并指出在该解释下公式B的真值。 解:设对个体常量a和函数f(x)的值指派为: 对谓词的真值指派为: 由于已指派a=1,因此P(1,2)和P(2,2)不可能出现,故没给它们指派真值。 上述指派是公式B在D上的一个解释。在此解释下有 当x=1时,a=1使P(1,1)=T 当x=2时
21、,a=1 使P(2,1)=T 即对x在D上的任意取值,都存在a=1使P(f(x), a)的真值为T。因此,在此解释下公式B的真值为T。 由上面的例子可以看出,谓词公式的真值都是针对某一个解释而言的,它可能在某一个解释下真值为T,而在另一个解释下为F。,24,3.2.2 谓词公式的永真性和可满足性,为了以后推理的需要,下面先定义: 定义3.2 如果谓词公式P对非空个体域D上的任一解释都取得真值T,则称P在D 上是永真的;如果P在任何非空个体域上均是永真的,则称P永真。 可见,要判定一谓词公式为永真,必须对每个非空个体域上的每个解释逐一进行判断。当解释的个数为有限时,尽管工作量大,公式的永真性毕竟
22、还可以判定,但当解释个数为无限时,其永真性就很难判定了。 定义3.3 对于谓词公式P,如果至少存在D上的一个解释,使公式P在此解释下的真值为T,则称公式P在D上是可满足的。 谓词公式的可满足性也称为相容性。 定义3.4 如果谓词公式P对非空个体域D上的任一解释都取真值F,则称P在D上是永假的;如果P在任何非空个体域上均是永假的,则称P永假。 谓词公式的永假性又称不可满足性或不相容。 后面我们要给出的归结推理,就是采用一种逻辑上的反证法,将永真性转换为不可满足性的证明。,25,3.2.3 谓词公式的等价性和永真蕴含性 1. 等价式(1/2),谓词公式的等价性和永真蕴含性可分别用相应的等价式和永真
23、蕴含式来表示,这些等价式和永真蕴含式都是演绎推理的主要依据,因此也称它们为推理规则。 谓词公式的等价式可定义如下: 定义3.5 设P与Q是D上的两个谓词公式,若对D上的任意解释,P与Q都有相同的真值,则称P与Q在D 上是等价的。如果D是任意非空个体域,则称P与Q是等价的,记作PQ。,26,3.2.3 谓词公式的等价性和永真蕴含性 1. 等价式(2/2),(1) 双重否定律 P P (2) 交换律 (PQ) (QP), ( PQ) ( QP) (3) 结合律 (PQ)R P(QR) (PQ)R P(QR) (4) 分配律 P(QR) (PQ)(PR) P(QR) (PQ)(PR) (5) 摩根定
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 确定性 推理
链接地址:https://www.31doc.com/p-3223657.html