前向和反向链接

7.5.5 前向和反向链接

归结的完备性使其成为非常重要的推理方法。然而，在很多实际情况中无需用到归结的全部能力。现实世界的知识库通常只包含一类被称为霍恩子句（Horn clause）的受限子句。霍恩子句是至多只有一个正文字的文字析取式。例如，子句(¬L1,1∨¬Breeze∨B1,1)是一个霍恩子句，其中L1,1表示智能体的位置是[1, 1]，而(¬B1,1∨P1,2∨P2,1)不是。

只能有一个正文字的限制也许看起来有些随意和无趣，但是它实际上非常重要，理由有三：

① 每个霍恩子句都可以写成一个蕴涵式，它的前提为正文字的一个合取式，结论为一个单个的正文字。（参见习题7.12。）例如，霍恩子句(¬L1,1∨¬Breeze∨B1,1)可以写为蕴涵式(L1,1∧Breeze)B1,1。后面一种形式的语句更易于理解：它说明，如果智能体在[1, 1]，而且有微风，那么[1, 1]是有微风的。人们发现对于很多知识领域而言，采用这种形式很易于人们读写。

类似这样恰恰只有一个正文字的霍恩子句称为确定子句。正文字称为头，否定文字构成子句的体。没有否定文字的确定子句仅仅断言了一个已知命题——有时称为事实。确定子句形成了第九章中讨论的逻辑程序设计的基础。没有正文字的霍恩子句可写成结论为文字False的蕴涵式。例如，子句(¬W1,1∨¬W1,2) —— wumpus不能同时存在于[1, 1]和[1, 2]中——等价于(W1,1∧W1,2)False。这样的语句称为数据库世界的完整性约束，它们发出数据有错误的信号。在随后的算法中，为了简便起见，我们假定知识库只包含确定子句，而且没有完整性约束。我们说，这些知识库是霍恩形的。

② 使用霍恩子句的推理可以在前向链接和反向链接中进行，我们将在后面解释。这两种算法都非常自然，即推理步骤显而易见，而且易于人们理解。

③ 用霍恩子句判定蕴涵需要的时间与数据库大小成线性关系。

最后的事实是一个惊喜。它意味着对于实际中碰到的很多命题知识库，其逻辑推理的代价非常低廉。

前向链接算法PL-FC-ENTAILS?(KB, q)判定单个命题符号q ——查询——是否被霍恩子句的数据库所蕴涵。它从知识库中的已知事实（正文字）开始。如果蕴涵的所有前提已知，那么把它的结论添加到已知事实集。例如，如果L1,1和Breeze已知，而且(L1,1∧Breeze)B1,1在知识库中，那么B1,1被添加到知识库中。持续这一过程，直到询问q被添加或者直到无法进行更进一步的推理。详细的算法如图7.14所示，需要记住的重点是它以线性时间运行。

理解该算法最好的方式是通过示例和图。图7.15（a）显示了一个霍恩子句形式的简单知识库，其中，A 和B 为已知事实。图7.15（b）是用与或图画出的相同知识库。在与或图中，由弧线联系起来的多个连接代表一个合取式——每个连接都必须被证明——而没有弧线的多个连接表示一个析取式——任一连接都可以证明。很容易看出，与或图中的前向链接是如何工作的。已知的叶结点（在此，A 和B）是固定的，推理沿着图传播得尽可能远。无论什么情况下，当合取式出现时，传播暂停直到所有的合取子句在进行前都已知。我们鼓励读者详细地做完这个例子。

图7.14 命题逻辑的前向链接算法。Agenda记录了已知为真但还没有“处理”的符号。count表（计数表）记录着每个蕴涵还有多少前提依然未知。只要待办事项表Agenda中的一个新符号p被处理，对于每个前提中出现p的蕴涵而言，它相应的计数值减去 1。（如果 KB已经建立了适当的索引，这可以在固定的时间内完成。）如果计数达到 0，蕴涵的所有前提都已知，因此可以把它的结论添加到Agenda中。最后，我们需要记录哪些符号已经被处理过：一个推理符号无需添加到Agenda中，如果它先前已经被处理。这避免了冗余操作；它还能阻止发生可能由PQ和QP这样的蕴涵引起的无限循环

图7.15 （a）一个简单的霍恩子句知识库。（b）相应的与或图

很容易看出，前向链接是可靠的：每个推理本质上是分离规则的一个应用。前向连接也是完备的：每个被蕴涵的原子语句都将得以生成。验证这一点的最简单方法是考察 inferred 表的最终状态（在算法到达不动点以后，不可能再出现新的推理）。该表对于在推理过程中参与推理的每个符号都包含true，而所有其它的符号为false。我们可以把该推理表看作一个逻辑模型；而且，原始KB中的每个确定子句在该模型中都为真。为了看到这一点，假定相反情况成立，也就是说某个子句a1∧…∧akvb在模型中为假。那么 a1∧…∧ak在模型中必须为真，b 在模型中必须为假。但这和我们的假设，即算法已经到达一个不动点相矛盾！因而，我们可以得出结论，在不动点推理的原子语句集定义了原始 KB 的一个模型。此外，被KB蕴涵的任一原子语句q在它的所有模型中必须为真，尤其是这个模型。因此，每个被蕴涵的语句q必定会被算法推断出来。

前向链接是数据驱动的推理——即注意力从已知数据开始的推理——的一般概念的一个实例。它可以在智能体内使用，以便从输入感知信息中推导出结论，通常无需头脑中的特定查询。例如，wumpus世界智能体可能用一个渐增前向链接算法把它的感知TELL知识库，在该算法中，新事实可以被添加到待办事项表（agenda）中以便初始化新推理。对于人类，在新信息到达的时候，会发生一定数量的数据驱动的推理。例如，如果我在房子里听到开始下雨，我可能会想到野餐将取消。但是，我很可能不会想到我邻居的花园里最大的玫瑰的第17瓣花瓣将被淋湿；人们把前向链接置于谨慎的控制之下，以免被无关结果淹没。

反向链接算法，正如它的名字所暗示的，从该查询反向进行。如果查询q已知为真，那么无需进行任何操作。否则，算法寻找知识库中那些能以q为结论的蕴涵。如果那些蕴涵中的某一个，它所有的前提都能证明为真（通过反向链接），那么q为真。当把反向链接算法应用于图7.15中的查询Q时，它将沿着图后退，直到达到构成证明基础的一个已知事实集合。详细的算法留作一道习题；与前向链接一样，有效率的实现是按照线性时间运行的。

反向链接是目标指导的推理的一种形式。它对于回答特定的问题很有帮助，诸如“我现在该做什么？”和“我的钥匙在那里？”。通常，反向链接的耗散远小于知识库大小的线性值，因为该过程只接触相关事实。一般而言，智能体应该共享前向和反向推理的工作，将前向推理限制在生成与要用反向链接求解的查询相关的事实上。