[科普中国]-归纳逻辑程序设计

发展背景

学习是人类拥有智能的一种体现，也是获得知识或技能的基本途径，而机器学习是计算机系统具有智能的重要表现。怎样才能让计算机更好地模拟人类的思维，更好地进行学习，这是计算机领域科学家和逻辑学家十分关心的问题。目前的人工智能研究中，大量的知识工程实践已经表明，知识获取问题是智能系统性能和应用水平得以提高的主要障碍，因此以机器学习的方法和理论来解决知识获取问题是十分必要的，并且将在新一代智能系统中占据重要的地位。然而，目前的机器学习方法存在许多局限性，比如利用背景知识的局限性、知识表示机制的局限性，以及归纳结论的局限性。针对以上问题，归纳逻辑程序设计(Inductive Logic Programming，ILP)的研究领域应运而生。ILP是机器学习与逻辑程序设计的交叉领域，它借助于逻辑程序设计已有的理论与方法，在一阶逻辑的框架下，试图克服传统机器学习存在的问题，建立新的机器学习体系，使机器更好地模拟人的思维。

当人类考虑让计算机通过考察具体的事例，从事例中概括出刻画这些事例特有属性的一般规则时，也即归纳学习一阶规则时，就产生了归纳逻辑程序设计这一机器学习方法。2

归纳逻辑程序设计是机器学习与逻辑程序设计的交叉研究领域，它作为机器学习的研究热点之一，是在子句逻辑的框架下通过实例进行学习的方法。归纳逻辑程序设计的研究始于20世纪70年代，90年代初真正兴起。1991年，马格莱顿(S．Muggleton)和布拉兹蒂德(P．Brazdid)组织了第一届归纳逻辑程序设计的国际研讨会。自此之后这些专家们将归纳逻辑程序设计作为机器学习的一项专题进行研究，每年都要召开一次国际会议，吸引了众多计算机领域专家和逻辑学家们的关注。2

逻辑工具归纳逻辑程序设计所要达到的目的，是让计算机通过考察具体的事例，概括出能够刻画这些事例特有属性的一般性规则。完成这类任务所使用的工具是一阶逻辑，更准确地说，是一阶逻辑的一种变体———子句逻辑。这里有三个重要的概念：子句、赫尔布兰德解释和消解，它们分别涉及形式语言、形式语义和形式推演。

第一个重要的概念是子句（clause）。在ILP中使用子句来表达知识。子句是一种公式，定义为由文字的析取组成的公式（一个原子公式和原子公式的否定都叫做文字）。一个一阶逻辑的公式经过一定的操作步骤可以转化为子句的一个集合。与通常的一阶逻辑公式相比，子句更简单，能够为机器所阅读和接受，同时基本上保持了一阶语言的表现力。人工智能中经常使用的一种特殊子句是霍恩子句，这是以逻辑学家霍恩（Alfred Horn）的名字命名的。

第二个重要的概念是赫尔布兰德解释（Herbrand interpretation），这是以法国数学家赫尔布兰德(J.Herbrand)的名字命名的。熟悉一阶逻辑的人都知道，要使一阶逻辑的公式表达命题，必须通过解释来实现。首先是确定论域，然后将一阶语言中的个体符号解释为论域中的个体，将关系符号和函数符号分别解释为论域上的关系和函数。对于某个一阶语言，可以有许多种甚至无穷多种不同的解释。不同的解释可以有不同的论域，即使采用同一个论域，对于同一个个体符号，不同的解释可以让它对应于论域中不同的个体。赫尔布兰德解释是一类特别的、非常有意思的解释，对于某个一阶语言，如果这个语言中含有个体符号，则它的赫尔布兰德解释的论域是唯一的、确定的。

第三个重要的概念是消解（soudness），这是罗宾森（J.A.Robinson）于1965年发现的一个推演规则，有些学者把这个规则叫做“归结”，这一发现对于在计算机中应用逻辑是极其重要的。在ILP中把从公式集合Σ产生逻辑结论A的方式或过程叫做证明程序（proof procedure），它大致相当于一阶逻辑中的形式推演。我们熟悉的推演规则之一是分离规则（MP）：从集合{A→B，A}中推出公式 B。3

应用ILP得到很大的发展，其应用领域也不断拓宽。

一般说来，ILP最重要的应用领域之一是生物信息学(Bioinformatics)。ILP之所以能适用于生物信息学的任务，是因为它会将背景知识和结构数据考虑在内，学习产生人类能理解的知识。在学习蛋白质结构的折叠的过程中，由于对其结构的学习很重要，所以需要找到能够清晰描述其结构的语言。传统的属性一值方法无法描述对象间的关系，因而也就无法合理地表示蛋白质分子的三维结构，ILP的一阶逻辑工具——子句逻辑是非常适合描述这种关系的语言，它在预测蛋白质结构信息和蛋白质次级结构生成中发挥了很大作用。同时，在预测化合物诱变问题上，ILP也解决了传统方法无法解决的结构关系问题。

ILP系统还常常为工程学、环境监控、软件分析、模式学习和关系发现等领域的数据构造预测模型。虽然ILP与其他机器学习方法相比有一定的优势，然而随着科学技术发展和需求的增加，ILP在应用中也面临许多挑战：

首先，相比其他的机器学习系统来说，ILP系统对时间和空间有更高的要求，这使得ILP很难去处理大的数据集。因此，ILP应该努力寻求与随机搜索和并行处理技术等方法结合以处理结构复杂的数据集。

其次，隐马尔科夫模型、动态贝叶斯网络、双连词和三连词等技术都能充分表达任务中的内在概率，而ILP系统很少有表达、处理概率的能力，这也是ILP的重大不足之一。

最后，当背景知识和数据集用一阶逻辑清晰表达出来时，ILP可以运行良好。但是当数据集是无法通过一阶逻辑清晰表达的图像、视频、音频时，ILP就无能为力。就这一问题来说，ILP需要从约束逻辑程序设计中借鉴经验，学习处理特殊数据格式的技术。4