第四章知识推理技术p

第四章知识推理技术本章主要在知识表达的基础上，讨论“知识的运用”即知识推理的概念和方法。第一节知识推理的概念和类型一．知识推理的基本概念所谓“知识推理”（KnowledgeInference）是指在计算机或智能机器中，在知识表达的基础上，即利用形式化的知识模式——表达与问题有关知识的符号体系，进行及其思维、求解问题、实现知识推理的智能操作过程。一句话，知识推理就是运用知识求解问题。知识推理的过程就是问题求解的过程，知识推理技术就是使问题从初始状态转移到目标状态的方法和途径。研究人工智能的知识推理技术，目的是寻求问题、实现状态转移的智能操作序列，以便从初始状态，沿着最优或最经济的途径，有效地转移到所要求的目标状态，实现问题求解过程的智能机械化或计算机化。例如：利用计算机制定机器人的行动规划，安排机器人从出发地点到目的地点所需的操作序列和行动路线。又如，利用计算机证明数学定理，给出从已知条件开始到定理证明完毕所需的算子序列和演算步骤等等都是知识推理技术的运用。二．知识推理技术的类型1.根据知识表达法分类知识推理是以知识表达技术作为前提条件的，它们之间有着密切的关系，由知识表达的特点，知识推理技术可概括为两种类型：（1）“图搜索”方法在人工智能的知识表达技术中，许多基本的、常用的表达方式都具有图的形式，或者可以变换为相应的（同种或同态变换）图的形式，并且，往往可用树图表达。例如：状态空间态、与/或树图、语义网络图以及由生产是系统或框架表达方式所变换的树图或网络图。针对图的知识表达，问题求解的知识推理过程，就是从图中相当于初始状态的出发结点到相当于目标状态的终结点的路线搜索过程。即搜索从初始状态有效地转移到目标状态，所经历的最优向或最经济的路线，相应的知识推理方法即“图搜索”方法。广度优先搜索法基本的图搜索法深度优先搜索法（2）“逻辑论证”方法当知识采用谓词逻辑或其他方法的形式逻辑表达时，知识推理的便成为逻辑论证。在此情况下，求解两个问题相应于证明一个定理或几个定理，问题求解的知识推理过程相应于用数理逻辑方法进行定理证明的过程。例如：在自动问答系统中，如果用一组谓词逻辑表达式A描述提问的内容，包括有关的事实、情况和条件，而用另一组谓词逻辑表达式B描述问题的答案或结论，那么，只要通过逻辑演算的方法论证定理：A→B成立，也就相应于完成了该问题的知识推理。基本的逻辑推理方法主要有：命题逻辑中的机器定理证明的王浩算法和一阶谓词逻辑中定理证明的鲁宾逊消解方法。2.根据问题求解过程的完备性分类根据问题求解过程是否完备，可将知识推理方法分为：（1）推理算法若问题求解的知识推理过程是完备的，则对于可解的问题从任意初始状态出发，通过这种推理过程，总可以找到一条求解路线，经过有限的、确定的操作序列，转移所要求的目标状态，保证推理过程的收敛性，求得问题的解答。这种推理过程具有完备性，而完备的推理过程称为“推理算法”。例如：王浩算法就是一种知识推理算法。又如广度优先搜索推理方法具有完备性，也是一种知识推理的搜索算法。（2）推理步骤若问题求解的推理过程是不完备的，则不能保证其推理过程的收敛性，以任意初始状态转移到目标态，不一定能求得问题的解答。这种推理过程是不完备的、非算法的，称为“推理步骤”。例如：深度优先算法就是不完备的，它的搜索过程可能会进入无穷的分支，而达不到目标态，所以是一种推理步骤。3.根据启发性知识的运用分类根据在问题求解的过程中是否运用启发性知识，可将知识推理方法分为：（1）启发性推理在问题求解的推理过程中，运用与问题有关的启发性知识，即解决问题的策略、技巧、窍门，对解的特性及规律的估计等实践经验知识，以加快推理过程，提高搜索效率，这种推理过程称为“启发性推理”。例如：在图的搜索推理方法中，利用启发性知识改进的深度优先搜索法，如局部择优搜索法（瞎子爬山法）、最好优先搜索法等，只需要对部分状态空间进行搜索，大大提高了搜索效率。（2）非启发推理在问题求解的推理过程中，不运用启发性知识，而是按照一般的逻辑法则或控制性知识，进行通用性的推理。这种方法缺乏对求解问题的针对性，需要对全状态空间进行搜索，所以，推理效率较低，容易出现“组合爆炸”。知识推理技术分类表分类依据类别示例知识表达方式图搜索法广度、深度优先搜索法逻辑论证法王浩命题逻辑算法鲁宾逊谓词逻辑推理过程完备性推理算法广度优先推理步骤深度优先启发知识利用启发推理局部择优、最好优先搜索法非启发推理广度优先搜索法三．符号模式匹配所谓“符号模式”是指用于知识表达的各种符号表达式，即形式化系统，如谓词函数等。所谓“匹配”时进行比较和选择。“符号模式匹配”就是将一个符号表达式，如事实或数据与另一个符号表达式，如规则或算子，进行比较和选配，判定它们是否可以相互匹配。“符号模式匹配”是人工智能求解的基本技术之一。产生式规则系统在试图使用一条规则时，就必须检查规则的前提与系统的事实库能否匹配。通常可以将要匹配的符号模式分为目标模式和事实模式，如目标模式的各个分量能被事实模式匹配，则称目标模式可匹配。对产生式系统而言，一个待匹配规则的前提部分是一个目标模式，而事实库则构成了事实模式。例如，设含有变量的谓词公式如下：P1：father(John,Joe)^man(John)P2：father(x,y)^man(x)在这里，P1为事实模式，P2为目标模式。我们先检查P2的第一分量father(x,y)。显然father(x,y)与father(John,Joe)具有相同的谓词，若x和y分别可换成John与Joe,则它们事实上就是相同的谓词公式。在谓词运算中，变量可以用任一常量代换，因而，我们可以将x和y分别代换成John与Joe，以继续余下的分量匹配。我们比较P1和P2的第二个分量man(Joe)和man(x)，应该记住x已被替换成John，于是，第二个分量能够相匹配，从而，P1能被P2匹配，并且P2中的x、y分别被替换成John、Joe。由此可知，在符号模式匹配过程中，变量可以被任一常量所替换，但是，一个变量在一次匹配过程中只能被替换成相同的常量。所以，模式father(John,Joe)^man(John)不能匹配模式father(x,y)^man(x)。四．符号模式匹配的问题在符号模式匹配的程序设计中，如何保证变量替换的“一致性”是关键问题。还应注意到，对于产生式系统，为使用一条规则而进行的匹配方法直接影响到产生系统的推理效率。若匹配过程先找出目标模式第一分量的所有可能的匹配，则可能会因为其余的分量不能匹配，系统由于做无用功而影响效率，这是符号模式匹配过程必须考虑的重要因素。目前，符号模式匹配技术存在的问题是过分依赖符号表达式的结构。由于在人工智能系统中，可以用不同的结构化方法表达同一事物的不同表达结构。关于符号模式匹配技术更多的介绍可以参考相应的文献资料。第二节搜索的基本概念搜索技术，特别是启发式搜索，在人工智能的研究中，被看成各种问题求解的主要工具，因此从一开始就受到了极大的重视。在人工智能研究开始的第一个十年左右的时间里，问题求解的研究几乎就是搜索过程研究的同义语。一些早期著名的人工智能程序，如理论家程序（LT）、通用问题求解程序(GPS)、符号积分程序、几何定理证明程序、跳棋程序都是以搜索为基础的程序。既然求解被作为问题求解的主要工具，那么一个问题求解系统也可以看成是一个搜索系统。对问题求解可以狭义的理解，也可广义的理解。狭义理解时，就是解决某种特定问题，如数学求解问题、证明几何定理、逻辑推理、下棋等。广义理解时，可把问题求解看作为达到所期望的目标而进行的知识推理及其运用。所以，广义的问题求解可看作是人工智能的核心课题。下面介绍几个有关搜索的概念：一．显式图与隐式图为求解问题，需要把有关的知识存储在计算机的知识库中，一般有两种存储方式：1．显式存储把与问题有关的全部状态空间图，即相应的全部有关知识（叙述、过程和控制三方面的知识），都直接存入到计算机中，称为“显式存储”或“显式图”。2．隐式存储只存储与问题有关的部分知识，称为“隐式存储”。其它知识则靠规则等来推导出，这样可节省内存。在求解过程中，由初始状态出发，运用相应的知识，逐步生成所需的部分状态空间图，通过搜索推理，逐步转移到要求解的目标状态，只需在知识库中存储局部状态空间图，称为“隐式图”。二．隐式图搜索法一般地说，无法把问题的全部知识（或状态空间）直接存入计算机而是存入与问题有关的部分知识。这是因为：一方面某些问题的信息量太大，二方面计算机的存储容量是有限的。通常的人工智能程序大多采用隐式图搜索推理方法。要成功地求解只拥有隐式图的问题，初始存入的部分知识很重要，必须包含或覆盖全部要用到的知识，否则造成推理失败。此外还必须有一个产生新知识或生成状态空间的方法。在计算机中，利用有关知识逐步产生新的知识或状态空间，并检查问题是否解决的过程，叫隐式图搜索过程。这个问题和人解决问题的过程十分相似。如果计算机能按此过程工作，计算机也就有了一定的智慧。人工智能感兴趣的问题就是如何运用局部知识去解决给定的问题。用隐式图搜索法求解问题的方法与过程如下：搜索方法：①运用叙述性知识，给出问题的部分状态描述，包括初始状态So、目标状态Sg和某些中间状态Sh；②运用过程性知识，给出“生成器”函数G（x）（GeneratorFunction），即由状态空间图的“父结点”生成“子结点”的操作或算子；③运用控制性知识：给出评价函数E（x）（EvaluationFunction），用于评价新生成的结点，控制继续搜索的前进方向。相应的过程：①给定求解问题的初始状态（So、初始结点）；②用生成器函数G（小），由So出发生成中间状态Sh（各子结点），并检索每个中间状态是否为目标状态，若是则搜索成功。③若目标状态Sg未出现，则继续搜索，用评价函数E（x）对Sh的各节点进行评价，选取适当的或最有希望的结点，再用G（x）生成其子结点（状态S2），再检查是否为目标状态Sg。如此下去，直到找到目标状态Sg为止，若所有可生成的结点均已扩展，仍无Sg出现，则搜索失败。第三节广度优先搜索法一．广度优先搜索法的概念所谓广度优先搜索法就是按“先产生的结点先扩展”的原则进行搜索。如下图所示。在广度优先搜索法中，从初始结点So开始，按生成规则，G（x）逐步生成下一级各子点，并顺序检查是否出现目标状态Sg（现生成的子结点优先检查、优先扩展）。在该级全部结点中沿广度进行“横向”扫描，这里，评价函数E（x）=d（x）是结点x的深度（级数），即认为同一级各结点对问题求解的“价值”是同等的，只是按各结点生成的先后次序，先生成、先检查、先扩展，按广度遍历所有的结点，故称“广度优先搜索法”。二．广度优先搜索算法与流程为了实现广度优先搜索算法，使得先生成的点先扩展，必须引入两张表即一个OPEN表和一个CLOSE表。取出OPEN表CLOSE表写入写入图开表和闭表结构状态结构返回指针……..……..编号状态结构返回指针12…………….……….21734569108其中：开（OPEN）表是一个先进先出的结构表，专门登记新产生的结点，它们等待着被扩展；闭（CLOSE）表是一个专门登记已被扩展的结点的表，表中各节点按顺序编号。广度优先搜索的实质是：如果在问题树种存在有目标结点。则它们一定是在树的某些有限级上，用广度优先搜索法就一定可以找到它们，所以说广度优先搜索过程是算法的。广度优先搜索法的流程与算法如下：开始把S0放入OPEN表中OPEN=NIL?取OPEN表中最前面的结点N放入CLOSE表中，并编号N=S?可扩展？可扩展，将其子结点依次放入OPEN表的末尾，并配上指向N的返回指针成功失败NNNYYY步骤1：把初始点So放在OPEN表中；步骤2：若OPEN表为空，则搜索失败，问题无解；步骤3：取OPEN表中最前面的一个结点N，放在CLOSE表中，并给以编号n；步骤4：若N=Sg（目标结点），则搜索成功，问题得解；步骤5：若该结点无子结点，返回为否则继续；步骤6：扩展N结点，并把它的诸子结点依次放入OPEN标的末尾，且