人工智能5第五章确定性推理.pptx
- 文档编号:15118898
- 上传时间:2023-06-30
- 格式:PPTX
- 页数:73
- 大小:237.20KB
人工智能5第五章确定性推理.pptx
《人工智能5第五章确定性推理.pptx》由会员分享,可在线阅读,更多相关《人工智能5第五章确定性推理.pptx(73页珍藏版)》请在冰点文库上搜索。
第四章确定性推理,2023/6/30,1,4.1确定性推理概述,第四章确定性推理4.1概述,2023/6/30,2,推理,推理是指按照某种策略从巳知事实出发去推出结论的过程智能系统的推理过程实际上就是一种思维过程。
智能系统的推理过程是通过推理机来完成的。
推理机就是智能系统中用来实现推理的程序。
按照推理过程所用知识的确定性,推理可分为确定性推理和不确定性推理。
第四章确定性推理4.1概述,2023/6/30,3,事实,事实是推理过程中按知识表示方式表示的已知的知识推理所用的事实可分为两种情况:
与求解问题有关的初始证据推理过程中所得到的中间结论。
第四章确定性推理4.1概述,2023/6/30,4,推理的基本问题,智能系统的推理包括两个基本问题:
一个是推理的方法一个是推理的控制策略推理方法主要解决:
在推理过程中前提与结论之间的逻辑关系在非精确性推理中不确定性的传递问题,第四章确定性推理4.1概述,2023/6/30,5,推理方法的分类,推理可以有多种不同的分类方法按照推理的逻辑基础分类:
演绎推理归纳推理默认推理按照所用知识的确定性分类:
确定性推理不确定性推理按照推理过程的单调性分类(推理过程所得到的结论是否越来越接近目标):
单调推理非单调推理,第四章确定性推理4.1概述,2023/6/30,6,演绎推理,从已知的一般性知识出发,去推出蕴含在这些已知知识中的适合于某种个别情况的结论。
它是一种由一般到个别的推理方法。
核心是三段论,第四章确定性推理4.1概述,2023/6/30,7,归纳推理,从一类事物的大量特殊事例出发,去推出该类事物的一般性结论。
它是一种由个别到一般的推理方法。
基本思想:
先从已知事实中猜测出一个结论,然后对这个结论的正确性加以证明确认数学归纳法就是归纳推理的一种典型例子。
按照所选事例的广泛性,归纳推理可分为:
完全归纳推理和不完全归纳推理;按照推理所使用的方法可分为:
枚举归纳推理、类比归纳推理、统计归纳推理和差异归纳推理等。
第四章确定性推理4.1概述,2023/6/30,8,默认推理,在知识不完全的倩况下,假设某些条件已经具备所进行的推理,因此也称为缺省推理。
在推理过程中如果发现原先的假设不正确,就撤销原来的假设以及由此假设所推出的所有结论。
重新按新情况进行推理。
解决了在一个不完备的知识集中进行推理的问题。
第四章确定性推理4.1概述,2023/6/30,9,推理过程的单调性,按照推理过程所得到的结论是否越来越接近日标,推理可分为单调推理与非单调推理。
单调推理:
在推理过程中,每当使用新的知识后,所得到的结论会越来越接近于目标不会出现反复情况,即不会由于新知识的加入否定了前面推出的结论。
非单调推理:
在推理过程中,当某些新知识加入后,会否定原来推出的结论。
非单调推理往往是在知识不完全的情况下发生的。
第四章确定性推理4.1概述,2023/6/30,10,推理控制策略,推理的控制策略是在推理过程中采用的、解决如何使用领域知识使推理过程尽快达到目标的策略。
第四章确定性推理4.1概述,2023/6/30,11,推理控制策略分类,智能系统的推理过程一般表现为一种搜索过程,因此,推理的控制策略又可分为推理策略和搜索策略。
推理策略主要解决推理方向、冲突消解等问题。
搜索策略主要解决推理线路、推理效果、推理效率等问题。
第四章确定性推理4.1概述,2023/6/30,12,推理方向,推理方向确定推理过程是从初始证据开始到目标,还是从目标开始到初始证据。
按照对推理方向的控制,推理可分为正向推理、逆向推理、混合推理及双向推理四种情况。
第四章确定性推理4.1概述,2023/6/30,13,正向推理,正向推理是一种从已知事实出发、正向使用推理规则的推理方式,亦称为数据驱动推理。
基本思想是:
用户需要事先提供一组初始证据,并将其放入综合数据库。
推理机根据综合数据库中的已有事实,到知识库中寻找当前可用知识,形成一个当前可用知识集。
按照冲突消解策略,从该知识集中选择一条知识进行推理,并将新推出的事实加入综合数据库,作为后面继续推理时可用的巳知事实,重复这一过程,直到求出所需要的解或者知识库中再无可用知识为止,第四章确定性推理4.1概述,2023/6/30,14,逆向推理,逆向推理是一种从以某个假设目标作为出发点的推理方法,亦称为目标驱动推理基本思想是:
将要求证的目标(称为假设)构成一个假设集。
取一个假设对其进行验证,若在综合数据库里,则假设成立若能被用户认定为事实,则假设成立,并放入综合数据库若可由知识库中的一个或多个知识导出,则这些知识构成可用知识集。
按照冲突消解策略,从该知识集中选择一条知识,将其前提中的所有子条件作为新的假设加入假设集。
重复这一过程,直到假设集为空或假设集非空但可用知识集空为止,第四章确定性推理4.1概述,2023/6/30,15,混合推理,正向推理和逆向推理都有各自的优缺点。
当问题较复杂时,单独使用其中哪一种,都会影响到推理效率。
为了取长补短可将它们结合起来使用。
这种把正向推理和逆向推理结合起来所进行的推理称为混合推理。
第四章确定性推理4.1概述,2023/6/30,16,混合推理的实现方法,混合推理可有多种具体的实现方法先正向推理,后逆向推理的方法先逆向推理,后正向推理的方法采用随机选择正向和逆向推理的方法(双向混合推理),第四章确定性推理4.1概述,2023/6/30,17,混合推理的适用场合,已知事实不够充分。
由正向推理推出的结论可信度不高希望得出更多的结论希望从正反两个方向同时进行推理,第四章确定性推理4.1概述,2023/6/30,18,冲突消解策略,冲突消解策略是指当推理过程有多条知识可用时,如何从这多条可用知识中选出一条最佳知识用于推理的策略。
冲突消解的基本思想是对可用知识进行排序。
常用的冲突消解策略有:
特殊知识优先新鲜知识优先差异性大的知识优先领域特点知识优先上下文关系知识优先前提条件少的知识优先,第四章确定性推理4.1概述,2023/6/30,19,自然演绎推理,从一组己知为真的事实出发,直接运用经典逻辑中的推理规则推出结论的过程称为自然演绎推理。
在自然演绎推理中,需要避免两类错误:
肯定后件的错误和否定前件的错误。
优点:
定理证明过程自然,易于理解,有丰富的推理规则主要缺点:
容易产生知识爆炸,推理过程中得到的中间结论一般按指数规律递增,对于复杂问题的推理不利,甚至难以实现。
因此,提出了归结演绎推理,第四章确定性推理4.2自然演绎推理,2023/6/30,20,归结演绎推理,归结演绎推理是一种基于归结原理的推理方法。
归结原理亦称消解原理,是鲁宾逊1965年提出的归结演绎推理实际上是一种“反正法”,基本思想:
推理就是要对前提P和结论Q,证明PQ永真。
这就要证明PQ在任何一个非空的个体域上都是永真的。
这将是非常困难的,甚至是不可实现的。
而用反证法,只要能够证明(PQ)是不可满足的。
第四章确定性推理4.3归结演绎推理,2023/6/30,21,子句和子句集,原子谓词公式及其否定都称为文字文字的析取构成的公式称为子句不包含任何文字的子句称为空了句空子句不包含任何文字,因此,不能被任何指派所满足所以空子句是不可满足的子句集中的子句之间是合取关系含空子句的子句集也就一定是不可满足的。
第四章确定性推理4.3归结演绎推理,2023/6/30,22,谓词公式转化为子句集,消去蕴涵符号:
PQ取代PQ减少否定符号的管辖域对变量标准化消去存在量词化为前束形化为合取范式:
如:
P(PQ)(PQ)消去全称量词获得子句集更换变量名,第四章确定性推理4.3归结演绎推理,2023/6/30,23,化子句集例,例:
(z)(x)(y)(P(x)Q(x)R(y)U(z)1,消蕴涵符理论根据:
ab=ab(z)(x)(y)(P(x)Q(x)R(y)U(z)2,移动否定符理论根据:
(ab)=ab(ab)=ab(x)P(x)=(x)P(x)(x)P(x)=(x)P(x)(z)(x)(y)(P(x)Q(x)R(y)U(z),第四章确定性推理4.3归结演绎推理,2023/6/30,24,化子句集例(续1),3,变量标准化即:
对于不同的约束,对应于不同的变量(x)A(x)(x)B(x)=(x)A(x)(y)B(y)4,量词左移(x)A(x)(y)B(y)=(x)(y)A(x)B(y)5,消存在量词(skolem化)原则:
对于一个受存在量词约束的变量,如果他不受全程量词约束,则该变量用一个常量代替,如果他受全程量词约束,则该变量用一个函数代替。
(z)(x)(y)(P(x)Q(x)R(y)U(z)=(x)(P(x)Q(x)R(f(x)U(a),第四章确定性推理4.3归结演绎推理,2023/6/30,25,化子句集例(续2),6,化为合取范式即(ab)(cd)(ef)的形式(x)(P(x)Q(x)R(f(x)U(a)=(x)(P(x)Q(x)R(f(x)U(a)=(x)P(x)R(f(x)U(a)Q(x)R(f(x)U(a)7,隐去全程量词P(x)R(f(x)U(a)Q(x)R(f(x)U(a),第四章确定性推理4.3归结演绎推理,2023/6/30,26,化子句集例(续3),8,表示为子句集P(x)R(f(x)U(a),Q(x)R(f(x)U(a)9,变量标准化(变量换名)P(x1)R(f(x1)U(a),Q(x2)R(f(x2)U(a),第四章确定性推理4.3归结演绎推理,2023/6/30,27,归结(消解)原理基本思想,首先把欲证明问题的结论否定,并加入子句集,得到一个扩充的子句集S。
检验子句集S是否含有空子句若不含空子句,则继续使用归结法,在子句集中选择合适的子句进行归结直至导出空子句或不能继续归结为止。
第四章确定性推理4.3归结演绎推理,2023/6/30,28,归结原理分类,鲁宾逊归结原理可分为:
命题逻辑归结原理谓词逻辑归结原理,第四章确定性推理4.3归结演绎推理,2023/6/30,29,归结式,归结推理的核心是求两个子句的归结式若P是原子谓词公式,则称P与P为互补文字设C1和C2是子句集中的任意两个子句如果C1中的文字L1与C2中的文字L2互补那么可从C1和C2中分别消去L1和L2并将C1和C2中余下的部分按析取关系构成一个新的子句C12,则称这一过程为归结,称C12为C1和C2的归结式,C1和C2为C12的亲本子句。
第四章确定性推理4.3归结演绎推理,2023/6/30,30,消解过程举例,E2E1(前提)E2E3(前提)(消解式)E1E3(结论),第四章确定性推理4.2归结演绎推理,2023/6/30,31,命题逻辑的消解推理举例,三段论:
PQ(PQ)QR(QR),消解式:
PR(PQ),第四章确定性推理4.2归结演绎推理,2023/6/30,32,谓词逻辑的消解推理举例,第四章确定性推理4.2归结演绎推理,2023/6/30,33,消解反演,消解反演是利用消解原理进行推理的过程。
消解反演的推理过程:
给定公式集S和目标公式L证明公式L的步骤如下:
否定L,得L把L添加到S中去把新产生的集合L,S化成子句集应用消解原理力图推导出一个表示矛盾的空子句,第四章确定性推理4.2归结演绎推理,2023/6/30,34,命题逻辑消解反演的例子,设公理集:
P,(PQ)R,(ST)Q,T求证:
R子句集:
(1)P
(2)PQR(3)SQ(4)TQ(5)T(6)R(目标求反),化子句集:
(PQ)R=(PQ)R=PQR(ST)Q=(ST)Q=(ST)Q=(SQ)(TQ)=SQ,TQ,第四章确定性推理4.2归结演绎推理,2023/6/30,35,命题逻辑消解反演的例子(续),子句集:
(1)P
(2)PQR(3)SQ(4)TQ(5)T(6)R(目标求反),归结:
(7)PQ(2,6)(8)Q(1,7)(9)T(4,8)(10)nil(5,9),第四章确定性推理4.2归结演绎推理,2023/6/30,36,谓词逻辑消解反演的例子,例:
已知:
IfFidogoeswhereverJohngoesandifJohnisatschool,whereisFido?
(x)AT(John,x)AT(Fido,x)AT(John,School)求证:
(x)AT(Fido,x)子句集:
AT(John,y)AT(Fido,y)AT(John,School)AT(Fido,x)(x)AT(Fido,x)=(x)AT(Fido,x),第四章确定性推理4.2归结演绎推理,2023/6/30,37,谓词逻辑消解反演的例子(续),第四章确定性推理4.2归结演绎推理,2023/6/30,38,基于消解原理的问答系统,消解原理主要用来解决证明的问题,但有时我们希望得到如x=?
时,W(x)为真的回答消解原理是将结论的否定作为前提进行归结,而为了回答问题,用由结论的否定构成的重言式作为前提进行归结,得到的结论是问题的回答而不是空语句。
这个过程称为修改证明过程(或修改归结过程)。
下面以猴子摘香蕉问题为例来说明,第四章确定性推理4.2归结演绎推理,2023/6/30,39,用消解原理解猴子摘香蕉问题,为了把状态空间的算符描述与谓词演算结合起来,将状态添到谓词上;将算符看成是把一种状态映射成另一种状态的函数;问题简化成没有goto()规则;,第四章确定性推理4.2归结演绎推理,2023/6/30,40,猴子摘香蕉问题的表示,问题可以描述如下:
1,ONBOX(s0)2,(x)(s)(ONBOX(s)AT(box,x,push(x,s)3,(s)(ONBOX(climbbox(s)4,(s)(ONBOX(s)AT(box,c,s)HB(grasp(s)5,(x)(s)(AT(box,x,s)AT(box,x,climb(s)求解:
(s)HB(s),第四章确定性推理4.2归结演绎推理,2023/6/30,41,猴子摘香蕉问题的子句集,1,ON(s0)2,ON(s1)AT(box,x1,push(x1,s1)3,ON(climb(s2)4,ON(s3)AT(box,c,s3)HB(grasp(s3)5,AT(box,x4,s4)AT(box,x4,climb(s4)6,HB(s5),第四章确定性推理4.2归结演绎推理,2023/6/30,42,猴子摘香蕉问题的(修正)消解树,第四章确定性推理4.2归结演绎推理,2023/6/30,43,归结反演的搜索策略,归结反演过程是“运用归结规则直到产生空子句为止”在对子句集进行归结时,一个关键问题是如何选择子句进行归结。
如果对任意一对可以归结的子句都做归结,这样不仅消耗很多的时间,还会产生许多无用的归结式,占用很多空间因此,需要研究有效的归结控制(搜索)策略。
归结搜索策略一般包括:
排序策略和限制策略,第四章确定性推理4.2归结演绎推理,2023/6/30,44,排序策略,归结顺序与状态空间的扩展顺序类似。
状态空间的搜索问题有多种搜索策略。
把原始子句看成0层归结式。
(i+1)层的归结式是一个i层归结式和一个j(ji)层归结式进行归结所得到的归结式。
宽度优先:
先生成第1层的所有归结式然后是第2层所有的归结式,依次类推,直到产生空子句或不能再进行归结为止。
深度优先:
产生一个第1层的归结式,然后用第1层的归结式和第0层的归结式进行归结,得到第2层的归结式,直到产生空子句结束,或者不能归结,则回溯到其他的上层子句继续归结单元优先:
在归结过程中优先考虑仅由一个文字构成的子句,这样的子句称为单元子句。
第四章确定性推理4.2归结演绎推理,2023/6/30,45,限制策略,限制策略不涉及被归结子句的排序只允许某些归结发生。
其中几种限制归结策略:
删除策略支持集策略。
线性输入策略。
祖先过滤策略。
第四章确定性推理4.2归结演绎推理,2023/6/30,46,删除策略,如果在归结时能把子句集中的无用子句删除掉,这样就会缩小寻找范围,减少比较次数。
从而提高归结的效率。
删除策略有几种删除方法:
(1)纯文字删除法。
(2)重言式删除法。
(3)包孕删除法,第四章确定性推理4.2归结演绎推理,2023/6/30,47,纯文字删除法,如果某文字L在子句集中不存在可与之互补的文字L,则称该文字为纯文字。
在归结时纯文字不可能被消去,因而用包含它的子句进行归结时不可能得到空子句。
因此,这样的子句对归结是无意义的,把它从子句集中删去,不会影响子句集的不可满足性。
例如,子句集:
SPVQVR,QVR,Q,R可以看出,P是纯文字,因此可将子句PVQVR从S中删去。
第四章确定性推理4.2归结演绎推理,2023/6/30,48,重言式删除法,如果一个子句中同时包含互补文字对,则称该子句为重言式。
例如,P(x)VQ(x)VP(x)是重言式。
重言式是真值为真的子句。
对于一个子句集,增加或删去一个重言式子句都不会影响它的不可满足性,因而可从子句集中删去重言式。
第四章确定性推理4.2归结演绎推理,2023/6/30,49,包孕删除法,设C1,C2是两个子句,若存在置换,使得C1C2,则称子句C2包孕C1例如,P(a)VQ(y)包孕P(x)(=a/x)P(a)VQ(y)包孕Q(y)对于一个子句集,删去一个被别的子句包孕的子句,不会影响它的不可满足性。
因而可从子句集中删去被包孕的子句。
第四章确定性推理4.2归结演绎推理,2023/6/30,50,支持集策略,支持集策略:
每次归结时参与归结的子句中至少应有一个是由目标公式的否定所得到的子句,或者是它们的后裔后裔的定义:
设1是子句1与另外某子句的归结式是1的后裔1的后裔与其他子句的归结式是1的后裔。
支持集策略是完备的。
即对一个不可满足的子句集运用支持集策略进行归结,最终总会导出空子句。
第四章确定性推理4.2归结演绎推理,2023/6/30,51,线性输入策略,线性输入策略:
参加归结的两个子句中至少有一个是初始子句集中的子句。
线性输入策略是不完备的。
对于某些不可满足的子句集,无法用线性输入归结得到结果。
第四章确定性推理4.2归结演绎推理,2023/6/30,52,祖先过滤策略,祖先过滤策略:
参与归结的两个子句中至少有一个是初始子句集中的子句,或者一个子句是另一个子句的祖先。
祖先过滤策略是线性输入策略的改进策略,它是完备的。
第四章确定性推理4.2归结演绎推理,2023/6/30,53,消解方法小结,求子句集,进行归结,方法简单通过修改证明树的方法,提取回答方法通用求解效率低,不宜引入启发信息不宜理解推理过程,第四章确定性推理4.2归结演绎推理,2023/6/30,54,基于规则的演绎推理
(一),归结反演系统解决问题的效率低下归结演绎并非人类的自然思维方式,不利于人们从自然思维的角度组织问题的求解和提供问题求解所需的知识基于规则的演绎推理,运用推理规则,直接推导目标公式这符合人的自然思维方式,也能通过规则(作为启发式知识)更有效地引导演绎推理过程。
基于规则的演绎推理成为比归结反演更有效的技术,广泛地应用于许多问题求解中,第四章确定性推理4.3基于规则的演绎推理,2023/6/30,55,基于规则的演绎推理
(二),它把知识分为两类:
规则和事实规则表示为ifthen形式事实表示为与或形规则作为启发式知识,引导演绎推理过程。
事实是有关问题状态和环境的知识,规则演绎的任务就是从给定的事实证明某个目标公式成立。
采用直接法而不是反演系统证明目标公式,强调用规则进行演绎,故称基于规则的演绎推理.分为两类:
正向演绎和逆向演绎,第四章确定性推理4.3基于规则的演绎推理,2023/6/30,56,基于规则的正向演绎推理,将非蕴涵式部分的事实表示成与或形,可用与或图表示将蕴涵式部分的事实表示成规则规则表示成形式:
LW其中,L是单文字,W是与或形,变量受全称量词约束将目标公式表示成子句集正向演绎推理的过程,就是将规则运用于事实与或图,对与或图进行扩展变换的过程当与或图的叶节点包含目标公式的子句集时,推理成功,第四章确定性推理4.3基于规则的演绎推理正向演绎,2023/6/30,57,化目标公式为子句集,大部分步骤与归结原理中化子句集步骤相同消存在量词(skolem化)过程不同。
对于一个受存在量词约束的变量,消去原则:
如果他不受全程量词约束,则该变量用一个常量代替如果他受全程量词约束,则该变量用一个函数代替,且全称量词变为存在量词。
(z)(x)(y)(P(x)Q(x)R(y)U(z)=(x)(P(x)Q(x)R(f(x)U(a)消存在量词(P(x)Q(x)R(f(x)U(a)隐含目标公式的变量都受存在量词的约束,第四章确定性推理4.3基于规则的演绎推理正向演绎,2023/6/30,58,事实表达式的与或图表示,用K连线表示析取,无连线表示合取例:
Q(w,A)(R(v)P(v)S(A,v),第四章确定性推理4.3基于规则的演绎推理正向演绎,2023/6/30,59,将规则变换为限定形式,如果规则不是形式:
LW其中,L是单文字,W是与或形,变量受全称量词约束则首先变换为这种形式例:
(x)(y)(z)P(x,y,z)(u)Q(x,u)=(x)(y)(z)P(x,y,z)(u)Q(x,u)=(x)(y)(z)P(x,y,z)(u)Q(x,u)=(x)(y)(z)(u)(P(x,y,z)Q(x,u)=P(x,y,f(x,y)Q(x,u)(Skolem化)=P(x,y,f(x,y)Q(x,u)(恢复蕴涵式)例:
(L1L2)W=L1W和L2W,第四章确定性推理4.3基于规则的演绎推理正向演绎,2023/6/30,60,对与或图作变换例,例:
事实:
(PQ)R)(S(TU)规则:
S(XY)Z事实的与或图与规则对其进行的变换过程如下图:
第四章确定性推理4.3基于规则的演绎推理正向演绎,2023/6/30,61,(PQ)R)(S(TU),S(TU),S,TU,T,U,S,XY,Z,X,Y,PQSPQTUSRRTUPQXZPQYZRXZRYZ,规则的子句:
S(XY)Z=S(XY)Z=SXZSYZ,结论:
加入规则后得到的解图,是事实与规则对应子句的归结式,第四章确定性推理4.3基于规则的演绎推理正向演绎,2023/6/30,62,目标公式作为终止条件,应用规则进行推理的目的是为了证明某个目标公式在正向推理系统中,这种目标表达式只限于可证明的表达式,尤其是可证明的文字析取形的目标公式表达式在与或图的产生过程中,目标文字或规则与图中文字节点匹配时,产生新后裔节点,标记为匹配的目标文字。
当产生的图包含有终止在目标节点上的一个解图时,系统便成功地结束。
第四章确定性推理4.3基于规则的演绎推理正向演绎,2023/6/30,63,例:
事实:
AB规则集:
ACDBEG目标公式:
CG,AB,A,A,C,D,B,B,E,G,C,G,目标,目标公式作为终止条件例一,匹配弧,第四章确定性推理4.3基于规则的演绎推理正向演绎,2023/6/30,64,目标公式作为终止条件例二,例:
事实:
P(x,y)(Q(x,A)R(B,y)规则集:
P(A,B)(S(A)X(B)Q(B,A)U(A)R(B,B)V(B)目标:
S(A)X(B)(U(A)V(B)事实的与或图与规则对其进行的变换过程如下图:
第四章确定性推理4.3基于规则的演绎推理正向演绎,2023/6/30,65,P(x,y)(Q(x,A)R(B,y),P(x,y),Q(x,A)R(B,y),Q(x,A),R(B,y),P(A,B),A/x,B/y,S(A),X(B),Q(B,A),B/x,U(A),R(B,B),B/y,V(B),例二的与或图,第四章确定性推理4.3基于规则的演绎推理正向演绎,2023/6/30,66,基于规则的逆向演绎推理,将目标表达式表示成与或形
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 人工智能 第五 确定性 推理