人工智能基础04--推理技术

合肥工业大学人工智能与数据挖掘研究室1/101目录第一章绪论第二章知识表示第三章搜索技术第四章推理技术第五章机器学习第六章专家系统第七章自动规划系统第八章自然语言理解第九章智能控制第十章人工智能程序设计合肥工业大学人工智能与数据挖掘研究室2/1014.0推理的基本概念4.0.1推理的定义从初始证据出发，按某种策略不断应用知识库中的已知知识，逐步推出结论的过程称为推理。在人工智能系统中，推理是由程序实现的，称为推理机。已知事实和知识是构成推理的两个基本要素。事实又称为证据，用以指出推理的出发点及推理时应该使用的知识。知识是使推理得以向前推进，并逐步达到最终目标的依据。合肥工业大学人工智能与数据挖掘研究室3/1014.0推理的基本概念4.0.2推理方式及其分类（1）按推出结论的途径来划分，推理可分为：演绎推理（deductiveresoning）：是从全称判断推导出单称判断的过程，即由一般性知识推出适合某一具体情况的结论。一般到个别。归纳推理（inductiveresoning）：是从足够多的事例中归纳出一般性结论的推理过程。个别到一般。默认推理（defaultresoning）：是在知识不完全的情况下假设某些条件已经具备所进行的推理。合肥工业大学人工智能与数据挖掘研究室4/1014.0推理的基本概念4.0.2推理方式及其分类（2）按推理时所用的知识的确定性来划分，推理可分为：确定性推理：是指推理时所用的知识与证据都是确定的，退出的结论也是确定的，其真值或者为真或者为假，没有第三种情况出现。不确定性推理：是指推理时所用的知识与证据不都是确定的，推出的结论也是不确定的。合肥工业大学人工智能与数据挖掘研究室5/1014.0推理的基本概念4.0.2推理方式及其分类（3）按推理过程中推出的结论是否越来越接近最终目标来划分，推理可分为：单调推理：是指在推理过程中随着推理向前推进及新知识的加入，推出的结论越来越接近最终目标。非单调推理：是指在推理过程中由于新知识的加入，不仅没有加强已推出的结论，反而要否定它，使推理退回到前面的某一步，然后重新开始。合肥工业大学人工智能与数据挖掘研究室6/1014.0推理的基本概念4.0.2推理方式及其分类（4）按推理中是否运用与推理有关的启发性知识来划分，推理可分为：启发性推理：是指在推理过程中运用与推理有关的启发性知识。非启发性推理：是指在推理过程中未运用与推理有关的启发性知识。合肥工业大学人工智能与数据挖掘研究室7/1014.0推理的基本概念4.0.3推理的方向（1）正向推理是以事实作为出发点的一种推理。基本思想：从用户提供的初始已知事实出发，在知识库KB中找出当前可适用的知识，构成可适用知识集KS，然后按某种冲突消解策略从KS中选出一条知识进行推理，并将推出的新事实加入到数据库中作为下一步推理的已知事实，此后再在KB中选取可适用的知识进行推理，如此重复这一过程，直到求得了问题的解或者知识库中再无可适用的知识为止。合肥工业大学人工智能与数据挖掘研究室8/1014.0推理的基本概念4.0.3推理的方向（2）逆向推理是以某个假设目标为出发点的一种推理。基本思想：首先选择一个假设目标，然后寻找支持该假设的证据，若需的证据都能找到，则说明原假设是成立的；若无论如何都找不到所需的证据，则说明原假设不成立，为此需要另作新的假设。合肥工业大学人工智能与数据挖掘研究室9/1014.0推理的基本概念4.0.3推理的方向（3）混合推理正向推理具有盲目、效率低等缺点，推理过程中可能会推出许多与问题无关的子目标。逆向推理中，若提出的假设目标不符合实际，也会降低系统效率。可以把正向推理与逆向推理结合起来，使其各自发挥自己的优势，取长补短。这种既有正向推理又有逆向推理称为混合推理。合肥工业大学人工智能与数据挖掘研究室10/1014.0推理的基本概念4.0.3推理的方向（4）双向推理双向推理：是指正向推理与逆向推理同时进行，且在推理过程中的某一步骤上“碰头”的一种推理。基本思想：一方面根据已知事实进行正向推理，但并不推倒最终目标；另一方面从某假设目标出发进行逆向推理，但不推至原始事实，而是让它们在中途相遇，即由正向推理所得到的中间结论恰好是逆向推理此时所需求的证据，这时推理就可以结束，逆向推理时所做的假设就是推理的最终结论。合肥工业大学人工智能与数据挖掘研究室11/1014.0推理的基本概念4.0.4冲突消解策略系统将当前已知事实与KB中知识匹配的三种情况：（1）已知事实恰好只与KB中的一个知识匹配成功。（2）已知事实不能与KB中的任何知识匹配成功。（3）已知事实可与KB中的多个知识匹配成功；或者多个（组）事实都可与KB中的某一个知识匹配成功；或者多个（组）事实都可与KB中的多个知识匹配成功；第3种情况称为发生了冲突。合肥工业大学人工智能与数据挖掘研究室12/1014.0推理的基本概念4.0.4冲突消解策略消解冲突的基本思想：对知识进行排序：（1）按针对性排序：优先选择针对性强的知识（规则），即要求条件多的规则。（2）按已知事实的新鲜性排序：后生成的事实具有较大的新鲜性。（3）按匹配度排序：在不确定推理中，需要计算已知事实与知识的匹配度。（4）按条件个数排序：优先应用条件少的产生式规则。合肥工业大学人工智能与数据挖掘研究室13/1014.1消解原理4.1.1子句集的求取消解原理是针对谓词逻辑知识表示的问题求解方法。消解原理的基础知识：（1）谓词公式、某些推理规则以及置换合一等概念。（2）子句：由文字的析取组成的公式(一个原子公式和原子公式的否定都叫做文字)。（3）消解：当消解可使用时，消解过程被应用于母体子句对，以便产生一个导出子句。例如，如果存在某个公理E1∨E2和另一公理～E2∨E3，那么E1∨E3在逻辑上成立。这就是消解，而称E1∨E3为E1∨E2和～E2∨E3的消解式。合肥工业大学人工智能与数据挖掘研究室14/1014.1消解原理4.1.1子句集的求取步骤(1)消去蕴涵符号只应用∨和～符号，以～A∨B替换A→B。[(A→B)→B]∨C=〉[～(A→B)∨B]∨C=〉[～(～A∨B)∨B]∨C=〉[(A∧～B)∨B]∨C=〉[（A∨B）∧（～B∨B）]∨C=〉[（A∨B）]∨C合肥工业大学人工智能与数据挖掘研究室15/1014.1消解原理4.1.1子句集的求取(2)减少否定符号的辖域每个否定符号～最多只用到一个谓词符号上，并反复应用狄·摩根定律。例如：以～A∨～B代替～(A∧B)以～A∧～B代替～(A∨B)以A代替～(～A)以(彐x)｛～A｝代替～(x)A以(x)｛～A｝代替～(彐x)A合肥工业大学人工智能与数据挖掘研究室16/1014.1消解原理4.1.1子句集的求取(3)对变量标准化在任一量词辖域内，受该量词约束的变量为一哑元(虚构变量)，它可以在该辖域内处处统一地被另一个没有出现过的任意变量所代替，而不改变公式的真值。合适公式中变量的标准化意味着对哑元改名以保证每个量词有其自己唯一的哑元。如，对(x)｛P(x)→(彐x)Q(x)｝标准化可得：(x)｛P(x)→(彐y)Q(y)｝合肥工业大学人工智能与数据挖掘研究室17/1014.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)]合肥工业大学人工智能与数据挖掘研究室18/1014.1消解原理4.1.1子句集的求取从一个公式消去一个存在量词的一般规则是以一个Skolem函数代替每个出现的存在量词的量化变量，而这个Skolem函数的变量就是由那些全称量词所约束的全称量词量化变量，这些全称量词的辖域包括要被消去的存在量词的辖域在内。Skolem函数所使用的函数符号必须是新的，即不允许是公式中已经出现过的函数符号。如果要消去的存在量词不在任何一个全称量词的辖域内，则用不含变量的Skolem函数即常量。例如，(彐x)P(x)化为P(A)，其中常量符号A用来表示人们知道的存在实体。A必须是个新的常量符号，它未曾在公式中其它地方使用过。合肥工业大学人工智能与数据挖掘研究室19/1014.1消解原理4.1.1子句集的求取(5)化为前束形把所有全称量词移到公式的左边，并使每个量词的辖域包括这个量词后面公式的整个部分。所得公式称为前束形。前束形=（前缀）（母式）全称量词串无量词公式(6)把母式化为合取范式任何母式都可写成由一些谓词公式和(或)谓词公式的否定的析取的有限集组成的合取。这种母式叫做合取范式。如：A∨{B∧C}化为{A∨B}∧{B∨C}合肥工业大学人工智能与数据挖掘研究室20/1014.1消解原理4.1.1子句集的求取(7)消去全称量词消去明显出现的全称量词。(8)消去连词符号∧用｛A，B｝代替(A∧B)，以消去明显的符号∧。反复代替的结果，最后得到一个有限集，其中每个公式是文字的析取。任一个只由文字的析取构成的合适公式叫做一个子句。(9)更换变量名称可以更换变量符号的名称，使一个变量符号不出现在一个以上的子句中。合肥工业大学人工智能与数据挖掘研究室21/1014.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)]}}合肥工业大学人工智能与数据挖掘研究室22/1014.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))]}合肥工业大学人工智能与数据挖掘研究室23/1014.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))合肥工业大学人工智能与数据挖掘研究室24/1014.1消解原理4.1.2消解推理规则令L1为任一原子公式，L2为另一原子公式；L1和L2具有相同的谓词符号，但一般具有不同的变量。已知两子句L1∨α和～L2∨β,如果L1和L2具有最一般合一者σ，那么通过消解可以从这两个父辈子句推导出一个新子句(α∨β)σ。这个新子句叫做消解式。它是由取这两个子句的析取，然后消去互补对而得到的。合肥工业大学人工智能与数据挖掘研究室25/1014.1消解原理4.1.2消解推理规则常用消解规则(1)假言推理父辈子句P～P∨Q(即P→Q)消解式Q合