同作者内容：
Code：最有前途的ARC-AGI比赛方法：关系分解，关系型表示胜过函数型表示
Inductive Logic Programming At 30: A New Introduction
ILP系统 是出了名的难用：通常需要拥有 ILP 博士学位才能使用相关工具
自动发明新高层概念是达到人类水平人工智能所需的最重要步骤
谓词发明predicate invention （PI） 的目标与特征或表示学习（Bengio 等人，2013）的研究流派的目标相同，该流派起源于深度学习社区
如果一个子句没有蕴含一个正面示例，那么就没有必要探索它的任何特化，因为它们在逻辑上不可能蕴含该示例。同样，如果一个子句蕴含了一个负面示例，那么就没有必要探索它的任何泛化，因为它们也会蕴含该示例。
摘要
归纳逻辑编程（ILP）是一种机器学习方法。ILP的目标是归纳出能够概括训练示例的假设（一组逻辑规则）。随着ILP迎来30周年，我们为这个领域提供了一个新的介绍。我们介绍了必要的逻辑符号和主要的学习设置；描述了一个ILP系统的构建模块；在几个维度上比较了几个系统；描述了四个系统（Aleph、TILDE、ASPAL和Metagol）；强调了关键的应用领域；最后，总结了当前的局限性和未来研究的方向。
1. 引言
人类智能的一个显著成就是学习知识的能力。学习的一种关键形式是归纳：从特定观察（示例）中形成一般规则（假设）的过程。例如，假设你从一个袋子里拿出10个红色球，然后你可能会归纳出一个假设（规则），即袋子里的所有球都是红色的。归纳出这个假设后，你可以预测袋子里下一个球的颜色。
机器学习（ML）自动化了归纳过程。ML归纳出一个能够概括训练示例（观察）的假设（也称为模型）。例如，给定标记为猫和狗的图像，ML的目标是归纳出一个假设，该假设可以预测未标记图像是猫还是狗。归纳逻辑编程（ILP）（Muggleton，1991）是一种ML形式。与其他ML形式一样，ILP的目标是归纳出能够概括训练示例的假设。然而，大多数ML形式使用表格来表示数据（示例和假设），而ILP使用逻辑程序（逻辑规则集）。此外，大多数ML形式学习函数，而ILP学习关系。我们使用四个场景来说明ILP。
1.1 场景1：概念学习
假设我们想要预测某人是否快乐。为此，我们询问四个人（alice、bob、claire和dave）他们是否快乐。我们还要求提供额外的信息，具体来说，是他们的工作、公司以及他们是否喜欢乐高。许多ML方法，如决策树或神经网络学习器，会将这些数据表示为表格，如表1。使用标准ML术语，每一行代表一个训练示例，前三列（姓名、工作和喜欢乐高）代表特征，最后一列（快乐）代表标签或分类。给定这个表格作为输入，目标是归纳出一个概括训练示例的假设。例如，神经网络学习器将学习一个数字表格，这些数字衡量了特征（或多层网络中的隐藏特征）的重要性。然后我们可以使用假设来预测未见示例的标签。
与将数据表示为表格不同，ILP将数据表示为逻辑程序，即逻辑规则集。逻辑程序的主要构建块是原子（atom）。原子的形式为 p(x1, ..., xn)，其中p是n元的谓词符号（接受n个参数），每个xi是一个项（term）。逻辑程序使用原子来表示数据。例如，我们可以将“alice喜欢乐高”表示为原子 enjoys_lego(alice)，将“bob是乐高建造者”表示为 lego_builder(bob)。
一个ILP任务由三组（B, E+, E-）构成。集合B是背景知识（Background Knowledge, BK）。BK类似于特征，但可以包含与示例间接相关的信息和关系。我们可以将表1中的数据表示为集合B：
ILP通常遵循封闭世界假设（Reiter, 1977），所以如果有任何事物没有明确为真，我们就假设它是假的。有了这个假设，我们不需要明确指出enjoys_lego(bob)和enjoys_lego(dave)是假的。
集合E+和E-分别代表正面和负面示例。我们可以将表1中的示例表示为：
给定这些集合，ILP的目标是归纳出一个假设，该假设与背景知识（BK）一起，在逻辑上能够蕴含尽可能多的正面示例和尽可能少的负面示例。在ILP中，一个假设（H）是一组逻辑规则，例如：
这个假设包含一条规则，该规则表明对于所有的A，如果A是乐高建造者（lego_builder(A)）并且喜欢乐高（enjoys_lego(A)），那么A是快乐的（happy(A)）。归纳出一条规则后，我们可以从中推导出知识。例如，这条规则表明如果lego_builder(alice)和enjoys_lego(alice)为真，那么happy(alice)也必须为真。
上述规则是用标准一阶逻辑符号书写的。我们通常以逆蕴涵形式书写逻辑程序：
以这种形式的规则表明，当每个bodyi原子为真时，头原子为真。逗号表示合取（逻辑与）。在逻辑编程中，每个变量都被假定为全称量化的，因此我们省略了量词。我们还翻转了蕴涵符号的方向 → 到 ←，并且经常用 :- 替换它，因为在编写计算机程序时更容易使用。因此，在逻辑编程符号中，上述假设是：
1.2 场景2：数据整理
假设我们想要从输入 ↦→ 输出示例中学习字符串转换程序，例如返回字符串最后一个字符的程序：
许多形式的机器学习（ML）会将这些示例表示为表格，例如使用一种独热编码one hot技术。相比之下，ILP将这些示例表示为原子，例如：
符号 `last` 是我们想要学习的目標谓词（要概括的关系）。每个原子的第一个参数代表输入列表，第二个参数代表输出值。为了归纳出这些示例的假设，我们需要提供合适的背景知识（BK），例如常见的列表操作：
这个假设包含两条规则。第一条规则表明，当B是A的头部，且A的尾部为空时，B是A的最后一个元素。第二条规则表明，当B是A的尾部的最后一个元素时，B也是A的最后一个元素。
1.3 场景3：程序合成
假设我们有以下正面和负面示例，同样以原子的形式表示，其中第一个参数是未排序的列表，第二个参数是排序后的列表：
同样假设作为背景知识（BK），我们有字符串转换场景中相同的empty、head和tail关系，以及两个额外的关系：
这个假设对应于快速排序算法（Hoare, 1961），它概括了任意长度的列表和训练示例中未出现的元素。这个场景展示了ILP是一种程序合成（Shapiro, 1983）的形式，其目标是自动构建可执行的程序。
1.4情景4:科学发现
正如Srinivasan等人（1994年）所述，“科学理论的制定不仅仅是数据拟合。为了被接受，一个理论必须是可理解的，并且可以进行批判性分析。” 因此，ILP已被广泛用于科学发现。例如，King等人（1992年）使用ILP模拟药物设计中的结构-活性关系。在这项工作中，ILP系统以正面和负面示例以及背景知识（BK）作为输入。正面示例是活性更高的配对示例。例如，正面示例great(d20,d15)表示药物20的活性高于药物15。负面示例是活性较低的药物配对示例。背景知识包含有关药物化学结构和取代基团属性的信息。例如，原子struc(d35,no2,nhcoch3,h)表示药物35在位置3有no2取代，在位置4有nhcoch3取代，在位置5没有取代，原子flex(no2,3)表示no2的灵活性为3。给定这样的示例和背景知识，ILP系统Golem（Muggleton & Feng, 1990）归纳出多个规则来解释示例，包括这一条：
这条规则表明，如果药物B在位置4和5没有取代基团，药物B在位置3的灵活性大于6，药物A在位置3的极化率等于1，药物A在位置3有氢键供体等于0，并且药物A在位置3的灵活性小于药物B在位置3的灵活性，那么药物A就优于药物B。
正如这个场景所说明的，ILP可以学习人类可读的假设。这些规则的可解释性对于让领域专家获得洞察至关重要。
1.5 为什么选择ILP？
大多数机器学习方法依赖于统计推断。相比之下，ILP依赖于逻辑推断，并使用来自自动推理和知识表示的技术。表2显示了ILP和统计机器学习方法之间的简化比较。我们简要讨论这些差异。
例子。许多形式的机器学习因其无法从少量训练示例中泛化而臭名昭著，尤其是深度学习（Marcus, 2018; Chollet, 2019; Bengio et al., 2019）。正如Evans和Grefenstette（2018）所指出的，如果我们训练一个神经系统用10位数字进行加法，它可以泛化到20位数字，但当在100位数字上进行测试时，预测准确性急剧下降（Reed & de Freitas, 2016; Kaiser & Sutskever, 2016）。相比之下，ILP可以从少量示例中归纳出假设，通常从一个示例中就可以（Lin et al., 2014; Muggleton et al., 2018）。当我们只有少量训练数据时，这种数据效率非常重要。例如，Gulwani（2011）应用类似于ILP的技术，通过用户提供的Microsoft Excel示例来归纳程序，以解决字符串转换问题，在这种情况下，要求用户提供成千上万的示例是不可行的。这种数据效率使得ILP在许多实际应用中变得有吸引力，特别是在药物设计中，大量示例并不总是容易获得。
数据。使用逻辑程序来表示数据允许ILP学习复杂的关系信息，并轻松整合专家知识。例如，在学习因果网络中的因果关系时，用户可以编码有关网络的约束（Inoue等人，2013）。如果学习识别事件，用户可以提供事件演算的公理（Katzouris等人，2015）。关系背景知识允许我们简洁地表示无限关系。例如，定义自然数无限集上的求和关系（add(A,B,C):- C = A+B）是微不足道的。相比之下，基于表格的机器学习方法大多限于有限数据，无法表示这些信息。例如，我们无法为决策树学习器（Quinlan，1986, 1993）提供这个无限关系，因为这将需要一个无限的特征表。即使我们将自己限制在有限的n个自然数集上，基于表格的方法仍然需要n^3个特征来表示完整的求和关系。
假设。由于与关系数据库密切相关，逻辑程序自然支持关系数据，如图形。由于逻辑程序的表达能力，ILP可以学习复杂的关系理论，例如元胞自动机（Inoue等人，2014；Evans等人，2021）、事件演算理论（Katzouris等人，2015）和Petri网（Bain & Srinivasan，2018），以及各种形式的非单调程序（Bain & Muggleton，1991；Inoue & Kudoh，1997；Sakama，2001）。由于逻辑程序的符号性质，ILP可以对假设进行推理，这允许它学习最优程序，例如最小时间复杂度程序（Cropper & Muggleton，2019）和安全访问控制策略（Law等人，2020）。此外，由于归纳出的假设与背景知识使用相同的语言，它们可以存储在背景知识中，使迁移学习变得微不足道（Lin等人，2014）。
可解释性。由于逻辑与自然语言的相似性，逻辑程序可以被人类轻松阅读，这对于可解释的AI至关重要。由于这种可解释性，ILP长期以来一直被用于科学发现（King等人，1992；Srinivasan等人，1996, 1997, 2006；Kaalia等人，2016）。例如，机器人科学家（King等人，2004）是一个使用ILP生成假设以解释数据的系统，它还可以自动设计实验来测试假设，实际运行实验，解释结果，然后重复该循环。在研究基于酵母的功能基因组学时，机器人科学家成为第一台独立发现新科学知识的机器（King等人，2009）。
知识转移。大多数机器学习算法是单任务学习器，无法重用学到的知识。例如，尽管AlphaGo（Silver等人，2016）具有超人的围棋能力，但它不能重用这些知识来玩其他游戏，也不能在略有不同的棋盘上玩同一个游戏。相比之下，由于其符号表示，ILP自然支持终身学习和迁移学习（Torrey等人，2007；Cropper，2019），这被认为是类人AI所必需的（Lake等人，2016）。例如，在归纳一组字符串转换任务的解决方案时，如场景2中的任务，Lin等人（2014）表明，ILP系统可以自动识别出更简单的问题来解决，学习它们的程序，然后重用学到的程序来帮助学习更复杂问题的程序。此外，他们表明，这种知识转移方法导致了可重用程序的层次结构，每个程序都建立在更简单程序的基础上。
1.6 ILP如何工作？
构建一个ILP系统（图1）需要做出几个选择或假设。理解这些假设是理解ILP的关键。我们在第4节中讨论了这些假设，但现在简要总结它们：
学习设置。核心选择是如何表示示例。本节场景中的示例包括布尔概念（lego_builder）和输入输出示例（字符串转换和排序）。尽管布尔概念和输入输出示例是常见的表示，但还有其他表示，如解释（Blockeel & De Raedt, 1998）和转换（Inoue et al., 2014）。表示决定了学习设置，进而定义了程序解决ILP问题的含义。
表示语言。ILP将数据表示为逻辑程序。然而，有许多逻辑编程语言，每种语言都有其优点和缺点。例如，Prolog是一种图灵完备的逻辑编程语言。Datalog是Prolog的语法子集，它牺牲了特征（如数据结构）和表达能力（它不是图灵完备的）以获得效率和可判定性。一些语言支持非单调推理，如答案集编程ASP（Gebser et al., 2012）。选择合适的表示语言对于确定系统能够解决的问题至关重要。
定义假设空间。基本的ILP问题是在假设空间中搜索合适的假设。假设空间包含在所选表示语言中可以构建的所有可能程序。如果不加限制，假设空间是无限的，因此限制它是使搜索可行的关键。与所有机器学习技术一样，ILP通过实施归纳偏好（Mitchell, 1997）来限制假设空间。语言偏好对假设实施限制，如假设中可以有多少变量或关系。选择合适的语言偏好对于高效学习和是一个主要挑战是必要的。
搜索方法。在定义了假设空间之后，问题是如何有效地搜索它。传统的分类方法是它们是否使用自顶向下或自底向上的搜索，其中泛化顺序搜索空间7。自顶向下方法（Quinlan, 1990; Blockeel & De Raedt, 1998; Bratko,1999; Muggleton et al., 2008; Ribeiro & Inoue, 2014）从过于泛化的假设开始，试图对其进行专业化。自底向上方法（Muggleton, 1987; Muggleton & Buntine, 1988; Muggleton & Feng, 1990; Inoue et al., 2014）从过于具体的假设开始，试图对其进行概括。一些方法结合了两者（Muggleton, 1995; Srinivasan, 2001; Cropper, 2022）。最近出现了第三种方法，称为元级ILP（Inoue et al., 2013; Muggleton et al., 2015; Inoue, 2016; Law et al., 2020; Cropper & Morel, 2021）。这种方法将ILP问题表示为元级逻辑程序，即推理程序的程序。元级方法通常将搜索假设的任务委托给现成的求解器（Corapi et al., 2011; Muggleton et al., 2014; Law et al., 2014; Kaminski et al., 2018; Evans et al., 2021; Cropper & Morel, 2021），之后将元级解决方案翻译回ILP问题的标凈解决方案。
1.7 简史
ILP是一种机器学习形式，这让很多只将机器学习与统计技术联系在一起的研究人员感到惊讶。然而，如果我们遵循Mitchell（1997）对机器学习的定义，那么ILP与其他机器学习方法没有什么不同：随着更多示例的提供，它会得到改进。这种混淆似乎来自于ILP使用逻辑作为学习的表示。然而，正如Domingos（2015）所指出的，
图灵可以被视为第一个符号主义者之一，因为他提出了使用逻辑表示来构建思考机器（Turing, 1950; Muggleton, 1994a）。McCarthy（1959）在他的建议寻求者中提出了第一个全面使用逻辑进行人工智能的提议。随后，关于使用逻辑进行机器学习的工作接踵而至。Banerji（1964）认识到基于表格的表示的局限性，提出了使用谓词逻辑作为学习的表示语言。Michalski（1969）关于AQ算法的工作，该算法使用集合覆盖算法归纳规则，对许多ILP系统产生了巨大影响。Plotkin（1971）关于包含和最小通用泛化的工作影响了几乎所有的ILP，特别是理论。其他值得注意的工作包括Vera（1975）关于谓词演算的归纳算法，以及Sammut（1981）的MARVIN系统，这是最早学习可执行程序的系统之一。Shapiro（1983）关于归纳Prolog程序的工作对ILP做出了重大贡献，包括回溯和细化操作的概念。Quinlan（1990）的FOIL系统是最知名的ILP系统之一，是ID3（Quinlan, 1986）从命题设置到一阶设置的自然扩展。其他值得注意的贡献包括逆向解析（Muggleton & Buntine, 1988），这也是最早的谓词发明方法之一。ILP作为一个领域是由Muggleton（1991）创立的，他指出它位于机器学习和知识表示的交汇处。
1.8 贡献
已经有几篇优秀的ILP综述论文（Sammut, 1993; Muggleton & De Raedt, 1994; Muggleton, 1999a; Page & Srinivasan, 2003; Muggleton et al., 2012）和书籍（Nienhuys-Cheng & Wolf, 1997; De Raedt, 2008）。在本文中，我们希望为对符号学习感兴趣的通用AI读者提供一个针对该领域的新介绍。我们与现有综述的不同之处在于包括并主要关注最近的发展（Cropper et al., 2020a），例如学习递归程序、谓词发明和元级搜索的新方法。虽然我们涵盖了诱导Datalog和答案集程序的工作，但我们主要关注诱导确定性程序的方法，特别是Prolog程序。我们不详细讨论将神经网络与ILP结合的工作，因为已经有合适的综述论文（d’Avila Garcez et al., 2019; Raedt et al., 2020）。
本文的其余部分组织如下：
• 我们描述必要的逻辑编程符号（第2节）。
• 我们定义标准的ILP学习设置（第3节）。
• 我们描述构建ILP系统所需的基本假设（第4节）。
• 我们比较多个ILP系统并描述它们支持的功能（第5节）。
• 我们详细描述了四个ILP系统（Aleph、TILDE、ASPAL和Metagol）（第6节）。
• 我们总结了ILP的一些关键应用领域（第7节）。
• 我们简要调查相关工作（第8节）。
• 我们通过概述ILP的主要当前局限性并为未来研究提出方向来结束（第9节）。
2. 逻辑编程
ILP使用逻辑程序（Kowalski, 1974）来表示背景知识（BK）、示例和假设。逻辑程序与命令式程序（例如C、Java、Python）有根本的不同，也与功能性程序（例如Haskell、OCaml）非常不同。命令式编程将程序视为一系列逐步的指令，其中计算是执行指令的过程。相比之下，逻辑编程将程序视为逻辑理论（一组逻辑规则），其中计算是对该理论的各种形式的演绎，例如搜索证明、反驳或其模型。
另一个主要区别是逻辑程序是声明式的（Lloyd, 1994），因为它允许用户陈述程序应该做什么，而不是它应该如何工作。这种声明性质意味着逻辑程序中规则的顺序（通常）不重要。
在本节的剩余部分，我们将介绍理解本文其余部分所必需的逻辑编程的基础知识。我们涵盖了语法和语义，并简要介绍了不同的逻辑编程语言。我们重点介绍理解ILP所必需的概念，并将读者引向更详细的逻辑编程（Nienhuys-Cheng & Wolf, 1997; De Raedt, 2008; Lloyd, 2012）、Prolog（Sterling & Shapiro, 1994; Bratko, 2012）和ASP（Gebser et al., 2012）的阐述，以获取更多信息。因此，我们省略了逻辑编程中许多重要概念的描述，例如分层否定。熟悉逻辑的读者可以跳过这一节。
2.1 语法
。。。。。。
。。。
。。。。
4. 构建ILP系统
构建ILP系统需要做出几个选择或假设，这些是学习器归纳偏好的一部分。归纳偏好是必不可少的，所有机器学习方法都施加了归纳偏好（Mitchell, 1997）。理解这些假设是理解ILP的关键。这些选择可以分为：
• 学习设置：如何表示示例
• 表示语言：如何表示背景知识和假设
• 语言偏好：如何定义假设空间
• 搜索方法：如何在假设空间中搜索
表3显示了一些系统的假设。这个表格排除了许多重要的系统，包括交互式系统，如Marvin（Sammut, 1981）、MIS（Shapiro, 1983）、DUCE（Muggleton, 1987）、Cigol（Muggleton & Buntine, 1988）和Clint（De Raedt & Bruynooghe, 1992），理论修订系统，如FORTE（Richards & Mooney, 1995），以及概率系统，如SLIPCOVER（Bellodi & Riguzzi, 2015）和ProbFOIL（De Raedt et al., 2015）。涵盖所有系统超出了本文的范围。我们讨论这些差异/假设。
4.1 学习设置
两个主要的学习设置是LFE和LFI（第3节）。在LFE设置中，还有进一步的区别。一些系统，如Progol（Muggleton, 1995），允许将子句作为示例。然而，大多数系统从一组事实中学习，因此这个比较维度并不有用。
4.2 假设
尽管有些系统学习命题程序，如Duce（Muggleton, 1987），但大多数学习一阶（或高阶）程序。对于学习一阶程序的系统，它们学习的程序类别也有所不同。有些系统诱导完整的（无限制的）子句理论，如Claudien（De Raedt & Dehaspe, 1997）和CF-induction（Inoue, 2004）。然而，对完整子句理论进行推理计算上很昂贵，因此大多数系统学习子句逻辑的片段，通常是确定性程序。专注于程序合成的系统（Shapiro, 1983; Bratko, 1999; Ahlgren & Yuen, 2013; Cropper & Muggleton, 2016, 2019; Cropper & Morel, 2021）倾向于诱导确定性程序，通常作为Prolog程序。
4.2.1 正常程序
学习正常程序（第2.3.1节）的一个动机是许多实际应用需要非单调推理。此外，使用否定作为失败（NAF）通常可以更简单地表达一个概念。例如，考虑Ray（2009）提出的以下问题：
没有NAF，很难为这个问题归纳出一个通用的假设。相比之下，有了NAF，系统可以学习以下假设：
这个程序展示了ASP的有用语言特性。第一条规则是一个选择规则，意味着一个原子可以为真。在这个例子中，规则表明可以从顶点V1到V0有一个进入边。最后两条规则是硬约束，本质上是强制执行完整性约束。第一个硬约束表明不可能有一个不可达的节点。第二个硬约束表明不可能有一个顶点从不同的节点有两个进入边。有关ASP的更多信息，我们推荐阅读Gebser等人（2012）的书籍。
学习ASP程序的方法可以分为两类：勇敢学习器，旨在学习一个程序，使得至少有一个答案集覆盖示例；谨慎学习器，旨在找到一个在所有答案集中都覆盖示例的程序。我们参考Otero（2001）、Sakama和Inoue（2009, 2009）、Law等人（2018）的现有工作，以获取关于这些不同方法的更多信息。
4.2.3 高阶程序
正如许多程序员所知，使用高阶表示有其好处。例如，假设您有一些以Prolog事实表示的加密/解密字符串：
这个程序是高阶的，因为它允许文字将谓词符号作为参数。符号inv是发明出来的（我们在第5.5节讨论谓词发明），在第一条规则中被用作map的参数，在第二条规则中被用作谓词符号。高阶程序比一阶程序更小，因为高阶背景关系map抽象掉了学习递归程序的需要。Cropper等人（2020）表明，诱导高阶程序可以显著提高学习性能，包括预测准确性、样本复杂性和学习时间。
4.3 背景知识
背景知识（BK）类似于其他形式的机器学习中使用的特征。然而，特征是有限的表格，而BK是一个逻辑程序。使用逻辑程序来表示数据允许ILP学习复杂的关系信息。例如，假设我们想要学习列表或字符串转换程序，我们可能想要提供辅助关系，如head、tail和last作为BK：
这些关系适用于任何长度和任何类型的列表。
作为第二个例子，假设您想要学习质数的定义。那么您可能希望给系统提供执行算术推理的能力，例如使用Prolog关系：
这些关系是通用的，适用于任意数字，我们不需要预先计算定义的所有逻辑后果，这是不可能的，因为有无限多个。相比之下，基于表格的深度机器学习方法仅限于有限的命题数据。例如，由于需要无限大的特征表，因此在决策树学习器中无法使用自然数集上的大于关系。
4.3.1 约束
背景知识允许人类编码对问题的先验知识。作为一个简单的例子，如果学习银行规则以确定两家公司是否可以相互借贷，您可能会编码一个先验约束，以防止如果两家公司由同一家母公司拥有，则它们不能相互借贷：
约束在ILP中被广泛使用（Zeng等人，2014；Evans，2020；Cropper & Morel，2021）。例如，Inoue等人（2013）将知识表示为因果图，并使用约束来表示节点之间不可能的连接。Evans等人（2021）使用约束来归纳理论以解释感官序列。例如，他们统一条件的一个要求是对象（常量）通过二元关系的链相连。作者认为，这样的约束对于归纳出的解决方案实现良好的预测准确性是必要的。
4.3.2 讨论
与选择合适的特征一样，在ILP中选择合适的背景知识对于良好的学习性能至关重要。ILP传统上依赖于预定义和手工制作的背景知识，通常由领域专家设计。然而，获得这样的背景知识通常很困难且昂贵。事实上，过度依赖手工制作的背景知识是ILP的一个常见批评（Evans & Grefenstette，2018）。困难在于找到足够的背景知识来解决问题，但又不至于过多以至于系统变得不堪重负的平衡。我们讨论这两个问题。
背景知识太少。如果我们使用太少或不足的背景知识，我们可能会从假设空间中排除一个好的假设。例如，重新考虑引言中的字符串转换问题，我们希望从示例中学习一个返回字符串最后一个字符的程序。
为了从这些示例中归纳出假设，我们需要为ILP系统提供合适的背景知识。例如，我们可能提供包含常见列表/字符串操作的关系的背景知识，如empty（空）、head（头部）和tail（尾部）。给定这三个关系，ILP系统可以学习以下程序：
然而，假设用户没有提供tail作为背景知识。那么系统如何能学习上述假设呢？这种情况是一个主要问题，因为大多数系统只能使用用户提供的背景知识。为了缓解这个问题，有研究正在使系统能够自动发明新的谓词符号，称为谓词发明，我们在第5.5节讨论，这已被证明可以缓解缺少背景知识的问题（Cropper & Muggleton, 2015）。然而，ILP仍然在很大程度上依赖于人为输入来解决问题。解决这个局限性是一个重大挑战。
背景知识太多。与背景知识太少一样，一个主要挑战是太多无关的背景知识。太多的关联（假设它们可以出现在假设中）通常是一个问题，因为假设空间的大小是背景知识大小的函数。从经验上看，太多无关的背景知识对学习性能是不利的（Srinivasan等人，1995, 2003；Cropper, 2020），这也包括无关的语言偏好（Cropper & Tourret, 2020）。解决背景知识过多的问题研究不足。在第9节中，我们建议这个话题是未来工作的一个有前景的方向，特别是当考虑到ILP用于终身学习的潜力时（第5.5.4节）。
4.4 语言偏好
基本的ILP问题是在假设空间中搜索合适的假设。假设空间包含在所选表示语言中可以构建的所有可能程序。如果不加限制，假设空间是无限的，因此限制它是使搜索可行的关键。为了限制假设空间，系统实施归纳偏好（Mitchell, 1997）。语言偏好对假设实施限制，例如限制假设中的变量数量、文字和规则。这些限制可以分为句法偏好，对假设中规则形式的限制，以及语义偏好，对诱导假设行为的限制（Adé等人，1995）。例如，在happy示例（示例1.1）中，我们假设假设只包含出现在背景知识或示例中的谓词符号。然而，我们需要编码这种偏好以赋予ILP系统。
编码语言偏好有几种方法，例如语法（Cohen, 1994a）、Dlabs（De Raedt & Dehaspe, 1997）、生产字段（Inoue, 2004）和谓词声明（Cropper & Morel, 2021）。我们关注模式声明（Muggleton, 1995）和元规则（Cropper & Tourret, 2020），这两种流行的语言偏好。
4.4.1 模式声明
模式声明是最受欢迎的语言偏好形式（Muggleton, 1995; Blockeel & De Raedt, 1998; Srinivasan, 2001; Ray, 2009; Corapi等人，2010, 2011; Athakravi等人，2013; Ahlgren & Yuen, 2013; Law等人，2014; Katzouris等人，2015）。模式声明指出哪些谓词符号可能出现在规则中，频率如何，以及它们的参数类型。在模式语言中，modeh声明表示哪些文字可能出现在规则的头部，而modeb声明表示哪些文字可能出现在规则的主体中。模式声明的形式如下：
模式声明的第一个参数是一个整数，表示召回率。召回率是模式声明在规则中可以使用的最大次数。另一种理解召回率的方式是，它限制了一个文字的替代解决方案的数量。提供召回率是给系统一个提示，以忽略某些假设。例如，如果使用亲子关系，那么我们可以设置召回率为二，因为一个人最多有两个父母。如果使用祖父母关系，那么我们可以设置召回率为四，因为一个人最多有四个祖父母。如果我们知道一个关系是功能性的，如head，那么我们可以将召回率限制为一。符号*表示没有限制。
给定这些模式，规则 `target(A,B) :- head(A,C), tail(C,B)` 是模式不一致的，因为 `modeh(1,target(+list,-char))` 要求 `target` 的第二个参数 (B) 是 char 类型，而 `modeb(*,tail(+list,-list))` 要求 `tail` 的第二个参数 (B) 是 list 类型，因此这个规则是模式不一致的。规则 `target(A,B) :- empty(A), head(C,B)` 也是模式不一致的，因为 `modeb(*,head(+list,-char))` 要求 `head` 的第一个参数 (C) 必须被实例化，但在规则中变量 C 从未被实例化。
相比之下，以下规则都是模式一致的：
根据特定系统的不同，模式还可以支持引入常量符号。在Aleph系统中，这样一个声明的例子是 `modeb(*,length(+list,#int))`，它将允许在规则中包含整数值。
不同系统在使用模式声明时有细微的差别。Progol和Aleph使用带有输入/输出参数类型的模式声明，因为它们诱导Prolog程序，其中规则中文字的顺序很重要。相比之下，ILASP诱导ASP程序，其中规则中文字的顺序并不重要，因此ILASP不使用输入/输出参数。
尽管元规则被广泛使用，但很少有工作确定给定学习任务应使用哪些元规则。相反，这些方法假设合适的元规则作为输入，或者在没有理论保证的情况下使用元规则。与其他形式的ILP偏好（如模式或语法）不同，元规则本身是逻辑陈述，这允许我们对它们进行推理。因此，有关元规则的初步工作正在研究如何识别适合学习逻辑程序某些片段的通用集合（Cropper & Muggleton, 2014; Tourret & Cropper, 2019; Cropper & Tourret, 2020）。尽管有这些初步工作，但决定给定问题使用哪些元规则仍然是一个主要挑战，未来的工作必须解决这个问题。
4.4.3 讨论
选择合适的语言偏好对于使ILP问题可行至关重要，因为它定义了假设空间。如果偏好太弱，则搜索可能变得不可行。如果偏好太强，则我们可能冒着从假设空间中排除一个好的解决方案的风险。这种权衡是阻碍ILP广泛使用的主要问题之一。要了解不适当的语言偏好的影响，考虑第1.2节中的字符串转换示例。即使提供了所有必要的背景关系，如果没有提供递归元规则（例如 R(A,B) :- P(A,C), R(C,B)），基于元规则的系统将无法归纳出概括任何长度列表的程序。同样，如果没有为目标关系提供递归模式声明，基于模式的系统将无法找到一个好的假设。
不同的语言偏好提供不同的好处。模式声明足以强制执行强烈的偏好，显著减少假设空间。当用户对他们的数据有很多了解时，它们特别合适，例如，可以确定合适的召回值。如果用户没有这样的知识，那么确定合适的模式声明可能非常困难。此外，如果用户提供了弱模式声明（例如具有无限召回、单一类型且没有指定输入/输出参数），那么搜索很快就会变得不可行。尽管有一些关于学习模式声明的工作（McCreath & Sharma, 1995; Ferilli等人，2004; Picado等人，2017），但选择合适的模式声明仍然是一个主要挑战。
元规则的一个好处是它们不需要对背景知识有太多了解，用户不需要提供召回值、类型或指定输入/输出参数。因为它们精确地定义了假设的形式，所以它们可以大大减少假设空间，特别是如果用户了解要学习的程序类别。然而，正如前面提到的，元规则的主要缺点是确定给定学习任务使用哪些元规则。尽管有一些初步工作在识别通用元规则集合（Cropper & Muggleton, 2014; Tourret & Cropper, 2019; Cropper & Tourret, 2020），但决定给定问题使用哪些元规则是一个主要挑战，未来的工作必须解决这个问题。
4.5 搜索方法
定义了假设空间之后，下一个问题是如何有效地搜索它。有两种传统的搜索方法：自底向上和自顶向下。这些方法依赖于一般性的概念，其中一个程序比另一个程序更一般或更具体（第2.4节）。一般性关系在假设空间上施加了一个顺序。图2使用theta-subsumption（最受欢迎的排序关系）展示了这个顺序。系统可以在搜索假设时利用这个排序。例如，如果一个子句没有蕴含一个正面示例，那么就没有必要探索它的任何特化，因为它们在逻辑上不可能蕴含该示例。同样，如果一个子句蕴含了一个负面示例，那么就没有必要探索它的任何泛化，因为它们也会蕴含该示例。
上面的段落仅提及了单个子句的一般性顺序，因为许多系统采用覆盖算法，即逐个子句地构建假设（Quinlan, 1990; De Raedt & Dehaspe, 1997; Muggleton, 1995; Blockeel & De Raedt, 1998; Srinivasan, 2001）。然而，有些系统（Shapiro, 1983; Bratko, 1999; Cropper & Morel, 2021）诱导由多个子句形成的理论，因此需要在子句理论上的一般性顺序。我们推荐感兴趣的读者阅读De Raedt（2008）的第7章，以获取更多关于诱导理论的信息。
4.5.1 自顶向下
自顶向下算法（Quinlan, 1990; Blockeel & De Raedt, 1998; Bratko, 1999; Muggleton et al., 2008）从一般假设开始，然后对其进行特化。例如，HYPER（Bratko, 1999）搜索一个树，其中节点对应于假设。树中假设的每个子节点在theta-subsumption方面都比其前驱更具体或相等，即一个假设只能蕴含其父节点所蕴含示例的一个子集。假设的构建基于假设细化（Shapiro, 1983; Nienhuys-Cheng & Wolf, 1997）。如果考虑一个假设，它没有蕴含所有正面示例，它会立即被丢弃，因为它永远不可能被细化成一个完整的假设。
4.5.2 自底向上
自底向上算法从示例开始并泛化它们（Muggleton, 1987; Muggleton & Buntine, 1988; Muggleton & Feng, 1990; Muggleton et al., 2009; Inoue et al., 2014）。例如，Golem（Muggleton & Feng, 1990）基于相对最小通用泛化（RLGG）（Buntine, 1988）泛化示例对。为了介绍RLGG，我们首先引入Plotkin（1971）的最小通用泛化（LGG）概念，它告诉我们如何泛化两个子句。给定两个子句，LGG运算符返回一个比两者都更一般的最具体的单个子句。
也就是说，背景知识表明对象o1和o3是三角形，对象o2是圆形，对象o1和o2指向下方，图像1包含对象o1和o2，而图像2包含对象o3。我们可以使用相对最小通用泛化（RLGG）来识别共同因素，即找到一个代表共同因素的程序。我们将示例图像表示为bon(1)和bon(2)。我们首先制定描述示例相对于背景知识的子句，并移除背景知识中不相关的部分：
4.5.3 自顶向下和自底向上
Progol是一个非常重要的系统，启发了许多其他方法（Srinivasan, 2001; Ray, 2009; Ahlgren & Yuen, 2013），包括我们在第6.1节中详细描述的Aleph。然而，Progol有点令人困惑，因为它是一个自顶向下的系统，但它首先使用自底向上的方法来限制搜索空间。事实上，许多作者只将其视为自顶向下的方法。Progol使用集合覆盖算法。从空程序开始，Progol选择一个未被覆盖的正面示例进行泛化。为了泛化一个示例，Progol使用模式声明（第4.4.1节）构建底部子句（Muggleton, 1995），这是解释示例的逻辑上最具体的子句。使用底部子句限制了搜索空间的上界（空集）和下界（底部子句）。通过这种方式，Progol是一种自底向上的方法，因为它从底部子句开始并尝试泛化它。然而，为了找到底部子句的泛化，Progol使用A*算法以自顶向下（一般到特殊）的方式搜索泛化，并使用其他示例指导搜索。通过这种方式，Progol是一种自顶向下的方法。当底部子句的泛化搜索完成后，Progol将子句添加到其假设中（从而使其更一般），并移除新假设蕴含的任何正面示例。它重复这个过程，直到没有更多的正面示例未被覆盖。在第6.1节中，我们将更详细地讨论这种方法，当我们描述Aleph（Srinivasan, 2001），一个与Progol类似的系统。
4.5.4 元级
最近出现了一种称为元级ILP的新方法（Inoue等人，2013; Muggleton等人，2015; Inoue, 2016; Law等人，2020; Cropper & Morel, 2021）。对于元级ILP的含义没有公认的定义，但大多数方法将ILP问题编码为元级逻辑程序，即推理程序的程序。这种元级方法通常将搜索假设的任务委托给现成的求解器（Corapi等人，2011; Athakravi等人，2013; Muggleton等人，2014; Law等人，2014; Kaminski等人，2018; Evans等人，2021; Cropper & Dumančić, 2020; Cropper & Morel, 2021），之后将元级解决方案翻译回ILP问题的标凈解决方案。换句话说，元级方法不是编写一个以自顶向下或自底向上方式搜索的过程，而是将学习问题表述为一个声明性问题，通常是ASP问题（Corapi等人，2011; Athakravi等人，2013; Muggleton等人，2014; Law等人，2014; Kaminski等人，2018; Evans等人，2021; Cropper & Dumančić, 2020; Cropper & Morel, 2021）。例如，ASPAL（Corapi等人，2011）将ILP问题翻译成元级ASP程序，描述了每个示例和假设空间中的每个可能规则（由模式声明定义）。然后ASPAL使用ASP系统找到一组规则，这些规则覆盖了所有正面示例而没有覆盖任何负面示例。换句话说，ASPAL将搜索任务委托给ASP求解器。ASPAL使用ASP优化语句找到具有最少文字的假设。
元级方法通常可以学习最优和递归程序。此外，元级方法使用多种技术和技术。例如，Metagol（Muggleton等人，2015; Cropper & Muggleton, 2016）使用Prolog元解释器搜索元级Prolog程序的证明。ASPAL（Corapi等人，2011）、ILASP（Law等人，2014）、HEXMIL（Kaminski等人，2018）和Apperception Engine（Evans等人，2021）将ILP问题翻译成ASP问题，并使用强大的ASP求解器找到问题的模型——注意这些系统都采用了非常不同的算法。∂ILP（Evans & Grefenstette, 2018）使用神经网络解决问题。总体而言，元级ILP方法的发展令人兴奋，因为它使ILP从早期系统的标凈子句细化方法多样化。
有关元级推理的更多信息，我们建议阅读Inoue（2016）的工作，他提供了元级推理和学习的介绍。Law等人（2020）还提供了冲突驱动ILP的概述，这是系统ILASP3（Law, 2018）和Popper（Cropper & Morel, 2021）采用的。
4.5.5 讨论
上述讨论的不同搜索方法具有不同的优缺点，没有“最好”的方法。此外，正如Progol所示，自顶向下、自底向上和元级方法之间并没有明确的区分。然而，我们可以对不同方法进行一些一般性的观察。
自底向上方法可以被视为数据驱动或示例驱动的。这些方法的主要优点通常是它们非常快速。然而，正如Bratko（1999）所指出的，自底向上方法有几个缺点，例如（i）它们通常使用不必要地长且包含多个子句的假设，（ii）它们很难同时学习递归假设和多个谓词，以及（iii）它们不容易支持谓词发明。
自顶向下方法的主要优点是它们更容易学习递归程序和文本最小化程序。主要缺点是它们可能效率极低，因为它们可能生成许多甚至不覆盖单个正面示例的假设。自顶向下方法的另一个缺点是它们依赖于迭代改进。例如，TILDE不断特化每个子句，从而带来改进（即，一个子句覆盖的负面示例更少）。因此，如果必要子句非常长且中间特化不改善子句的得分（覆盖率），TILDE可能会陷入次优解决方案。为了避免这个问题，这些系统依赖于前瞻（Struyf等人，2006），这增加了学习的复杂性。
元级方法的主要优点是它们可以学习递归程序和最优程序（Corapi等人，2011; Law等人，2014; Kaminski等人，2018; Evans & Grefenstette, 2018; Evans等人，2021; Cropper & Morel, 2021）。它们还可以利用约束求解中的最新技术，特别是在ASP中。然而，仍存在一些未解决的问题。一个关键问题是，许多方法将ILP问题编码为一个单一的（通常非常大的）ASP问题（Corapi等人，2011; Law等人，2014; Kaminski等人，2018; Evans等人，2021），因此在非常大的域的问题上难以扩展。此外，由于大多数ASP求解器只适用于地面程序（Gebser等人，2014），纯基于ASP的方法固有地限于具有小且有限grounding的任务。尽管初步工作试图解决这个问题（Cropper & Morel, 2021; Cropper, 2022），但这些方法仍需工作以扩展到非常大的问题。许多方法还预先计算假设中的每个可能规则（Corapi等人，2011; Law等人，2014），因此难以学习具有大规则的程序，尽管初步工作试图解决这个问题（Cropper & Dumančić, 2020）。
5. ILP特性
表4在少数几个维度上比较了表3中的相同系统。这个表格排除了许多其他重要的比较维度，例如系统是否支持非观察谓词学习，其中目标关系的示例不是直接给出的（Muggleton, 1995）。我们依次讨论这些特性。
5.1 噪声处理
在机器学习（ML）中，噪声处理非常重要。在ILP中，我们可以区分三种类型的噪声：
- 噪声示例：示例被错误分类
- 错误的背景知识（BK）：应该不成立的关系却成立（或者应该成立的关系没有成立）
- 不完美的背景知识：缺少关系或有太多不相关的关系
我们讨论这三种类型的噪声。
噪声示例。第3节中的问题定义对于解释噪声（错误标记）示例来说过于严格，因为它们期望一个假设能够蕴含所有正面示例而不蕴含任何负面示例。因此，大多数系统放宽了这一约束，接受一个不一定涵盖所有正面示例或涵盖一些负面示例的假设。大多数使用集合覆盖循环的系统自然支持噪声处理。例如，TILDE将决策树学习器（Quinlan, 1986, 1993）扩展到一阶设置，并使用相同的信息增益方法来归纳假设。ILASP的噪声容忍版本（Law, 2018）使用ASP的优化能力来可靠地学习具有最佳覆盖率的程序。总的来说，处理噪声示例是ILP中一个研究充分的主题。
错误的背景知识。正如训练示例可能存在噪声/错误分类一样，背景知识中的事实/规则也可能是噪声/错误分类的。例如，如果在学习预测天气的规则时，背景知识可能包含关于历史天气的事实，这些事实可能不是100%准确的。然而，大多数系统假设背景知识是完美的，即原子是真的或假的，没有不确定性的余地。这一假设是一个主要限制，因为现实世界的数据，如图像或语音，并不总能轻易地转换为纯粹的无噪声符号表示。我们在第9.1节中更详细地讨论了这一限制。
∂ILP的一个关键吸引力在于它采用了ILP的可微分方法，并且可以接受模糊或不明确的数据。与原子真或假不同，∂ILP为原子提供了连续的语义，将原子映射到实数单位区间[0, 1]。作者成功地在MNIST数据集上展示了这种方法。
不完美的背景知识。处理不完美的背景知识是ILP中一个未充分探索的话题。我们可以区分两种类型的不完美背景知识：缺失的背景知识和过多的背景知识，我们在第4.3.2节中讨论了这些。
5.2 优化性
在许多情况下，解决ILP问题（或具有相同的训练误差）有多个（有时是无限多）假设。在这种情况下，我们应该选择哪个假设呢？
5.2.1 奥卡姆剃刀偏见
许多系统试图学习一个文本上最小的假设。这种方法是遵循奥卡姆剃刀偏见（Schaffer, 1993）。奥卡姆剃刀偏见最常见的解释是，在所有与数据一致的假设中，最简单的是最有可能的。大多数方法使用奥卡姆剃刀偏见来找到最小的假设，以子句（Muggleton等人，2015）、文字（Law等人，2014）或描述长度（Muggleton, 1995）来衡量。然而，大多数系统并不保证能够诱导出最小的程序。这种局限性的一个关键原因是，许多方法一次学习一个子句，导致构建的子程序在程序大小和覆盖范围方面是次优的。例如，下一节详细描述的Aleph，对于程序大小和覆盖范围没有保证。较新的系统通过元级推理（第4.5节）来解决这个局限性（Corapi等人，2011；Law等人，2014；Cropper & Muggleton, 2016；Kaminski等人，2018；Cropper & Morel, 2021）。例如，ASPAL（Corapi等人，2011）的输入是一个带有一组候选子句的假设空间。ASPAL的任务是找到最小的子句子集，这些子句能够推导出所有正面例子而不推导出任何负面例子。ASPAL利用ASP的优化能力，可以证明地学习最少文字的程序。
5.2.2 成本最小化程序
学习高效的逻辑程序一直被认为是一个难题（Muggleton & De Raedt, 1994; Muggleton等人，2012），主要是因为高效程序（如归并排序）与低效程序（如冒泡排序）之间在声明性上没有区别。为了解决这个问题，Metaopt（Cropper & Muggleton, 2019）学习高效程序。Metaopt在假设搜索过程中保持成本，并使用这个成本来剪枝假设空间。为了学习最小时间复杂度的逻辑程序，Metaopt最小化了解算步骤的数量。例如，想象学习一个查找重复程序，该程序在列表中找到一个重复的元素，例如 [p,r,o,g,r,a,m] ↦→ r 和 [i,n,d,u,c,t,i,o,n] ↦→ i。在给定合适的输入数据的情况下，Metagol诱导出程序：
该程序首先对输入列表进行排序，然后遍历列表以检查相邻的重复元素。虽然在子句和文字方面都更大，但由 Metaopt 学习的程序比由 Metagol 学习的程序更高效（O(n log n) 相对于 O(n²)）。
其他系统也可以学习最优程序（Schüller & Benz, 2018）。例如，FastLAS（Law等人，2020）遵循这个理念，并接受一个自定义评分函数作为输入，为给定的评分函数计算最优解。作者展示了这种方法允许用户在现实世界的数据集上优化特定领域的性能指标，例如访问控制策略。
这个程序没有泛化，因为它没有定义任意深度的可达性。此外，大多数系统需要每个深度的例子才能学习这样的程序。相比之下，支持递归的系统可以学习以下程序：
尽管更小，但这个程序将可达性泛化到任何深度。此外，系统可以从少量任意可达性深度的例子中学习这个定义。
例6（字符串转换）。重新考虑第1.2节中介绍的字符串转换问题。与可达性示例一样，如果没有递归，系统将需要为每个长度为n的列表学习一个单独的子句来找到最后一个元素，例如：
由于符号表示和递归特性，这个程序泛化到任意长度的列表，并且包含任意元素（例如整数和字符）。
没有递归，系统通常很难从小数量的例子中泛化（Cropper等人，2015）。此外，递归对于许多程序合成任务至关重要，例如介绍中的快速排序场景。尽管它很重要，但学习递归程序一直是一个难题（Muggleton等人，2012）。此外，关于递归程序的可学习性有许多负面的理论结果（Cohen, 1995d）。正如表4所示，许多系统无法学习递归程序，或者只能以有限的形式学习。
一个常见的限制是，许多系统依赖于底部子句构造（Muggleton, 1995），我们在第6.1节详细讨论了这一点。在这种方法中，对于每个正面例子，系统创建一个最具体的子句来推导该例子，然后尝试泛化该子句以推导其他例子。然而，由于系统每个例子只学习一个子句，这种覆盖方法需要底部和归纳情况的例子，这意味着这样的系统在学习递归程序时遇到困难，尤其是从小数量的例子中学习。
随着元解释学习（MIL）的引入，对递归的兴趣最近重新兴起（Muggleton等人，2014, 2015; Cropper等人，2020）和MIL系统Metagol（Cropper & Muggleton, 2016）。MIL的关键思想是使用元规则（第4.4.2节）来限制可诱导程序的形式，从而限制假设空间。例如，链式元规则（P (A, B) ← Q (A, C), R (C, B)）允许Metagol诱导程序，例如：
Metagol使用递归元规则来诱导递归程序，例如尾递归元规则
。Metagol还可以学习相互递归的程序，例如通过发明并学习奇数（odd_1）的定义来学习偶数的定义：
现在许多系统都能学习递归程序（Law等人，2014; Evans & Grefenstette, 2018; Kaminski等人，2018; Evans等人，2021; Cropper & Morel, 2021）。有了递归，系统可以从少量例子中泛化，通常是一个单一的例子（Lin等人，2014; Cropper, 2019）。例如，Popper（Cropper & Morel, 2021）可以从仅有的几个例子中学习列表转换程序，例如一个程序来删除列表的最后一个元素：
学习递归程序的能力已经将归纳逻辑编程（ILP）扩展到新的应用领域，包括学习字符串转换程序（Lin等人，2014）、机器人策略（Cropper & Muggleton, 2015）、上下文无关文法（Muggleton等人，2014）和答案集文法（Law等人，2019）。
5.5 谓词发明
大多数系统假设给定的背景知识（BK）适合于归纳出解决方案。这个假设可能并不总是成立。谓词发明（PI）的目标不是期望用户提供所有必要的背景知识，而是让系统自动发明新的辅助谓词符号，即在假设中引入不在示例或背景知识中给出的新谓词符号。这个想法类似于人类在手动编写程序时创建新函数，例如为了减少代码重复或提高可读性。例如，要学习快速排序算法，学习器需要能够在给定枢轴元素的情况下对列表进行分区，并连接两个列表。如果分区和连接不在背景知识中提供，学习器需要发明它们。
谓词发明被反复声明为一个重要挑战（Muggleton & Buntine, 1988; Stahl, 1995; Muggleton, 1994b; Muggleton等人，2012）。Russell（2019）甚至认为，自动发明新高层概念是达到人类水平人工智能所需的最重要步骤。谓词发明的一个经典例子是从仅包含母亲和父亲背景关系的示例中学习祖父母的定义。在给定合适的示例且没有其他背景关系的情况下，系统可以学习以下程序：
尽管正确，但这个程序很大，包含4个子句和12个文字。相比之下，考虑一个支持谓词发明（PI）的系统学习到的程序：
为了学习这个程序，系统发明了一个新的谓词符号 inv。这个程序在语义上等同于前一个程序，但在文字和子句的数量上都更短。发明的符号 inv 可以被解释为 "parent"（父母）。换句话说，如果我们将 inv 重命名为 parent，我们就有了以下程序：
正如这个例子所示，谓词发明（PI）可以帮助学习更小的程序，这通常是更可取的，因为大多数系统在学习大型程序时都会遇到困难（Cropper等人，2020b; Cropper & Dumančić, 2020）。已经证明，谓词发明有助于减少程序的大小，这反过来又降低了样本复杂性并提高了预测准确性（Dumančić & Blockeel, 2017; Cropper, 2019; Cropper等人，2020; Dumančić等人，2019; Dumancic等人，2021）。
为了学习这个程序，Metagolho发明了谓词符号 `droplasts1`，它在程序中被使用了两次：一次作为文字 `map(A,B,droplasts1)` 中的项，一次作为文字 `droplasts1(A,B)` 中的谓词符号。这个高阶程序使用 `map` 来抽象列表的操作，避免了学习显式递归程序的需要（递归在 `map` 中是隐式的）。
现在考虑学习一个双重 `droplasts` 程序（`ddroplasts`），它扩展了 `droplast` 问题，除了从每个子列表中删除最后一个元素外，它还删除最后一个子列表，例如 [alice,bob,carol] ↦→ [alic,bo]。在给定合适的示例、元规则和背景知识的情况下，Metagolho学习了以下程序：
这个程序与前面提到的 `droplasts` 程序类似，但此外还在文字 `ddroplasts1(C,B)` 中重用了发明的谓词符号 `ddroplasts1`。这个程序展示了谓词发明（PI）帮助学习更复杂程序的强大能力。
大多数早期尝试谓词发明都未能成功，正如表4所示，大多数系统不支持它。正如Kramer（1995）所指出的，谓词发明之所以困难，至少有三个原因：
when- 我们什么时候应该发明一个新的符号？必须有发明新符号的理由；否则，我们永远不会发明一个。
how- 你应该如何发明一个新的符号？它应该有多少个参数？
what- 我们如何判断一个新符号的质量？什么时候我们应该保留一个发明的符号？
有许多谓词发明技术。我们现在简要讨论一些方法。
5.5.1 逆向解析
早期关于谓词发明的工作基于逆向解析（Muggleton & Buntine, 1988）的思想，特别是W运算符。深入讨论逆向解析超出了本文的范围。我们建议读者参考Muggleton和Buntine（1988）的原始工作，或者Nienhuys-Cheng和Wolf（1997）以及De Raedt（2008）的综述书籍，以获取更多信息。尽管逆向解析方法可以支持谓词发明，但它们从未证明完整性，部分原因是缺乏声明性偏见来限定假设空间（Muggleton等人，2015）。
5.5.2 占位符
谓词发明的一种方法是通过模式声明预定义发明的符号，Leban等人（2008）称之为占位符，而Law（2018）称之为规范性谓词发明。例如，要发明 `parent` 关系，需要一个合适的 `modeh` 声明，例如：
然而，这种占位符方法是有限的，因为它要求用户手动指定符号的元数和参数类型（Law等人，2014），这反而违背了谓词发明的初衷，或者需要生成所有可能的发明谓词（Evans & Grefenstette, 2018; Evans等人，2021），这在计算上是昂贵的。
5.5.3 元规则
为了减少谓词发明的复杂性，Metagol使用元规则（第4.4.2节）来定义假设空间。例如，链式元规则允许Metagol诱导出如下程序：
这个程序从列表中删除前两个元素。为了诱导更长的子句，例如从列表中删除前三个元素，Metagol可以使用相同的元规则，但可以发明一个新的谓词符号，然后链式应用它们，例如诱导出以下程序：
这种由元规则驱动的谓词发明方法的一个副作用是，问题被迫被分解成更小的问题。例如，假设你想要学习一个程序，它从列表中删除前四个元素，那么Metagol可以学习以下程序，其中发明的谓词符号 `inv` 被使用了两次：
为了学习这个程序，Metagol发明了谓词符号 `inv` 并使用链式元规则为其诱导定义。Metagol在目标谓词 `f` 的定义中使用了这个新谓词符号。
5.5.4 终身学习
上述谓词发明技术针对的是单一任务问题。谓词发明可以通过持续学习程序（元学习）来执行。例如，Lin等人（2014）使用一种称为依赖学习的技术，使Metagol能够随着时间学习字符串转换程序。给定一组17个字符串转换任务，他们的学习器自动识别出更简单的问题，学习它们的程序，然后重用这些已学习的程序来帮助学习更复杂问题的程序。为了确定哪些问题更容易解决，作者最初以非常强的偏见开始，只允许学习器使用一条规则来找到解决方案。然后他们逐步放宽这个限制，每次在解决方案中允许更多的规则。作者使用谓词发明来改革学习器的偏见，在学习到解决方案后，不仅将目标谓词添加到背景知识中，还将其构成的发明谓词也添加进去。作者通过实验表明，他们的多任务方法比单一任务方法表现得好得多，因为经常重用已学习的程序。此外，他们展示了这种方法导致了由可重用程序组成的背景知识层次结构，每个层次都建立在更简单程序的基础上。图4显示了这种方法。请注意，这种终身学习设置带来了挑战，我们将在第9.1节中讨论。
5.5.5 理论精炼
理论精炼（Wrobel, 1996）的目标是提高理论的质量。理论修订方法（Adé等人，1994；Richards & Mooney, 1995）修订程序，使其包含缺失的答案或不包含不正确的答案。理论压缩（De Raedt等人，2008）方法选择一组子句，使得相对于某些例子，性能受到的最小影响。理论重构改变了逻辑程序的结构，以优化其执行或可读性（Flach, 1993; Wrobel, 1996）。我们讨论两种基于谓词发明的最近精炼方法。
自动编码逻辑程序。自动编码逻辑程序（ALPs）（Dumančić等人，2019）通过同时学习一对逻辑程序来发明谓词：（i）一个编码器，将给定的解释映射到完全用发明谓词定义的新解释，以及（ii）一个解码器，从发明的解释中重建原始解释。发明的解释压缩了给定的例子，并通过捕捉数据中的规律来发明有用的谓词。因此，ALPs改变了问题的表示。该方法最重要的含义是，通过发明的谓词更容易表达目标程序。作者通过实验表明，从ALPs发明的表示中学习提高了生成性马尔可夫逻辑网络（MLN）（Richardson & Domingos, 2006）的学习性能。生成性MLN学习一个（概率性）逻辑程序，解释一个解释中的所有谓词，而不是单个目标谓词。因此，ALPs发明的谓词有助于学习背景知识中的所有谓词。
程序重构。Knorf（Dumancic等人，2021）将ALPs的思想推向了更进一步。在终身学习环境中学习解决用户提供的任务后，Knorf通过移除其中的冗余来压缩学习到的程序。如果学习到的程序包含发明的谓词，Knorf会修订它们并引入新的谓词，以得到更小的程序。通过这样做，Knorf优化了获得的知识的表示。重构的程序在大小上更小，包含的冗余子句更少。作者通过实验证明，重构提高了终身学习中的学习性能。更确切地说，当使用重构的背景知识时，Metagol学习解决更多任务，特别是当背景知识很大时。此外，作者还证明Knorf大大减少了背景知识程序的大小，将程序中的文字数量减少了50%或更多。
6. ILP案例研究
我们现在详细描述四个ILP系统：Aleph（Srinivasan, 2001）、TILDE（Blockeel & De Raedt, 1998）、ASPAL（Corapi等人，2011）和Metagol（Cropper & Muggleton, 2016）。这些系统不一定是最好或最受欢迎的，但使用了相当不同的技术，并且相对容易解释。Aleph基于逆向蕴含（Muggleton, 1995），并使用底部子句构造来限制假设空间。尽管Aleph已经有些年头，但它仍然是最受欢迎的系统之一。TILDE是决策树的一阶泛化，并使用信息增益来分割和征服训练例子。ASPAL是一个元级系统，它使用ASP求解器来解决ILP问题，这影响了后续的许多工作，特别是ILASP。最后，Metagol使用Prolog元解释器来构建一组例子的证明，并从证明中提取程序。我们依次讨论这些系统。
6.1 Aleph
Progol（Muggleton, 1995）可以说是最有影响力的ILP系统，影响了众多系统（Inoue, 2004; Srinivasan, 2001; Ray, 2009; Ahlgren & Yuen, 2013），这些系统反过来又启发了许多其他系统（Katzouris等人，2015, 2016; Schüller & Benz, 2018）。Aleph基于Progol。我们讨论Aleph而不是Progol，因为Aleph的实现是用Prolog编写的，更容易使用，手册也更详细。
6.1.1 Aleph 设置
Aleph的问题设置是：
6.1.2 Aleph 算法
Aleph从一个空的假设开始，并使用以下集合覆盖方法：
1. 选择一个正面例子进行泛化。如果不存在，则停止并返回当前假设；否则，继续下一步。
2. 构建与模式声明（第4.4.1节）一致且能推导例子的最具体子句（底部子句）（Muggleton, 1995）。
3. 搜索一个比底部子句更一般的子句，并具有最佳得分。
4. 将子句添加到假设中，并移除它所覆盖的所有正面例子。返回步骤1。
我们讨论步骤2和3的基本方法。
步骤2：底部子句构造
构造底部子句的目的是限制步骤3中的搜索。底部子句是能推导要泛化的例子的最具体子句。一般来说，底部子句可以有无限的基数。因此，Aleph使用模式声明（第4.4.1节）来限制它们。描述如何构造底部子句超出了本文的范围。参见Muggleton（1995）的论文或De Raedt（2008）的书了解对比方法。构建了底部子句后，Aleph可以忽略任何不比它更一般的子句。换句话说，Aleph只考虑底部子句的泛化子句，这些子句必须都能推导例子。我们使用De Raedt（2008）提供的底部子句定义：
定义4（底部子句）。让H是一个子句假设，C是一个子句。那么底部子句 ⊥(C) 是最具体的子句，使得：
这个底部子句包含文字 rectangle(A)，因为它是由 square(A) 蕴含的。rectangle(A) 的包含反过来又意味着 polygon(A) 的包含。尽管 blue 和 triangle 出现在 B 中，它们与 e 无关，因此没有出现在底部子句中。
任何不比底部子句更一般的子句都不能蕴含 e，因此可以忽略。例如，我们可以忽略子句 pos(A) :- blue(A)，因为它不比 ⊥(e) 更一般。
常量符号。注意 ⊥(e) 包含变量，而不是常量符号，这会使底部子句更加具体。原因是给定的模式声明禁止常量符号。如果在 M 中给出了 modeb(*,polygon(#shape))，那么 ⊥(e) 也会包含 polygon(s1)。
步骤3：子句搜索
构建了底部子句后，Aleph 搜索它的泛化。构建底部子句的重要性在于它从下面（底部子句）限制了搜索空间。图5说明了在给定我们之前形状示例中的底部子句 ⊥(e) 时 Aleph 的搜索空间。Aleph 执行有界的广度优先搜索，先枚举较短的子句，然后是较长的子句，尽管用户可以轻松更改搜索策略。搜索由几个参数限定，例如最大子句大小和最大证明深度。在这种情况下，Aleph 从 ⊥(e) 的最一般泛化 pos(A) 开始，它简单地表明一切都是真的。Aleph 评估（给分数）搜索中的每个子句，即格中的每个子句。Aleph 的默认评估函数是覆盖度，定义为 P - N，其中 P 和 N 分别是由子句蕴含的正面和负面例子的数量。然后 Aleph 尝试通过向其主体添加文字或通过实例化变量来专门化子句。每个子句的专门化称为细化。细化操作符（Shapiro, 1983）的性质在 ILP 中得到了很好的研究（Nienhuys-Cheng & Wolf, 1997; De Raedt, 2008），但超出了本文的范围。关键是要理解 Aleph 的搜索是从上面（最一般的子句）和下面（最具体的子句）限定的。找到最佳子句后，Aleph 将其添加到假设中，移除新假设所覆盖的所有正面例子，然后返回步骤1。描述完整的子句搜索机制和如何计算分数超出了本文的范围，因此我们建议读者参考 Muggleton 和 Firth（2001）的 Progol 教程，以获得更详细的介绍。
6.1.3 讨论
优点。Aleph 是最受欢迎的 ILP 系统之一，因为 (i) 它有一个稳定且易于获取的实现，并且有许多选项，(ii) 它具有良好的经验性能。此外，它是一个单一的 Prolog 文件，这使得下载和使用变得容易。因为它使用底部子句来限制搜索，Aleph 在识别可能出现在假设中的相关常量符号方面也很高效，这与纯粹的自顶向下方法不同。Aleph 还支持许多其他特性，如数值推理、归纳约束，并允许用户提供成本函数。
缺点。由于它基于逆向蕴含，并且一次只学习单个子句，Aleph 在学习递归程序和最优程序方面存在困难，并且不支持谓词发明。Aleph 还使用了许多参数，例如在泛化底部子句时改变搜索策略的参数（步骤 3），以及改变可学习程序结构的参数（例如限制底部子句中文字的数量）。这些参数可以极大地影响学习性能。即使对于专家来说，为一个问题找到合适的参数集也不是一件容易的事情。
6.2 TILDE
TILDE（Blockeel & De Raedt, 1998）是决策树的一阶泛化，特别是 C4.5（Quinlan, 1993）学习算法。TILDE 从解释中学习，而不是像 Aleph 那样从蕴含中学习，并且是自顶向下方法的一个实例。
TILDE 的学习设置与其他 ILP 系统不同，因为它紧密模仿了机器学习中的标准分类设置。也就是说，TILDE 学习一个为例子（一个解释）分配类别的程序。通过检查给定程序和背景知识时，一个例子蕴含哪个类别来分配类别。类别分配表示为形式为 class(c) 的特殊文字，其中 c 来自一组类别 C。例如，如果一个分类器区分猫和狗，那么 C = {cat, dog}。
6.2.1 TILDE 设置
6.2.2 TILDE 算法
TILDE 的行为几乎与限于二元属性的 C4.5 相同，这意味着它使用相同的启发式和剪枝技术。TILDE 不同之处在于生成候选分裂的方法。而 C4.5 将候选生成为属性-值对（或者在连续属性的情况下为值不等式），TILDE 使用文字的合取。这些合取从最一般到最具体逐渐探索，其中使用θ-蕴含（第2节）作为排序。
为了找到假设，TILDE 采用分而治之的策略，递归重复以下步骤：
- 如果所有例子都属于同一类别，创建一个预测该类别的叶节点
- 对于每个候选合取 conj，找到在 conj 上分裂时的归一化信息增益
- 如果没有候选提供信息增益，将前一个节点转变为预测多数类别的叶节点
- 创建一个决策节点 n，它在具有最高信息增益的候选合取上分裂
- 递归地在通过分裂获得的数据子集上分裂，并添加这些节点作为 n 的子节点
示例 8（机器维修示例（Blockeel & De Raedt, 1998））。为了说明 TILDE 的学习过程，考虑以下示例。每个例子是一个解释（一组事实），它描述了 (i) 一个有磨损部件的机器，以及 (ii) 工程师应执行的操作：修理机器、将其送回制造商，或者如果机器正常则什么都不做。这些操作是预测的类别。
像任何自顶向下的方法一样，TILDE 从最一般的程序开始；在这种情况下，初始程序将多数类别分配给所有例子。然后，TILDE 逐渐细化（专业化）程序，直到达到令人满意的性能。为了细化程序，TILDE 使用模式声明。由于 TILDE 的自顶向下特性，将模式理解为可以添加到当前子句的合取更为自然。这种解释与第4.4节中给出的解释不冲突。TILDE 将输入参数解释为绑定到当前子句中已经存在的变量；这与声明在调用文字时需要实例化的参数相同，因为它将由引入该变量的现有文字实例化。同样，在 TILDE 中，输出参数引入了一个新的变量；这个变量将在调用文字后被实例化。
假设有以下模式声明：
计算所有候选分裂的信息增益（就像命题 C4.5 一样），合取 worn(X) 产生了最高的增益，并被设置为树的根。有关 C4.5 和信息增益的详细信息，我们推荐读者阅读 Mitchell（1997）的优秀机器学习书籍。
TILDE 通过递归重复相同的程序来处理测试的结果：当 worn(X) 为真和假时。当根测试失败时，数据集包含一个单一的例子（E4）；TILDE 通过创建预测类别为 ok 的叶节点来形成一个分支。当根测试成功时，并不是所有的例子（E1、E2、E3）都属于同一个类别。因此，TILDE 进一步细化根节点：
候选细化 worn(X), irreplaceable(X) 完美地划分了剩余的例子，因此 irreplaceable(X) 被添加为后续测试。所有例子都被正确分类，因此学习停止。
最终的 TILDE 树是（如图6所示）：
请注意使用剪枝（!）操作符，这对于确保每个例子只有一个决策树分支适用至关重要。
6.2.3 讨论
优点。TILDE 有趣的一个方面是它学习普通逻辑程序（包括否定），而不是确定逻辑程序。TILDE 的另一个优点是，与其他 ILP 系统相比，它支持分类和数值数据。事实上，TILDE 在 ILP 系统中是个例外，这些系统通常难以处理数值数据。在任何细化步骤中，TILDE 可以添加形式为 <(X,V) 的文字，或者等价地 X < V，其中 V 是一个值。TILDE 的逐步细化使得不等式测试的数量可控。
缺点。尽管 TILDE 学习普通程序，但它要求它们必须是树形的，并且不支持递归。此外，TILDE 继承了自顶向下系统的局限性，例如生成许多不必要的候选。TILDE 的另一个弱点是需要前瞻。当一个文字只有与另一个文字合取时才有用时，就需要前瞻。例如，考虑机器维修场景有一个关系 number_of_components，目标规则是当一个由三个以上部件组成的部件磨损时，需要修理机器：
然而，这个候选子句将被拒绝，因为它没有产生信息增益（第一个子句覆盖的每个例子也被第二个子句覆盖）。引入与文字的第二个参数相关的不等式的文字只有在与 number_of_components 谓词一起引入时才有帮助。告知 TILDE 这种依赖性被称为前瞻。
6.3 ASPAL
ASPAL（Corapi 等人，2011）是最早的元级 ILP 系统之一，它直接影响了其他 ILP 系统，特别是 ILASP。ASPAL 建立在 TAL（Corapi 等人，2010）的基础上，但更简单易懂。事实上，ASPAL 是最简单的 ILP 系统之一。它使用模式声明构建假设中可能存在的每个子句。它为每个子句添加一个标志，指示是否应该将子句包含在假设中。然后，它将决定哪些标志打开的问题表述为一个 ASP 问题。
6.3.1 ASPAL 设置
ASPAL 问题设置是：
6.3.2 ASPAL 算法
ASPAL 将 ILP 问题编码为一个元级 ASP 程序。这个元级程序的答案集是 ILP 问题的解决方案。ASPAL 算法是 ILP 中最简单的之一：
1. 生成与给定模式声明一致的所有可能规则。为每个规则分配一个唯一标识符，并将其作为可猜原子添加到每个规则中。
2. 使用 ASP 求解器找到规则的最小子集（通过将问题表述为 ASP 优化问题）。
步骤1稍微复杂一些，我们在下文解释原因。与Aleph类似，ASPAL有几个输入参数来限制假设空间的大小，例如，最大体文字数量和最大子句数量。步骤2使用ASP优化语句来学习一个最小惩罚的程序。
6.3.3 ASPAL 示例
示例 9（ASPAL）。为了说明 ASPAL，我们略微修改了 Corapi 等人（2011）中的例子。我们也忽略了惩罚语句。ASPAL 的输入为 B、E+、E- 和 M：
这个陈述是一个选择规则，它指出 {rule(r1), rule(r2,fly), rule(r2,swim), rule(r3,fly,swim)} 中的文字可以全部不成立，或者最多只有四个是真。ASP 求解器的任务是确定哪些文字应该为真（表述为一个 ASP 优化问题），这对应于这个程序的一个答案集：
6.3.4 讨论
优点。ASPAL 的一个主要优点是它的简单性，这启发了其他方法，尤其是 ILASP。它还通过使用 ASP 优化约束来学习最优程序。
缺点。ASPAL 的主要限制是可扩展性。它预先计算假设中的所有可能规则，这在所有但最琐碎的问题上是不可行的。例如，在从观察中学习游戏规则（Cropper 等人，2020b）时，ASPAL 由于这个原因表现不佳。
6.4 Metagol
解释器是一个评估（解释）程序的程序。元解释器是用它评估的同一语言编写的解释器。Metagol（Muggleton 等人，2015; Cropper & Muggleton, 2016; Cropper 等人，2020）是基于 Prolog 元解释器的一种 ILP 形式。
6.4.1 Metagol 设置
Metagol 问题设置是：
最后一个条件确保假设是给定元规则的一个实例。正是这个条件在 Metagol 中实施了强烈的归纳偏见。
6.4.2 Metagol 算法
Metagol 使用以下程序来找到假设：
1. 选择一个正面例子（一个原子）进行泛化。如果存在，进行步骤 2。如果不存在，用负面例子测试假设。如果假设不蕴含任何负面例子，停止并返回假设；否则，回溯到步骤 2 的选择点并继续。
2. 尝试证明原子通过：
(a) 使用给定的背景知识或已经归纳出的子句
(b) 将原子与元规则（第4.4.2节）的头部统一，将元规则中的变量绑定到谓词和常量签名中的符号，保存替换，并通过对元规则体进行元解释（通过将体原子视为例子并应用步骤 2 来证明它们）来证明元规则的体
换句话说，Metagol 通过构建正面例子的证明来归纳逻辑程序。它使用元规则来指导证明搜索。在证明所有例子后，Metagol 检查假设与负面例子的一致性。如果程序不一致，Metagol 回溯以探索不同的证明（假设）。
元规则。元规则对 Metagol 至关重要。例如，链式元规则是 P(A,B):- Q(A,C), R(C,B)。字母 P、Q 和 R 表示二阶变量。Metagol 内部将元规则表示为 Prolog 原子的形式 metarule(Name,Subs,Head,Body)。这里 Name 表示元规则名称，Subs 是 Metagol 应该找到替换的变量列表，Head 和 Body 是子句的列表表示。例如，链式元规则的内部表示是 metarule(chain,[P,Q,R],[P,A,B], [[Q,A,C],[R,C,B]])。Metagol 表示替换，我们将称之为 metasubs，作为形式为 sub(Name,Subs) 的原子，其中 Name 是元规则的名称，Subs 是替换的列表。例如，在链式元规则中用 second、tail 和 head 分别绑定变量 P、Q 和 R 会导致 metasub sub(chain,[second,tail,head]) 和子句 second(A,B):- tail(A,C),head(C,B)。
最优性。为了学习最优程序，Metagol 对程序大小（metasubs 的数量）实施了限制。Metagol 使用迭代加深来搜索假设。在深度 d = 1 时，Metagol 只允许归纳出一个子句，即最多使用一个 metasub。如果存在这样的假设，Metagol 就返回它。否则，Metagol 继续进行下一轮迭代 d + 1。在每次迭代 d 中，Metagol 引入 d - 1 个新的谓词符号，并允许使用 d 个子句。新谓词符号是通过取任务的名称并添加下划线和数字形成的。例如，如果任务是 f 且深度是 4，那么 Metagol 将向谓词签名中添加谓词符号 f_1、f_2 和 f_3。
6.4.3 Metagol 示例
示例 10（亲属关系示例）。为了说明 Metagol，假设你有以下背景知识（BK）：
在这个 metasub 中，符号 Q 仍然是一个变量。Metagol 递归地尝试证明原子 Q(ann,amelia)。由于没有这样的 Q 使得 Q(ann,amelia) 为真，这一步失败了。因为 ident 元规则失败了，Metagol 移除了 metasub 并回溯尝试使用不同的元规则。Metagol 将原子与链式元规则统一，形成以下子句：
Metagol 递归地尝试证明原子 `Q(ann,C)` 和 `R(C,amelia)`。假设递归调用证明 `Q(ann,C)` 成功，通过将 Q 替换为 mother 来形成原子 `mother(ann,amy)`。这个替换将 Q 绑定到 mother，将 C 绑定到 amy，这个绑定被传播到另一个原子，现在变成了 `R(amy,amelia)`。Metagol 也通过将 R 替换为 mother 来证明这第二个原子，形成了原子 `mother(amy,amelia)`。证明现在完成了，metasub 是：
在证明了这个例子之后，Metagol 转到步骤 1 并选择另一个要泛化的例子。假设它选择了例子 grandparent(steve,amelia)。在步骤 2a 中，Metagol 尝试使用背景知识来证明这个原子，再次失败，所以尝试使用已经归纳出的子句来证明，这也失败了。因此，Metagol 尝试使用元规则来证明这个原子。Metagol 可以再次使用链式元规则，但使用不同的替换来形成 metasub：
在这个程序中，符号 `grandparent_1` 被发明出来，对应于 `parent` 关系。然而，在这个例子中很难简洁地说明谓词发明（PI）。因此，我们用一个更简单的例子来说明 Metagol 中的 PI。
示例 11（谓词发明）。假设我们有以下单一正面例子：
还假设我们只有链式元规则和背景关系 `head` 和 `tail`。给定这些输入，在步骤 2b 中，Metagol 将尝试使用链式元规则来证明这个例子。然而，仅使用给定的背景知识和元规则，Metagol 唯一能构造的程序是四个子句的组合：
这些子句的任何组合都无法证明这些例子，所以 Metagol 必须使用谓词发明（PI）来学习解决方案。要使用 PI，Metagol 将尝试使用链式元规则来证明这个例子，这将导致构造以下程序：
Metagol 将尝试递归证明 Q([i,l,p],C) 和 R(C,p)。为了证明 Q([i,l,p],C)，Metagol 会表示它无法使用背景知识中的某个关系来证明它，因此它将尝试发明一个新的谓词符号，这导致产生新的原子 f_1([i,l,p],C) 和以下程序：
Metagol 接着尝试证明原子 `Q2([i,l,p],D)` 和 `R2(D,C)`。Metagol 可以通过将 `Q2` 绑定到 `tail` 来证明 `Q2([i,l,p],D)`，这样 `D` 就被绑定到 `[l,p]`。然后，Metagol 可以通过将 `R2` 绑定到 `tail` 来证明 `R2([l,p],C)`，这样 `C` 就被绑定到 `[p]`。记住，变量的绑定是通过程序传递的，所以 `R(C,p)` 中的 `C` 现在被绑定到 `R([p],p)`。Metagol 然后尝试证明剩余的原子 `R([p],p)`，它可以通过将 `R` 绑定到 `head` 来完成。现在所有原子的证明都已完成，最终的 metasubs 是：
6.4.4 讨论
优点。Metagol 支持谓词发明、学习递归程序，并保证学习到最小的程序。因为它使用元规则，Metagol 可以严格限制假设空间，这意味着它在寻找解决方案时极为高效。基本的 Metagol 实现不到 100 行 Prolog 代码，这使得 Metagol 易于适应，例如支持 NAF（Siebers & Schmid, 2018）、类型（Morel 等人，2019）、学习高阶程序（Cropper 等人，2020）、学习高效程序（Cropper & Muggleton, 2015, 2019）和贝叶斯推理（Muggleton 等人，2013）。
缺点。决定对于给定任务使用哪些元规则是一个主要问题。如果给出太多元规则，假设空间可能太大，以至于搜索变得不可行。如果给出的元规则不足，假设空间可能太小，以至于排除了好的假设。对于某些任务，例如字符串转换，选择合适的元规则集是直接的，因为人们已经知道假设的一般形式。然而，当对解决方案知之甚少时，Metagol 就不适合了。尽管有识别通用元规则集的初步工作（Cropper & Muggleton, 2014; Tourret & Cropper, 2019; Cropper & Tourret, 2020），但这些工作主要集中在二元逻辑上。如果问题包含元数大于二的谓词，那么 Metagol 就不适合了。最后，Metagol 无法处理带有噪声的例子，并且在学习大型程序时遇到困难（Cropper, 2017; Cropper & Dumančić, 2020; Cropper & Morel, 2021）。
7. 应用
我们现在简要讨论一下 ILP 的一些应用领域。
生物信息学和药物设计。ILP 最突出的应用领域之一是生物信息学和药物设计。ILP 特别适合这类问题，因为生物结构，包括分子和蛋白质相互作用网络，可以很容易地表示为关系：分子键定义原子之间的关系，相互作用定义蛋白质之间的关系。此外，如引言中提到的，ILP 诱导出人类可读的模型。因此，ILP 可以根据生物结构中存在的（子）结构进行预测，领域专家可以解释这些预测。ILP 已经应用的任务类型包括识别和预测配体（负责医疗活动的子结构）（Finn 等人，1998; Srinivasan 等人，2006; Kaalia 等人，2016）、预测分子的致突变活性和识别化学癌症原因的结构警报（Srinivasan 等人，1997, 1996）、学习蛋白质折叠签名（Turcotte 等人，2001）、推断蛋白质信号网络中缺失的途径（Inoue 等人，2013）和模拟代谢网络中的抑制作用（Tamaddoni-Nezhad 等人，2006）。
机器人科学家。ILP 最引人注目的应用之一是在机器人科学家项目（King 等人，2009）中。机器人科学家使用逻辑背景知识来表示蛋白质编码序列、酶和代谢物在途径中的关系。机器人科学家使用 ILP 自动生成假设来解释数据，然后设计实验来测试假设，运行实验，解释结果，然后重复循环（King 等人，2004）。在研究基于酵母的功能基因组学时，机器人科学家成为第一台独立发现新科学知识的机器（King 等人，2009）。
生态学。最近在生态学中应用 ILP 有很多工作（Bohan 等人，2011; Tamaddoni-Nezhad 等人，2014; Bohan 等人，2017）。例如，Bohan 等人（2011）使用 ILP 从生态数据中生成合理且可检验的捕食关系（“谁吃谁”）假设。
程序分析。由于逻辑程序作为表示语言的表达性，ILP 系统在软件设计中找到了成功的应用。ILP 系统在学习 SQL 查询（Albarghouthi 等人，2017; Sivaraman 等人，2019）和编程语言语义（Bartha & Cheney, 2019）方面证明是有效的。其他应用包括代码搜索（Sivaraman 等人，2019），在这种情况下，ILP 系统从例子中互动式地学习搜索查询，以及从执行行为中恢复软件规格说明（Cohen, 1994b, 1995a）。
数据策划和转换。ILP 在数据策划和转换方面的另一个成功应用，这在很大程度上是因为 ILP 可以学习可执行的程序。这些任务中最突出的例子是字符串转换，如引言中给出的例子。人们对这个话题非常感兴趣，很大程度上是因为在合成最终用户问题的程序方面取得了成功，例如 Microsoft Excel 中的字符串转换（Gulwani, 2011）。字符串转换已成为一些最新 ILP 论文的标准基准（Lin 等人，2014; Cropper 等人，2020; Cropper & Dumančić, 2020; Cropper & Morel, 2021; Cropper, 2019）。其他转换任务包括从半结构化数据（例如 XML 文件或医疗记录）中提取值，从生态论文中提取关系，以及电子表格操作（Cropper 等人，2015）。
从轨迹中学习。从解释转换中学习（LFIT）（Inoue 等人，2014）自动从系统状态转换的观察中构建系统动态模型。给定离散基因表达的时间序列数据，它可以学习基因相互作用，从而允许解释和预测随时间的状态变化（Ribeiro 等人，2020）。LFIT 已应用于学习生物模型，如在几种语义下的布尔网络：无记忆确定性系统（Inoue 等人，2014; Ribeiro & Inoue, 2014）、概率系统及其多值扩展（Ribeiro 等人，2015; Martínez 等人，2016）。Martínez 等人（2015, 2016）将 LFIT 与强化学习算法结合起来，从零开始学习具有外生效应（与任何动作无关的效应）的概率模型。学习器特别被集成到机器人中，执行清理桌子上餐具的任务。在这个任务中，外部代理互动，人们不断带来新的餐具，操纵机器人必须与移动机器人合作将餐具拿到厨房。学习器能够在仅五次动作执行的五个情节中学习到可用的模型。Evans 等人（2021）应用 Apperception Engine 来解释序列数据，如节奏和简单的儿歌、图像遮挡任务和序列归纳智力测试。他们展示了他们的系统能够达到人类水平的性能。
自然语言处理。许多自然语言处理任务需要理解语言的语法和语义。ILP 适合解决这类任务有三个原因：（i）它基于一种可以捕捉/尊重自然语言的语法和语义的表达性形式语言，（ii）语言学知识和原则可以集成到 ILP 系统中，以及（iii）学习到的子句对语言学家来说是可理解的。ILP 已应用于从例子中学习语法（Mooney & Califf, 1995; Muggleton 等人，2014; Law 等人，2019）和解析器（Zelle & Mooney, 1996, 1995; Mooney, 1999）。有关可以从 ILP 中受益的语言任务的广泛概述，请参阅 Dzeroski 等人（1999）的论文。
物理信息学习。ILP 的一个主要优势是其能够结合和利用背景知识。几个 ILP 应用从第一原理解决问题：提供了基本原语的物理模型，ILP 系统可以归纳出其行为源自基本原语的目标假设。例如，ILP 系统可以使用关于光的理论来理解图像（Dai 等人，2017; Muggleton 等人，2018）。类似地，可以从目标行为的例子和基本电子组件的物理中构建简单电路（Grobelnik, 1992），并且可以在给定关于微分方程的知识的情况下学习简单动态系统的模型（Bratko 等人，1991）。
机器人学。与前一类类似，机器人应用通常需要结合领域知识或对学习到的程序施加某些要求。例如，机器人工程师（Sammut 等人，2015）使用 ILP 为机器人设计工具甚至完整的机器人，这些机器人在模拟和现实世界环境中进行了测试。Metagolo（Cropper & Muggleton, 2015）学习考虑其资源效率的机器人策略，Antanas 等人（2015）通过对象的关系表示识别对象上的可抓取点。
游戏。归纳游戏规则在 ILP 中有着悠久的历史，其中象棋经常是焦点（Goodacre, 1996; Morales, 1996; Muggleton 等人，2009）。例如，Bain（1994）研究归纳规则以确定象棋 KRK（王-车-王）残局中的合法移动。Castillo 和 Wrobel（2003）使用自顶向下的 ILP 系统和主动学习来归纳出在扫雷游戏中何时一个方格是安全的规则。Legras 等人（2018）表明 Aleph 和 TILDE 在桥牌游戏中可以胜过 SVM 学习器。Law 等人（2014）使用 ILASP 归纳出数独的规则，并表明这种更表达性的形式化允许更紧凑地表达游戏规则。Cropper 等人（2020b）引入了归纳通用游戏玩法的 ILP 问题：从观察中归纳游戏规则的问题，例如跳棋、仓库搬运工和四子棋。
其他。其他值得注意的应用包括学习事件识别系统（Katzouris 等人，2015, 2016）、追踪在线社区的演变（Athanasopoulos 等人，2018）、MNIST 数据集（Evans & Grefenstette, 2018）和需求工程（Alrajeh 等人，2013）。
8. 相关工作
8.1 程序合成
因为 ILP 归纳程序，所以它也是程序合成的一种形式（Shapiro, 1983），其目标是根据规范构建程序。通用归纳方法，如 Solomonoff 归纳（Solomonoff, 1964a, 1964b）和 Levin 搜索（Levin, 1973）是程序合成的形式。然而，通用方法不切实际，因为它们仅从例子中学习，正如 Mitchell（1997）所指出的，无偏见的学习是徒劳的。
演绎程序合成方法（Manna & Waldinger, 1980）以完整规范为输入，并且擅长构建程序。通用归纳方法仅以例子为输入，并且不擅长构建程序。介于两者之间的领域称为归纳程序合成。与通用归纳方法类似，归纳程序合成系统从不完整的规范中学习程序，通常是输入/输出例子。与通用归纳方法不同，归纳程序合成系统使用背景知识，因此比通用方法更不通用，但更实用，因为背景知识是一种归纳偏见（Mitchell, 1997），它限制了假设空间。当没有给定背景知识，因此没有归纳偏见时，归纳程序合成方法等同于通用归纳方法。
归纳程序合成的早期工作包括 Plotkin（1971）关于最一般归纳，Vera（1975）关于谓词演算的归纳算法，Summers（1977）关于归纳 Lisp 程序，以及 Shapiro（1983）关于归纳 Prolog 程序。最近对归纳程序合成的兴趣有所增长，部分原因是在现实世界问题中的应用，如最终用户编程（Gulwani, 2011）。归纳程序合成吸引了计算机科学许多领域的研究人员的兴趣，特别是机器学习和编程语言（PL）。ML 和 PL 方法之间的两个主要区别是（i）解决方案（合成程序）的通用性，以及（ii）噪声处理。PL 方法通常旨在找到符合规范的任何程序，无论它是否泛化。事实上，PL 方法很少评估他们的系统合成泛化解决方案的能力，即他们不测量预测准确性（Feser 等人，2015; Osera & Zdancewic, 2015; Albarghouthi 等人，2017; Si 等人，2018; Raghothaman 等人，2020）。相比之下，ML（因此 ILP）的主要挑战是学习泛化到未见例子的假设。事实上，对于给定问题，学习过于具体的解决方案通常是微不足道的。例如，ILP 系统可以为每个例子轻易地构造底部子句（Muggleton, 1995）。同样，噪声处理是 ML 的一个主要问题，但在 PL 文献中很少考虑。
除了 ILP，归纳程序合成在 ML 的许多领域都有研究，包括深度学习（Balog 等人，2017; Ellis 等人，2018, 2019）。神经方法的主要优势是它们可以处理有噪声的背景知识，正如 ∂ILP 所说明的，并且可以利用巨大的计算能力（Ellis 等人，2019）。然而，神经方法通常需要更多的例子（Reed & de Freitas, 2016; Dong 等人，2019）来学习符号 ILP 仅从少数几个例子中就能学习的概念。神经方法的另一个缺点是它们通常需要为每个领域手工制作神经架构。例如，REPL 方法（Ellis 等人，2019）需要为每个领域手工制作语法、解释器和神经架构。相比之下，因为 ILP 使用逻辑编程作为例子、背景知识和假设的统一表示，它可以轻松地应用于任意领域。
8.2 StarAI
由于 ILP 建立在逻辑程序和知识表示的逻辑基础上，ILP 也继承了它们的主要限制之一：无法处理不确定或错误的背景知识。为了克服这个限制，统计关系人工智能（StarAI）领域（De Raedt & Kersting, 2008b; De Raedt 等人，2016）将逻辑编程与概率推理结合起来。
StarAI 形式化允许用户通过用概率注释背景知识的部分来明确量化对背景知识正确性的信心。StarAI 语言中最简单的一种，也是直接建立在逻辑编程和 Prolog 上的一种，是基于分布语义的语言家族（Sato, 1995; Sato & Kameya, 2001; De Raedt 等人，2007）。Problog（De Raedt 等人，2007）是这个家族的杰出成员，它代表了对 Prolog 的最小扩展，支持这种随机执行。Problog 引入了两种类型的概率选择：概率事实和注释的析取。概率事实是 Problog 中最基本的随机单元。它们采用带有概率 p 的逻辑事实形式，表示以概率 p 为真，以概率 1 − p 为假的布尔随机变量。例如，以下概率事实表明那不勒斯发生地震的几率为 1%。
与确定性逻辑程序不同，在确定性逻辑程序中，如果事实被陈述为真，则总是为真，Problog 引擎在 SLD 解析（逻辑程序的主要执行原则）期间确定概率事实的真值分配。事实被认为是真还是假的频率由所述概率指导。对这一陈述的另一种解释是，执行概率程序的 1% 会观察到地震。而概率事实引入了事实层面的非确定性行为，注释的析取则在子句层面引入非确定性。注释的析取允许在头部有多个文字，但一次只能有一个头部文字为真。例如，以下注释的析取表明一个球可以是绿色、红色或蓝色，但不能是颜色的组合：
尽管 StarAI 框架允许存在错误的背景知识，但它们为学习增加了另一层复杂性：除了识别正确的程序（在 StarAI 中也称为结构）之外，学习任务还包括学习概率选择（也称为参数）的相应概率。学习概率逻辑程序在很大程度上还未被探索，只有少数现有方法（De Raedt 等人，2015; Bellodi & Riguzzi, 2015）。
8.3 神经 ILP
深度学习在各种任务上的成功促使研究人员探讨是否可以利用这些技术来解决 ILP 问题。这一研究方向之所以有趣，原因在于这些技术基于数值优化，如果成功，可以在无需组合搜索的情况下学习程序，而组合搜索正是 ILP 难解的核心原因。然而，为了利用这些技术，ILP 需要被表述为一个在固定变量集上的问题，这在 ILP 的假设空间是组合的且本质上是无限的情况下，可能并不自然。此外，将神经网络整合到 ILP 中可以使 ILP 处理非结构化数据，如图像和声音，以及与非结构化数据相关的噪声。虽然将 ILP 和程序合成与神经网络相结合是一个迅速发展的领域，但目前很少有方法直接解决 ILP 问题。
现有的大多数神经 ILP 系统将 ILP 问题重新表述为通过参数学习进行的结构学习。神经 ILP 技术通过假设整个假设空间是解决方案程序，而不是其中一个成员，使 ILP 问题适应数值优化。由于这样的解决方案程序几乎可以推导出任何东西，神经 ILP 技术放宽了蕴涵的概念。即，假设空间中的每个成员 c 都与一个估值 wc 相关联，指示 c 的蕴涵是正确的信心水平。由 c 蕴涵的一个事实被认为是具有估值 wc；一个事实的估值则是蕴涵该事实的所有 c 的估值之和。因此，蕴涵的概念失去了明确性，需要在连续谱中进行解释。学习任务则是拟合估值，使得正例具有较高估值，负例的估值较低，任何数值优化技术都可以用于此任务。这些技术通过限制复杂性使假设空间变为有限，从而只能学习语法上简单的程序（例如，最多包含两个文字和两个子句的程序）。这一范式的突出例子包括 ∂ILP、神经定理证明器（Rocktäschel & Riedel, 2017）、DiffLog（Si 等，2019）和 LRNN（Sourek 等，2018）。
截至发表时，只有一种方法可以同时学习训练神经网络来解决任务感官部分的逻辑程序（Dai & Muggleton, 2021）。Dai 和 Muggleton（Dai & Muggleton, 2021）通过一个归纳步骤（Flach & Hadjiantonis, 2013）扩展了 ILP，该步骤从背景知识和当前探索的程序中推导出训练神经网络的标签。作者展示了他们的框架能够从以图像表示的数字中学习算术和排序操作。这是一个尚未充分探索的研究方向，在使 ILP 更加能够处理噪声和非结构化数据方面充满潜力。
8.4 表示学习
如第5.5节所述，谓词发明predicate invention （PI）——通过引入以提供的谓词定义的新谓词符号来改变问题的表示——是 ILP 中的一个主要开放性挑战。谓词发明predicate invention （PI） 的目标与特征或表示学习（Bengio 等人，2013）的研究流派的目标相同，该流派起源于深度学习社区（LeCun 等人，2015）。表示学习旨在重新表示给定的数据，无论是图像还是关系知识库，在向量空间中保持某些语义属性。例如，要将知识库（指定为逻辑程序）表示在向量空间中，表示学习方法用向量替换每个常量和谓词，使得经常一起出现在事实中的常量的向量在向量空间中接近。这种表示变化的好处是，现在任何表格型机器学习方法都可以在复杂的关系结构上操作。表示学习的核心目标与 PI 背后的目标一致：通过改变问题的表示来提高学习性能。
尽管有强烈的联系，但 PI 和表示学习之间的互动很少。将表示学习中的思想转移到 PI 的主要挑战是它们不同的操作原理。目前尚不清楚如何通过当前表示学习方法使用的基于表格的学习原则来发明符号概念。只有少数方法（Dumančić & Blockeel, 2017; Dumančić 等人，2019; Sourek 等人，2018）从表示学习的核心思想出发，剥离它们的数值原理，并从符号原理重新发明它们。更常见的方法是将关系数据转换为可以作为神经网络输入的命题表格形式（Dash 等人，2018; Kaur 等人，2019, 2020）。后者方法的一个缺点是它们只适用于命题学习任务，不适用于无法命题化的一阶程序归纳任务。像 ∂ILP 和神经定理证明器（Rocktäschel & Riedel, 2017）这样迫使神经网络发明符号构造的方法，是通过牺牲逻辑的表达性来实现的（它们只能学习简短的 Datalog 程序）。
9. 总结和局限性
在十年前的一篇综述论文中，Muggleton 等人（2012）提出了未来研究的方向。自那时以来，这些方向中的许多领域都取得了重大进展，包括 PI（第5.5节）、使用高阶逻辑作为表示语言（第4.4.2节）和假设（第4.2.3节），以及在学习和策略学习应用（第7节）。我们认为，这些和其他最近的进展使 ILP 处于在未来十年对 AI 产生重大影响的有利位置，特别是为了解决标准形式的 ML 的关键局限性。然而，仍然有许多局限性是未来的工作应该解决的。
9.1 局限性
用户友好的系统。Muggleton 等人（2012）认为 ILP 的一个问题是缺乏精心设计的的工具。他们指出，尽管自 1991 年 ILP 成立以来已经构建了 100 多个 ILP 系统，但 ILP 研究人员能够有意义使用的系统不足一手之数。一个原因是 ILP 系统通常只设计为原型，并且往往没有经过良好的工程化或维护。另一个主要问题是 ILP 系统出了名的难以使用：通常需要拥有 ILP 博士学位才能使用任何工具。即便如此，通常也只有系统的开发者才知道如何正确使用它。这种使用难度由于 ILP 系统通常使用许多不同的偏见或甚至对相同偏见使用不同的语法而加剧。例如，尽管它们都使用模式声明，但在 Progol、Aleph、TILDE 和 ILASP 中指定学习任务的方式差异很大。如果 ILP 研究人员使用 ILP 工具都很困难，那么非 ILP 研究人员又有什么希望呢？为了让 ILP 在学术界内外更广泛地被采用，我们必须开发更加标准化、用户友好和更好的工程化工具。
语言偏见。ILP 允许用户提供背景知识和语言偏见。两者都是重要且强大的特性，但只有正确使用时才是如此。例如，Metagol 利用元规则（第 4.4.2 节）来限制假设的语法，从而限制假设空间。如果用户能够提供合适的元规则，那么 Metagol 就极其高效。然而，如果用户无法提供合适的元规则（这通常是情况），那么 Metagol 几乎无用。这种脆弱性也适用于使用模式声明的 ILP 系统（第 4.4.1 节）。理论上，用户可以提供非常通用的模式声明，例如只使用单一类型并允许无限回溯。然而，实际上，弱模式声明通常会导致非常差的性能。为了获得良好的性能，基于模式的系统的用户通常需要手动分析给定的学习任务，以调整模式声明，通常是通过试错的过程。此外，如果用户在模式声明中犯了一个小错误，例如给出了错误的参数类型，那么 ILP 系统就不太可能找到一个好的解决方案。这种对几乎完美的语言偏见的需求严重阻碍了 ILP 的广泛采用。为了解决这个局限性，我们认为未来工作的一个重要方向是开发自动识别合适的语言偏见的技术。尽管有关模式学习（McCreath & Sharma, 1995; Ferilli 等人，2004; Picado 等人，2017）和识别合适元规则（Cropper & Tourret, 2020）的工作，但这个研究领域在很大程度上还没有得到充分研究。
PI 和抽象。Russell（2019）认为，自动发明新的高层概念是达到人类水平 AI 所需的最重要步骤。PI 的新方法（第 5.5 节）提高了 ILP 发明这种高层概念的能力。然而，PI 仍然很困难，并且有许多挑战需要克服。例如，在归纳通用游戏玩法（Cropper 等人，2020b）中，任务是从游戏玩法的观察中学习符号规则，例如学习四子棋的规则。游戏的参考解决方案来自通用游戏玩法竞赛（Genesereth & Björnsson, 2013），通常包含辅助谓词以使它们更简单。例如，四子棋的规则是依据线条的定义来定义的，而这些线条本身又是依据列、行和对角线来定义的。尽管这些辅助谓词并不是学习参考解决方案所必需的，但发明这样的谓词显著减少了解决方案的大小（有时是数量级的减少），这反过来使它们更容易学习。尽管 PI 的新方法（第 5.5 节）可以发明高层概念，但它们还没有足够的能力在 IGGP 数据集上表现良好。在这个领域取得进展将构成 ILP 的一个重大进步，也是迈向人类水平 AI 的一个重要步骤。
终身学习。由于其符号表示，ILP 的一个关键优势是学习到的知识可以被记忆并明确地存储在背景知识中。因此，ILP 自然支持终身学习（Silver 等人，2013）、多任务学习（Caruana, 1997）和迁移学习（Torrey & Shavlik, 2009），这些被认为是类人 AI 所必需的（Lake 等人，2016）。所有这些方法背后的一般思想是重用解决一个问题所获得的知识来帮助解决一个不同的问题。尽管 ILP 的早期工作探索了这种形式的学习（Sammut, 1981; Quinlan, 1990），但直到最近（Lin 等人，2014; Cropper, 2019, 2020; Hocquette & Muggleton, 2020; Dumancic 等人，2021），由于 PI 的新技术，它才得到较少的探索。例如，Lin 等人（2014）随着时间的推移学习了 17 个字符串转换程序，并展示了他们的多任务方法比单一任务方法表现更好，因为经常重用已学习的程序。然而，这些方法只在少量任务上得到了证明。要达到类人 AI，我们期望学习器学习数千甚至数百万的概念。但是，处理数千个任务的复杂性是具有挑战性的，因为正如我们在第 4.3 节中解释的，ILP 系统难以处理大量的背景知识。这种情况导致了灾难性记忆问题（Cropper, 2020）：学习器无法忘记知识。尽管有关这个话题的初步工作（Cropper, 2020），我们认为未来工作的一个关键领域是处理终身学习的复杂性。
相关性。灾难性记忆问题本质上是相关性问题：给定一个带有大量背景知识的新 ILP 问题，ILP 系统如何决定哪些背景知识是相关的？尽管过多的不相关背景知识对学习性能有害（Srinivasan 等人，1995, 2003），但在 ILP 中几乎没有工作试图识别相关的背景知识。一种新兴技术是训练一个神经网络来评估背景知识中的程序的相关性，然后只使用得分最高的背景知识来学习程序（Balog 等人，2017; Ellis 等人，2018）。然而，这种方法的经验有效性尚未得到明确证明。此外，这些方法只在少量背景知识上得到了证明，它们如何扩展到包含数千个关系的背景知识尚不清楚。没有有效的相关性方法，终身学习如何实现还不清楚。
有噪声的背景知识。与终身学习相关的另一个问题是将学习到的程序添加到背景知识中所固有的不确定性。根据归纳的固有性质，归纳出的程序不能保证是正确的（即，预计是有噪声的），但它们是后续归纳的构建块。在其他有噪声的程序之上构建有噪声的程序可能会导致学习到的程序最终不连贯。这个问题尤其成问题，因为如第5.1节所述，大多数 ILP 方法假设背景知识是无噪声的，即一个关系是真或假，没有任何不确定性的余地。∂ILP 的一个吸引人的特性是它采用了一种可微分的 ILP 方法，它可以提供模糊或不明确的数据。开发类似的技术来处理有噪声的背景知识是 ILP 中一个尚未充分研究的话题。
概率 ILP。处理噪声的一个原则性方法是统一逻辑和概率推理，这是统计关系人工智能（StarAI）的重点（De Raedt 等人，2016）。虽然 StarAI 是一个不断发展的领域，但诱导概率逻辑程序却鲜有关注，只有少数值得注意的例外（Bellodi & Riguzzi, 2015; De Raedt 等人，2015），因为推理仍然是主要挑战。解决这个问题，即在归纳环境中统一概率和逻辑，将是一个重大成就（Marcus, 2018）。
可解释性。可解释性是符号表示所声称的优势之一。最近的工作（Muggleton 等人，2018; Ai 等人，2021）使用 Michie（1988）的超强 ML 框架评估 ILP 假设的可理解性，其中期望学习到的假设不仅准确，而且能够明显提高人类在获得学习到的假设后的表现。Muggleton 等人（2018）通过学习到的假设直接经验性地证明了人类理解的提高。然而，需要更多的工作来更好地理解在何种条件下可以实现这一点，特别是鉴于 PI 的兴起。
从原始数据中学习。大多数 ILP 系统需要完美符号形式的数据。然而，许多现实世界的数据，如图像和语音，不能轻易地转换为符号形式。也许 ILP 面临的最大挑战是如何学习感知感官输入并学习一个符号逻辑程序来解释输入。例如，考虑一个从 MNIST 数字中学习执行加法的任务。当前的 ILP 系统需要作为背景知识给出数字的符号表示，这可以通过首先训练一个神经网络来识别数字来实现。理想情况下，我们不希望将这两个问题分开处理，而是同时学习如何识别数字和学习执行加法的程序。一些方法已经开始解决这个问题（Manhaeve 等人，2018; Dai 等人，2019; Evans 等人，2021; Dai & Muggleton, 2021），但开发更好的 ILP 技术，既能感知感官输入又能学习复杂的关系程序，将不仅是对 ILP，而且对整个 AI 领域的重大突破。
进一步阅读
对于逻辑和自动推理基础的介绍，我们推荐 Harrison（2009）的书籍。要更多地了解 ILP，我们建议从 Muggleton（1991）的创立性论文和随后不久的综述论文（Muggleton & De Raedt, 1994）开始。对于 ILP 理论的详细阐述，我们彻底推荐 Nienhuys-Cheng 和 Wolf（1997）以及 De Raedt（2008）的书籍。
https://arxiv.org/pdf/2008.07912
