人工智能392

第三章确定性推理3.1基本概念3.3自然演绎推理3.4归结演绎推理3.5基于规则的演绎推理（与/或形演绎推理）3.1基本概念为使计算机具有智能，仅仅使它拥有知识还不够，更重要地，还必须使它具有思维能力，即能运用知识进行推理、求解问题的能力。知识表示（知识库）→求解过程（推理）经典推理是根据经典逻辑（命题逻辑和一阶谓词逻辑）的逻辑规则进行的一种推理，又称机械-自动定理证明。主要推理方法有：自然演绎推理、归结演绎推理、基于规则的演绎推理（与/或形演绎推理）。基本概念推理推理是按某种策略由已知判断推出另一种判断的过程。在AI系统中，推理是由程序来实现的，称为推理机。不同的控制策略推理方式及分类：默认推理归纳推理演绎推理从新判断推出的途径)1(演绎推理由一般（全称判断）到个别（特称判断）的推理方法。核心是三段论，通常由一个大前提、一个小前提和一个结论三部分组成的。例：阿凡提的故事---两头驴的故事①我肩上驮的是两头驴的东西（大前提）②国王和大臣的衣衫是我肩上驮的（小前提）③国王和大臣的衣衫是两头驴的东西（结论）归纳推理从个别到一般归纳结论不具备逻辑必然性莫里斯·科恩逻辑学著作包括两部分，第一部分是演绎，其功能是解释谬误；第二部分是归纳，其功能是生成谬误我们获得关于这个实在世界的一般性事实的唯一方法！演绎推理所得出的结论蕴含在一般性知识的前提中，演绎推理只不过是将已有事实揭示出来，因此它不能增殖新知识。在归纳推理中，所推出的结论是没有包含在前提内容中的。这种由个别事物或现象推出一般性知识的过程，是增殖新知识的过程。默认推理默认推理是在知识不完全的情况下假设某些条件已经具备所进行的推理，也称为缺省推理。在推理过程中，如果发现原先的假设不正确，就撤消原来的假设以及由此假设所推出的所有结论，重新按新情况进行推理。由于默认推理允许在推理过程中假设某些条件是成立的，因此解决了在一个不完备的知识集中进行推理的问题。封闭世界假设：如果没有足够的证据证明某命题不成立，就假定该命题成立不确定性推理确定性推理从知识的确定性)2(非单调性推理单调性推理从结论的单调性)3(非启发式推理启发式推理从启发性知识是否运用)4(直觉推理统计推理基于知识的推理从方法论的角度)5(推理的控制策略推理过程涉及到求解方法和求解策略。求解方法包括匹配方法、不确定性的传递方法求解策略包括推理方向、求解策略、限制策略等。指推理是求一个解、所有解，还是最优解。为防止无穷的推理过程，以及由此带来的时间和空间复杂性，限制策略是对推理的深度、宽度、时间、空间等进行限制。推理方向推理方向分为正向推理、逆向推理、混合推理、双向推理四种。无论哪一种推理，系统都具有知识库、数据库和推理机。正向推理需要解决的问题：1、确定匹配的方法2、确定搜索策略3、消解冲突正向推理的缺点：盲目，效率低逆向推理的优点：1、目标性强2、有利于向用户提供解释逆向推理的缺点：初始目标的选择有盲目性开始提出假设该假设在数据库中？该假设是证据？在知识库中找出所有能导出该假设的知识，形成适用知识集KS从KS中选出一条知识，并将该知识的每一个运用条件都作为新的假设目标退出有此事实？询问用户NNNYYY逆向推理该假设成立该假设成立，并将此事实存入数据库还有假设？NYY开始把初始已知事实送入DBDB中包含问题的解KB中有可适用的知识把KB中所有的适用知识都选出送入KSKS空？按冲突消解策略从KS中选出一条知识进行推理推出的是新知识？将该新知识加入DB成功，退出失败，退出用户补充新知识？把用户提供的新事实加入DBNNNYYYY正向推理NYN逆向推理-例有关知识规则1：IF你丢了自行车钥匙，并且车胎没气THEN自行车不能骑规则2：IF自行车不能骑，并且你只有走路去THEN你听课会迟到事实1：你丢了自行车钥匙事实2：车胎没气问题“你听课会迟到？”逆向推理-例1.首先查找知识库，知该假设不是已有事实，但可由规则2导出，于是将规则2放入可用知识集，并将其两个前提条件“自行车不能骑”和“你只有走路去”都作为新的假设放入假设集。2.从假设集中取出假设“自行车不能骑”，它不是已有事实，但可由规则1导出，于是规则1被放入可用知识集，并将其两个前提条件“你丢了自行车钥匙”和“车胎没气”也作为新的假设放入假设集。3.从假设集中取出假设“你只有走路去”，此假设既不是已有事实，也不能被任何一条规则导出，询问用户“你只有走路去吗？”，若用户回答“是”，则该假设成立，并被放入已有事实集。4.假设集中还有两个假设“你丢了自行车钥匙”和“车胎没气”，它们都是已有事实，均为真。继续推理，假设集为空，推理过程结束，“你听课会迟到”得证。混合推理是把正向推理和逆向推理结合起来，吸取两种推理的优点。它通常适用以下3种情况：（1）已知事实不充分（2）由正向推理推出的可信度不高（3）希望得到更多的结论混合推理有两种方式：先正后逆和先逆后正双向推理是指正向推理和逆向推理同时进行，在推理过程的某步碰头。基本思想双向推理的难点是碰头的判定。开始进行正向推理需要逆向推理？以正向推理所得的结果作为假设进行逆向推理还需要正向推理？输出结果开始YYNN先正后逆开始进行逆向推理需要正向推理？进行正向推理还需要逆向推理？输出结果开始YYNN先逆后正模式匹配模式匹配是指对两个知识模式（如两个谓词公式、框架或语义片段等）的比较与藕合，即检查这两个知识模式是否完全一致或近似一致。按匹配的近似程度划分，可分为确定性匹配和不确定性匹配。确定性匹配是指两个知识模式完全一致，或经过变量代换后变得完全一致。例如：)(),(:)(),(:21ymanandyxfatherPLixiaosimanandLixiaosiLisifatherP不确定性匹配是指两个知识模式不完全一致，但总体上它们的相似度在一定的限度内。定义3.1置换（代换）代换是形如的有限集合。其中是项是互不相同的变元；表示用代换，不允许与相同，也不允许变元循环地出现在另一个中。nnxtxtxt/,/,/2211nttt21,nxxx21,iixt/itixitjtixix根据定义}/,/)(,/{zwybfxa}/)(,/)({yxfxyg}/)(,/)({yxfxag是代换不是代换是代换}/))((,/)({yagfxag设有代换θ＝{a/x,f(b)/y,u/z}则对公式E＝P(x,y,z)有Eθ＝P(a,f(b),u)对公式E运用代换s，记作Es。Es称作公式E在代换s下的例（例示），它是E的逻辑结论。设是两个代换，则此两个代换的复合也是一个代换，它是从删除以下两种元素后剩下的元素所构成的集合，记作nnnnyuyuyuxtxtxt//,/,/,/,/22112211niiiiiixxxyyuxtxti,,//21当当nnnnyuyuyuxtxtxt//,//,/,/22112211定义3.2代换的复合例如：则zyybxayzxyf/,/,//,/)(zyybxbf/,/,/)(解释：zyybxayzxyf/,/,/,/,/)(zyybxaybxbf/,/,/,/,/)(}/,/,/)({}/,/,/)({/,/,//,/,//,/)(/,/)(zbybxbfzyybxbfzbybxazyybxayzxzfyzxyf就是对一个公式先运用θ代换，然后再运用λ代换.！注意：即：)()(PP大家验证一下！定义3.3公式集的合一设有公式集，若存在一个代换使得则称是公式集的一个合一，且称是可合一的。NFFFF21,NFFF21,NFFF21F一个公式集的合一一般来说不是唯一的例如公式集有合一)),(,(),),(,(bbfzPbyfxPFybxz/,/1ybzx/,/2zaybxa/,/,/3定义3.4最一般合一设是公式集的一个合一，如果对任一个合一都存在一个代换，使得则称是公式集的一个最一般合一。FF如前面提到的公式集是最一般合一，而则不是最一般合一。按照最一般合一的定义，有：)),(,(),),(,(bbfzPbyfxPFybxz/,/1zaybxa/,/,/3}/{13za)),(,(,)),(,(31bbfaPFbbfzPF因此，对于一个公式集来说，如果存在多个合一，则其中代换数最少、限制最少、产生的例最具一般性的代换称为最一般合一。如：ybzx/,/2一般来说，最一般合一也不是唯一的，同样是该公式集的一个最一般合一。求最一般合一差异集：)(,)(,21bhzDafyD))(),(,(:),,(:21bhafxPFzyxPF求最一般合一算法：（1）令。这里，是欲求最一般合一的公式集，是空代换，它表示不做代换。（2）若只含一个表达式，则算法停止，就是最一般合一。（3）找出的差异集。（4）若中存在元素和，其中是变元，是项，且不在中出现，则置：然后转向（2）。（5）算法终止，的最一般合一不存在。kkFFk,,0kFFkkFkDkDkxktkxktkt1//11kkxtFFxtkkkkkkkkkxF举例：求的最一般合一。))(),(,())),((,,(ufzfzPygfxaPF11)(),(,())),((,,(//,)1(0101000kkufafaPygfxaPFzazazaDFFk令21)(),(,())),((),(,(/)(,//)()(,)2(2121kkufafaPygfafaPFxafzaxafafxD31)))((),(,())((),(,())),((),(,(/)(,/)(,//)(),()3(3232kkygfafaPygfafaPygfafaPFuygxafzauyguygD消解冲突策略在推理过程中，系统要不断地用当前已知事实与知识库中的知识进行匹配，此时可能发生以下三种情况：（1）已知事实不能与知识库中的任何知识匹配（2）已知事实恰好与知识库中的一条知识匹配（3）已知事实可与知识库中的多条知识匹配，或者多组已知事实可与知识库中的某一条知识匹配，或者多组已知事实可与知识库中的多条知识匹配。处于第三种情况时，就发生冲突。此时需要按一定的消解策略解决冲突。冲突：多个知识都匹配成功。冲突消解的基本思想都是对知识进行排序。对于产生式系统，若出现以下情况就认为发生冲突：（1）对正向推理而言，如果有多条产生式规则的前件都和已知事实匹配，或者有多组已知事实都与同一条产生式规则的前件匹配；或者以上两种情况同时出现。（2）对逆向推理而言，如果有多条产生式规则的后件都和同一假设匹配，或者有多条产生式规则的后件可与多个假设匹配。常用的消解冲突策略：1、按针对性排序设有如下两条产生式规则：22121211::HthenBandandBandBifrHthenAandandAandAifrnn如果存在最一般合一，使得r1中的每个Ai都可以变成相应的Bi，如Ai=P(x,y)，Bi=P(a,z)则称r2比r1有更大的针对性，r1比r2有更大的通用性。该策略选用针对性较强的产生式规则。2、按已知事实的新鲜性排序把数据库中后生成的事实称为新鲜的事实，该策略要求具有最大新鲜性的事实总是排在前面。设规则r1可与事实组A匹配成功，规则r2可与事实组B匹配成功，则A和B哪一组中的事实更新鲜，与它匹配的规则就先被利用。如何衡量A和B哪一组中的事实更新鲜呢？3、按匹配度排序4、根据领域问题的特点排序先验知识、启发式知识5、按上下文限制排序把规则按照下上文分组，并只能选取组中的规则。6、按冗余限制排序冗余知识少