人工智能5第五章确定性推理

12019/8/1第四章确定性推理22019/8/14.1确定性推理概述第四章确定性推理4.1概述32019/8/1推理推理是指按照某种策略从巳知事实出发去推出结论的过程智能系统的推理过程实际上就是一种思维过程。智能系统的推理过程是通过推理机来完成的。推理机就是智能系统中用来实现推理的程序。按照推理过程所用知识的确定性，推理可分为确定性推理和不确定性推理。第四章确定性推理4.1概述42019/8/1事实事实是推理过程中按知识表示方式表示的已知的知识推理所用的事实可分为两种情况:与求解问题有关的初始证据．推理过程中所得到的中间结论。第四章确定性推理4.1概述52019/8/1推理的基本问题智能系统的推理包括两个基本问题：一个是推理的方法一个是推理的控制策略推理方法主要解决：在推理过程中前提与结论之间的逻辑关系在非精确性推理中不确定性的传递问题第四章确定性推理4.1概述62019/8/1推理方法的分类推理可以有多种不同的分类方法按照推理的逻辑基础分类：演绎推理归纳推理默认推理按照所用知识的确定性分类：确定性推理不确定性推理按照推理过程的单调性分类（推理过程所得到的结论是否越来越接近目标）：单调推理非单调推理第四章确定性推理4.1概述72019/8/1演绎推理从已知的一般性知识出发，去推出蕴含在这些已知知识中的适合于某种个别情况的结论。它是一种由一般到个别的推理方法。核心是三段论第四章确定性推理4.1概述82019/8/1归纳推理从一类事物的大量特殊事例出发，去推出该类事物的一般性结论。它是一种由个别到一般的推理方法。基本思想：先从已知事实中猜测出一个结论，然后对这个结论的正确性加以证明确认数学归纳法就是归纳推理的一种典型例子。按照所选事例的广泛性，归纳推理可分为：完全归纳推理和不完全归纳推理；按照推理所使用的方法可分为：枚举归纳推理、类比归纳推理、统计归纳推理和差异归纳推理等。第四章确定性推理4.1概述92019/8/1默认推理在知识不完全的倩况下，假设某些条件已经具备所进行的推理，因此也称为缺省推理。在推理过程中．如果发现原先的假设不正确，就撤销原来的假设以及由此假设所推出的所有结论。重新按新情况进行推理。解决了在一个不完备的知识集中进行推理的问题。第四章确定性推理4.1概述102019/8/1推理过程的单调性按照推理过程所得到的结论是否越来越接近日标，推理可分为单调推理与非单调推理。单调推理：在推理过程中，每当使用新的知识后，所得到的结论会越来越接近于目标不会出现反复情况，即不会由于新知识的加入否定了前面推出的结论。非单调推理：在推理过程中，当某些新知识加入后，会否定原来推出的结论。非单调推理往往是在知识不完全的情况下发生的。第四章确定性推理4.1概述112019/8/1推理控制策略推理的控制策略是在推理过程中采用的、解决如何使用领域知识使推理过程尽快达到目标的策略。第四章确定性推理4.1概述122019/8/1推理控制策略分类智能系统的推理过程一般表现为一种搜索过程，因此，推理的控制策略又可分为推理策略和搜索策略。推理策略主要解决推理方向、冲突消解等问题。搜索策略主要解决推理线路、推理效果、推理效率等问题。第四章确定性推理4.1概述132019/8/1推理方向推理方向确定推理过程是从初始证据开始到目标，还是从目标开始到初始证据。按照对推理方向的控制，推理可分为正向推理、逆向推理、混合推理及双向推理四种情况。第四章确定性推理4.1概述142019/8/1正向推理正向推理是一种从已知事实出发、正向使用推理规则的推理方式，亦称为数据驱动推理。基本思想是：用户需要事先提供一组初始证据，并将其放入综合数据库。推理机根据综合数据库中的已有事实，到知识库中寻找当前可用知识，形成一个当前可用知识集。按照冲突消解策略，从该知识集中选择一条知识进行推理，并将新推出的事实加入综合数据库，作为后面继续推理时可用的巳知事实，重复这一过程，直到求出所需要的解或者知识库中再无可用知识为止第四章确定性推理4.1概述152019/8/1逆向推理逆向推理是一种从以某个假设目标作为出发点的推理方法，亦称为目标驱动推理基本思想是：将要求证的目标(称为假设)构成一个假设集。取一个假设对其进行验证，若在综合数据库里，则假设成立若能被用户认定为事实，则假设成立，并放入综合数据库若可由知识库中的一个或多个知识导出，则这些知识构成可用知识集。按照冲突消解策略，从该知识集中选择一条知识，将其前提中的所有子条件作为新的假设加入假设集。重复这一过程，直到假设集为空或假设集非空但可用知识集空为止第四章确定性推理4.1概述162019/8/1混合推理正向推理和逆向推理都有各自的优缺点。当问题较复杂时，单独使用其中哪一种，都会影响到推理效率。为了取长补短．可将它们结合起来使用。这种把正向推理和逆向推理结合起来所进行的推理称为混合推理。第四章确定性推理4.1概述172019/8/1混合推理的实现方法混合推理可有多种具体的实现方法先正向推理，后逆向推理的方法先逆向推理，后正向推理的方法采用随机选择正向和逆向推理的方法（双向混合推理）第四章确定性推理4.1概述182019/8/1混合推理的适用场合已知事实不够充分。由正向推理推出的结论可信度不高希望得出更多的结论希望从正反两个方向同时进行推理第四章确定性推理4.1概述192019/8/1冲突消解策略冲突消解策略是指当推理过程有多条知识可用时，如何从这多条可用知识中选出一条最佳知识用于推理的策略。冲突消解的基本思想是对可用知识进行排序。常用的冲突消解策略有：特殊知识优先新鲜知识优先差异性大的知识优先领域特点知识优先上下文关系知识优先前提条件少的知识优先第四章确定性推理4.1概述202019/8/1自然演绎推理从一组己知为真的事实出发，直接运用经典逻辑中的推理规则推出结论的过程称为自然演绎推理。在自然演绎推理中，需要避免两类错误：肯定后件的错误和否定前件的错误。优点：定理证明过程自然，易于理解，有丰富的推理规则主要缺点：容易产生知识爆炸，推理过程中得到的中间结论一般按指数规律递增，对于复杂问题的推理不利，甚至难以实现。因此，提出了归结演绎推理第四章确定性推理4.2自然演绎推理212019/8/1归结演绎推理归结演绎推理是一种基于归结原理的推理方法。归结原理亦称消解原理，是鲁宾逊1965年提出的归结演绎推理实际上是一种“反正法”，基本思想：推理就是要对前提P和结论Q，证明PQ永真。这就要证明PQ在任何一个非空的个体域上都是永真的。这将是非常困难的，甚至是不可实现的。而用反证法，只要能够证明～(PQ)是不可满足的。第四章确定性推理4.3归结演绎推理222019/8/1子句和子句集原子谓词公式及其否定都称为文字文字的析取构成的公式称为子句不包含任何文字的子句称为空了句空子句不包含任何文字，因此，不能被任何指派所满足所以空子句是不可满足的子句集中的子句之间是合取关系含空子句的子句集也就一定是不可满足的。第四章确定性推理4.3归结演绎推理232019/8/1谓词公式转化为子句集消去蕴涵符号：～P∨Q取代P→Q减少否定符号的管辖域对变量标准化消去存在量词化为前束形化为合取范式：如：PΛ(P∨Q）Λ(～P∨Q）消去全称量词获得子句集更换变量名第四章确定性推理4.3归结演绎推理242019/8/1化子句集例例：(z)(x)(y){[(P(x)Q(x))R(y)]U(z)}1,消蕴涵符理论根据：ab=~ab(z)(x)(y){[~(P(x)Q(x))R(y)]U(z)}2,移动否定符理论根据：~(ab)=~a~b~(ab)=~a~b~(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归结演绎推理252019/8/1化子句集例（续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归结演绎推理262019/8/1化子句集例（续2）6,化为合取范式即(ab)(cd)(ef)的形式(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归结演绎推理272019/8/1化子句集例（续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归结演绎推理282019/8/1归结(消解)原理基本思想首先把欲证明问题的结论否定，并加入子句集，得到一个扩充的子句集S’。检验子句集S’是否含有空子句若不含空子句，则继续使用归结法，在子句集中选择合适的子句进行归结直至导出空子句或不能继续归结为止。第四章确定性推理4.3归结演绎推理292019/8/1归结原理分类鲁宾逊归结原理可分为:命题逻辑归结原理谓词逻辑归结原理第四章确定性推理4.3归结演绎推理302019/8/1归结式归结推理的核心是求两个子句的归结式若P是原子谓词公式，则称P与~P为互补文字设C1和C2是子句集中的任意两个子句如果C1中的文字L1与C2中的文字L2互补那么可从C1和C2中分别消去L1和L2并将C1和C2中余下的部分按析取关系构成一个新的子句C12，则称这一过程为归结，称C12为C1和C2的归结式，C1和C2为C12的亲本子句。第四章确定性推理4.3归结演绎推理312019/8/1消解过程举例E2∨E1（前提）～E2∨E3（前提）（消解式）E1∨E3（结论）第四章确定性推理4.2归结演绎推理322019/8/1命题逻辑的消解推理举例假言推理：P～P∨Q(P→Q）消解式：Q合并：P∨Q～P∨Q消解式：Q∨Q=Q重言式：P∨Q～P∨～Q消解式：P∨～P或Q∨～Q空子句：P～P消解式：NIL三段论：～P∨Q(P→Q）～Q∨R(Q→R）消解式：～P∨R(P→Q）第四章确定性推理4.2归结演绎推理332019/8/1谓词逻辑的消解推理举例B(x)～B(x)∨C(x）消解式：C(x)P(x)∨Q(x）～Q[f(y)]消解式：P[f(y)]置换：f(y)/xP[x,f(y)]∨Q(x)∨R[f(a),y]～P[f(f(a)),z]∨R(z,w）消解式：Q[f(f(a))]∨R[f(a),y]∨R[f(y),w]置换：f(f(a))/x,f(y)/z第四章确定性推理4.2归结演绎推理342019/8/1消解反演消解反演是利用消解原理进行推理的过程。消解反演的推理过程:给定公式集S和目标公式L证明公式L的步骤如下：否定L，得～L把～L添加到S中去把新产生的集合{～L,S}化成子句集应用消