归纳逻辑编程30年新简介

CreateAMind

发布于 2023-09-01 08:36:27

2730

发布于 2023-09-01 08:36:27

文章被收录于专栏：CreateAMind

摘要

归纳逻辑编程(ILP)是机器学习的一种形式。ILP的目标是归纳一个假设(一组逻辑规则),概括训练示例。随着ILP步入3o，我们提供了该领域的新介绍。我们介绍必要的逻辑符号和主要的学习设置；描述ILP系统的组成部分；在几个维度上比较几个系统；描述四个系统(Aleph、TILDE、ASPAL和meta gol)；突出重点应用领域；最后，总结当前的局限性和未来研究的方向。

1.介绍

学习知识的能力是人类智慧的一个非凡成就。一种重要的学习形式是

归纳:从具体的观察(例子)中形成一般规则(假设)的过程。例如，假设你从一个袋子里拿出10个红色的球，那么你可能会得出一个假设(一个规则)，即袋子里的所有球都是红色的。有了这个假设，你可以预测下一个球的颜色。

机器学习(ML)自动化归纳。ML归纳了一个假设(也称为模型)，它概括了训练示例(观察)。例如，给定猫和狗的标记图像，ML的目标是诱导一个假设，该假设预测未标记的图像是猫还是狗。归纳逻辑程序设计(ILP) (Muggleton，1991)是ML的一种形式。与其他形式的ML一样，ILP的目标是归纳一个概括训练示例的假设。然而，大多数形式的ML使用表1来表示数据(例子和假设)，而ILP使用逻辑程序(逻辑规则集)。此外，大多数形式的ML学习函数，而ILP学习关系。

Examples 训练数据的数量，众所周知，许多形式的人工智能无法从少量的训练样本中进行归纳，特别是深度学习(Marcus，2o18Chollet，2o19本吉奥等人，2o19)。正如Evans和Grefenstette (2o18)指出的，如果我们训练一个神经系统将1o位的数字相加，它可以推广到2o位的数字，但当对1oo位的数字进行测试时，预测精度会急剧下降(Reed & de Freitas，2o16Kaiser & Sutskever，2o16)。相比之下，ILP可以从少量的例子中归纳出假设，通常是从单个例子中归纳出假设(Lin等人，2014；Muggleton等人，2o18)。当我们只有少量的训练数据时，这种数据效率是很重要的。例如，Gulwani (2o11)应用类似于ILP的技术，从用户在Microsoft Excel中提供的示例中归纳出程序来解决字符串转换问题，在这种情况下，要求用户提供数千个示例是不可行的。这种数据效率使得ILP在许多现实应用中很有吸引力，尤其是在药物设计中，在这些应用中，大量的例子并不总是容易获得的。

Data。使用逻辑程序来表示数据允许ILP学习复杂的关系信息，并且易于集成专家知识。例如，如果学习因果网络中的因果关系，用户可以对关于网络的约束进行编码(Inoue等人，2013)。如果学习识别事件，用户可以提供事件演算的公理。关系BK允许我们简洁地表示无限关系。例如，定义上的求和关系是微不足道的,自然数的无限集合(add(A，B，C):- C = A+B)。相比之下，基于表格的ML方法,大多限于有限的数据，无法表示这些信息。例如，不可能向决策树学习者(Quinlan，1986，1993)提供这种无限关系，因为它需要一个无限特征表。即使我们把自己限制在n个自然数的有限集合中，一个基于表的方法仍然需要n3特征来表示完整的求和关系。

Hypotheses。因为它们与关系数据库密切相关，所以逻辑程序自然支持关系数据，如图形。由于逻辑程序的表达能力，ILP可以学习复杂的关系理论，如细胞自动机(Inoue et al .，2o14Evans等人，2o21)、事件演算理论(Katzouris等人，2o15)、Petri网(Bain & Srinivasan，2o18)、各种形式的非单调程序(Bain & Muggleton，1991；井上&工藤，1997；坂马，2oo1)。由于逻辑程序的符号性，ILP可以对假设进行推理，这使得它可以学习最优程序，如最小时间复杂度程序(Cropper & Muggleton，2o19)和安全访问控制策略(Law et al .，2o2o)。此外，由于归纳假设与BK具有相同的语言，它们可以存储在BK中，从而使迁移学习变得微不足道(Lin et al .，2o14)。

可解释性。由于逻辑与自然语言的相似性，逻辑程序可以容易地被人类阅读，这对于可解释的AI5是至关重要的。由于这种可解释性，ILP长期用于科学发现6 (King等人，1992；Srinivasan等人，1996，1997，2oo6Kaalia等人，2o16)。例如，机器人科学家(King等人，2oo4)是一个使用ILP生成假设来解释数据的系统，并且还可以自动设计实验来测试假设，实际运行实验，解释结果，然后重复循环。在研究基于酵母的功能基因组学时，机器人科学家成为第一个独立发现新科学知识的机器(King等人，2oo9)。

知识转移。大多数ML算法是单任务学习器，不能重用学习到的知识。例如，尽管AlphaGo (Silver等人，2016)具有超人的围棋能力，但它不能重复使用这一知识来玩其他游戏，也不能使用略有不同的棋盘来玩相同的游戏。相比之下，由于其符号表示，ILP自然支持终身学习和迁移学习(Torrey et al .，2oo7Crop- per，2o19)，它被认为是类人AI所必需的(Lake等人，2o16)。例如，在归纳一组字符串转换任务的解决方案时，如场景2中的那些，Lin等人(2014)表明，ILP系统可以自动识别要解决的较简单的问题，为它们学习程序，然后重用所学习的程序来帮助学习更困难问题的程序。此外，他们表明这种知识转移方法导致了可重用程序的层次结构，其中每个程序都建立在更简单的程序之上。

1.6ILP是如何工作的？

构建ILP系统(图1)需要做出几个选择或假设。理解这些假设是理解ILP的关键。我们将在第4节讨论这些假设，但现在对它们进行简要总结。

学习设置。中心选择是如何表示例子。本节场景中的示例包括布尔概念(lego_builder)和输入输出示例(字符串转换和排序)。虽然布尔概念和输入输出示例是常见的表示，但还有其他表示，如解释(Blockeel & De Raedt，1998)和转换(Inoue等人，2o14)。这种表示决定了学习设置，而学习设置又决定了它对程序解决ILP问题的意义。

表示语言。ILP将数据表示为逻辑程序。然而，有许多逻辑编程语言，每一种都有长处和短处。例如，Prolog是一种图灵完全逻辑编程语言。Datalog是Prolog的语法子集，它牺牲了特性(如数据结构)和表达能力(它不是图灵完全的)来获得效率和可判定性。一些语言支持非单调推理，例如回答集编程(Gebser等人，2012)。选择一种合适的表示语言对于决定一个系统能解决哪些问题是至关重要的。

定义假设空间。基本的ILP问题是在假设空间中搜索合适的假设。假设空间包含可以用所选的表示语言构建的所有可能的程序。无限制，假设空间是无限的，因此限制它以使搜索可行是至关重要的。和所有的ML技术一样，ILP通过加强归纳偏差来限制假设空间(Mitchell，1997)。语言偏见加强了对假设的限制，例如一个假设中可以有多少变量或关系。选择一个合适的语言偏好是有效学习的必要条件，也是一个重大挑战。

搜索方法。已经定义了假设空间，问题是有效地搜索它。传统的分类方法是使用自上而下还是自下而上的搜索，其中一般对搜索空间进行排序7。自上而下的方法(昆兰，1990；布洛克尔和德·雷德特，1998年；布拉特科，1999;Muggleton等人，2oo8Ribeiro & Inoue，2o14)从一个过于笼统的假设开始，并试图将其具体化。自下而上的方法(马格顿，1987；马格顿&邦汀，1988年；马格顿&冯，199oInoue et al .，2o14)从一个过于具体的假设开始，并试图将其一般化。一些方法将两者结合起来(Muggleton，1995；斯里尼瓦桑，2oo1Cropper，2o22)。最近出现了第三种方法，称为元级ILP (Inoue等人，2013；Muggleton等人，2o15井上，2o16Law等，2o2oCropper & Morel，2o21)。这种方法将ILP问题表示为元级逻辑程序，即推理程序的程序。元级方法通常将对假设的搜索委托给现成的求解器(Corapi等人，2011；Muggleton等人，2o14Law等人，2o14卡明斯基等人，2o18埃文斯等人，2o21Cropper & Morel，2021)之后，元级解决方案被翻译回ILP问题的标准解决方案。

1.7简史

ILP是ML的一种形式，这让许多只把ML与统计技术联系起来的研究人员感到惊讶。然而，如果我们遵循Mitchell(1997)对ML8的定义，那么ILP与其他ML方法没有什么不同:它在给出更多示例的情况下有所改进。混乱似乎来自于ILP使用逻辑作为学习的表示。然而，正如Domingos (2o15)指出的，通常有五个领域的ML:象征主义者，连接主义者，贝叶斯，类比者和进化论者。ILP属于符号学习范畴。

图灵可以被视为最早的象征主义者之一，因为他提出用逻辑表示法来建造思维机器(图灵，195oMuggleton，1994a)。McCarthy (1959)和他的咨询者一起对人工智能中逻辑的使用提出了第一个全面的建议。随后，大量关于使用逻辑进行ML的工作接踵而至。Banerji (1964)认识到基于表的表示的局限性，提出使用谓词逻辑作为学习的表示语言。michalski(1969)在AQ算法方面的工作，使用集合覆盖算法归纳规则，极大地影响了许多ILP系统。plot kin(1971)关于包容和最小广义化的工作影响了几乎所有的ILP，尤其是理论。其他值得注意的工作包括维拉(1975年)对谓词演算的归纳算法和萨姆特(1981年)的马文系统，最早学习可执行程序之一。Shapiro(1983)在归纳原对数程序方面的工作对ILP做出了重大贡献，包括回溯和精化运算符的概念。Quinlan(1990)的FOIL系统是最著名的ILP系统之一，是ID3 (Quinlan，1986)从命题设置到一阶设置的自然扩展。其他值得注意的贡献包括逆分解(Muggleton & Buntine，1988)，这也是谓词发明的最早方法之一。ILP作为一个领域是由Muggleton (1991)建立的，他指出它位于ML和知识表示的交叉点。

1.8贡献

有几篇优秀的ILP调查论文(萨姆特，1993；Muggleton & De Raedt，1994年；马格顿，1999年a；Page & Srinivasan，2oo3Muggleton et al .，2o12)和书籍(Nienhuys-Cheng & Wolf，1997；De Raedt，2oo8)。在这篇文章中，我们想提供一个新的领域介绍，目标是对符号学习感兴趣的一般人工智能读者。我们与现有调查的不同之处在于，我们包括并主要关注最近的发展(Cropper等人，2o2oa)，例如学习递归程序的新方法、谓词发明和元级搜索。虽然我们涵盖了归纳数据日志和答案集程序的工作，但我们主要关注归纳确定程序的方法，尤其是Prolog程序。我们不详述将神经网络与ILP相结合的工作，对此已有合适的调查论文(d'Avila Garcez等人，2019；Raedt等人，22o)。

本文的其余部分组织如下:

•我们描述必要的逻辑编程符号(第2节)。

•我们定义标准的ILP学习设置(第3节)。

•我们描述了构建ILP系统所需的基本假设(第4节)。

•我们比较了许多ILP系统，并描述了它们支持的特性(第5节)。

•我们详细描述了四个ILP系统(Aleph、TILDE、ASPAL和Metagol)(第6节)。

•我们总结了ILP的一些关键应用领域(第7节)。

•我们简要地调查相关的工作(第8节)。

•最后，我们概述了ILP目前的主要局限性，并为未来的研究提出了建议(第9节)

2.Logic Programming

ILP使用逻辑程序(Kowalski，1974)来表示BK、例子和假设。逻辑程序与命令式程序(如C、Java、Python)有着本质的不同，与函数式程序(如Haskell、OCaml)也有很大的不同。命令式编程将程序视为一系列分步指令，其中计算是执行指令的过程。相比之下，逻辑编程将程序视为一种逻辑理论(一组逻辑规则)，其中计算是对理论的各种形式的推导，例如寻找证明、反驳或模型。另一个主要区别是，逻辑程序是声明性的(Lloyd，1994)，因为它允许用户陈述程序应该做什么，而不是它应该如何工作。这种声明性意味着逻辑程序中规则的顺序(通常)并不重要。

在本节的其余部分，我们将介绍理解本文其余部分所必需的逻辑编程基础。我们涵盖了语法和语义，并简要介绍了不同的逻辑编程语言。我们把重点放在理解ILP所必需的概念上，并把读者引向逻辑编程的更详细的论述(Nienhuys-Cheng & Wolf，1997；De Raedt，2oo8Lloyd，2o12)，Prolog (Sterling & Shapiro，1994；Bratko，2o12)和ASP (Gebser等人，2o12)了解更多信息。因此，我们省略了逻辑程序设计中许多重要概念的描述，如分层否定。熟悉逻辑的读者可以跳过这一节。

2.1句法

我们首先定义逻辑程序的语法: