使用逆向演绎的归纳学习

19.5.3 使用逆向演绎的归纳学习

ILP中的第2种主要方法使用了普通演绎推理证明的逆过程。逆向归结是基于这样一个观察事实的：如果实例Classifications是根据Background∧Hypothesis∧Descriptions得出的，那么一定能够通过归结证明这个事实（因为归结是完备的）。如果我们可以“反向运行证明过程”，就能找到证明过程中的Hypothesis。那么这里的关键就在于找到一条逆转归结过程的途径。

下面我们将给出一个逆向归结的反向证明过程，它由单独的反向步骤组成。回忆一下，一个普通的归结步骤选取两个子句C1和C2，对它们进行归结产生归结式C。逆向归结步骤选取一个归结式C，产生两个子句C1和C2，其中C是对子句C1和子句C2进行归结的结果。另一种方法，也可以选取一个归结式C和子句C1，产生子句C2，其中C是对子句C1和子句C2进行归结的结果。

逆向归结过程的前面几步如图 19.13 所示，其中我们的注意力集中在正例 Grandparent(George, Anne)上。处理过程从证明的末尾开始（显示在图的底部）。我们设归结式 C 为空子句（即矛盾），设C2 为¬Grandparent(George, Anne)，它是目标实例的非。第一个逆向步骤选取 C 和 C2 生成子句Grandparent(George, Anne)作为C1。下面的一步，将这个子句作为C，将子句Parent(Elizabeth, Anne)作为C2，生成子句

¬Parent(Elizabeth,y) ∨ Grandparent(George,y)

图19.13 逆向归结过程的前几步。带有阴影的子句是根据右侧的子句和下边的子句通过逆向归结步骤生成的。无阴影的子句来源于Descriptions与Classifications

作为C1。最后一步将这个子句作为归结式。C2取Parent(George, Elizabeth)，一个可能的子句C1为所求假设

现在我们有了一个归结证明，假设、描述和背景知识导致的结果是分类Grandparent(George, Anne)。

很显然，逆向归结涉及一个搜索过程。每一个逆向归结步骤都是非确定性的，因为对于任意的 C，都可能有许多个甚至无限个子句 C1和 C2可以归结出 C。例如图19.13中最后一步，逆向归结步骤也许没有选择¬Parent(Elizabeth, y)∨Grandparent(George, y)作为C1，而是从下面的语句中任意选择：

¬Parent(Elizabeth,Anne) ∨ Grandparent(George,Anne)

¬Parent(z,Anne) ∨ Grandparent(George,Anne)

¬Parent(z,y) ∨ Grandparent(George,y)

Μ

（参见习题19.4和19.5）此外，参与每一步的子句可以从Background（背景）知识、实例Descriptions （描述）以及对 Classifications（分类）的否定式中选取，或者从逆向归结树中已经生成的假设子句中选取。如果没有额外的控制，可能性的大数量就意味着较大的分支因子（因此产生低效率的搜索）。在已实现的ILP系统中，尝试过许多对搜索进行控制的方法：

① 可以消除冗余选择——例如，通过只生成最特殊化的可能假设，以及要求所有假设子句彼此之间以及与观察事实之间保持一致。后面的这个限制可以排除前面列出的子句¬Parent(z, y)∨Grandparent(George, y)。

② 对证明策略加以限制。例如，在第九章中我们见到的线性归结就是一个完备的、受限的策略，它只允许证明树有线性的分支结构（如图19.13中所示）。

③ 对表示语言加以限制，例如，通过消除函数符号或者只允许有霍恩子句。举例来看，PROLOG使用逆向蕴涵处理霍恩子句，其思想就是把蕴涵约束

Background∧Hypothesis∧Description|= Classifications

加以改变，成为如下的逻辑等价形式

Background∧Descriptions∧¬Classifications|= ¬Hypothesis

据此，可以使用一个类似于普通 Prolog 霍恩子句演绎的处理过程，利用失败的否定式来产生Hypothesis。由于它被限定在霍恩子句上，所以它是一个不完备算法，但是它能够比完全的归结要高效得多。也可以使用逆向蕴涵的Inoue方法（2001）进行完备的推理。

④ 可以通过模型检查而不是定理证明来完成推理。PROLOG 系统（Muggleton，1995）使用了一种形式的模型检查对搜索加以限制。和问题集程序设计一样，它为逻辑变量生成可能的取值，并对一致性进行检查。

⑤ 可以使用基本命题子句而不是一阶逻辑来完成推理。LINUS 系统（Lavraĕ 和 Džeroski， 1994）将一阶逻辑理论翻译成命题逻辑，通过一个命题学习系统求解问题，然后再翻译回来。通过命题逻辑公式进行处理对于某些问题会更有效，如我们在第十一章中见过的SATPLAN。