归纳逻辑程序设计

19.5 归纳逻辑程序设计

归纳逻辑程序设计（ILP）将归纳方法和一阶表示的表达能力结合起来，特别集中于把理论表示为逻辑程序 [10]。它之所以很常用有3个原因。首先，ILP为一般的基于知识的归纳学习问题提供了一种严格的方法。其次，它提供了完备的算法，从实例中归纳一般的一阶理论，因此它可以在那些基于属性的算法难于应用的场合中成功地完成学习。一个例子是学习蛋白质结构的折叠（见图 19.10）。蛋白质分子的三维结构无法通过一组属性合理地进行表示，这是因为结构指的本来就是对象之间的关系，而不是单一对象的属性。一阶逻辑是描述这种关系的合适语言。第三，归纳逻辑程序设计所产生的假设（相对）很容易为人所理解。例如，图19.10的自然语言表述是可以由现在的生物学家进行考察和鉴定的。这意味着归纳逻辑程序设计系统可以参与到实验、假设生成、争论以及反驳的科学研究循环中来。这种参与对于生成“黑盒子”分类器的系统（比如神经网络）而言是不可能的。

图19.10 （a）和（b）分别显示了蛋白质折叠结构域中的“四螺旋头尾并列聚集束”概念的正例和反例。每个样例结构被编码为大约100个合取子句组成的逻辑表达式，比如TotalLength(D2mhr,118)∧NumberHelices(D2mhr,6)∧…。根据这些描述和诸如Fold(FOUR-HELICAL-UP-AND-DOWN-BUNDLE, D2mhr)的分类，归纳逻辑程序设计系统PROGOL（Muggleton，1995）学习到下述规则：

Fold(FOUR-HELICAL-UP-AND-DOWN-BUNDLE,p)⇐

Helix(p,h1)∧Length(h1,HIGH)∧Position(p,h1,n)

∧(1 ≤ n ≤ 3)∧Adjacent(p, h1, h2)∧Helix(p, h2)

这类规则是无法通过类似于我们前面章节里见过的基于属性的机制进行学习的，甚至也无法表示。规则可以被翻译成自然语言：蛋白质P属于分类“四螺旋头尾并列聚集束”，如果它在1和3之间的第二个结构位置包含一条长螺旋h1，并且h1旁边有第二条螺旋