高效的前向链接

9.3.3 高效的前向链接

图 9.3 所示的前向链接算法设计的目的是为了提高它的可理解性而不是操作的效率。算法中有 3种可能的复杂性来源。第一，算法的“内循环”涉及寻找所有可能的合一者，把规则的前提与知识库中一个适合的事实集进行合一。这一过程通常被称为模式匹配，它的成本可能很高。第二，算法每次遍历都要对每条规则进行重新检查，以观察其前提是否已经得以满足，即使每次遍历添加到知识库的规则非常少，也要全部检查。最后，算法可能生成许多与目标无关的事实。我们将依次解决这些问题。

一、对于已知事实的规则匹配

把规则前提与知识库中的事实进行匹配的问题可能看起来足够简单。例如，假设我们打算使用规则

那么我们需要找出所有能与Missile(x)合一的事实；在已经建立了适当索引的知识库中，这一过程对于每个事实都可以在常数时间内完成。现在，考虑如下规则

再一次，我们可以对每个对象花费固定的时间找出 Nono 拥有的全部对象；然后对于每个对象，我们能够检查它是不是导弹。可是如果知识库包含很多 Nono 拥有的对象，却只有很少的导弹，那么更好的方法是先找出所有的导弹，然后检查它们是否为 Nono 所有。这就是合取排序问题：寻找一个顺序来解决规则前提的合取，以使得总成本最小。寻求最优排序是个 NP 难题，但是有一些可用的优秀的启发式。例如，如果Nono拥有的导弹数目少于对象的数目，那么第五章中用于CSP的最大约束变量启发式将建议：如果导弹数目少于对象数目，那么应对合取项进行排序以便首先搜索导弹。

实际上模式匹配和约束满足之间的联系非常紧密。我们可以将每个合取子句看作它所包含的变量上的一个约束，例如 Missile(x)是 x 的一元约束。把该思想加以拓展，我们可以把每个有限域的CSP表达为单个确定子句以及一些相关的基本事实。考虑图5.1的地图染色问题，如图9.5（a）再次所示。作为单个确定子句的等价公式如图9.5（b）所示。显然，只有CSP有解时，才能推导出结论Colorable()。因为一般来说，CSP包含3SAT问题作为特例，我们可以得出结论：把确定子句与事实集相匹配是一个NP难题。

图9.5 （a）对澳大利亚地图进行染色的约束图（来自图5.1）。（b）把地图染色CSP表达为单个确定子句。注意，变量域是通过Diff的基本事实中已知的常量隐含地定义的

在前向链接的内循环中存在匹配的NP难题可能看来让人沮丧。然而有3种途径可以让我们高兴起来：

• 我们可以提醒自己，现实世界知识库的大多数规则数量少而且简单（如犯罪例子中的规则），而不是数量巨大而且复杂（如图 9.5 的 CSP 形式化）。在数据库世界中，常见的是规则的规模和谓词的元数都限于某个常数，所需操心的只是数据复杂度——也就是作为数据库内基本事实数量的函数的推理复杂度。很容易看出前向链接的数据复杂度是多项式的。

• 我们可以考虑那些可以高效匹配的规则的子类。本质上，每个数据日志子句都可以视为在定义一个CSP，所以只有当相应的CSP可操作时，匹配才是可操作的。第五章描述了几个可操作的CSP族。例如，如果约束图（图中的节点对应于变量，连接对应于约束）形成一棵树，那么求解CSP需要的时间是线性的。对于规则匹配，完全相同的结果也成立。例如，如果我们从图9.5的地图中将南澳大利亚（SA）移走，结果子句将是：

它对应于如图5.11所示的简化CSP。用于解决树结构CSP的算法可以直接用于规则匹配问题。

• 我们可以努力消除前向链接算法中冗余的规则匹配，这将是下一节的主题。

二、增量前向链接

当我们说明前向链接在犯罪例子中如何工作时，我们使了诈；特别是，我们省略了由图 9.3 所示的算法完成的某些规则匹配。例如，在二次迭代时，规则

与 Missile(M1)匹配（再次），当然结论 Weapon(M1)已知，所以什么都不会发生。如果我们注意到以下事实：每个第t次迭代推理出来的新事实应该由至少一个第t − 1次迭代中推理出来的新事实导出，那么这类多余的规则匹配就可以避免。这一事实是正确的，因为如果任何推理不需要来自第t − 1次迭代的新事实，那么该推理可能在第t − 1次迭代中已经完成。

这个观察结果自然地引出了增量前向链接算法：第 t 次迭代时，只有某个规则的前提包含了一个能与第t − 1次迭代新推理出的事实pi' 进行合一的合取子句pi，我们才会检验该规则。规则匹配步骤固定pi与pi' 进行匹配，但是允许规则的其它合取子句与任何一次先前迭代得到的事实进行匹配。该算法在每次迭代中都恰好生成与图9.3中的算法相同的事实，但是效率更高。

如果有合适的索引，那么很容易辨别所有能被任何已知事实触发的规则，而且实际上许多真实系统在一种“升级”模式中运转，前向链接出现在对每个被TELL给系统的新事实进行响应时。对规则集逐级进行推理直到不动点，然后过程重新开始处理下一个新的事实。

典型情况下，知识库中只有一小部分规则可以真正由添加的已知事实触发。这就意味着，在重复构造具有某些不满足前提的不完全匹配的过程中做了大量的冗余工作。我们的犯罪例子规模太小而无法有效地表现出这种情况，但是我们应该注意到不完全匹配是第一次迭代时在规则

和事实 American(West)之间构造的。该不完全匹配在第二次迭代时被舍弃并重建（规则得以成功匹配时）。当新事实出现时，比较好的做法是保留并逐步完成不完全匹配，而不是舍弃它们。

网（rete）[30]算法是第一个认真处理该问题的算法。rete 算法对知识库中的规则集进行预处理，构造一种数据流网络，在该网络中，每个节点是来自规则前提的一个文字。变量绑定流经网络，如果它们与文字的匹配失败则将被过滤掉。如果一条规则中的两个文字共享一个变量——例如犯罪例子中的Sells(x, y, z)∧Hostile(z)——那么每个文字的绑定都将通过一个等式节点进行过滤。一个变量绑定到达有n个文字的节点诸如Sells(x, y, z)后，在处理过程可以继续运行之前，可能必须等待其它变量的绑定得以建立。在任何给定节点，rete网络的状态捕获所有规则的不完全匹配，从而避免了大量的重复计算。

rete 网络以及建立在其上的其它改进理论已经成为产生式系统的关键组成部分，它是最早广泛使用的前向链接系统之一[31]。XCON系统（最初称为R1，McDermott，1987）是采用产生式系统结构建造起来的。XCON 包含几千条规则，为数字设备公司（DEC）的客户设计计算机部件的配置。在专家系统这个新兴领域中，它是最早取得显著的商业成功的系统之一。许多其它类似的系统也采用相同的基本技术建造，并已经用通用语言OPS-5实现了。

产生式系统在认知体系结构中也很流行——也就是人类推理模型——比如 ACT（Anderson，1983）和 SOAR（Laird 等人，1987）。在这类系统里，系统的“工作内存”模拟人类的短期记忆，产生式是长期记忆的一部分。在每个操作循环过程中，产生式在工作内存中与事实进行匹配。条件得到满足的产生式可以增加或者删除工作内存中的事实。与知识库中典型的情况相反，产生式系统通常包含大量的规则以及相对少的事实。经过有效地最优化匹配技术，某些现代系统可以实时处理上百万条规则。

三、无关的事实

前向链接中最后一个低效率的来源似乎是这一方法所固有的，同时它也会在命题的上下文中出现。（参见第 7.5 节。）前向链接产生所有基于已知事实的容许的推理，即使它们与需要达到的目标无关。在我们的犯罪实例中，不存在能够推理出无关结论的规则，所以缺乏方向性并不是一个问题。在其它实例中（例如，假设我们有好几个分别描述美国人的饮食习惯和导弹价格的规则），FOL-FC-ASK将生成许多无关结论。

避免推导出无关结论的一个途径是采用反向链接，如第 9.4 节中所描述的。另一个解决方法是把前向链接限制在一个选定的规则子集内；此方法在命题的上下文中讨论过。第三种方法已经出现在演绎数据库领域，前向链接是该领域的标准工具。它的思想是利用从目标得到的信息重写规则集，从而在向前推理过程中只考虑相关的变量绑定——这些都属于一个所谓的魔法集。例如，如果目标是Criminal(West)，结论为Criminal(x)的规则将被重写以便包含附加的、对x的取值进行约束的合取子句：

事实Magic(West)也被加入到KB（知识库）中。这样，即使知识库中包括上百万美国人的事实，在前向推理过程中，也只会考虑韦斯特（West）上校。定义魔法集和重写知识库的完整过程太复杂，不属于这里的讨论范围，但其基本的思想是执行来自目标的一种“通用”反向推理以推导出哪些变量绑定需要得到约束。因此可以认为魔术集方法是介于前向推理和反向预处理之间的混合体。