人工智能基础04--推理技术.pptx
《人工智能基础04--推理技术.pptx》由会员分享，可在线阅读，更多相关《人工智能基础04--推理技术.pptx（101页珍藏版）》请在冰点文库上搜索。
目录,第一章绪论第二章知识表示第三章搜索技术第四章推理技术第五章机器学习第六章专家系统第七章自动规划系统第八章自然语言理解第九章智能控制第十章人工智能程序设计,4.0推理的基本概念,4.0.1推理的定义从初始证据出发，按某种策略不断应用知识库中的已知知识，逐步推出结论的过程称为推理。
在人工智能系统中，推理是由程序实现的，称为推理机。
已知事实和知识是构成推理的两个基本要素。
事实又称为证据，用以指出推理的出发点及推理时应该使用的知识。
知识是使推理得以向前推进，并逐步达到最终目标的依据。
4.0推理的基本概念,4.0.2推理方式及其分类
（1）按推出结论的途径来划分，推理可分为：
演绎推理（deductiveresoning）：
是从全称判断推导出单称判断的过程，即由一般性知识推出适合某一具体情况的结论。
一般到个别。
归纳推理（inductiveresoning）：
是从足够多的事例中归纳出一般性结论的推理过程。
个别到一般。
默认推理（defaultresoning）：
是在知识不完全的情况下假设某些条件已经具备所进行的推理。
4.0推理的基本概念,4.0.2推理方式及其分类
（2）按推理时所用的知识的确定性来划分，推理可分为：
确定性推理：
是指推理时所用的知识与证据都是确定的，退出的结论也是确定的，其真值或者为真或者为假，没有第三种情况出现。
不确定性推理：
是指推理时所用的知识与证据不都是确定的，推出的结论也是不确定的。
4.0推理的基本概念,4.0.2推理方式及其分类（3）按推理过程中推出的结论是否越来越接近最终目标来划分，推理可分为：
单调推理：
是指在推理过程中随着推理向前推进及新知识的加入，推出的结论越来越接近最终目标。
非单调推理：
是指在推理过程中由于新知识的加入，不仅没有加强已推出的结论，反而要否定它，使推理退回到前面的某一步，然后重新开始。
4.0推理的基本概念,4.0.2推理方式及其分类（4）按推理中是否运用与推理有关的启发性知识来划分，推理可分为：
启发性推理：
是指在推理过程中运用与推理有关的启发性知识。
非启发性推理：
是指在推理过程中未运用与推理有关的启发性知识。
4.0推理的基本概念,4.0.3推理的方向
（1）正向推理是以事实作为出发点的一种推理。
基本思想：
从用户提供的初始已知事实出发，在知识库KB中找出当前可适用的知识，构成可适用知识集KS，然后按某种冲突消解策略从KS中选出一条知识进行推理，并将推出的新事实加入到数据库中作为下一步推理的已知事实，此后再在KB中选取可适用的知识进行推理，如此重复这一过程，直到求得了问题的解或者知识库中再无可适用的知识为止。
4.0推理的基本概念,4.0.3推理的方向
（2）逆向推理是以某个假设目标为出发点的一种推理。
基本思想：
首先选择一个假设目标，然后寻找支持该假设的证据，若需的证据都能找到，则说明原假设是成立的；若无论如何都找不到所需的证据，则说明原假设不成立，为此需要另作新的假设。
4.0推理的基本概念,4.0.3推理的方向（3）混合推理正向推理具有盲目、效率低等缺点，推理过程中可能会推出许多与问题无关的子目标。
逆向推理中，若提出的假设目标不符合实际，也会降低系统效率。
可以把正向推理与逆向推理结合起来，使其各自发挥自己的优势，取长补短。
这种既有正向推理又有逆向推理称为混合推理。
4.0推理的基本概念,4.0.3推理的方向（4）双向推理双向推理：
是指正向推理与逆向推理同时进行，且在推理过程中的某一步骤上“碰头”的一种推理。
基本思想：
一方面根据已知事实进行正向推理，但并不推倒最终目标；另一方面从某假设目标出发进行逆向推理，但不推至原始事实，而是让它们在中途相遇，即由正向推理所得到的中间结论恰好是逆向推理此时所需求的证据，这时推理就可以结束，逆向推理时所做的假设就是推理的最终结论。
4.0推理的基本概念,4.0.4冲突消解策略系统将当前已知事实与KB中知识匹配的三种情况：
（1）已知事实恰好只与KB中的一个知识匹配成功。
（2）已知事实不能与KB中的任何知识匹配成功。
（3）已知事实可与KB中的多个知识匹配成功；或者多个（组）事实都可与KB中的某一个知识匹配成功；或者多个（组）事实都可与KB中的多个知识匹配成功；第3种情况称为发生了冲突。
4.0推理的基本概念,4.0.4冲突消解策略消解冲突的基本思想：
对知识进行排序：
（1）按针对性排序：
优先选择针对性强的知识（规则），即要求条件多的规则。
（2）按已知事实的新鲜性排序：
后生成的事实具有较大的新鲜性。
（3）按匹配度排序：
在不确定推理中，需要计算已知事实与知识的匹配度。
（4）按条件个数排序：
优先应用条件少的产生式规则。
4.1消解原理,4.1.1子句集的求取消解原理是针对谓词逻辑知识表示的问题求解方法。
消解原理的基础知识：
（1）谓词公式、某些推理规则以及置换合一等概念。
（2）子句：
由文字的析取组成的公式（一个原子公式和原子公式的否定都叫做文字）。
（3）消解：
当消解可使用时，消解过程被应用于母体子句对，以便产生一个导出子句。
例如，如果存在某个公理E1E2和另一公理E2E3，那么E1E3在逻辑上成立。
这就是消解，而称E1E3为E1E2和E2E3的消解式。
4.1消解原理,4.1.1子句集的求取步骤
（1）消去蕴涵符号只应用和符号，以AB替换AB。
（AB）BC=（AB）BC=（AB）BC=（AB）BC=（AB）（BB）C=（AB）C,4.1消解原理,4.1.1子句集的求取
（2）减少否定符号的辖域每个否定符号最多只用到一个谓词符号上，并反复应用狄摩根定律。
例如：
以AB代替（AB）以AB代替（AB）以A代替（A）以（彐x）A代替（x）A以（x）A代替（彐x）A,4.1消解原理,4.1.1子句集的求取（3）对变量标准化在任一量词辖域内，受该量词约束的变量为一哑元（虚构变量），它可以在该辖域内处处统一地被另一个没有出现过的任意变量所代替，而不改变公式的真值。
合适公式中变量的标准化意味着对哑元改名以保证每个量词有其自己唯一的哑元。
如，对（x）P（x）（彐x）Q（x）标准化可得：
（x）P（x）（彐y）Q（y）,4.1消解原理,4.1.1子句集的求取（4）消去存在量词Skolem函数：
（y）（彐x）P（x,y）中，存在量词是在全称量词的辖域内，允许所存在的x可能依赖于y值。
令这种依赖关系明显地有函数g（y）所定义，它把每个y值映射到存在的那个x。
这种函数叫做Skolem函数。
如果用Skolem函数代替存在的x，就可以消去全部存在量词，并写成：
（y）P（g（y）,y）,4.1消解原理,4.1.1子句集的求取从一个公式消去一个存在量词的一般规则是以一个Skolem函数代替每个出现的存在量词的量化变量，而这个Skolem函数的变量就是由那些全称量词所约束的全称量词量化变量，这些全称量词的辖域包括要被消去的存在量词的辖域在内。
Skolem函数所使用的函数符号必须是新的，即不允许是公式中已经出现过的函数符号。
如果要消去的存在量词不在任何一个全称量词的辖域内，则用不含变量的Skolem函数即常量。
例如，（彐x）P（x）化为P（A），其中常量符号A用来表示人们知道的存在实体。
A必须是个新的常量符号，它未曾在公式中其它地方使用过。
4.1消解原理,4.1.1子句集的求取（5）化为前束形把所有全称量词移到公式的左边，并使每个量词的辖域包括这个量词后面公式的整个部分。
所得公式称为前束形。
前束形=（前缀）（母式）全称量词串无量词公式（6）把母式化为合取范式任何母式都可写成由一些谓词公式和（或）谓词公式的否定的析取的有限集组成的合取。
这种母式叫做合取范式。
如：
ABC化为ABBC,4.1消解原理,4.1.1子句集的求取（7）消去全称量词消去明显出现的全称量词。
（8）消去连词符号用A，B代替（AB），以消去明显的符号。
反复代替的结果，最后得到一个有限集，其中每个公式是文字的析取。
任一个只由文字的析取构成的合适公式叫做一个子句。
（9）更换变量名称可以更换变量符号的名称，使一个变量符号不出现在一个以上的子句中。
4.1消解原理,4.1.1子句集的求取例：
将下列谓词演算公式化为一个子句集（x）P（x）（y）P（y）P（f（x,y）（y）Q（x,y）P（y）
（1）消去蕴涵符号（x）P（x）（y）P（y）P（f（x,y）（y）Q（x,y）P（y）
（2）减少否定符号辖域（x）P（x）（y）P（y）P（f（x,y）（彐y）Q（x,y）P（y）（x）P（x）（y）P（y）P（f（x,y）（彐y）Q（x,y）P（y）（3）对变量标准化（x）P（x）（y）P（y）P（f（x,y）（彐w）Q（x,w）P（w）,4.1消解原理,4.1.1子句集的求取（4）消去存在量词（x）P（x）（y）P（y）P（f（x,y）Q（x,g（x）P（g（x）w=g（x）为一个skolem函数。
（5）化为前束形（x）（y）P（x）P（y）P（f（x,y）Q（x,g（x）P（g（x）（6）把母式化为合取范式（x）（y）P（x）P（y）P（f（x,y）P（x）Q（x,g（x）P（x）P（g（x）,4.1消解原理,4.1.1子句集的求取（7）消去全称量词P（x）P（y）P（f（x,y）P（x）Q（x,g（x）P（x）P（g（x）（8）消去连词符号P（x）P（y）P（f（x,y），P（x）Q（x,g（x），P（x）P（g（x）（9）更换变量名称P（x1）P（y）P（f（x1,y），P（x2）Q（x2,g（x2），P（x3）P（g（x3）,4.1消解原理,4.1.2消解推理规则令L1为任一原子公式，L2为另一原子公式；L1和L2具有相同的谓词符号，但一般具有不同的变量。
已知两子句L1和L2,如果L1和L2具有最一般合一者，那么通过消解可以从这两个父辈子句推导出一个新子句（）。
这个新子句叫做消解式。
它是由取这两个子句的析取，然后消去互补对而得到的。
4.1消解原理,4.1.2消解推理规则常用消解规则
（1）假言推理父辈子句PPQ（即PQ）消解式Q,4.1消解原理,4.1.2消解推理规则常用消解规则
（2）合并父辈子句PQPQ消解式QQ=Q,4.1消解原理,4.1.2消解推理规则常用消解规则（3）重言式PQPQPQPQ消解式QQPP,4.1消解原理,4.1.2消解推理规则常用消解规则（4）空子句（矛盾）PP消解式NIL,4.1消解原理,4.1.2消解推理规则常用消解规则（5）链式（三段论）PQQR消解式PR,4.1消解原理,4.1.3含有变量的消解式为了对含有变量的子句使用消解规则，必须找到一个置换，作用于父辈子句使其含有互补文字。
例：
设有两个字句P（x）Q（x）Q（f（y））置换=f（y）/x消解可得：
P（f（y））,4.1消解原理,4.1.3含有变量的消解式令父辈子句由Li和Mi给出，假设这两个子句中的变量已经分别标准化。
设li是Li的一个子集，mi是Mi的一个子集，若是li和mi的最一般的合一，消解两个子句Li和Mi，得到新子句Li-liMi-mi就是这两个子句的消解式。
消解两个子句时，可能有一个以上的消解式，因为有多种选择li和mi的方法。
4.1消解原理,4.1.3含有变量的消解式例：
考虑两个子句：
Px,f（A）Px,f（y）Q（y）pz,f（A）Q（z）取li=Px,f（A），mi=pz,f（A）可得消解式Pz,f（y）Q（y）Q（z）,=z/x,4.1消解原理,4.1.3含有变量的消解式如果取li=Q（y），mi=Q（z）则可得消解式Px,f（A）Px,f（y）py,f（A）进一步消解的消解式Py,f（y）,=y/z,4.1消解原理,4.1.3含有变量的消解式几个含有变量的子句使用消解的例子：
B（x）,B（x）C（x）,C（x）,4.1消解原理,4.1.3含有变量的消解式几个含有变量的子句使用消解的例子：
P（x）Q（x）,Qf（y）,Pf（y）,=f（y）/x,4.1消解原理,4.1.3含有变量的消解式几个含有变量的子句使用消解的例子：
P（x,f（y）Q（x）Rf（a）,y,Pf（f（a）,zR（z,w）,Q（f（f（a）Rf（a）,yR（f（y）,w）,=f（f（a）/x,f（y）/z,4.1消解原理,4.1.4消解反演求解过程1.基本思想把要解决的问题作为一个要证明的命题，其目标公式被否定并化成子句形，然后添加到命题公式集中去，把消解反演系统应用于联合集，并推导出一个空子句（NIL），产生一个矛盾，这说明目标公式的否定式不成立，即有目标公式成立，定理得证，问题得到解决，与数学中反证法的思想十分相似。
4.1消解原理,4.1.4消解反演求解过程2、消解反演反演求解的步骤给出一个公式集S和目标公式L，通过反证或反演来求证目标公式L，其证明步骤如下：
（1）否定L，得L；
（2）把L添加到S中去；（3）把新产生的集合L，S化成子句集；（4）应用消解原理，力图推导出一个表示矛盾的空子句NIL。
4.1消解原理,4.1.4消解反演求解过程反演求解的正确性设公式L在逻辑上遵循公式集S，那么按照定义满足S的每个解释也满足L。
决不会有满足S的解释能够满足L的，所以不存在能够满足并集SL的解释。
如果一个公式集不能被任一解释所满足，那么这个公式是不可满足的。
因此，如果L在逻辑上遵循S，那么SL是不可满足的。
可以证明，如果消解反演反复应用到不可满足的子句集，那么最终将要产生空子句NIL。
因此，如果L在逻辑上遵循S，那么由并集SL消解得到的子句，最后将产生空子句；反之，可以证明，如果从SL的子句消解得到空子句，那么L在逻辑上遵循S。
4.1消解原理,4.1.4消解反演求解过程反演求解举例例：
储蓄问题前提：
每个储蓄钱的人都获得利息。
结论：
如果没有利息，那么就没有人去储蓄钱证明：
令S（x,y）表示“x储蓄y”M（x）表示“x是钱”I（x）表示“x是利息”E（x,y）表示“x获得y”于是上述命题写成：
4.1消解原理,4.1.4消解反演求解过程（x）（彐y）（S（x,y）M（y）=（彐y）（I（y）E（x,y）结论：
（彐x）I（x）=（x）（y）（M（y）=（S（x,y）化为子句集：
S=S（x,y）M（y）I（f（x）,S（x,y）M（y）E（x,f（x）其中，y=f（x）为Skolem函数。
而L=（彐x）I（x）=（x）（y）（s（x,y）=M（y）=I（z）,S（a,b）,M（b）,P=Q等价Q=P,4.1消解原理,4.1.4消解反演求解过程按4个步骤进行反演求解
（1）否定L，即有L=I（z）,S（a,b）,M（b）
（2）将L添加到S中去,即S=L,S=S（x,y）M（y）I（f（x）,S（x,y）M（y）E（x,f（x）,I（z）,S（a,b）,M（b）（3）把新产生的集合化成子句集，即S=S（x,y）M（y）I（f（x）,S（x,y）M（y）E（x,f（x）,I（z）,S（a,b）,M（b）（4）应用消解原理，推导出一个表示矛盾的空子句NIL。
4.1消解原理,4.1.4消解反演求解过程,S（x,y）M（y）I（f（x）,I（z）,S（x,y）M（y）,=f（x）/z,M（b）,S（a,b）,=a/x,b/y,NIL,M（b）,4.1消解原理,4.1.4消解反演求解过程反演求解过程步骤：
（1）把由目标公式的否定产生的每个子句添加到目标公式否定之否定的子句中去。
（2）按照反演树，执行和以前相同的消解，直至在根部得到某个子句止。
（3）用根部的子句作为一个回答语句。
4.1消解原理,4.1.4消解反演求解过程分析：
答案求取涉及到把一棵根部有NIL的反演树变换为在根部带有可用作答案的某个语句的一颗证明树。
由于变换关系涉及到把由目标公式的否定产生的每个子句变换为一个重言式，所以被变换的证明树就是一棵消解的证明树，其在根部的语句在逻辑上遵循公理加上重言式，因而也单独地遵循公理。
因此被变换的证明树本身就证明了求取办法是正确的。
4.1消解原理,4.1.4消解反演求解过程例4.3如果无论约翰（John）到哪里去，菲多（Fido）也就去那里，那么如果约翰在学校里，菲多在哪里呢?
事实公式集：
S=（x）AT（JOHN,x）=AT（FIDO,x）,AT（JOHN,SCHOOL）目标公式L：
（彐x）AT（FIDO,x）首先证明L在逻辑上遵循公式集SL=（彐x）AT（FIDO,x）=（x）AT（FIDO,x）其子句为AT（FIDO,x）,4.1消解原理,4.1.4消解反演求解过程例4.3的反演树,AT（FIDO,x）,AT（JOHN,y）AT（FIDO,y）,AT（JOHN,x）,=x/y,NIL,AT（JOHN,SCHOOL）,=SCHOOL/x,4.1消解原理,4.1.4消解反演求解过程例4.3从消解求取答案的反演树,AT（FIDO,x）AT（FIDO,y）,AT（JOHN,y）AT（FIDO,y）,AT（JOHN,x）AT（FIDO,x）,=x/y,AT（FIDO,SCHOOL）,AT（JOHN,SCHOOL）,=SCHOOL/x,目标公式的重言式,4.2规则演绎系统,规则演绎系统的定义：
基于规则的问题求解系统运用下述规则来建立：
IfThen其中，If部分可能由几个if组成，而Then部分可能由一个或一个以上的then组成。
在所有基于规则系统中，每个if可能与某断言（assertion）集中的一个或多个断言匹配。
有时把该断言集称为工作内存。
在许多基于规则系统中，then部分用于规定放入工作内存的新断言。
这种基于规则的系统叫做规则演绎系统（rulebaseddeductionsystem）。
在这种系统中，通常称每个if部分为前项（antecedent），称每个then部分为后项（consequent）。
4.2规则演绎系统,4.2.1正向规则演绎系统正向规则演绎系统是从事实到目标进行操作的，即从状况条件到动作进行推理的，也就是从if到then的方向进行推理的。
1.事实表达式的与或形变换把事实表示为非蕴涵形式的与或形，作为系统的总数据库。
具体变换步骤与前述化为子句形类似。
注意：
我们不想把这些事实化为子句形，而是把它们表示为谓词演算公式，并把这些公式变换为叫做与或形的非蕴涵形式。
4.2规则演绎系统,4.2.1正向规则演绎系统例：
有事实表达式（彐u）（v）Q（v,u）（R（v）P（v）S（u,v）把它化为Q（v,A）R（v）P（v）S（A,v）对变量更名标准化，使得同一变量不出现在事实表达式的不同主要合取式中，得：
Q（w,A）R（v）P（v）S（A,v）,4.2规则演绎系统,4.2.1正向规则演绎系统2.事实表达式的与或图表示将上例与或形的事实表达式用与或图来表示,Q（w,A）R（v）P（v）S（A,v）,Q（w,A）,R（v）P（v）S（A,v）,R（v）P（v）,S（A,v）,R（v）,P（v）,4.2规则演绎系统,4.2.1正向规则演绎系统3.与或图的F规则变换这些规则是建立在某个问题辖域中普通陈述性知识的蕴涵公式基础上的。
把允许用作规则的公式类型限制为下列形式LW式中：
L是单文字；W为与或形的唯一公式。
4.2规则演绎系统,4.2.1正向规则演绎系统3.与或图的F规则变换将这类规则应用于与或图进行推演。
假设有一条规则L=W，根据此规则及事实表达式F（L），可以推出表达式F（W）。
F（W）是用W代替F中的所有L而得到的。
当用规则L=W来变换以上述方式描述的F（L）的与或图表示时，就产生一个含有F（W）表示的新图；也就是说，它的以叶节点终止的解图集以F（W）子句形式代表该子句集。
这个子句集包括在F（L）的子句形和L=W的子句形间对L进行所有可能的消解而得到的整集。
该过程以极其有效的方式达到了用其它方法要进行多次消解才能达到的目的。
4.2规则演绎系统,4.2.1正向规则演绎系统4.作为终止条件的目标公式应用F规则的目的在于从某个事实公式和某个规则集出发来证明某个目标公式。
在正向推理系统中，这种目标表达式只限于可证明的表达式，尤其是可证明的文字析取形的目标公式表达式。
用文字集表示此目标公式，并设该集各元都为析取关系。
结论：
当正向演绎系统产生一个含有以目标节点作为终止的解图时，此系统就成功地终止。
4.2规则演绎系统,4.2.2逆向规则演绎系统基于规则的逆向演绎系统，其操作过程与正向演绎系统相反，即为从目标到事实的操作过程，从then到if的推理过程。
逆向推理过程1.目标表达式的与或形式逆向演绎系统能够处理任意形式的目标表达式。
首先，采用与变换事实表达式同样的过程，把目标公式化成与或形。
4.2规则演绎系统,4.2.2逆向规则演绎系统2.与或图的B规则变换B规则是建立在确定的蕴涵式基础上的，正如正向系统的F规则一样。
不过，我们现在把这些B规则限制为WL形式的表达式。
其中，W为任一与或形公式，L为文字，而且蕴涵式中任何变量的量词辖域为整个蕴涵式。
3.作为终止条件的事实节点的一致解图逆向系统成功的终止条件是与或图包含有某个终止在事实节点上的一致解图。
4.2规则演绎系统,4.2.2双向规则演绎系统基于规则的正向演绎系统和逆向演绎系统的特点和局限性正向演绎系统能够处理任意形式的if表达式，但被限制在then表达式为由文字析取组成的一些表达式。
逆向演绎系统能够处理任意形式的then表达式，但被限制在if表达式为文字合取组成的一些表达式。
双向（正向和逆向）组合演绎系统具有正向和逆向两系统的优点，克服各自的缺点。
4.2规则演绎系统,4.2.2双向规则演绎系统双向（正向和逆向）组合演绎系统的构成正向和逆向组合系统是建立在两个系统相结合的基础上的。
此组合系统的总数据库由表示目标和表示事实的两个与或图结构组成，并分别用F规则和B规则来修正。
4.2规则演绎系统,4.2.2双向规则演绎系统终止条件组合演绎系统的主要复杂之处在于其终止条件，终止涉及两个图结构之间的适当交接处。
当用F规则和B规则对图进行扩展之后，匹配就可以出现在任何文字节点上。
在完成两个图间的所有可能匹配之后，目标图中根节点上的表达式是否已经根据事实图中根节点上的表达式和规则得到证明的问题仍然需要判定。
只有当求得这样的一个证明时，证明过程才算成功地终止。
若能够断定在给定方法限度内找不到证明时过程则以失败告终。
4.3产生式系统,在基于规则系统中，每个if可能与某断言（assertion）集中的一个或多个断言匹配，then部分用于规定放入工作内存的新断言。
当then部分用于规定动作时，称这种基于规则的系统为反应式系统（reactionsystem）或产生式系统（productionsystem）。
4.3产生式系统,4.3.1产生式系统的结构产生式系统由3个部分组成，即总数据库（或全局数据库）、产生式规则和控制策略。
控制策略,产生式规则,总数据库,4.3产生式系统,4.3.1产生式系统的结构总数据库有时也被称作上下文，当前数据库或暂时存储器。
总数据库是产生式规则的注意中心。
产生式规则的左边表示在启用这一规则之前总数据库内必须准备好的条件。
例如在上述例子中，在得出该动物是食肉动物的结论之前，必须在总数据库中存有“该动物是哺乳动物”和“该动物吃肉”这两个事实。
执行产生式规则的操作会引起总数据库的变化，这就使其他产生式规则的条件可能被满足。
产生式规则是一个规则库，用于存放与求解问题有关的某个领域知识的规则之集合及其交换规则。
规则库知识的完整性、一致性、准确性、灵活性和知识组织的合理性，将对产生式系统的运行效率和工作性能产生重要影响。
4.3产生式系统,4.3.1产生式系统的结构控制策略为一推理机构，由一组程序组成，用来控制产生式系统的运行，决定问题求解过程的推理线路
升级会员 