第四章 知识推理技术
本章主要在知识表达的基础上，讨论“知识的运用”即知识推理的概念和方法。
第一节 知识推理的概念和类型
一． 知识推理的基本概念
所谓“知识推理”（Knowledge Inference）是指在计算机或智能机器中，在知识表达的基础上，即利用形式化的知识模式——表达与问题有关知识的符号体系，进行及其思维、求解问题、实现知识推理的智能操作过程。一句话，知识推理就是运用知识求解问题。
知识推理的过程就是问题求解的过程，知识推理技术就是使问题从初始状态转移到目标状态的方法和途径。
研究人工智能的知识推理技术，目的是寻求问题、实现状态转移的智能操作序列，以便从初始状态，沿着最优或最经济的途径，有效地转移到所要求的目标状态，实现问题求解过程的智能机械化或计算机化。
例如：利用计算机制定机器人的行动规划，安排机器人从出发地点到目的地点所需的操作序列和行动路线。又如，利用计算机证明数学定理，给出从已知条件开始到定理证明完毕所需的算子序列和演算步骤等等都是知识推理技术的运用。
二． 知识推理技术的类型
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．隐式存储
只存储与问题有关的部分知识，称为“隐式存储”。其它知识则靠规则等来推导出，这样可节省内存。在求解过程中，由初始状态出发，运用相应的知识，逐步生成所需的部分状态空间图，通过搜索推理，逐步转移到要求解的目标状态，只需在知识库中存储局部状态空间图，称为“隐式图”。
二．隐式图搜索法
一般地说，无法把问题的全部知识（或状态空间）直接存入计算机而是存入与问题有关的部分知识。这是因为：一方面某些问题的信息量太大，二方面计算机的存储容量是有限的。通常的人工智能程序大多采用隐式图搜索推理方法。