人工智能7课题.pptx

,0871-5031301,2019年12月11日星期三,人工智能,#,/,1,6,jhzhang,信 息 学 院,人工智能,1,2,3,4,人工智能,一种现代方法,第三部分 知识和推理,命题逻辑谓词逻辑知识表示方法,第七章 逻辑智能体,7.1,基于知识的智能体,7.2 wumpus,世界,7.3,逻辑,7.4,命题逻辑,7.5,命题逻辑的推理模式,7.6,基于命题逻辑的智能体,基于知识的智能体,知识库,(Knowledge base,，,KB),：语句的集合,TELL,：将新语句添加到知识库，,告诉知识库感知的信息,记录选择的行动,ASK,：查询知识库，以获得应该执行的行动,Wumpus,世界,性能度量：,金子,+1000,，死亡,-1000,每次行动,-1,，用掉箭,-10,环境：,4*4,网格，金子、陷阱、,wumpus,传感器：,Stench,Breeze,Glitter,Bump,Scream,执行器：向前移动，左、右转,90,度，,Grab,，,shoot,，,部分可观察、确定性的、延续式的、静态的、离散的、单智能体环境。,None,None,None,None,None,None,Breeze,None,None,None,Stench,None,None,None,None,None,None,None,None,None,Stench,Breeze,Glitter,None,None,逻辑,逻辑的历史,Aristotle,：逻辑学,Leibnitz,：数理逻辑,Gottlob frege:,一阶谓词演算系统，,符号论,(19,世纪,),20,世纪,30,年代，数理逻辑广泛发展,逻辑系统,一个逻辑系统是定义语言和它的含义的方法。,逻辑符号集合：在所有该逻辑的逻辑理论中均出现的符号,非逻辑符号集合：不同的逻辑理论中出现的不同的符号,语句规则：定义什么样的符号串是有意义的,语义规则：定义符号串的语义,推理规则、公理和证明,逻辑和程序语言的对比,逻辑系统,程序语言,逻辑符号,保留字或符号,非逻辑符号,用户自定义的符号,(,变量名，函数名等,),语句规则,构造一个程序的语句规则,语义规则,定义程序做什么的规则,推理规则、公理和证明,无,语义,x+2 y,在,x=7,y=1,的世界中为真,x+2 y,在,x=0,y=6,的世界中为假,可能世界,模型,m,是,的一个模型，表示语句,在模型,m,中为真,逻辑推理,-,蕴含关系（,entailment,）,，当且仅当在,为真的模型中，,也为真,（当,为真，,必定为真）,即,的真值包含于,的真值中,例如：,x+y=4,蕴含,4=x+y,KB,一个语句逻辑上跟随另一个语句而出现,模型检验,3,个方格中的每个可能包含或不包含陷阱，则存在,8,个可能的模型,与智能体所知内容相矛盾的模型中，,KB,为假。,1,：,1,2,无陷阱，,2,：,2,2,无陷阱,模型检验,根据,1,1,无微风，则在任意,1,2,有陷阱的模型中，,KB,为假,仅,3,个模型使得,KB,为真。,1,：,1,2,无陷阱,KB,1,模型检验,KB,2,2,：,2,2,无陷阱,模型检验,模型检验,:,枚举出所有可能的模型用于检验在,KB,中为真的所有模型中,为真。,推理的可靠性和完备性,KB,i,：,通过推理算法,i,从,KB,中导出，,推理算法,i,从,KB,中导出,推理算法,i,是可靠的：如果,KB,i,，则,KB,推理算法,i,是完备的：如果,KB,，则,KB,i,命题逻辑,命题：能够分辨真假的陈述句。,例如：,1+1=2,雪是绿色的,昆明是云南的省会,快点走吧,!,到哪去？,一个原子命题可以用字母表示,(,命题符号,),。,命题逻辑是由命题符号和逻辑连接符组成。,原子命题：一个命题，且是不能再进一步分解成更简单语句。是命题的基本单位。,逻辑连接符,合取式：,p,与,q,，记为,p,q,析取式：,p,或,q,，记为,p,q,蕴含式：如果,p,则,q,，记为,p,q,等价式：,p,当且仅当,q,，记为,p,q,否定式：非，,p,优先级：,，,，,，,，,命题表示,将陈述句转化为命题公式：,例如：设,“,下雨,”,为,p,，,“,骑车上班,”,为,q,1.,“,只要不下雨，我就骑自行车上班,”,。,p,是,q,的充分条件，可得命题公式：,p,q,2.,“,只有不下雨，我才骑自行车上班,”,。,p,是,q,的必要条件，可得命题公式：,q,p,3.“,应届毕业生，得过国家级竞赛一等奖或全班排名第一，保送研究生”,设：,p“,应届毕业生,”,，,q“,保送研究生,”,，,r“,得过国家级竞赛一等奖,”,，,t“,全班排名第一,”,则有命题公式：,p,（,r,t,）,q,True,永真命题，,False,永假命题,析取范式：仅由有限个简单合取式组成的析取式,p,（,p,q,）,（,p,q,）,合取范式：仅由有限个简单析取式组成的合取式,p,（,p,q,）,（,p,q,）,语义,例如：某模型下，,P,1,2,P,2,2,P,3,1,假真,假,语义定义了用于判定关于特定模型的语句真值的规则,逻辑连接符的真值表：指定了复合句在其组成部分的真值的每种可能赋值情况下的真值。,P,1,2,(P,2,2,P,3,1,)=,true,(,true,false,)=,true,true,=,true,Wumpus,世界的知识库,P,i,j,：在,i,j,有陷阱,B,i,j,：在,i,j,有微风,P,1,1,B,1,1,B,2,1,陷阱使得其邻域方格有微风,B,1,1,(P,1,2,P,2,1,),B,2,1,(P,1,1,P,2,2,P,3,1,),推理的基本概念,推理：从已知事实出发，运用已掌握的知识，推导出其中蕴含的事实性结论或归纳出某些新的结论的过程。,推理所用的事实：初始证据；中间结论。,初始,证据,推理机,结论,知识库,目标是判断某些语句,x,，,kB|=x,是否成立。,模型检验：枚举出模型，验证,x,在,KB,为真的每个模型中为真,推理真值表,1,：,P,1,2,2,：,P,2,2,真值表枚举算法,真值表枚举算法，是可靠的、完备的,n,个符号，存在,2,n,个模型，时间复杂度,O(2,n,),用于命题逻辑的有效模型检验推理算法包括回溯,(DPLL,算法,),和局部搜索方法（,WALKSAT,算法）。,推理方法,演绎推理：从已知的一般性知识出发，推理出适合于某些个别情况的结论的过程。,归纳推理：从大量的特殊事例出发，归纳出一般性结论的推理过程。,默认推理：在知识不完全的情况下假设某些条件已经具备所进行的推理。,推理的不确定性及其单调性,确定性推理：推理所用的证据、知识及结论都是可以精确表示的，其真值不为真就为假，不会有第三种情况出现。,不确定性推理：推理所用的证据、知识及结论都是不确定的，都是不可以精确表示的，其真值位于真和假之间。,单调性推理：由于新知识的加入和使用，使推理所得到的结论会越来越接近目标。,非单调性推理：推理过程中某些新知识的加入和使用，不但没有加强已经推出的结论，反而会否定原来已推出的结论。,交换律：,p,q,q,p,p,q,q,p,结合律,：,(,p,q,),r,p,(,q,r,),(,p,q,),r,p,(,q,r,),分配率：,p,(,q,r,),(,p,q,),(,p,r,),p,(,q,r,),(,p,q,),(,p,r,),基本等值式：,，当且仅当,且,摩根律：,(,p,q,),p,q,(,p,q,),p,q,吸收律：,p,(,p,q,),p,p,(,p,q,),p,同一律：,p,0,p,p,1,p,蕴含等值式,：,p,q,p,q,（蕴含消去）,假言易位式：,p,q,q,p,（逆否命题）,双向蕴含消去：,p,q,(,p,q,),(,q,p,),基本等值式：,合法性和可满足性,例如：,True,，,A,A,A,A,(A,(A,B),B,若,至少有一个成真赋值，则称,为可满足的,e.g.,A,B,C,若,无成真赋值，则称,为不可满足的，称矛盾式或永假式，,例如：,A,A,若语句,无成假赋值，则称,是合法的，称重言式或永真式，,是合法的，当且仅当,是不可满足的,是可满足的，当且仅当,是不合法的,反证法（归谬）：,KB,当且仅当,(,KB,),是不可满足的,推理规则,逻辑等价,分离规则：,例如，已知,（,WumpusAhead,WumpusAlive)shoot,和,（,WumpusAhead,WumpusAlive),，可推导出,shoot,与消去（合取式推导出任何合取子句）：,例如：,WumpusAhead,WumpusAlive,可推导出,WumpusAlive,推理规则的应用序列,-,证明,1.,双向蕴含消去：,代换为,(,),(,).,由语句,(4),得：,(B,1,1,(P,1,2,P,2,1,),(P,1,2,P,2,1,),B,1,1,)-(6),2.,语句（,6,）与消去：,(P,1,2,P,2,1,),B,1,1,)-(7),语句,(7),再根据,（逆否命题）,得：,(,B,1,1,(,(P,1,2,P,2,1,)-,（,8,）,3.,由语句（,8,）和（,2,）根据分离规则得：,(,(P,1,2,P,2,1,)-(9),4.,根据摩根律：,P,1,2,P,2,1,-,（,10,）,（,1,）,P,1,1,（,2,）,B,1,1,（,3,）,B,2,1,（,4,）,B,1,1,(P,1,2,P,2,1,),（,5,）,B,2,1,(P,1,1,P,2,2,P,3,1,),归结,A,B,反证法：证明,A,B,是矛盾式（永假式）,建立子句集,合取范式：命题、命题或的与,例如：,p,（,p,q,）,（,p,q,）,子句集,S,：合取范式形式下得子命题（元素）的集合,例如：上述命题公式的子句集,S=p,p,q,p,q,合取范式,B,1,1,(P,1,2,P,2,1,),1.,消去,：,替换为,(,),(,).,(B,1,1,(P,1,2,P,2,1,),(P,1,2,P,2,1,),B,1,1,),2.,消去,：,替换为,.,(,B,1,1,P,1,2,P,2,1,),(,(P,1,2,P,2,1,),B,1,1,),3.,根据摩根律移入,：,(,B,1,1,P,1,2,P,2,1,),(,P,1,2,P,2,1,),B,1,1,),4.,根据分配率,:,(,B,1,1,P,1,2,P,2,1,),(,P,1,2,B,1,1,),(,P,2,1,B,1,1,),单元归结规则,l,1,l,k,m,l,1,l,i-1,l,i+1,l,k,其中,l,i,and,m,是互补文字,(,一个文字是另一个文字的否定式,).,全归结规则,l,1,l,k,m,1,m,n,l,1,l,i-1,l,i+1,l,k,m,1,m,j-1,m,j+1,.,m,n,其中,l,i,和,m,j,是互补文字,归结规则：,P,1,3,P,2,2,P,2,2,P,1,3,归并：（,A,B,）和（,A B,）归结,得到,A,A,，最终简化为,A,l,i,真，則,m,j,假,(,m,1,m,j-1,m,j+1,.,m,n,),真,l,i,假，,l,1,l,i-1,l,i+1,l,k,真,归结规则的完备性：任何完备的搜索算法，只使用归结规则，就可以生成命题逻辑中被任何知识库蕴涵的任何结论。,l,1,l,k,m,1,m,n,l,1,l,i-1,l,i+1,l,k,m,1,m,j-1,m,j+1,.,m,n,归结规则的可靠性：,已知,A,为真，无法用归结自动生成结论,A B,，但可以用归结判断,A B,是否为真。,将命题写成合取范式,求出子句集,S,对子句集使用归结推理规则,归结式作为新子句参加归结,归结式为空子句，,S,是不可满足的（矛盾），原命题成立,归结过程,例如：证明公式（,p,q,）,（,q p,）,证：将待证明公式转化为归结命题公式：,（,p,q,）,(q p),将该公式转化为合取范式,p,q,p,q,(q p),(q,p),q p,（,p,q,）,(q p),(,p,q,),q p,则子句集：,p,q,，,q,，,p,对子句集中的子句进行归结：,（,1,）,p,q,（,2,）,q,（,3,）,p,（,4,）,q,（,1,3,归结）,（,5,）空（,2,4,归结）,KB,=(B,1,1,(P,1,2,P,2,1,),B,1,1,=,P,1,2,Wumpus,世界的归结推理,(B,1,1,(P,1,2,P,2,1,),B,1,1,P,1,2,(,B,1,1,P,1,2,P,2,1,),(,P,1,2,B,1,1,),(,P,2,1,B,1,1,),B,1,1,P,1,2,前向和反向链接,霍恩子句：至多只有一个正文字的文字析取式,(,P,1,2,B,1,1,)P,2,1,P,1,2,P,2,1,(,B,1,1,P,1,2,P,2,1,),每个霍恩子句都可写成一个蕴涵式：,(,P,1,2,B,1,1,),P,1,2,B,1,1,没有正文字的霍恩子句：可写成结论为,False,的蕴涵式,例如：,P,1,2,P,2,1,（,P,1,2,P,2,1,),False,确定子句：只有一个正文字，例如：,P,2,1,，断言一个事实,使用霍恩子句的推理可在前向链接和反向链接中进行,使用霍恩子句判定蕴涵需要的时间和数据库大小成线性关系,前向链接,判定单个命题符号,q,是否被霍恩子句的知识库所蕴涵：,从知识库的已知事实,(,正文字,),开始，如果蕴涵的所有前提已知，则将其结论添加到已知事实集。直到查询,q,被添加或无法进行更进一步的推理,前向链接,前向链接,前向链接,前向链接,前向链接,前向链接,前向链接,前向链接,可靠的,完备的,前向链接中每个推理本质上是分离规则的一个应用。,从查询,q,反向进行：,查询,q,是否是已知事实，否则,寻找知识库中能以,q,为结论的蕴涵，若其中某个蕴涵的所有前提都能证明为真，则,q,为真。,反向链接,反向链接,反向链接,反向链接,反向链接,反向链接,反向链接,反向链接,反向链接,反向链接,反向链接,前向链接和反向链接的比较,前向链接是数据驱动的推理，由感知信息自动推理，无意识,多用于目标识别，路线决策,可能产生和目标无关的中间结果,反向链接是目标指导的推理，,适用于求解：“现在该做什么”，“钥匙在哪里”一类问题,耗散远小于知识库大小的线性值,常将前向推理限制在生成与要用反向链接求解的查询相关的事实上。,基于命题逻辑的智能体,采用推理算法和知识库的智能体,以电路形式直接计算逻辑表达式的智能体,采用推理算法和知识库的智能体,P,1,1,W,1,1,B,x,y,(P,x,y+1,P,x,y-1,P,x+1,y,P,x-1,y,),S,x,y,(W,x,y+1,W,x,y-1,W,x+1,y,W,x-1,y,),W,1,1,W,1,2,W,4,4,W,1,1,W,1,2,W,1,1,W,1,3,4*4,世界，,64,个命题符号，,155,个语句,Agent,位置，时间,L,1,1,1,FacingRight,Forward,L,2,2,1,Wumpus,世界智能体,以电路形式直接计算逻辑表达式的智能体,感知信息是序列电路（门和寄存器网络）的输入,每个门实现一个逻辑连接符,用寄存器的比特表示命题（即每个寄存器存储一个单个命题的真值），并用逻辑电路的信号传播对它们进行更新。,电路的输出对应于行动的寄存器,命题逻辑对于智能体内的特定任务是合理有效的，但没有足够的表达能力来准确地处理时间、空间以及对象间关系的普遍模式，因而无法处理大小无界的环境。,