人工智能推理技术

Artificial Intelligence,第,7,章、基本的推理技术,推理技术概述,基于规则的演绎推理,正向演绎推理,逆向演绎推理,双向演绎推理,不确定性推理,概率推理,人工智能是用计算机来模拟人的智能,，就是,用能在计算机上实现的技术和方法来模拟人的思维规律和过程,。,1),在确定知识表达方法后，就可以把知识表示出来并存储到计算机中。,2),然后,利用,知识进行推理,以求得问题的解,.,利用知识进行推理是知识利用的基础。各种人工智能应用领域如专家系统、智能机器人、模式识别、自然语言理解等都是利用知识进行广义问题求解的智能系统,.,7.1,推理技术概述,-1.,推理的概念与类型,推理是人类求解问题的主要思维方法,.,所谓推理就是按照某种策略从已有事实和知识推出结论的过程。推理是由程序实现的，称为推理机。,人类的智能活动有多种思维方式，人工智能作为对人类智能的模拟，相应地也有多种推理方式。,1.,演绎推理、归纳推理、默认推理,(1).,演绎推理：演绎推理是,从全称判断推出特称判断或单称判断的过程，即从一般到个别的推理,。最常用的形式是三段论法。例如：,1,）所有的推理系统都是智能系统；,2,）专家系统是推理系统；,3,）所以，专家系统是智能系统。,(2).,归纳推理,:,是从足够多的事例中归纳出一般性结论的推理过程，是一种从个别到一般的推理过程,。,(3).,默认推理：默认推理又称,缺省推理,，它是在知识不完全的情况下,假设某些条件已经具备所进行的推理,。,2,、确定性推理、不确定性推理,如果按推理时所用的知识的确定性来分，推理可分为确定性推理与不确定性推理。,（,1,）确定性推理（精确推理）。如果,在推理中所用的知识都是精确的,，即可以把知识表示成必然的因果关系，然后进行逻辑推理，推理的,结论或者为真，或者为假，这种推理就称为确定性推理,。（如归结反演、基于规则的演绎系统等）,（,2,）不确定性推理,(,不精确推理,),。在,人类知识,中，有相当,一部分,属于人们的主观判断，,是不精确的和含糊的,。由这些知识归纳出来的,推理规则往往是不确定的,。基于这种不确定的推理规则进行推理，形成的,结论也是不确定的,，这种推理称为不确定推理。,(,在专家系统中主要使用的方法,),。,3,、单调推理、非单调推理,如果按推理过程中推出的结论是否单调增加，或者说推出的结论是否越来越接近最终目标来划分，推理又可分为单调推理与非单调推理。,（,1,）单调推理。是指在推理过程中随着推理的向前推进及新知识的加入，推出的,结论呈单调增加的趋势,，并且越来越接近最终目标。,(,演绎推理是单调推理。,),（,2,）非单调推理。是指在推理过程中随着推理的向前推进及新知识的加入，不仅,没有加强已推出的结论,，,反而要否定它,，使得推理退回到前面的某一步，重新开始。,(,一般是在知识不完全的情况下进行的,),4,、启发式推理、非启发式推理,如果按推理中是否运用与问题有关的启发性知识，推理可分为启发式推理和非启发式推理。,（,1,）启发式推理：如果在推理过程中，,运用与问题有关的启发性知识,，如解决问题的策略、技巧及经验等，以加快推理过程，提高搜索效率，这种推理过程称为启发式推理。如,A,、,A*,等算法。,（,2,）非启发式推理。如果在推理过程中，,不运用启发性知识,，只按照一般的控制逻辑进行推理，这种推理过程称为非启发式推理。,(,推理效率较低，容易出现“组合爆炸”问题。,),-,推理的控制策略,主要是指,推理方向的选择,、,推理时所用的搜索策略,及,冲突解决策略,等。一般推理的控制策略与知识表达方法有关,(,产生式系统,).,1,、推理方向：用于,确定推理的驱动方式,。分为,正向推理,(,由已知事实出发,),、反向推理,(,以某个假设目标作为出发点,),和正反向混合推理,(,正向推理和反向推理相结合,),.,系统组成,:,知识库（,KB,）,+,初始事实和中间结果的数据库（,DB,）,+,推理机,2,、搜索策略,:,推理时要反复用到知识库中的规则，而知识库中的规则又很多，这样就存在着如何,在知识库中寻找可用规则的问题,(,代价小,解好,).,可以采用,各种搜索策略有效地控制规则的选取,.,3,、冲突解决策略,在推理过程中，系统要,不断地用数据库中的事实与知识库中的规则进行匹配,，当有一个以上规则的条件部分和当前数据库相匹配时，就需要有一种策略来决定首先使用哪一条规则，这就是冲突解决策略。,冲突解决策略实际上就是确定规则的启用顺序,。,（,1,）专一性排序,(,条件部分更具体的规则,),（,2,）规则排序,(,规则编排顺序,),（,3,）数据排序,(,所有条件按优先级次序编排起来,),（,4,）就近排序,(,最近使用的规则优先,),（,5,）上下文限制,(,在某种上下文条件下,),（,6,）按匹配度排序,(,计算这两个模式的相似程度,),（,7,）按条件个数排序,(,条件少的优先,),7,2,基于规则的演绎推理,许多,AI,系统中所用到的知识一般是由蕴含式直接表示的，但在归结反演中，必须首先将它们转化为子句的形式，所以这种推理是比较低效的。,基于规则的演绎推理则是直接的推理方法,。它,把有关问题的知识和信息划分为规则与事实两种类型,。,规则由包含蕴含形式的表达式,表示，,事实由无蕴含形式的表达式,表示，并,画出相应的与或图，然后通过规则进行演绎推理,。,可分为正向、反向和正反向演绎推理。在,正向推理,中，作为,F,规则用,的蕴含式对事实的总数据库进行操作运算，直至得到该目标公式的一个终止条件为止；在,反向推理,中，作为,B,规则,用的蕴含式对目标的总数据库进行操作运算，直至得到包含这些事实的一个终止条件为止；在,双向推理,中，分别从,两个方向应用不同的规则,（,F,和,B,）进行操作运算。,7,2,1,正向演绎推理,正向演绎推理属于正向推理，它是从已知事实出发，反复尝试所有可利用的规则（,F,规则）进行演绎推理，直到得到某个目标公式的一个终止条件为止。,1,、事实表达式及其与或图表示,正向演绎要求事实用不包含蕴含符号“,”的与或形表示。,把一个表达式转化为标准的与或形的步骤如下：,（,1,）利用等价式,P,Q,与,P,Q,消去蕴含符“,”。,（,2,）把否定符号“,”移到每个谓词符号的前面。,（,3,）变量标准化，即重新命名变量，使不同量词约束的变量有不同的名字。,（,4,）引入,Skolem,函数消去存在量词。,（,5,）将公式化为前束形。,（,6,）略去全称量词（默认变量是全称量词量化的）。,（,7,）重新命名变量，使同一变量不出现在不同的主要合取式中。,例如：有如下的表达式,（,x,）（,y,）,Q,（,y,，,x,）,（,R,（,y,）,P,（,y,）,S,（,x,，,y,）,可将其转化为下面标准的与或形：,Q,（,z,，,A,）,R,（,y,）,P,（,y,）,S,（,A,，,y,）,于是,它的标准与或形可用一棵与或树表示出来。,在与或图中，节点表示事实表达式及其子表达式。根节点表示整个表达式，叶节点表示其中的单文字,.,规定,:,对于一个表示,析取表达式（,E,1,E,2,E,n,）,的节点，用一个,n,连接符,（含半圆的弧）与连接它的,n,个子表达式节点相连。对于一个表示,合取表达式（,E,1,E,2,E,n,）,的节点，用,n,个,1,连接符,与连接它的,n,个子表达式节点相连。,重要性质,:,就是由变换表达式得到的,一组子句，可以从与或图中读出,，,每个子句相当于与或图的一个解图,，每个子句是由叶节点组合成的公式。上例的,3,个子句是：,Q,（,z,，,A,）；,S,（,A,，,y,）,R,（,y,）；,S,（,A,，,y,）,P,（,y,）,这三个子句正是原表达式化成的子句集。因此，与或树可以看成是一组子句的一个简洁的表达式。,2,、,F,规则的表示形式,基于规则的正向推理中，要求,F,规则具有以下形式：,L,W,。,具体要求如下：,L,是单文字,，,W,是任意的与或形表达式。,L,和,W,中的,所有变量都是全称量词量化的,，默认的全称量词作用于整个蕴含式。,各条规则的变量各不相同,，而且规则中的变量与事实表达式中的变量也不相同。,将,F,规则的左部限制为,单文字,，是因为与或图的叶节点都是单文字，这样就可用,F,规则的左部,与叶节点进行匹配,，大大简化了规则的应用过程。,如果所给知识的表示形式不是所要求的形式，则可用如下步骤将其变换成标准形式：,（,1,）暂时消去蕴含符号“,”。例如公式,（,x,）,（,y,）（,z,）,P,（,x,，,y,，,z,）,（,u,）,Q,（,x,，,u,）,消去蕴含符号“,”变为：,（,x,）,（,y,）（,z,）,P,（,x,，,y,，,z,）,（,u,）,Q,（,x,，,u,）,（,2,）,把否定号“,”移到每个谓词的前面,可变为,（,x,）,（,y,）（,z,）,P,（,x,，,y,，,z,）,（,u,）,Q,（,x,，,u,）,（,3,）,引入,skolem,函数消去存在量词。消去存在量词后，为,（,x,）,（,y,）,P,（,x,，,y,，,f,（,x,，,y,）,（,u,）,Q,（,x,，,u,）,（,4,）,将公式化为前束式，并略去全称量词,可变为,P,（,x,，,y,，,f,（,x,，,y,）,Q,（,x,，,u,）,（,5,）,恢复为蕴含式。利用等价关系,P,Q,与,P,Q,将上式变为,P,（,x,，,y,，,f,（,x,，,y,）,Q,（,x,，,u,）,3,、目标公式的表示形式,要求目标公式用文字的析取式,(,子句,),表示，否则就要化为子句形式。,4,、推理过程,应用,F,规则作用于表示事实的与或图，改变与或图的结构，从而产生新事实，直至推出了目标公式。过程为：,首先,用与或图把已知事实表示出来,。,用,F,规则的左部和与或图的叶节点进行匹配，并将匹配成功的,F,规则结论加入到与或图中，即,利用,F,规则转换与或图。,重复第（,2,）步，,直到产生一个含有以目标节点作为终止节点的解图为止,，,当一个目标文字和与或图中的一个文字匹配时，可以将表示该目标文字的节点,(,目标节点,),通过匹配连接到与或图中相应的文字节点上,。当演绎产生的与或图包括一个目标节点上结束的解图时，推理便成功结束。,1),、命题逻辑的情况,应用规则的匹配过程比较简单。设已知事实的与或形表达式为：（,P,Q,）,R,）,（,S,（,T,U,）,规则为,S,（,X,Y,）,Z,把,已知事实用与或图表示,，图中有一个叶节点是文字,S,，,它正好,与规则的前项,的文字,S,完全,匹配,，由此可直接用这条规则对与或图进行变换，,即把规则后项的与或形公式用与或图表示后添加到已知事实的与或图上,，,并用一个匹配弧连接起来,，规则匹配后演绎的结果如下图所示。图中匹配弧后面是规则部分。,例：事实表达式：,A,B,；,规则集合,：,A,C,D,，,B,E,G,；,目标公式,：,C,G,应用完这两条规则后，得到的与或图如图所示，其中有一个解图满足目标公式（,C,G,）,所建立的结束条件。,2),、谓词逻辑的情况,需要讨论对含有变量的目标公式的处理,(,匹配问题,),。,对具有量词量化变量的目标公式来说,，化简时要使用,Skolem,化过程的对偶形式,。即目标中,属于存在量词辖域内的全称量化变量要用存在量化变量的,Skolem,函数来替代,，经过,Skolem,化的公式,只剩下存在量词,，然后对析取元作变量改名，最后再把存在量词省略掉。,例如，设目标公式为（,y,）（,x,）（,P,（,x,，,y,）,Q,（,x,，,y,）,用函数消去全称量词后有（,y,）（,P,（,f,（,y,），,y,）,Q,（,f,（,y,），,y,）,；然后,进行变量改名，使每个析取元具有不同的变量符号,，于是有,（,y,）（,P,（,f,（,y,），,y,）,（,y,1,）,Q,（,f,（,y,1,），,y,1,）,最后省去存在量词（,