归纳逻辑编程

定义及描述

归纳逻辑程序是机器学习与逻辑程序设计交叉所形成的一个领域，克服了传统机器学习方法中的两个主要限制：知识表示的限制和背景知识利用的限制。

背景

机器学习的目标是从大量的经验数据中抽取出一般的判定规则和模式。传统的机器学习方法，如自顶向下的决策树家族，虽然取得了长足的进步和成功的应用，但其主要局限在命题逻辑(即属性-值表示)的框架内。随着机器学习应用领域的不断扩展，传统的机器学习方法已经不能满足实际应用的需求，主要体现在两个方面：

• 命题逻辑的描述能力弱，包括得经验数据的描述和对规则的描述。在命题逻辑中，数据的描述和规则的描述都采用属性-值的形式。但这一描述方式却不适于描述复杂的对象，也不能刻画属性-值间的本质关系。因此，在涉及复杂对象间关系的学习任务中，属性-值表示在对象的描述和规则的描述方面都存在着巨大的障碍。
• 知识的获取并不都是单纯地从原始数据中获得。在人类获得知识的过程中，常常需要或多或少地利用已掌握的相关知识，即背景知识(background knowledge)。由于这些背景知识通常采用更具表达力的一阶谓词逻辑来描述，传统的机器学习方法不便利用相关的背景知识。在这种情况下，归纳逻辑程序设计应运而生。

归纳逻辑程序设计

ILP是机器学习与逻辑程序设计相结合而形成的新的研究领域。ILP继承了逻辑程序设计坚实的理论基础，承续了机器学习实验的方法和面向应用的方向，采用比命题逻辑更具表达力的一阶谓词逻辑表示经验数据和学习到的规则，而且可以非常自然地利用背景知识。ILP克服了传统机器学习方法的两个主要限制：描述能力的限制和背景知识利用的限制，为机器学习提供了更深入的理论和方法，为知识工程等人工智能的应用领域提供了新的、强有力的技术支持。

一阶谓词逻辑表示机制使得ILP在无法用属性-值表示的领域取得了广泛的应用，这些领域包括：植物生物学、蛋白质远程同源检测、共指消解问题、机器翻译、医学图像挖掘、多关系数据挖掘、符号识别、新陈代谢网络、化妆品产品选择、建筑结构规则等。

在ILP系统中，假设给定(先验)背景知识B和实例E(包含正例集E+、反例集E-(均为子句(clause)的集合))，目标就是寻找满足特定条件的假设H(子句有限集)。在不同语义下，需要满足的条件各不相同：

• 常规语义(Normal Semantics)

背景知识、实例和假设可以是任意符合语法规则的逻辑公式。ILP系统在该语义下需要满足的条件如下：

上图中的四个条件分别为：先验满足性、后验满足性、先验必要性、后验充分性。

• 有定语义(Definite Semantics)

这种语义可被考虑为常规语义的特殊情况，不同之处在于背景知识和假设必须是有定子句(definite clauses)。这种情况比常规语义的一般问题背景要简单，因为一个有定子句T有唯一的最小赫尔布兰德模型(minimal Herbrand model) M+(T)，并且在这个模型中任意逻辑公式只有真或假两种取值。ILP系统在该语义下需要满足的条件如下：

其中后验充分性可被看作是相对于正实例的完备性(completeness)，后验满足性也可以被认为是相对于反实例的一致性(consistency)。

实例设置(example setting)是有定语义的一种特殊情况，该情况下实例只能是真或假的实际事实(ground facts)。也可将实例设置看作是常规语意下规定了B和H为有定子句、E是实际单位子句 (ground unit clauses) 集的情况。实例设置是ILP系统中使用最多的设置方式。

[图片及描述来源：Data Mining, Rough Sets and Granular Computing，李艳娟,郭茂祖.归纳逻辑程序设计方法综述[J].智能计算机与应用,2012,2(03):13-17+22.]

发展历史

描述

归纳逻辑编程的根源可以追溯到60年前。1956年，Bruner，Goodnow和Austin 出版了A Study of Thinking一书，成为了心理学的里程碑，并在后来对机器学习产生了巨大影响。

60年代到70年代期间，涌现出了很多后来为ILP发展提供基础的计算概念。

60年代前期，机器学习的概念还未出现。学习被看作是当时还未从AI领域独立出的模式识别(pattern recognition)的一部分。当时的一个主要问题是应如何表示模式，以使其能更易地被识别出。Banerji(1960，1962)首次提出一种称为“description list”的语言，这种语言利用了对象的属性来实现模式识别。Banerji和其学生Pennypacker的研究，对Cohen于1978年发表的用于学习谓词逻辑(predicaet logic)中概念的算法奠定了基础。Banerji于1964年提出了使用谓词逻辑作为一种，描述性语言。因此，Banerji被看作是最早一批提倡被后人称为ILP概念的学者。

1970年，Plotkin和J.C. Reynolds都在研究least general generalizations的应用。Reynolds还提出了演绎律检验(deductive theorem proving)和归纳学习(inductive learning)之间的联系。

70年代，机器学习还处在从AI领域分离、走向独立的过程中。在这段时期，有很多研究都与ILP相关。Dietterich(1978)和Michalski(1980)提到了一种被称为INDUCE的学习算法/程序。该算法是一次很好的尝试，但受制于无法给出坚实的理论基础，未能得以实现。Steven Vere在机器学习的逻辑基础领域取得了大幅的进展，但很少有人认可他的贡献。Vere(1975)致力于开发正规的归纳算法，识别谓词演算(predicate calculus)的表达。他于1977年开发出了在提供背景知识前提下进行学习的方法。Brian Cohen(1978)在自己的CONFUCIUS项目中，使用了通过学习领域知识(domain knowledge)建立有效描述/摘要的方法。CONFUCIUS是首个在一阶逻辑(first-order logic)下学习摘要，并可以重复使用已学习概念的程序。

之后出现了首批可被看作使用了ILP概念的程序，包括Shapiro(1981)的MIS和Claude Sammut(1986)的Marvin。

Wray Buntine于1986年和1988年发表的论文成为了连接先前研究和之后inverse resolution的重要桥梁。之后Muggleton先后于1987年和1988年提出了DUCE项目和CIGOL项目。

Inductive Logic Programming一词是由Stephen Muggleton于1991年在论文中首次提出的，标志了ILP领域的诞生。Muggleton同时创立了ILP的年度国际会议。Muggleton在PROGOL系统中结合了Inverse Entailment和general-to-specific search两项技术。

主要事件

发展分析

瓶颈

虽然ILP与其他机器学习方法相比有一定的优势，但随着科学技术发展和需求的增加，ILP在应用中也面临许多挑战。

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

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

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

未来发展方向

ILP应用过程中所显现出来的不足之处，使得ILP必须与其他研究领域的技术相结合，来提高它解决问题的能力。为了使ILP更好地完成归纳学习任务，戴维培基提出了ILP未来发展的五个研究方向：

• ILP和贝叶斯网络

目前在人工智能中，贝叶斯网络是处理不确定信息和进行概率推理的最有力工具，它在很大程度上取代了传统的基于规则的专家系统。一般说来，ILP和贝叶斯网络学习是正交的。ILP擅长处理关系域，而贝叶斯网络对概率处理的很好。因此，设想一个能够具有贝叶斯网络学习和ILP二者优点的学习算法的存在和应用是合理的，尝试将贝叶斯网络学习和ILP结合的领域也应该是一个有前途、有希望的研究领域。

• ILP和随机搜索

1992年，考茨、塞尔曼、维斯克、米切尔以及其他学者对局部搜索算法诸如LSAT, WSAT的可满足性问题的研究，已经证实了随机搜索更具优势。塞巴格和罗维洛从事于随机匹配和定理证明，并且在诱变性研究上超越PROGOL程序，同时并没有牺牲预测准确性和理解力。由此可以看出，随机搜索是ILP中一个有前途的研究方向。ILP可以尝试与随机搜索算法结合，利用随机搜索可选择的形式去检测子句格，尝试解决不确定搜索问题。

• ILP和约束逻辑程序设计

机器学习中广为人知的成功理论之一是约束逻辑程序设计。这个理论成功的原因在于它整合逻辑和特殊目的的推理者或约束解决者的能力。关于约束问题，斯里尼瓦森和卡马乔使用线性回归去构建一个约束，而克莱文和斯拉特利的工作是用朴素贝叶斯技术去构造一个约束。ILP确实需要从约束逻辑程序设计中借鉴经验，学习处理特殊数据格式的技术，提高其处理问题和解决问题的能力。

• ILP和人类专家的交流

在从远程通讯、分子生物学、制药学等领域的数据库中发现新知识的过程中，如果一个机器学习系统和人类专家能够以团队的形式合作，充分利用计算机的速度优势及人类专家的知识和技术优势，那么在很大程度上会提高机器学习的效率和工作水平，促进新知识的发现。ILP系统的三个特性使得它在知识发现中能够很自然地与人类专家进行合作：

首先，ILP系统能够利用可宣告的背景知识去构造假设，这就使得ILP和领域专家之间能够展开合作。其次，基于特征的学习系统要求使用者从描述创造实例的特征开始，ILP系统允许结构实例根据组成它的对象以及这些对象之间的关系一起自然地被描述。最后，ILP系统和命题逻辑学习者一样，都具有输出用户可以理解的规则的能力，一些ILP系统甚至可以用返回规则。

尽管ILP系统呈现了如此多的有用特性，它在知识发现中作为人类的合作者，仍然还有许多缺点和不足。首先，大多数ILP系统在探试程序基础上返回单一理论，因此丢掉了对一些领域专家来说有意义的子句。其次，ILP系统不能用人类合作者所使用的那种方式来回答人类专家的问题。它们用简单的成批处理模式操作，采用一个数据库作为输入，并且在此基础上返回一个假设。再次，ILP系统不会像人类合作者那样对输入的数据进行质疑。最后，人类专家能够为假设提供知识丰富的辩护形式，例如将一个新的假设与现有的信念联系起来，ILP系统做不到这一点，它仅仅能提供正确的判断。在知识发现和知识获取的人机合作中，要克服ILP的不足，不仅需要逻辑和人工智能的技术，还需要对逻辑主体进行研究，只有二者结合才能使机器与人类专家进行良好沟通。

• ILP和并行处理技术

面对今天复杂的科学计算、各式各样的图象处理以及大量的信号等问题，提高计算机的运行速度和缩短程序的运行时问至关重要。ILP系统对时问和空间有很高的要求，这使得ILP很难去处理大的数据集。并行处理技术的出现，为ILP处理大数据集提供了解决思路。

[描述来源：陈晶晶.归纳逻辑程序设计的应用与发展[J].理论界,2013(12):118-120.]

Contributor: Xiaoxue Zhang