第三章确定性推理方法ppt课件.ppt

《第三章确定性推理方法ppt课件.ppt》由会员分享，可在线阅读，更多相关《第三章确定性推理方法ppt课件.ppt（75页珍藏版）》请在三一办公上搜索。

1、第 3 章 确定性推理方法,5个房间的问题（给福尔摩斯出的问题）,5个不同颜色的房间，每间有个不同国籍的人，每人有自己喜欢的饮料，香烟和宠物，已知信息：1.英国人住在红房间里；2.西班牙人有一条狗；3.挪威人住在左边第一个房间里；4.黄房间的人在抽库尔斯牌香烟；5.抽切斯菲尔德牌香烟的人是养了一只狐狸的人的邻居；6.挪威人住在蓝房间隔壁；7.抽温斯顿牌香烟的人有一只蜗牛；8.抽幸运牌香烟的人喝橘子汁；9.乌克兰人喝茶；10.日本人抽国会牌香烟；11.抽库尔斯牌香烟的人的房间在有匹马的房间隔壁；12.绿房间的人喝咖啡；13.中间房间的人喝牛奶14.绿房间的人在白房间的隔壁问题： 哪个房间的人喝水

2、？斑马在哪个房间？,3.挪威人住在左边第一个房间6.挪威人住在蓝房间旁边13.中间房间的人喝牛奶,挪威人,蓝色,牛奶,12.绿房间的人喝咖啡14.绿房间的人在白房间的隔壁,绿色,白色,咖啡,1.英国人住在红色的房间,红色,英国人,黄色,4.黄房间的人抽库尔斯牌香烟11.抽库尔斯牌烟的房间在有匹马的房间的隔壁,库尔斯牌,马,水,2.西班牙人有一条狗8.抽幸运牌香烟的人喝橘子汁9.乌克兰人喝茶10.日本人抽国会牌香烟,橘子汁是谁喝的？,橘子汁,狗,幸运牌,西班牙人,茶,乌克兰人,日本人,国会牌,7.抽温斯顿牌香烟的人有一只蜗牛,温斯顿,蜗牛,切斯菲尔德,5.抽切斯菲尔德香烟的人的是养了一只狐狸的人

3、的邻居,狐狸,斑马,8.抽幸运牌香烟的人喝橘子汁9.乌克兰人喝茶,用Prolog语言编的程序，一秒钟都不到就知道了答案,不过它的推理过程和人的完全不一样；Prolog：Programm Logic (逻辑程序设计语言)推理方法：确定性推理：（演绎推理） （1）谓词公式化为子句集 （2）鲁宾逊归结原理（消解原理） （3）归结反演,机器证明,第3章 确定性推理方法,3.1 推理的基本概念 3.2 自然演绎推理 3.3 谓词公式化为子句集的方法3.4 海伯伦定理3.5 鲁宾逊归结原理3.6 归结反演3.7 应用归结反演求解问题,3.1 推理的基本概念,3.1.1 推理的定义3.1.2 推理方式及其分

4、类3.1.3 推理的方向3.1.4 冲突消解策略,3.1.1 推理的定义,推理：,3.1 推理的基本概念,3.1.1 推理的定义3.1.2 推理方式及其分类3.1.3 推理的方向3.1.4 冲突消解策略,（1）演绎推理 (deductive reasoning) : 一般 个别 三段论式（三段论法） 足球运动员的身体都是强壮的 ； 高波是一名足球运动员； 所以，高波的身体是强壮的。,3.1.2 推理方式及其分类,1.演绎推理、归纳推理、默认推理,（ 大前提 ）（ 小前提 ）（ 结 论 ）,3.1.2 推理方式及其分类,1.演绎推理、归纳推理、默认推理（按推出结论的途径）,检查全部产品合格,该厂

5、产品合格,完全归纳推理,检查全部样品合格,该厂产品合格,不完全归纳推理,3.1.2 推理方式及其分类,（3）默认推理（default reasoning，缺省推理） 知识不完全的情况下假设某些条件已经具备所进行的推理。,1.演绎推理、归纳推理、默认推理,3.1.2 推理方式及其分类,2. 确定性推理、不确定性推理（按知识的确定性）,（1）确定性推理：推理时所用的知识与证据都是确定的，推出的结论也是确定的，其真值或者为真或者为假。 （2）不确定性推理：推理时所用的知识与证据不都是确定的，推出的结论也是不确定的。,X：鸟 X：会飞,3.1.2 推理方式及其分类,3. 单调推理、非单调推理（按靠近结

6、论的方式） （1）单调推理：随着推理向前推进及新知识的加入，推出的结论越来越接近最终目标。 （2）非单调推理：由于新知识的加入，不仅没有加强已推出的结论，反而要否定它，使推理退回到前面的某一步，重新开始。,默认推理是非单调推理,基于经典逻辑的演绎推理,X：不会飞,3.1.2 推理方式及其分类,4启发式推理、非启发式推理（是否运用启发式知识） 启发性知识：与问题有关且能加快推理过程、提高搜索效率的知识。,目标：在脑膜炎、肺炎、流感中选择一个 产生式规则 r1：脑膜炎 r2：肺 炎 r3：流 感 启发式知识：“脑膜炎危险”、“目前正在盛行流感”。,3.1 推理的基本概念,3.1.1 推理的定义3.

7、1.2 推理方式及其分类3.1.3 推理的方向3.1.4 冲突消解策略,3.1.3 推理的方向,3.1.3 推理的方向,正向推理（事实驱动推理）: 已知事实 结论 基本思想（1）从初始已知事实出发，在知识库KB中找出当前可适用的知识，构成可适用知识集KS。（2）按某种冲突消解策略从KS中选出一条知识进行推理，并将推出的新事实加入到数据库DB中作为下一步推理的已知事实，再在KB中选取可适用知识构成KS 。（3）重复（2），直到求得问题的解或KB中再无可适用的知识。,1. 正向推理,3.1.3 推理的方向,实现正向推理需要解决的问题： 确定匹配（知识与已知事实）的方法。 按什么策略搜索知识库。 冲

8、突消解策略。 正向推理简单，易实现，但目的性不强，效率低。,1. 正向推理,3.1.3 推理的方向,逆向推理（目标驱动推理）：以某个假设目标作为出发点。 基本思想： 选定一个假设目标。 寻找支持该假设的证据，若所需的证据都能找到，则原假设成立；若无论如何都找不到所需要的证据，说明原假设不成立的；为此需要另作新的假设。 主要优点：不必使用与目标无关的知识，目的性强，同时它还有利于向用户提供解释。 主要缺点：起始目标的选择有盲目性。,2. 逆向推理,3.1.3 推理的方向,逆向推理需要解决的问题： 如何判断一个假设是否是证据？ 当导出假设的知识有多条时，如何确定先选哪一条？ 一条知识的运用条件一般

9、都有多个，当其中的一个经验证成立后，如何自动地换为对另一个的验证？ . 逆向推理：目的性强，利于向用户提供解释，但选择初始目标时具有盲目性，比正向推理复杂。,2. 逆向推理,3.1.3 推理的方向,正向推理: 盲目、效率低。 逆向推理: 若提出的假设目标不符合实际，会降低效率。 正反向混合推理：（1）先正向后逆向：先进行正向推理，帮助选择某个目标，即从已知事实演绎出部分结果，然后再用逆向推理证实该目标或提高其可信度；（2）先逆向后正向：先假设一个目标进行逆向推理，然后再利用逆向推理中得到的信息进行正向推理，以推出更多的结论。,3. 混合推理,双向推理：正向推理与逆向推理同时进行，且在推理过程中

10、的某一步骤上“碰头”的一种推理。,3.1.3 推理的方向,4. 双向推理,中间结论证 据,3.1 推理的基本概念,3.1.1 推理的定义3.1.2 推理方式及其分类3.1.3 推理的方向3.1.4 冲突消解策略,3.1.4 冲突消解策略,已知事实与知识的三种匹配情况：（1）恰好匹配成功（一对一）；（2）不能匹配成功；（3）多种匹配成功（一对多、多对一、多对多）,冲突消解,3.1.4 冲突消解策略,多种冲突消解策略：（1）按针对性排序（2）按已知事实的新鲜性排序（3）按匹配度排序（4）按条件个数排序（5）按上下文限制排序（6）按冗余限制排序（7）根据领域问题的特点排序,r1: IF A1 AND

11、 A2 THEN H1r2: IF A1 AND A2 AND A3 AND A4 THEN H2,第3章 确定性推理方法,3.1 推理的基本概念 3.2 自然演绎推理 3.3 谓词公式化为子句集的方法3.4 海伯伦定理3.5 鲁宾逊归结原理3.6 归结反演3.7 应用归结反演求解问题,27,定义1 设P与Q是两个谓词公式，D是它们共同的个体域，若对D上的任何一个解释，P与Q都有相同的真值，则称公式P和Q在D上是等价的。如果D是任意个体域，则称P和Q是等价的，记为P Q 。常用的等价式见P32（4）德.摩根律(De. Morgen) （8）连接词化规律（蕴含、等价等值式） （10）量词转换律,

12、3.2 自然演绎推理,自然演绎推理：从一组已知为真的事实出发，运用经典逻辑的推理规则推出结论的过程。,28,定义2 对于谓词公式P与Q，如果PQ永真，则称公式P永真蕴含Q，且称Q为P的逻辑结论，称P为Q的前提，记为P Q。常用的永真蕴含式见P33（3）假言推理 （4）拒取式推理 （5）假言三段论,3.2 自然演绎推理,29,谓词逻辑的其他推理规则1. P规则：在推理的任何步骤上都可引入前提。2. T规则：在推理过程中，如果前面步骤中有一个或多个公式永真蕴含公式S，则可把S引入推理过程中。3. CP规则：如果能从任意引入的命题R和前提集合中推出S来，则可从前提集合推出R S来。,3.2 自然演绎

13、推理,30,所有的人都是会死的， 因为诸葛亮是人， Human（Zhugeliang） 所以诸葛亮是会死的。 Die（Zhugeliang）, 1 P规则 2 Human（Zhugeliang） P规则 1, 2 Die（Zhugeliang） T规则,3.2 自然演绎推理,31,谓词逻辑的其他推理规则：4.反证法：PQ ，当且仅当 PQF，即Q为P的逻辑结论，当且仅当PQ是不可满足的。,定理：Q为P1,P2,Pn 的逻辑结论，当且仅当 P1P2, Pn Q 是不可满足的。,3.2 自然演绎推理,推理规则：P规则、T规则、假言推理、拒取式推理,3.2 自然演绎推理,拒取式推理： PQ, Q P

14、 “如果下雨，则地下就湿” , “地上不湿” 推出 “没有下雨”,（1） 如果下雨，则地上是湿的（ PQ ）；（2）没有下雨（P ）； （3）所以，地上不湿（Q ）。,3.2 自然演绎推理,错误1否定前件： PQ, P Q,（1）如果行星系统是以太阳为中心的，则金星会显示出位相变化（ PQ ）；（2）金星显示出位相变化（ Q ）；（3） 所以，行星系统是以太阳为中心（ P ）。,错误2肯定后件： PQ, Q P,3.2 自然演绎推理,例1 已知事实： （1）凡是容易的课程小王( Wang )都喜欢； （2）C 班的课程都是容易的； （3）ds 是 C 班的一门课程。 求证：小王喜欢 ds 这门

15、课程。,3.2 自然演绎推理,证明：定义谓词： EASY ( x )：x 是容易的 LIKE ( x, y )：x 喜欢 y C ( x )：x 是 C 班的一门课程,已知事实和结论用谓词公式表示： (x) ( EASY ( x ) LIKE ( Wang, x ) ) (x) ( C ( x ) EASY ( x ) C ( ds ) LIKE ( Wang, ds ),3.2 自然演绎推理,应用推理规则进行推理：,(x)（EASY ( x ) LIKE ( Wang, x ) EASY (z) LIKE ( Wang, z ) 全称固化,(x ) (C ( x ) EASY ( x ) C

16、 ( y ) EASY ( y ) 全称固化,所以 C (ds), C (y) EASY (y) EASY (ds) P规则及假言推理,所以 EASY (ds), EASY (z) LIKE (Wang，z) LIKE ( Wang, ds ) T规则及假言推理,优点：表达定理证明过程自然，易理解。拥有丰富的推理规则，推理过程灵活。便于嵌入领域启发式知识。,3.2 自然演绎推理,第3章 确定性推理方法,3.1 推理的基本概念 3.2 自然演绎推理3.3 谓词公式化为子句集的方法3.4 海伯伦定理3.5 鲁宾逊归结原理3.6 归结反演3.7 应用归结反演求解问题,3.3 谓词公式化为子句集的方法

17、,原子（atom）谓词公式： 一个不能再分解的命题。 文字（literal）：原子谓词公式及其否定。 ：正文字， ：负文字。（封闭世界假设） 子句（clause）：任何文字的析取式。任何文字本身也都是子句。 空子句（NIL）：不包含任何文字的子句。 子句集：由子句构成的集合。,空子句是永假的，不可满足的。,3.3 谓词公式化为子句集的方法,例2 将下列谓词公式化为子句集。,解：（1）消去谓词公式中的“ ”和“ ”符号,（2）把否定符号” 移到紧靠谓词的位置上,（3）变量标准化,（4）消去存在量词 a. 存在量词不出现在全称量词的辖域内。 b. 存在量词出现在一个或者多个全称量词的辖域内。,（5

18、）化为前束形 前束形=（前缀）母式,（前缀）：全称量词串。 母式：不含量词的谓词公式。,3.3 谓词公式化为子句集的方法,3.3 谓词公式化为子句集的方法,（6）化为 Skolem 标准形,（7）略去全称量词,（8）消去合取词,（9）子句变量标准化,3.3 谓词公式化为子句集的方法,例3 将下列谓词公式化为子句集。解：（1）消去蕴含符号（2）把否定符号移到每个谓词前面 （3）变量标准化 （4）消去存在量词，,例3 将下列谓词公式化为子句集。（续）（5）化为前束形(没变化) （6）化为标准形 （7）略去全称量词 （8）消去合取词，把母式用子句集表示 （9）子句变量标准化,3.3 谓词公式化为子句

19、集的方法,3.3 谓词公式化为子句集的方法,练习: 将下列谓词公式化为子句集。解：（1）消去蕴含符号（2）把否定符号移到每个谓词前面 （3）变量标准化 （4）消去存在量词，,例3 将下列谓词公式化为子句集。（续）（5）化为前束形 （6）化为标准形 （7）略去全称量词 （8）消去合取词，把母式用子句集表示 （9）子句变量标准化,3.3 谓词公式化为子句集的方法,第3章 确定性推理方法,3.1 推理的基本概念 3.2 自然演绎推理3.3 谓词公式化为子句集的方法3.4 海伯伦定理3.5 鲁宾逊归结原理3.6 归结反演3.7 应用归结反演求解问题,定理： PQ当且仅当P Q F 即 Q为 P 的逻辑

20、结论，当且仅当P Q 是不可满足的。,定理：Q 为 ， ， 的逻辑结论，当且仅当 是不可满足的。,3.5 鲁宾逊归结原理,定理 : 谓词公式不可满足的充要条件是其子句集不可满足。,3.5 鲁宾逊归结原理,3.5 鲁宾逊归结原理,3.5 鲁宾逊归结原理,鲁宾逊归结原理（消解原理）的基本思想：检查子句集 S 中是否包含空子句，若包含，则 S 不可满足。若不包含，在 S 中选择合适的子句进行归结，一旦归结出空子句，就说明 S 是不可满足的。,子句集中子句之间是合取关系，只要有一个子句不可满足， 则子句集就不可满足。,3.5 鲁宾逊归结原理,1. 命题逻辑中的归结原理（基子句的归结） 归结：设C1与C

21、2是子句集中的任意两个子句，如果 C1中的文字L1与 C2中的文字L2互补，那么从C1和 C2中分别消去L1和L2，并将二个子句中余下的部分析取，构成一个新子句C12 。C12 称为C1 和C2 的归结式;C1 和C2 为C12的亲本子句。,（归结）,（归结）,P Q,P,R, Q R, P R,推论1：设C1与C2是子句集S中的两个子句，C12是它们的归结式，若用C12代替C1与C2后得到新子句集S1，则由S1不可满足性可推出原子句集S的不可满足性，即：,推论2：设C1与C2是子句集S中的两个子句，C12是它们的归结式，若C12 加入原子句集S，得到新子句集S1，则S与S1在不可满足的意义上

22、是等价的，即：,定理1：归结式C12是其亲本子句C1与C2的逻辑结论。即如果 C1与C2为真，则C12为真。,3.5 鲁宾逊归结原理,S1的不可满足性 S 的不可满足性,S1的不可满足性 S的不可满足性,3.5 鲁宾逊归结原理,2. 谓词逻辑中的归结原理（含有变量的子句的归结）,？,最一般合一,最一般合一,例：,3.5 鲁宾逊归结原理,例4设：,求其二元归结式。,解：令,3.5 鲁宾逊归结原理,则得：,解：f(a)是个体常项，令,再令：,得：,3.5 鲁宾逊归结原理,注：对于谓词逻辑，归结式是其亲本子句的逻辑结论。 对于一阶谓词逻辑，即若子句集是不可满足的，则必存在一个从该子句集到空子句的归结

23、演绎；若从子句集存在一个到空子句的演绎，则该子句集是不可满足的。如果没有归结出空子句，则既不能说 S 不可满足，也不能说 S 是可满足的。,第3章 确定性推理方法,3.1 推理的基本概念 3.2 自然演绎推理3.3 谓词公式化为子句集的方法3.4 海伯伦定理3.5 鲁宾逊归结原理3.6 归结反演3.7 应用归结反演求解问题,3.6 归结反演,应用归结原理证明定理的过程称为归结反演。用归结反演证明的步骤是：（1）将已知前提表示为谓词公式F。（2）将待证明的结论表示为谓词公式Q，并否定得到 Q 。（3）把谓词公式集F， Q 化为子句集S。（4）应用归结原理对子句集S中的子句进行归结，并把每次 归结

24、得到的归结式都并入到S中。如此反复进行，若出 现了空子句，则停止归结，此时就证明了Q为真。,3.6 归结反演,例6 某公司招聘工作人员，A，B ，C 三人应试，经面试后公司表示如下想法：（1）三人中至少录取一人。（2）如果录取 A 而不录取 B ，则一定录取 C。（3） 如果录取 B ，则一定录取 C 。,求证：公司一定录取 C。,3.6 归结反演,证明：公司的想法用谓词公式表示： 。,把要求证的结论用谓词公式表示出来并否定，得：,（1）（2）（3）,（4）,把上述公式化成子句集：,（1）,（2）,（3）,（4）,3.6 归结反演,P(A)P(B)P(C),P(A)P(B)P(C),P(B)P

25、(C), P(B)P(C),P(C), P(C),NIL,应用归结原理进行归结：,（1）,（2）,（3）,（4）,3.6 归结反演,例7 已知： 规则1：任何人的兄弟不是女性； 规则2：任何人的姐妹必是女性。 事 实：Mary 是 Bill 的姐妹。 求证： Mary 不是 Tom 的兄弟。 证明：定义谓词 brother ( x, y ) : x 是 y 的兄弟 sister ( x, y ) : x 是 y 的姐妹 woman ( x ) : x 是女性,证明：将规则与事实用谓词公式表示：,把要求证的结论用谓词公式表示出来并否定，得：,把上述公式化成子句集：,（1）（2）（3）,（4）,3

26、.6 归结反演,（1）（2）（3）,（1）（2）（3）,3.6 归结反演, sisiter(x,y)woman(x),sister(Mary,Bill),woman(Mary),brother(x,y) woman(x),brother(Mary,y),brother(Mary,Tom),NIL,=Mary/x,=Mary/x,将子句集进行归结：,（C2）,（C3）,（C1）,（C4）,第3章 确定性推理方法,3.1 推理的基本概念 3.2 自然演绎推理3.3 谓词公式化为子句集的方法3.4 海伯伦定理3.5 鲁宾逊归结原理3.6 归结反演3.7 应用归结反演求解问题,3.7 应用归结原理求解

27、问题,应用归结原理求解问题的步骤：（1）已知前提 F 用谓词公式表示，并化为子句集 S ；,（3）把（ Q ANSWER） 化为子句集，并入到子句集 S中，得到子句集 ；,（4）对 应用归结原理进行归结；,（5）若得到归结式 ANSWER ，则答案就在 ANSWER 中。,（2）把待求解的问题 Q 用谓词公式表示，并否定 Q，再与 ANSWER 构成析取式（ Q ANSWER ）；,例8 已知： ：王（Wang）先生是小李（Li）的老师。 ：小李与小张（Zhang）是同班同学。 ：如果 x 与y 是同班同学，则 x的老师也是 y的老师。,求：小张的老师是谁？,3.7 应用归结原理求解问题,3.

28、7 应用归结原理求解问题,解： 定义谓词：,： 是 的老师。 ： 与 是同班同学。,把已知前提表示成谓词公式：,把目标表示成谓词公式，并把它否定后与 ANSWER 析取：,F1：王（Wang）先生是小李（Li）的老师。F2：小李与小张（Zhang）是同班同学。F3：如果 x与 y 是同班同学，则 x的老师也是 y的 老师。求：小张的老师是谁？,把上述公式化为子句集：,3.7 应用归结原理求解问题,（1） （2）（3）（4）,应用归结原理进行归结：,（5） （1）与（3）归结（6） （4）与（5）归结（7） （2）与（6）归结,3.6 归结反演,T(Wang,Li), C(x,y)T(z,x)T

29、(z,y),C(Li,y)T(Wang,y),T(u,Zhang) ANSWER(u),C(Li,Zhang) ANSWER(Wang),C(Li,Zhang),ANSWER(Wang),1=Li/x 2=Wang/z,1=Zhang/y2=Wang/u,将子句集进行归结：,（1）,（3）,（4）,（2）,（1） （2）（3）（4）,局限性（1）范式复杂，体积庞大（2）缺乏不确定性概念除了一阶逻辑，还有模态逻辑（刻画认知概念）；时序逻辑（在逻辑系统中引入时间概念）；模糊逻辑（更多考虑自然语言的成分）；非单调逻辑、刻画情景演算的多类逻辑等等,在AI技术中，存在着多种推理机制，它们存在的形态和使用的方法不同，但就其应用来讲都各有其优缺点。可以说，目前还没有一种相当成熟的、真正通用化的推理技术或方法。除了基于规则的推理（RBR）外，基于案例的推理（CBR），基于模型的推理（MBR）是高级人工智能研究的内容,小结,小结,作业：P90 3.3 （3）（4）；3.6（3）(5); 3.7 ; 3.10,75,THANKS,