通过归纳逻辑程序设计进行发现

19.5.4 通过归纳逻辑程序设计进行发现

逆向归结过程将一个完备的归结策略反其道而行之，从原理上讲，它是学习一阶理论的一个完备算法。也就是说，如果某个未知的Hypothesis生成了一组实例，那么逆向归结过程可以根据这些实例生成 Hypothesis。这个现象提示了一个有趣的可能性：设想现成的实例中包含了落体的各种轨迹，那么逆向归结程序是不是在理论上有能力推导出万有引力定律呢？答案显然是肯定的，因为在给定了合适的数学背景知识之后，万有引力定律可以用来解释这些实例。类似地，可以想象电磁学、量子力学和相对论都在ILP程序的范畴内。当然，同样也在猴子与打印机问题的范畴内。我们还需要更好的启发式算法和新思路来构造搜索空间。

逆向归结系统将为我们完成的任务之一是创造新谓词。这种能力看上去多少有些不可思议，因为计算机通常被认为“只知道按照所给予它们的进行工作”。而事实上，新谓词是直接从逆向归结步骤中瓜熟蒂落的。最简单的情况是对于给定的子句C，假设两个新子句C1和C2能归结得到C。对C1和C2的归结消去了两个子句共享的文字；因此，在被消去的文字中很可能含有在C中未出现过的谓词。这样，当进行逆向处理时，就可能生成一个新谓词，重构被消去的文字。

图 19.14 显示了一个例子，在学习 Ancestor 的定义的过程中，生成了一个新谓词 P。谓词 P一旦生成，就可以用于后面的逆向归结步骤。例如后面的一个步骤可能会假设Mother(x, y)  P(x, y)。因此，新谓词P的含义就受到生成涉及它的假设的约束。另一个实例也许会导致Father(x, y) P(x, y)。换句话说，谓词P就是我们通常考虑的Parent关系。如前面我们所提到的，创造新谓词可以显著缩减目标谓词的定义大小。因此，借助于创造新谓词的能力，逆向归结系统经常可以解决许多对于其它系统而言不可行的学习问题。

图19.14 一个生成新谓词P的逆向归结过程

在科学中，某些具有深远意义的革新来自于新谓词和新函数的发明——例如，伽利略发明的“加速度”，以及焦耳发明的“热能”。一旦这些术语可用，发现新定律就变得（相对）容易了。困难之处在于意识到某个新的实体，通过与已有事物的特定关系，将允许用一个比已有理论更简单和更优美的理论来解释全体观察事实。

至今，ILP 系统的新发现还不能达到伽利略和焦耳的水平，但是它们的发现已经被认为可以发表在科技文献中了。例如，在《分子生物学期刊》（Journal of Molecular Biology）中，Turcotte等人（2001）描述了通过 ILP程序 PROLOG完成的“蛋白质折叠规则的自动发现”。PROLOG发现的许多规则都可以根据已知的原理推导出来，但是其中大部分都尚未作为标准生物数据库的一部分被发表过。（参见图 19.10，为其中一例。）在相关工作中，Srinivasan 等人（1994）对发现基于分子结构的硝基化合物诱变规则的问题进行了研究。这些化合物能在汽车排放的尾气中找到。对于标准数据库中80％的化合物而言，辨识化合物的4个主要特征是可能的，而在这些特征上使用线性回归要优于使用 ILP。对于剩下的 20％，单靠特征是不可预测的，对它们使用 ILP来辨识其中的关系要比使用线性回归、神经元网络以及决策树更好。King等人（1992）说明了如何根据分子结构来预测各种药品的疗效。所有这些例子表明，对关系进行表示的能力和利用背景知识的能力对 ILP 的良好性能表现有很大贡献。ILP 发现的规则易于被人理解，这个事实使得这些技术出现在生物学期刊上而不是计算机科学期刊上。

除了生物学，ILP 方法对其它科学领域也做出了贡献。最重要的领域之一就是自然语言处理，其中ILP已经被用于从文本中抽取复杂的关系信息。这些结果在第二十三章中进行了概括。