自顶向下的归纳学习方法

19.5.2 自顶向下的归纳学习方法

ILP 的第一种方法从一条很一般的规则入手，逐步对其进行特殊化以使它能拟合数据。这本质上就是决策树学习中发生的情况，其中决策树正是逐步成长的，直到与观察结果相一致。要实现 ILP，我们选择一阶文字而不使用属性特征，并且用一组子句而不是决策树表示假设。本节描述了 FOIL 算法（Quinlan，1990），最早的ILP程序之一。

设想我们尝试学习Grandfather(x, y)这个谓词的定义，使用和前面相同的家族数据。和决策树学习一样，我们可以将实例分成正例和反例，正例有

反例有

注意这里的每个实例都是成对的对象，因为Grandfather（祖父）是一个二元谓词。总计，在家族树中共有12个正例和388个反例（除正例外的所有其它成对数据）。

FOIL方法构造了一组子句，每个子句都以 Grandfather(x, y)作为子句的头。这些子句必须能够将12个正例划分到Grandfather(x,y)关系中，而将388个反例排除在外。这些子句属于霍恩子句，和Prolog语言中一样，将反例的处理结果作为失败来对负文字进行扩展。初始子句设为空：

这个子句对每个实例的处理结果都是正的，因此要对其进行修正。我们每次在左边加入一个文字，下面是3种可能的结果：

（注意，我们假定一个定义Parent的子句已经是背景知识的一部分了。）这3个子句中的第1个无法正确地将12个正例和那些反例区分开来，所以它要被忽略掉。第2个子句和第3个子句和所有的正例都符合，但是第2条对于反例来说，有很大比例都是不正确的，这是由于它既包含了父亲又包含了母亲。这样，我们比较倾向于选取第3个子句。

下面我们要进一步对其进行修正，来排除这样的情况：x是一些z的父亲，但z不是y的父亲。我们加入一个文字Parent(z, y)，则会得到

它可以对所有的实例进行正确分类。使用FOIL算法可以找到这个文字，也就解决了相应的学习问题。通常情况下，FOIL算法在找到正确的解之前会搜索大量的不成功子句。

上面的例子是对FOIL如何运转的一个很简单的说明。完整算法的框架如图19.12所示。本质上，这个算法就是一个文字一个文字地不断构造一个子句，直到该子句符合正例的某个子集并且不符合任何反例为止。然后，把被该子句覆盖的正例从训练集中去除，持续这个过程直到没有剩余的正例。有两个主要的子过程需要解释一下：NEW-LITERALS 用于构造加入子句的所有可能的新文字， CHOOSE-LITERAL用于挑选一个要添加的文字。

NEW-LITERALS 选取一个子句，然后构造出所有可以加入子句的可能“有用”文字。让我们以一个子句为例，如

图19.12 用于根据实例学习一阶霍恩子句的FOIL算法框架，其中NEW-LITERALS和CHOOSE-LITERAL在后面有解释

有3种可以加入的文字：

① 使用谓词的文字：这样的文字可以是否定的，也可以不是否定的，可以使用任何已有的谓词（包括目标谓词），参数必须全部是变量。任何变量都可以用于谓词的任何参数，不过有一条限制：每个文字必须包含至少一个来自前面文字的变量或者来自子句头的变量。诸如 Mother(z, u)，Married(z, z)，¬Male(y)和 Grandfather(v, x)这样的文字是允许的，而 Married(u, v)是不允许的。注意，使用来自子句头的谓词使得 FOIL能够学习递归的定义。

② 相等与不相等文字：这些文字与已经出现在子句中的变量相关。例如，我们可以加入z ≠ x。这些文字还可以包含用户定义的常量。学习算术时，我们可以使用 0、1，而学习表函数时，我们可以使用空表符号 [ ] 。

③ 算术比较符：当处理连续变量的函数时，可以加入诸如x＞y和y ≤ z这样的文字。如同在决策树学习中一样，可以选取一个常数阈值使得测试的辨识能力达到最大。

在这个搜索空间中产生的分支因子很大（参见习题19.6），不过FOIL还可以利用类型的信息来缩减它。例如，如果在域中包含数字以及人，则类型约束可以阻止NEW-LITERALS生成诸如Parent(x,n)这样的文字，其中x代表人，n代表数字。

CHOOSE-LITERAL使用一个有些类似于信息增益（参见第18.3.4节）的启发式决定添加哪个文字。准确的细节在这里不是那么重要，已经有许多各种不同的方法被尝试过。在FOIL中还有一个很有趣的附加特征，使用了奥卡姆剃刀原则来消除某些假设。如果（在某个尺度下）一个子句的长度变得大于这个子句所解释的正例的总长度，则它将不被当作一个潜在的假设。这个技术提供了一条途径，避免出现过于复杂的、能拟合数据中的噪声的子句。关于噪声与子句长度之间的关系的解释，参见第20.1节。

FOIL 以及一些相关算法已经被用于学习很宽泛的各种定义。有最令人印象深刻的演示之一（Quinlan和Cameron-Jones，1993）涉及求解Bratko（1986）的Prolog语言课本上关于表处理函数的一系列习题。在每种情况下，利用前面学习到的函数作为背景知识，程序能够从一个很小的实例集中学习到正确的函数定义。