讯享网

 <p id="303L2HN6">同作者内容：</p><p id="303L2HN8">Inductive Logic Programming At 30: A New Introduction</p><p id="303L2HNA"><strong> ILP系统 是出了名的难用：通常需要拥有 ILP 博士学位才能使用相关工具</strong></p><p id="303L2HNC"><strong>自动发明新高层概念是达到人类水平人工智能所需的最重要步骤</strong></p><p id="303L2HND"><strong><strong><strong>谓词发明predicate invention （PI）</strong> 的目标与特征或表示学习（Bengio 等人，2013）的研究流派的目标相同，该流派起源于深度学习社区</strong></strong></p><p id="303L2HNE"><strong>如果一个子句没有蕴含一个正面示例，那么就没有必要探索它的任何特化，因为它们在逻辑上不可能蕴含该示例</strong>。同样，<strong>如果一个子句蕴含了一个负面示例，那么就没有必要探索它的任何泛化，因为它们也会蕴含该示例。</strong></p><p class="f_center"><img src="https://nimg.ws.126.net/?url=http%3A%2F%2Fdingyue.ws.126.net%2F2024%2F0903%2F00e27350j00sj70yx003pd200u000e3g00u000e3.jpg&thumbnail=660x&quality=80&type=jpg"/><br/></p><p class="f_center"><img src="https://nimg.ws.126.net/?url=http%3A%2F%2Fdingyue.ws.126.net%2F2024%2F0903%2Fb7j00sj70yy004md200u0008yg00u0008y.jpg&thumbnail=660x&quality=80&type=jpg"/><br/></p><p class="f_center"><img src="https://nimg.ws.126.net/?url=http%3A%2F%2Fdingyue.ws.126.net%2F2024%2F0903%2F14ab44f4j00sj70z000gnd200u000rug00u000ru.jpg&thumbnail=660x&quality=80&type=jpg"/><br/></p><p id="303L2HNL"><strong><strong><br/></strong></strong></p><p id="303L2HNM"><strong>摘要</strong><br/></p><p id="303L2HNN">归纳逻辑编程（<strong>ILP</strong>）是一种机器学习方法。ILP的目标是<strong>归纳出能够概括训练示例的假设（一组逻辑规则）。</strong>随着ILP迎来30周年，我们为这个领域提供了一个新的介绍。我们介绍了<strong>必要的逻辑符号和主要的学习设置；</strong>描述了一个ILP系统的构建模块；在几个维度上比较了几个系统；描述了四个系统（Aleph、TILDE、ASPAL和Metagol）；强调了关键的应用领域；最后，总结了当前的局限性和未来研究的方向。</p><p id="303L2HNO"><strong>1. 引言</strong><br/></p><p id="303L2HNP">人类智能的一个显著成就是学习知识的能力。<strong>学习的一种关键形式是归纳：从特定观察（示例）中形成一般规则（假设）的过程</strong>。例如，假设你从一个袋子里拿出10个红色球，然后你可能会归纳出一个假设（规则），即袋子里的所有球都是红色的。<strong>归纳出这个假设后，你可以预测袋子里下一个球的颜色。</strong></p><p id="303L2HNQ">机器学习（ML）自动化了归纳过程。ML归纳出一个能够概括训练示例（观察）的假设（也称为模型）。例如，给定标记为猫和狗的图像，ML的目标是归纳出一个假设，该假设可以预测未标记图像是猫还是狗。<strong>归纳逻辑编程（ILP）（Muggleton，1991）是一种ML形式。与其他ML形式一样，ILP的目标是归纳出能够概括训练示例的假设。然而，大多数ML形式使用表格来表示数据（示例和假设），而ILP使用逻辑程序（逻辑规则集）。</strong>此外，大多数ML形式<strong>学习函数</strong>，<strong>而ILP学习关系。</strong>我们使用四个场景来说明ILP。<br/></p><p id="303L2HNR"><strong>1.1 场景1：概念学习</strong><br/></p><p id="303L2HNS">假设我们想要预测某人是否快乐。为此，我们询问四个人（alice、bob、claire和dave）他们是否快乐。我们还要求提供额外的信息，具体来说，是他们的工作、公司以及他们是否喜欢乐高。许多ML方法，如决策树或神经网络学习器，会将这些数据表示为表格，如表1。使用标准ML术语，每一行代表一个训练示例，前三列（姓名、工作和喜欢乐高）代表特征，最后一列（快乐）代表标签或分类。给定这个表格作为输入，目标是归纳出一个概括训练示例的假设。例如，神经网络学习器将学习一个数字表格，这些数字衡量了特征（或多层网络中的隐藏特征）的重要性。然后我们可以使用假设来预测未见示例的标签。</p><p class="f_center"><img src="https://nimg.ws.126.net/?url=http%3A%2F%2Fdingyue.ws.126.net%2F2024%2F0903%2F23b6c98cj00sj70z1001dd200lm007ug00lm007u.jpg&thumbnail=660x&quality=80&type=jpg"/><br/></p><p id="303L2HNU">与将数据表示为表格不同，<strong>ILP将数据表示为逻辑程序，即逻辑规则集。逻辑程序的主要构建块是原子（atom）。原子的形式为 p(x1, ..., xn)，</strong>其中p是n元的谓词符号（接受n个参数），每个xi是一个项（term）。逻辑程序使用原子来表示数据。例如，我们可以将“alice喜欢乐高”表示为原子 enjoys_lego(alice)，将“bob是乐高建造者”表示为 lego_builder(bob)。</p><p id="303L2HNV">一个ILP任务由三组<strong>（B, E+, E-）构成。集合B是背景知识（Background Knowledge, BK）。BK类似于特征，</strong>但可以包含与示例间接相关的信息和关系。我们可以将表1中的数据表示为集合B：</p><p class="f_center"><img src="https://nimg.ws.126.net/?url=http%3A%2F%2Fdingyue.ws.126.net%2F2024%2F0903%2Fd70d2a1cj00sj70z1001hd200nq005ug00nq005u.jpg&thumbnail=660x&quality=80&type=jpg"/><br/></p><p id="303L2HO1">ILP通常遵循<strong>封闭世界假设（Reiter, 1977），所以如果有任何事物没有明确为真，我们就假设它是假的</strong>。有了这个假设，我们不需要明确指出enjoys_lego(bob)和enjoys_lego(dave)是假的。<br/></p><p id="303L2HO2">集合E+和E-分别代表正面和负面示例。我们可以将表1中的示例表示为：<br/></p><p class="f_center"><img src="https://nimg.ws.126.net/?url=http%3A%2F%2Fdingyue.ws.126.net%2F2024%2F0903%2Fbb180db3p00sj70z2000nd200o20038g00o20038.png&thumbnail=660x&quality=80&type=jpg"/><br/></p><p id="303L2HO4">给定这些集合，ILP的目标是归纳出一个假设，该假设与背景知识（BK）一起，在逻辑上能够蕴含尽可能多的正面示例和尽可能少的负面示例。在ILP中，一个假设（H）是一组逻辑规则，例如：<br/></p><p id="303L2HO5">这个假设包含一条规则，该规则表明对于所有的A，如果A是乐高建造者（lego_builder(A)）并且喜欢乐高（enjoys_lego(A)），那么A是快乐的（happy(A)）。<strong>归纳出一条规则后，我们可以从中推导出知识</strong>。例如，这条规则表明如果lego_builder(alice)和enjoys_lego(alice)为真，那么happy(alice)也必须为真。<br/></p><p id="303L2HO6">上述规则是用标准一阶逻辑符号书写的。我们通常以<strong>逆蕴涵形式书写逻辑程序：</strong><br/></p><p id="303L2HO7">以这种形式的规则表明，当每个bodyi原子为真时，头原子为真。逗号表示合取（逻辑与）。在逻辑编程中，每个变量都被假定为全称量化的，因此我们<strong>省略了量词。我们还翻转了蕴涵符号的方向 → 到 ←，并且经常用 :- 替换它，</strong>因为在编写计算机程序时更容易使用。因此，在逻辑编程符号中，上述假设是：<br/></p><p class="f_center"><img src="https://nimg.ws.126.net/?url=http%3A%2F%2Fdingyue.ws.126.net%2F2024%2F0903%2Fb573fc1bj00sj70z30043d200u0005ig00u0005i.jpg&thumbnail=660x&quality=80&type=jpg"/><br/></p><p id="303L2HO9"><strong>1.2 场景2：数据整理</strong><br/></p><p id="303L2HOA">假设我们想要从输入 ↦→ 输出示例中学习字符串转换程序，例如返回字符串最后一个字符的程序：<br/></p><p class="f_center"><img src="https://nimg.ws.126.net/?url=http%3A%2F%2Fdingyue.ws.126.net%2F2024%2F0903%2F70fdab94j00sj70z4000fd200m8004kg00m8004k.jpg&thumbnail=660x&quality=80&type=jpg"/><br/></p><p id="303L2HOC">许多形式的机器学习（ML）会将这些示例表示为表格，例如使用一种独热编码one hot技术。相比之下，ILP将这些示例表示为原子，例如：</p><p class="f_center"><img src="https://nimg.ws.126.net/?url=http%3A%2F%2Fdingyue.ws.126.net%2F2024%2F0903%2Fb4c4ec10p00sj70z5000od200ng0034g00ng0034.png&thumbnail=660x&quality=80&type=jpg"/><br/></p><p id="303L2HOE">符号 `last` 是我们想要学习的目標谓词（要概括的关系）。每个原子的第一个参数代表输入列表，第二个参数代表输出值。为了归纳出这些示例的假设，我们需要提供合适的背景知识（BK），例如常见的列表操作：<br/></p><p class="f_center"><img src="https://nimg.ws.126.net/?url=http%3A%2F%2Fdingyue.ws.126.net%2F2024%2F0903%2Fac8b7892j00sj70z50019d200q4004yg00q4004y.jpg&thumbnail=660x&quality=80&type=jpg"/><br/></p><p id="303L2HOG">给定上述示例和包含上述列表操作的<strong>BK，目标是搜索能够概括这些示例的假设。在高层次上，ILP系统通过结合BK和示例中的信息来构建假设。所有可能假设的集合称为假设空间。换句话说，ILP系统的目标是在假设空间中搜索能够概括示例的假设。</strong><br/></p><p id="303L2HOH">在这个数据整理场景中，ILP系统可以归纳出以下假设</p><p class="f_center"><img src="https://nimg.ws.126.net/?url=http%3A%2F%2Fdingyue.ws.126.net%2F2024%2F0903%2Fb95121b5p00sj70z6000ld200pe002og00pe002o.png&thumbnail=660x&quality=80&type=jpg"/><br/></p><p id="303L2HOJ">这个假设包含两条规则。第一条规则表明，当B是A的头部，且A的尾部为空时，B是A的最后一个元素。第二条规则表明，当B是A的尾部的最后一个元素时，B也是A的最后一个元素。<br/></p><p id="303L2HOK"><strong>1.3 场景3：程序合成</strong><br/></p><p id="303L2HOL">假设我们有以下正面和负面示例，同样以原子的形式表示，其中第一个参数是未排序的列表，第二个参数是排序后的列表：<br/></p><p class="f_center"><img src="https://nimg.ws.126.net/?url=http%3A%2F%2Fdingyue.ws.126.net%2F2024%2F0903%2Fc3a1ad7cp00sj70z6000id200pu002kg00pu002k.png&thumbnail=660x&quality=80&type=jpg"/><br/></p><p id="303L2HON">同样假设作为背景知识（BK），我们有字符串转换场景中相同的empty、head和tail关系，以及两个额外的关系：<br/></p><p class="f_center"><img src="https://nimg.ws.126.net/?url=http%3A%2F%2Fdingyue.ws.126.net%2F2024%2F0903%2F5d9d36b7j00sj70z7006vd200u000bwg00u000bw.jpg&thumbnail=660x&quality=80&type=jpg"/><br/></p><p id="303L2HOP"><strong>这个假设对应于快速排序算法（Hoare, 1961），它概括了任意长度的列表和训练示例中未出现的元素。这个场景展示了ILP是一种程序合成（Shapiro, 1983）的形式，其目标是自动构建可执行的程序。</strong><br/></p><p id="303L2HOQ"><strong>1.4情景4:科学发现</strong><br/></p><p id="303L2HOR">正如Srinivasan等人（1994年）所述，“科学理论的制定不仅仅是数据拟合。为了被接受，一个理论必须是可理解的，并且可以进行批判性分析。” 因此，ILP已被广泛用于科学发现。例如，King等人（1992年）使用ILP模拟药物设计中的结构-活性关系。在这项工作中，ILP系统以正面和负面示例以及背景知识（BK）作为输入。正面示例是活性更高的配对示例。例如，<strong>正面示例great(d20,d15)表示药物20的活性高于药物</strong>15。<strong>负面示例是活性较低的药物配对示例</strong>。<strong>背景知识包含有关药物化学结构和取代基团属性的信息</strong>。例如，原子struc(d35,no2,nhcoch3,h)表示药物35在位置3有no2取代，在位置4有nhcoch3取代，在位置5没有取代，原子flex(no2,3)表示no2的灵活性为3。给定这样的示例和背景知识，ILP系统Golem（Muggleton &amp; Feng, 1990）归纳出多个规则来解释示例，包括这一条：<br/></p><p class="f_center"><img src="https://nimg.ws.126.net/?url=http%3A%2F%2Fdingyue.ws.126.net%2F2024%2F0903%2F425f0289p00sj70z7000td200qg003gg00qg003g.png&thumbnail=660x&quality=80&type=jpg"/><br/></p><p id="303L2HOT">这条规则表明，如果药物B在位置4和5没有取代基团，药物B在位置3的灵活性大于6，药物A在位置3的极化率等于1，药物A在位置3有氢键供体等于0，并且药物A在位置3的灵活性小于药物B在位置3的灵活性，那么药物A就优于药物B。<br/></p><p id="303L2HOU">正如这个场景所说明的，<strong>ILP可以学习人类可读的假设。这些规则的可解释性对于让领域专家获得洞察至关重要。</strong><br/></p><p id="303L2HOV"><strong>1.5 为什么选择ILP？</strong><br/></p><p id="303L2HP0">大多数机器学习方法依赖于统计推断。相比之下，ILP依赖于逻辑推断，并使用来自自动推理和知识表示的技术。表2显示了ILP和统计机器学习方法之间的简化比较。我们简要讨论这些差异。<br/></p><p class="f_center"><img src="https://nimg.ws.126.net/?url=http%3A%2F%2Fdingyue.ws.126.net%2F2024%2F0903%2Fb7j00sj70yy004md200u0008yg00u0008y.jpg&thumbnail=660x&quality=80&type=jpg"/><br/></p><p id="303L2HP2"><strong>例子</strong>。许多形式的机器学习因其无法从少量训练示例中泛化而臭名昭著，尤其是深度学习（Marcus, 2018; Chollet, 2019; Bengio et al., 2019）。正如Evans和Grefenstette（2018）所指出的，如果我们训练一个神经系统用10位数字进行加法，它可以泛化到20位数字，但当在100位数字上进行测试时，<strong>预测准确性急剧下降（Reed &amp; de Freitas, 2016; Kaiser &amp; Sutskever, 2016）。相比之下，ILP可以从少量示例中归纳出假设，通常从一个示例中就可以</strong>（Lin et al., 2014; Muggleton et al., 2018）。当我们只有少量训练数据时，这种<strong>数据效率非常重要</strong>。例如，Gulwani（2011）应用类似于ILP的技术，通过用户提供的Microsoft Excel示例来归纳程序，以解决字符串转换问题，在这种情况下，要求用户提供成千上万的示例是不可行的。这种数据效率使得ILP在许多实际应用中变得有吸引力，特别是在药物设计中，大量示例并不总是容易获得。<br/></p><p id="303L2HP3"><strong>数据</strong>。使用逻辑程序来表示数据允许<strong>ILP学习复杂的关系信息，并轻松整合专家知</strong>识。例如，在学习因果网络中的因果关系时，用户可以编码有关网络的约束（Inoue等人，2013）。如果学习识别事件，用户可以提供事件演算的公理（Katzouris等人，2015）。关系背景知识允许我们<strong>简洁地表示无限关系。例如，定义自然数无限集上的求和关系</strong>（add(A,B,C):- C = A+B）是微不足道的。相比之下，基于表格的机器学习方法大多限于有限数据，无法表示这些信息。例如，我们无法为决策树学习器（Quinlan，1986, 1993）提供这个无限关系，因为这将需要一个无限的特征表。即使我们将自己限制在有限的n个自然数集上，基于表格的方法仍然需要n^3个特征来表示完整的求和关系。<br/></p><p id="303L2HP4"><strong>假设。</strong>由于与关系数据库密切相关，<strong>逻辑程序自然支持关系数据，如图形</strong>。由于<strong>逻辑程序的表达能力，ILP可以学习复杂的关系理论，例如元胞自动机</strong>（Inoue等人，2014；Evans等人，2021）、<strong>事件演算理论</strong>（Katzouris等人，2015）和<strong>Petri网</strong>（Bain &amp; Srinivasan，2018），以及各种形式的非单调程序（Bain &amp; Muggleton，1991；Inoue &amp; Kudoh，1997；Sakama，2001）。由于逻辑程序的<strong>符号性质，ILP可以对假设进行推理，这允许它学习最优程序，例如最小时间复杂度程序</strong>（Cropper &amp; Muggleton，2019）和安全访问控制策略（Law等人，2020）。此外，<strong>由于归纳出的假设与背景知识使用相同的语言，它们可以存储在背景知识中，使迁移学习变得微</strong>不足道（Lin等人，2014）。<br/></p><p id="303L2HP5"><strong>可解释性</strong>。由于逻辑与自然语言的相似性，逻辑程序可以被人类轻松阅读，这对于可解释的AI至关重要。由于这种可解释性，ILP长期以来一直被用于科学发现（King等人，1992；Srinivasan等人，1996, 1997, 2006；Kaalia等人，2016）。例如，机器人科学家（King等人，2004）是一个使用ILP生成假设以解释数据的系统，它还可以自动设计实验来测试假设，实际运行实验，解释结果，然后重复该循环。在研究基于酵母的功能基因组学时，<strong>机器人科学家成为第一台独立发现新科学知识的机器（King等人，2009）。</strong><br/></p><p id="303L2HP6"><strong>知识转移</strong>。大多数机器学习算法是单任务学习器，无法重用学到的知识。例如，尽管AlphaGo（Silver等人，2016）具有超人的围棋能力，但它不能重用这些知识来玩其他游戏，也不能在略有不同的棋盘上玩同一个游戏。相比之下，由于其符号表示，<strong>ILP自然支持终身学习和迁移学习</strong>（Torrey等人，2007；Cropper，2019），这被认为是类人AI所必需的（Lake等人，2016）。例如，在归纳一组字符串转换任务的解决方案时，如场景2中的任务，Lin等人（2014）表明，ILP系统可以自动识别出更简单的问题来解决，学习它们的程序，然后重用学到的程序来帮助学习更复杂问题的程序。此外，他们表明，<strong>这种知识转移方法导致了可重用程序的层次结构，每个程序都建立在更简单程序的基础上。</strong><br/></p><p id="303L2HP7"><strong>1.6 ILP如何工作？</strong><br/></p><p id="303L2HP8">构建一个ILP系统（图1）需要做出几个选择或假设。理解这些假设是理解ILP的关键。我们在第4节中讨论了这些假设，但现在简要总结它们：</p><p class="f_center"><img src="https://nimg.ws.126.net/?url=http%3A%2F%2Fdingyue.ws.126.net%2F2024%2F0903%2Fc24bfd53j00sj70z9006ed200u000bxg00u000bx.jpg&thumbnail=660x&quality=80&type=jpg"/><br/></p><p id="303L2HPA">学习设置。核心选择是如何表示示例。本节场景中的示例包括布尔概念（lego_builder）和输入输出示例（字符串转换和排序）。尽管布尔概念和输入输出示例是常见的表示，<strong>但还有其他表示，如解释（Blockeel &amp; De Raedt, 1998）和转换（Inoue et al., 2014）。表示决定了学习设置</strong>，进而定义了程序解决ILP问题的含义。<br/></p><p id="303L2HPB"><strong>表示语言。</strong>ILP将数据表示为逻辑程序。然而，<strong>有许多逻辑编程语言，每种语言都有其优点和缺点。例如，Prolog是一种图灵完备的逻辑编程语言。Datalog是Prolog的语法子集，它牺牲了特征（如数据结构）和表达能力（它不是图灵完备的）以获得效率和可判定性。一些语言支持非单调推理，如答案集编程ASP</strong>（Gebser et al., 2012）。选择合适的表示语言对于确定系统能够解决的问题至关重要。<br/></p><p id="303L2HPC"><strong>定义假设空间</strong>。基本的ILP问题是在假设空间中搜索合适的假设。<strong>假设空间包含在所选表示语言中可以构建的所有可能程序。如果不加限制，假设空间是无限的，因此限制它是使搜索可行的关键。与所有机器学习技术一样，ILP通过实施归纳偏好</strong>（Mitchell, 1997）来限制假设空间。<strong>语言偏好对假设实施限制，如假设中可以有多少变量或关系。</strong>选择合适的语言偏好对于高效学习和是一个主要挑战是必要的。<br/></p><p id="303L2HPD"><strong>搜索方法</strong>。在定义了假设空间之后，问题是如何有效地搜索它。传统的分类方法是它们是否使用<strong>自顶向下或自底向上的搜索</strong>，其中泛化顺序搜索空间7。自顶向下方法（Quinlan, 1990; Blockeel &amp; De Raedt, 1998; Bratko,1999; Muggleton et al., 2008; Ribeiro &amp; Inoue, 2014）<strong>从过于泛化的假设开始，试图对其进行专业化</strong>。自底向上方法（Muggleton, 1987; Muggleton &amp; Buntine, 1988; Muggleton &amp; Feng, 1990; Inoue et al., 2014）<strong>从过于具体的假设开始，试图对其进行概括</strong>。一些方法结合了两者（Muggleton, 1995; Srinivasan, 2001; Cropper, 2022）。<strong>最近出现了第三种方法，称为元级IL</strong>P（Inoue et al., 2013; Muggleton et al., 2015; Inoue, 2016; Law et al., 2020; <strong>Cropper &amp; Morel, 2021）。这种方法将ILP问题表示为元级逻辑程序，即推理程序的程序。元级方法通常将搜索假设的任务委托给现成的求解器</strong>（Corapi et al., 2011; Muggleton et al., 2014; Law et al., 2014; Kaminski et al., 2018; Evans et al., 2021; Cropper &amp; Morel, 2021），之后将元级解决方案翻译回ILP问题的标凈解决方案。<br/></p><p id="303L2HPE"><strong>1.7 简史</strong><br/></p><p id="303L2HPF">ILP是一种机器学习形式，这让很多只将机器学习与统计技术联系在一起的研究人员感到惊讶。然而，如果我们遵循Mitchell（1997）对机器学习的定义，那么ILP与其他机器学习方法没有什么不同：随着更多示例的提供，它会得到改进。这种混淆似乎来自于ILP使用逻辑作为学习的表示。然而，正如Domingos（2015）所指出的，</p><p id="303L2HPG"><strong><strong>图灵可以被视为第一个符号主义者之一</strong></strong>，因为他提出了使用逻辑表示来构建思考机器（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 &amp; Buntine, 1988），这也是最早的谓词发明方法之一。ILP作为一个领域是由Muggleton（1991）创立的，他指出它位于机器学习和知识表示的交汇处。</p><p id="303L2HPH"><strong>1.8 贡献</strong><br/></p><p id="303L2HPI">已经有几篇优秀的ILP综述论文（Sammut, 1993; Muggleton &amp; De Raedt, 1994; Muggleton, 1999a; Page &amp; Srinivasan, 2003; Muggleton et al., 2012）和书籍（Nienhuys-Cheng &amp; Wolf, 1997; De Raedt, 2008）。在本文中，我们希望为对符号学习感兴趣的通用AI读者提供一个针对该领域的新介绍。我们与现有综述的不同之处在于包括并主要关注最近的发展（Cropper et al., 2020a），例如学习递归程序、谓词发明和元级搜索的新方法。虽然我们涵盖了诱导Datalog和答案集程序的工作，但我们主要关注诱导确定性程序的方法，特别是Prolog程序。我们不详细讨论将神经网络与ILP结合的工作，因为已经有合适的综述论文（d’Avila Garcez et al., 2019; Raedt et al., 2020）。<br/></p><p id="303L2HPJ">本文的其余部分组织如下：<br/></p><p id="303L2HPK">• 我们描述必要的逻辑编程符号（第2节）。</p><p id="303L2HPL">• 我们定义标准的ILP学习设置（第3节）。</p><p id="303L2HPM">• 我们描述构建ILP系统所需的基本假设（第4节）。</p><p id="303L2HPN">• 我们比较多个ILP系统并描述它们支持的功能（第5节）。</p><p id="303L2HPO">• 我们详细描述了四个ILP系统（Aleph、TILDE、ASPAL和Metagol）（第6节）。</p><p id="303L2HPP">• 我们总结了ILP的一些关键应用领域（第7节）。</p><p id="303L2HPQ">• 我们简要调查相关工作（第8节）。</p><p id="303L2HPR">• 我们通过概述ILP的主要当前局限性并为未来研究提出方向来结束（第9节）。</p><p id="303L2HPT"><strong>2. 逻辑编程</strong><br/></p><p id="303L2HPU">ILP使用逻辑程序（Kowalski, 1974）来表示背景知识（BK）、示例和假设。逻辑程序与命令式程序（例如C、Java、Python）有根本的不同，也与功能性程序（例如Haskell、OCaml）非常不同。命令式编程将程序视为一系列逐步的指令，其中计算是执行指令的过程。相比之下，逻辑编程将程序视为逻辑理论（一组逻辑规则），其中计算是对该理论的各种形式的演绎，例如搜索证明、反驳或其模型。</p><p id="303L2HPV">另一个主要区别是逻辑程序是声明式的（Lloyd, 1994），因为它允许用户陈述程序应该做什么，而不是它应该如何工作。这种声明性质意味着逻辑程序中规则的顺序（通常）不重要。</p><p id="303L2HQ0">在本节的剩余部分，我们将介绍理解本文其余部分所必需的逻辑编程的基础知识。我们涵盖了语法和语义，并简要介绍了不同的逻辑编程语言。我们重点介绍理解ILP所必需的概念，并将读者引向更详细的逻辑编程（Nienhuys-Cheng &amp; Wolf, 1997; De Raedt, 2008; Lloyd, 2012）、Prolog（Sterling &amp; Shapiro, 1994; Bratko, 2012）和ASP（Gebser et al., 2012）的阐述，以获取更多信息。因此，我们省略了逻辑编程中许多重要概念的描述，例如分层否定。熟悉逻辑的读者可以跳过这一节。<br/></p><p id="303L2HQ1"><strong>2.1 语法</strong><br/></p><p class="f_center"><img src="https://nimg.ws.126.net/?url=http%3A%2F%2Fdingyue.ws.126.net%2F2024%2F0903%2Fb144e22dj00sj70zc00lid200u0016dg00u0016d.jpg&thumbnail=660x&quality=80&type=jpg"/><br/></p><p id="303L2HQ3">。。。。。。</p><p class="f_center"><img src="https://nimg.ws.126.net/?url=http%3A%2F%2Fdingyue.ws.126.net%2F2024%2F0903%2Fcaj00sj70ze00hjd200u0014sg00u0014s.jpg&thumbnail=660x&quality=80&type=jpg"/><br/></p><p id="303L2HQ5">。。。</p><p class="f_center"><img src="https://nimg.ws.126.net/?url=http%3A%2F%2Fdingyue.ws.126.net%2F2024%2F0903%2Fbdf49d40j00sj70zg0094d200u000xug00u000xu.jpg&thumbnail=660x&quality=80&type=jpg"/><br/></p><p id="303L2HQ7">。。。。</p><p class="f_center"><img src="https://nimg.ws.126.net/?url=http%3A%2F%2Fdingyue.ws.126.net%2F2024%2F0903%2F91cc3020j00sj70zi001sd200h400pmg00h400pm.jpg&thumbnail=660x&quality=80&type=jpg"/><br/></p><p id="303L2HQ9"><strong>4. 构建ILP系统</strong></p><p id="303L2HQA">构建ILP系统需要做出几个选择或假设，这些是学习器归纳偏好的一部分。归纳偏好是必不可少的，所有机器学习方法都施加了归纳偏好（Mitchell, 1997）。理解这些假设是理解ILP的关键。这些选择可以分为：</p><p id="303L2HQB"><strong>• 学习设置：如何表示示例</strong></p><p id="303L2HQC"><strong>• 表示语言：如何表示背景知识和假设</strong></p><p id="303L2HQD"><strong>• 语言偏好：如何定义假设空间</strong></p><p id="303L2HQE"><strong>• 搜索方法：如何在假设空间中搜索</strong></p><p id="303L2HQF">表3显示了一些系统的假设。这个表格排除了许多重要的系统，包括交互式系统，如Marvin（Sammut, 1981）、MIS（Shapiro, 1983）、DUCE（Muggleton, 1987）、Cigol（Muggleton &amp; Buntine, 1988）和Clint（De Raedt &amp; Bruynooghe, 1992），理论修订系统，如FORTE（Richards &amp; Mooney, 1995），以及概率系统，如SLIPCOVER（Bellodi &amp; Riguzzi, 2015）和ProbFOIL（De Raedt et al., 2015）。涵盖所有系统超出了本文的范围。我们讨论这些差异/假设。</p><p class="f_center"><img src="https://nimg.ws.126.net/?url=http%3A%2F%2Fdingyue.ws.126.net%2F2024%2F0903%2F14ab44f4j00sj70z000gnd200u000rug00u000ru.jpg&thumbnail=660x&quality=80&type=jpg"/><br/></p><p id="303L2HQH"><strong>4.1 学习设置</strong></p><p id="303L2HQI">两个主要的<strong>学习设置是LFE和LFI（</strong>第3节）。在LFE设置中，还有进一步的区别。一些系统，如Progol（Muggleton, 1995），允许将子句作为示例。然而，大多数系统从一组事实中学习，因此这个比较维度并不有用。<br/></p><p id="303L2HQK"><strong>4.2 假设</strong></p><p id="303L2HQL">尽管有些系统<strong>学习命题程序</strong>，如Duce（Muggleton, 1987），但<strong>大多数学习一阶（或高阶）程</strong>序。对于学习一阶程序的系统，它们学习的程序类别也有所不同。有些系统诱导完整的（无限制的）子句理论，如Claudien（De Raedt &amp; Dehaspe, 1997）和CF-induction（Inoue, 2004）。然而，对完整子句理论进行推理计算上很昂贵，因此大多数系统学习子句逻辑的片段，通常是确定性程序。专注于程序合成的系统（Shapiro, 1983; Bratko, 1999; Ahlgren &amp; Yuen, 2013; Cropper &amp; Muggleton, 2016, 2019; Cropper &amp; Morel, 2021）倾向于诱导确定性程序，通常作为Prolog程序。</p><p id="303L2HQM"><strong>4.2.1 正常程序</strong><br/></p><p id="303L2HQN">学习正常程序（第2.3.1节）的一个动机是许多实际应用需要非单调推理。此外，使用否定作为失败（NAF）通常可以更简单地表达一个概念。例如，考虑Ray（2009）提出的以下问题：</p><p class="f_center"><img src="https://nimg.ws.126.net/?url=http%3A%2F%2Fdingyue.ws.126.net%2F2024%2F0903%2F0144f635j00sj70zk002ld200u0005vg00u0005v.jpg&thumbnail=660x&quality=80&type=jpg"/><br/></p><p id="303L2HQP">没有NAF，很难为这个问题归纳出一个通用的假设。相比之下，有了NAF，系统可以学习以下假设：<br/></p><p class="f_center"><img src="https://nimg.ws.126.net/?url=http%3A%2F%2Fdingyue.ws.126.net%2F2024%2F0903%2Fba3ddfe4p00sj70zk000id200ra0028g00ra0028.png&thumbnail=660x&quality=80&type=jpg"/><br/></p><p id="303L2HQR">学习正常逻辑程序的ILP方法可以根据它们的语义进一步特征化，例如它们是否基于完成（Clark, 1977）、良基（Gelder et al., 1991）或稳定模型（答案集）（Gelfond &amp; Lifschitz, 1988）语义。讨论这些语义之间的差异超出了本文的范围。</p><p id="303L2HQT"><strong>4.2.2 答案集程序</strong></p><p id="303L2HQU">学习<strong>ASP程序（Otero, 2001; Law et al., 2014）有许多好处。当学习带有NAF的Prolog程序时，程序必须是分层的；否则，学习到的程序在某些查询下可能会循环（Law et al., 2018）。相比之下，一些系统可以学习非分层的ASP程序</strong>（Law et al., 2014）。此外，<strong>ASP程序支持Prolog中不可用的规则，如选择规则以及弱和硬约束。例如，ILASP（Law et al., 2014）可以学习以下哈密顿图的定义（摘自Law et al. (2020)）作为ASP程序：</strong></p><p class="f_center"><img src="https://nimg.ws.126.net/?url=http%3A%2F%2Fdingyue.ws.126.net%2F2024%2F0903%2Fc0daf43dj00sj70zl001cd200r4006cg00r4006c.jpg&thumbnail=660x&quality=80&type=jpg"/><br/></p><p id="303L2HR0">这个程序展示了ASP的有用语言特性。第一条规则是一个选择规则，意味着一个原子可以为真。在这个例子中，规则表明可以从顶点V1到V0有一个进入边。最后两条规则是硬约束，本质上是强制执行完整性约束。第一个硬约束表明不可能有一个不可达的节点。第二个硬约束表明不可能有一个顶点从不同的节点有两个进入边。有关ASP的更多信息，我们推荐阅读Gebser等人（2012）的书籍。</p><p id="303L2HR1">学习ASP程序的方法可以分为两类：<strong>勇敢学习器，旨在学习一个程序，使得至少有一个答案集覆盖示例；谨慎学习器，旨在找到一个在所有答案集中都覆盖示例的程序。</strong>我们参考Otero（2001）、Sakama和Inoue（2009, 2009）、Law等人（2018）的现有工作，以获取关于这些不同方法的更多信息。</p><p id="303L2HR2"><strong>4.2.3 高阶程序</strong><br/></p><p id="303L2HR3">正如许多程序员所知，使用高阶表示有其好处。例如，假设您有一些以Prolog事实表示的加密/解密字符串：<br/></p><p class="f_center"><img src="https://nimg.ws.126.net/?url=http%3A%2F%2Fdingyue.ws.126.net%2F2024%2F0903%2Fd5e9645bj00sj70zn00a7d200u000g8g00u000g8.jpg&thumbnail=660x&quality=80&type=jpg"/><br/></p><p id="303L2HR5">这个程序是高阶的，因为它允许文字将谓词符号作为参数。符号inv是发明出来的（我们在第5.5节讨论谓词发明），在第一条规则中被用作map的参数，在第二条规则中被用作谓词符号。高阶程序比一阶程序更小，因为高阶背景关系map抽象掉了学习递归程序的需要。Cropper等人（2020）表明，<strong>诱导高阶程序可以显著提高学习性能，包括预测准确性、样本复杂性和学习时间。</strong><br/></p><p id="303L2HR6"><strong>4.3 背景知识</strong><br/></p><p id="303L2HR7">背景知识（BK）类似于其他形式的机器学习中使用的特征。然而，特征是有限的表格，而BK是一个逻辑程序。使用逻辑程序来表示数据允许ILP学习复杂的关系信息。例如，假设我们想要学习列表或字符串转换程序，我们可能想要提供辅助关系，如head、tail和last作为BK：</p><p class="f_center"><img src="https://nimg.ws.126.net/?url=http%3A%2F%2Fdingyue.ws.126.net%2F2024%2F0903%2Febdac1c6j00sj70zo001od200u00058g00u00058.jpg&thumbnail=660x&quality=80&type=jpg"/><br/></p><p id="303L2HR9">这些<strong>关系适用于任何长度和任何类型的列表。</strong><br/></p><p id="303L2HRA">作为第二个例子，假设您想要学习质数的定义。那么您可能希望给系统提供执行算术推理的能力，例如使用Prolog关系：</p><p class="f_center"><img src="https://nimg.ws.126.net/?url=http%3A%2F%2Fdingyue.ws.126.net%2F2024%2F0903%2Ff3ee855bj00sj70zp001dd200qo0068g00qo0068.jpg&thumbnail=660x&quality=80&type=jpg"/><br/></p><p id="303L2HRC">这些<strong>关系是通用的，适用于任意数字，我们不需要预先计算定义的所有逻辑后果，这是不可能的，因为有无限多个。相比之下，基于表格的深度机器学习方法仅限于有限的命题数据。例如，由于需要无限大的特征表，因此在决策树学习器中无法使用自然数集上的大于关系。</strong></p><p id="303L2HRD"><strong>4.3.1 约束</strong><br/></p><p id="303L2HRE">背景知识允许人类编码对问题的先验知识。作为一个简单的例子，如果学习银行规则以确定两家公司是否可以相互借贷，您可能会编码一个先验约束，以防止如果两家公司由同一家母公司拥有，则它们不能相互借贷：</p><p class="f_center"><img src="https://nimg.ws.126.net/?url=http%3A%2F%2Fdingyue.ws.126.net%2F2024%2F0903%2F166ff7a1p00sj70zp000hd200ts001ug00ts001u.png&thumbnail=660x&quality=80&type=jpg"/><br/></p><p id="303L2HRG">约束在ILP中被广泛使用（Zeng等人，2014；Evans，2020；Cropper &amp; Morel，2021）。例如，<strong>Inoue等人（2013）将知识表示为因果图，并使用约束来表示节点之间不可能的连接</strong>。Evans等人（2021）<strong>使用约束来归纳理论以解释感官序列。例如，他们统一条件的一个要求是对象（常量）通过二元关系的链相连。作者认为，这样的约束对于归纳出的解决方案实现良好的预测准确性是必要的。</strong></p><p id="303L2HRH"><strong>4.3.2 讨论</strong><br/></p><p id="303L2HRI">与选择合适的特征一样，在ILP中选择合适的背景知识对于良好的学习性能至关重要。<strong>ILP传统上依赖于预定义和手工制作的背景知识，通常由领域专家设计。然而，获得这样的背景知识通常很困难且昂贵。事实上，过度依赖手工制作的背景知识是ILP的一个常见批评</strong>（Evans &amp; Grefenstette，2018）。困难在于找到足够的背景知识来解决问题，但又不至于过多以至于系统变得不堪重负的平衡。我们讨论这两个问题。</p><p id="303L2HRJ"><strong>背景知识太少</strong>。如果我们使用太少或不足的背景知识，我们可能会从假设空间中排除一个好的假设。例如，重新考虑引言中的字符串转换问题，我们希望从示例中学习一个返回字符串最后一个字符的程序。<br/></p><p class="f_center"><img src="https://nimg.ws.126.net/?url=http%3A%2F%2Fdingyue.ws.126.net%2F2024%2F0903%2F9d803c10p00sj70zq000td200ss003wg00ss003w.png&thumbnail=660x&quality=80&type=jpg"/><br/></p><p id="303L2HRL">为了从这些示例中归纳出假设，我们需要为ILP系统提供合适的背景知识。例如，我们可能提供包含常见列表/字符串操作的关系的背景知识，如empty（空）、head（头部）和tail（尾部）。给定这三个关系，ILP系统可以学习以下程序：<br/></p><p class="f_center"><img src="https://nimg.ws.126.net/?url=http%3A%2F%2Fdingyue.ws.126.net%2F2024%2F0903%2F6cc67aa9p00sj70zq000pd200tc002wg00tc002w.png&thumbnail=660x&quality=80&type=jpg"/><br/></p><p id="303L2HRN">然而，假设用户没有提供tail作为背景知识。那么系统如何能学习上述假设呢？这种情况是一个主要问题，因为大多数系统只能使用用户提供的背景知识。<strong>为了缓解这个问题，有研究正在使系统能够自动发明新的谓词符号，称为谓词发明，我们在第5.5节讨论，这已被证明可以缓解缺少背景知识的问题</strong>（Cropper &amp; Muggleton, 2015）。<strong>然而，ILP仍然在很大程度上依赖于人为输入来解决问题。解决这个局限性是一个重大挑战。</strong></p><p id="303L2HRO"><strong>背景知识太多。</strong>与背景知识太少一样，一个主要挑战是太多无关的背景知识。太多的关联（假设它们可以出现在假设中）通常是一个问题，因为假设空间的大小是背景知识大小的函数。从经验上看，<strong>太多无关的背景知识对学习性能是不利的（Srinivasan等人，1995, 2003；Cropper, 2020），这也包括无关的语言偏好（Cropper &amp; Tourret, 2020）。解决背景知识过多的问题研究不足。在第9节中，我们建议这个话题是未来工作的一个有前景的方向，特别是当考虑到ILP用于终身学习的潜力时（第5.5.4节）。</strong><br/></p><p id="303L2HRP"><strong>4.4 语言偏好</strong></p><p id="303L2HRQ">基本的ILP问题是在假设空间中搜索合适的假设。<strong>假设空间包含在所选表示语言中可以构建的所有可能程序。如果不加限制，假设空间是无限的，因此限制它是使搜索可行的关键。为了限制假设空间，系统实施归纳偏好（Mitchell, 1997）。语言偏好对假设实施限制，例如限制假设中的变量数量、文字和规则。这些限制可以分为句法偏好，对假设中规则形式的限制，以及语义偏好，对诱导假设行为的限制（</strong>Adé等人，1995）。例如，在happy示例（示例1.1）中，我们假设假设只包含出现在背景知识或示例中的谓词符号。然而，我们需要编码这种偏好以赋予ILP系统。</p><p id="303L2HRR">编码语言偏好有几种方法，例如<strong>语法（Cohen, 1994a）、Dlabs（De Raedt &amp; Dehaspe, 1997）、生产字段（Inoue, 2004）和谓词声明（Cropper &amp; Morel, 2021）。我们关注模式声明（Muggleton, 1995）和元规则</strong>（Cropper &amp; Tourret, 2020），这两种流行的语言偏好。<br/></p><p id="303L2HRS"><strong>4.4.1 模式声明</strong><br/></p><p id="303L2HRT">模式声明是最受欢迎的语言偏好形式（Muggleton, 1995; Blockeel &amp; De Raedt, 1998; Srinivasan, 2001; Ray, 2009; Corapi等人，2010, 2011; Athakravi等人，2013; Ahlgren &amp; Yuen, 2013; Law等人，2014; Katzouris等人，2015）。<strong>模式声明指出哪些谓词符号可能出现在规则中，频率如何，以及它们的参数类型</strong>。在模式语言中，<strong>modeh声明表示哪些文字可能出现在规则的头部，而modeb</strong>声明表示哪些文字可能出现在规则的主体中。模式声明的形式如下：</p><p class="f_center"><img src="https://nimg.ws.126.net/?url=http%3A%2F%2Fdingyue.ws.126.net%2F2024%2F0903%2Fc7ffb9a5j00sj70zs002rd200u0005og00u0005o.jpg&thumbnail=660x&quality=80&type=jpg"/><br/></p><p id="303L2HRV"><strong>模式声明的第一个参数是一个整数，表示召回率。召回率是模式声明在规则中可以使用的最大次数。另一种理解召回率的方式是，它限制了一个文字的替代解决方案的数量</strong>。提供召回率是给系统一个<strong>提示，以忽略某些假设。例如，如果使用亲子关系，那么我们可以设置召回率为二，因为一个人最多有两个父母。如果使用祖父母关系，那么我们可以设置召回率为四，因为一个人最多有四个祖父母</strong>。如果我们知道一个关系是功能性的，如head，那么我们可以将召回率限制为一。符号*表示没有限制。<br/></p><p id="303L2HS0">第二个参数表示可能出现在规则头部（modeh）或主体（modeb）的<strong>谓词符号以及它所接受的参数类型。</strong>符号<strong>+、-和#分别表示参数是输入、输出还是地面ground参数</strong>。输入参数指定，在调用文字时，相应的参数必须被实例化。换句话说，参数需要绑定到规则中已经出现的变量。输出参数指定，在调用相应的文字后，参数应该被绑定。<strong>地面ground参数指定，参数应该是地面ground的，通常用于学习包含常量符号的规则。</strong></p><p id="303L2HS1">为了说明模式声明，考虑以下模式</p><p class="f_center"><img src="https://nimg.ws.126.net/?url=http%3A%2F%2Fdingyue.ws.126.net%2F2024%2F0903%2F035ffa94j00sj70zt0033d200u0006vg00u0006v.jpg&thumbnail=660x&quality=80&type=jpg"/><br/></p><p id="303L2HS3">给定这些模式，规则 `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 从未被实例化。</p><p id="303L2HS4">相比之下，以下规则都是模式一致的：</p><p class="f_center"><img src="https://nimg.ws.126.net/?url=http%3A%2F%2Fdingyue.ws.126.net%2F2024%2F0903%2F23e0683cp00sj70zu001rd200u00030g00u00030.png&thumbnail=660x&quality=80&type=jpg"/><br/></p><p id="303L2HS6">根据特定系统的不同，模式还可以支持引入常量符号。在Aleph系统中，这样一个声明的例子是 `modeb(*,length(+list,#int))`，它将允许在规则中包含整数值。</p><p id="303L2HS7">不同系统在使用模式声明时有细微的差别。<strong>Progol和Aleph使用带有输入/输出参数类型的模式声明，因为它们诱导Prolog程序，其中规则中文字的顺序很重要。相比之下，ILASP诱导ASP程序，其中规则中文字的顺序并不重要，因此ILASP不使用输入/输出参数。</strong><br/></p><p id="303L2HS8"><strong>4.4.2 元规则</strong></p><p id="303L2HS9">元规则是句法偏好的一种流行形式，被许多系统使用（De Raedt &amp; Bruynooghe, 1992; Flener, 1996; Kietz &amp; Wrobel, 1992; Wang等人，2014; Muggleton等人，2015; Cropper &amp; Muggleton, 2016; Kaminski等人，2018; Evans &amp; Grefenstette, 2018; Bain &amp; Srinivasan, 2018）。<strong>元规则是定义可学习程序结构的二阶规则，进而定义假设空间。</strong></p><p id="303L2HSA"><strong>例如，给定亲子关系来学习祖父母关系，链式元规则将是合适的</strong></p><p class="f_center"><img src="https://nimg.ws.126.net/?url=http%3A%2F%2Fdingyue.ws.126.net%2F2024%2F0903%2F2cd2112ap00sj70zz000cd200mm0026g00mm0026.png&thumbnail=660x&quality=80&type=jpg"/><br/></p><p id="303L2HSC"><strong>字母P、Q和R表示二阶变量（可以绑定到谓词符号的变量），而字母A、B和C表示一阶变量（可以绑定到常量符号的变量）。给定链式元规则、背景中的亲子关系，以及祖父母关系的示例，ILP方法将尝试找到适合的二阶变量替换，例如替换{P/grandparent, Q/parent, R/parent}来归纳理论：</strong></p><p id="303L2HSD">尽管元规则被广泛使用，但很少有工作确定给定学习任务应使用哪些元规则。相反，这些方法假设合适的元规则作为输入，或者在没有理论保证的情况下使用元规则。与其他形式的ILP偏好（如模式或语法）不同，元规则本身是逻辑陈述，这允许我们对它们进行推理。因此，<strong>有关元规则的初步工作正在研究如何识别适合学习逻辑程序某些片段的通用集合（Cropper &amp; Muggleton, 2014; Tourret &amp; Cropper, 2019; Cropper &amp; Tourret, 2020）。</strong>尽管有这些初步工作，但决定给定问题使用哪些元规则<strong>仍然是一个主要挑战，未来的工作必须解决这个问题。</strong></p><p id="303L2HSE"><strong>4.4.3 讨论</strong><br/></p><p id="303L2HSF">选择<strong>合适的语言偏好对于使ILP问题可行至关重要，因为它定义了假设空间。如果偏好太弱，则搜索可能变得不可行。如果偏好太强，则我们可能冒着从假设空间中排除一个好的解决方案的风险。这种权衡是阻碍ILP广泛使用的主要问题之一</strong>。要了解不适当的语言偏好的影响，考虑第1.2节中的字符串转换示例。即使提供了所有必要的背景关系，如果没有提供递归元规则（例如 R(A,B) :- P(A,C), R(C,B)），基于元规则的系统将无法归纳出概括任何长度列表的程序。同样，如果没有为目标关系提供递归模式声明，基于模式的系统将无法找到一个好的假设。</p><p id="303L2HSG">不同的语言偏好提供不同的好处。<strong>模式声明足以强制执行强烈的偏好，显著减少假设空间。当用户对他们的数据有很多了解时，它们特别合适</strong>，例如，可以确定合适的召回值。如果用户没有这样的知识，那么确定合适的模式声明可能非常困难。此外，如果用户提供了弱模式声明（例如具有无限召回、单一类型且没有指定输入/输出参数），那么搜索很快就会变得不可行。尽管有一些关于学习模式声明的工作（McCreath &amp; Sharma, 1995; Ferilli等人，2004; Picado等人，2017），但<strong>选择合适的模式声明仍然是一个主要挑战。</strong><br/></p><p id="303L2HSH">元规则的一个好处是它们不需要对背景知识有太多了解，用户不需要提供召回值、类型或指定输入/输出参数。因为它<strong>们精确地定义了假设的形式，所以它们可以大大减少假设空间，特别是如果用户了解要学习的程序类别</strong>。然而，正如前面提到的，元规则的主要缺点是确定给定学习任务使用哪些元规则。尽管有一些初步工作在识别通用元规则集合（Cropper &amp; Muggleton, 2014; Tourret &amp; Cropper, 2019; Cropper &amp; Tourret, 2020），但决定给定问题使用哪些元规则是一个主要挑战，未来的工作必须解决这个问题。<br/></p><p id="303L2HSI"><strong>4.5 搜索方法</strong></p><p id="303L2HSJ">定义了假设空间之后，下一个问题是如何有效地搜索它。有两种传统的搜索方法：自底向上和自顶向下。这些方法依赖于一般性的概念，其中一个程序比另一个程序更一般或更具体（第2.4节）。一般性关系在假设空间上施加了一个顺序。图2使用theta-subsumption（最受欢迎的排序关系）展示了这个顺序。系统可以在搜索假设时利用这个排序。例如，<strong>如果一个子句没有蕴含一个正面示例，那么就没有必要探索它的任何特化，因为它们在逻辑上不可能蕴含该示例</strong>。同样，<strong>如果一个子句蕴含了一个负面示例，那么就没有必要探索它的任何泛化，因为它们也会蕴含该示例。</strong><br/></p><p class="f_center"><img src="https://nimg.ws.126.net/?url=http%3A%2F%2Fdingyue.ws.126.net%2F2024%2F0903%2Fdb06d659j00sjgvd200u000s7g00u000s7.jpg&thumbnail=660x&quality=80&type=jpg"/><br/></p><p id="303L2HSL">上面的段落仅提及了单个子句的一般性顺序，因为许多系统采用覆盖算法，即逐个子句地构建假设（Quinlan, 1990; De Raedt &amp; Dehaspe, 1997; Muggleton, 1995; Blockeel &amp; De Raedt, 1998; Srinivasan, 2001）。然而，有些系统（Shapiro, 1983; Bratko, 1999; Cropper &amp; Morel, 2021）<strong>诱导由多个子句形成的理论</strong>，因此需要在子句理论上的一般性顺序。我们推荐感兴趣的读者阅读De Raedt（2008）的第7章，以获取更多关于诱导理论的信息。<br/></p><p id="303L2HSM"><strong>4.5.1 自顶向下</strong><br/></p><p id="303L2HSN">自顶向下算法（Quinlan, 1990; Blockeel &amp; De Raedt, 1998; Bratko, 1999; Muggleton et al., 2008）从一般假设开始，然后对其进行特化。例如，HYPER（Bratko, 1999）搜索一个树，其中节点对应于假设。树中假设的每个子节点在theta-subsumption方面都比其前驱更具体或相等，即一个假设只能蕴含其父节点所蕴含示例的一个子集。假设的构建基于假设细化（Shapiro, 1983; Nienhuys-Cheng &amp; Wolf, 1997）。如果<strong>考虑一个假设，它没有蕴含所有正面示例，它会立即被丢弃，因为它永远不可能被细化成一个完整的假设。</strong><br/></p><p id="303L2HSO"><strong>4.5.2 自底向上</strong><br/></p><p id="303L2HSP">自底向上算法从示例开始并泛化它们（Muggleton, 1987; Muggleton &amp; Buntine, 1988; Muggleton &amp; Feng, 1990; Muggleton et al., 2009; Inoue et al., 2014）。例如，Golem（Muggleton &amp; Feng, 1990）基于相对最小通用泛化（RLGG）（Buntine, 1988）泛化示例对。为了介绍RLGG，我们首先引入Plotkin（1971）的最小通用泛化（LGG）概念，它告诉我们如何泛化两个子句。给定两个子句，LGG运算符返回一个比两者都更一般的最具体的单个子句。<br/></p><p class="f_center"><img src="https://nimg.ws.126.net/?url=http%3A%2F%2Fdingyue.ws.126.net%2F2024%2F0903%2Fe595f3f9j00sjiad200u000vjg00u000vj.jpg&thumbnail=660x&quality=80&type=jpg"/><br/></p><p id="303L2HSR">也就是说，背景知识表明对象o1和o3是三角形，对象o2是圆形，对象o1和o2指向下方，图像1包含对象o1和o2，而图像2包含对象o3。我们可以使用相对最小通用泛化（RLGG）来识别共同因素，即找到一个代表共同因素的程序。我们将示例图像表示为bon(1)和bon(2)。我们首先制定描述示例相对于背景知识的子句，并移除背景知识中不相关的部分：</p><p class="f_center"><img src="https://nimg.ws.126.net/?url=http%3A%2F%2Fdingyue.ws.126.net%2F2024%2F0903%2F95cb62fcj00sjmed200u000pjg00u000pj.jpg&thumbnail=660x&quality=80&type=jpg"/><br/></p><p id="303L2HST"><strong>4.5.3 自顶向下和自底向上</strong><br/></p><p id="303L2HSU">Progol是一个非常重要的系统，启发了许多其他方法（Srinivasan, 2001; Ray, 2009; Ahlgren &amp; 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类似的系统。</p><p id="303L2HSV"><strong>4.5.4 元级</strong><br/></p><p id="303L2HT0">最近出现了一种称为元级ILP的新方法（Inoue等人，2013; Muggleton等人，2015; Inoue, 2016; Law等人，2020; Cropper &amp; Morel, 2021）。对于元级ILP的含义没有公认的定义，但大多数方法<strong>将ILP问题编码为元级逻辑程序，即推理程序的程序。这种元级方法通常将搜索假设的任务委托给现成的求解器</strong>（Corapi等人，2011; Athakravi等人，2013; Muggleton等人，2014; Law等人，2014; Kaminski等人，2018; Evans等人，2021; Cropper &amp; Dumančić, 2020; Cropper &amp; Morel, 2021），之后将元级解决方案翻译回ILP问题的标凈解决方案。换句话说，<strong>元级方法不是编写一个以自顶向下或自底向上方式搜索的过程，而是将学习问题表述为一个声明性问题，通常是ASP问题</strong>（Corapi等人，2011; Athakravi等人，2013; Muggleton等人，2014; Law等人，2014; Kaminski等人，2018; Evans等人，2021; Cropper &amp; Dumančić, 2020; Cropper &amp; Morel, 2021）。例如，ASPAL（Corapi等人，2011）<strong>将ILP问题翻译成元级ASP程序，描述了每个示例和假设空间中的每个可能规则（由模式声明定义）。然后ASPAL使用ASP系统找到一组规则，这些规则覆盖了所有正面示例而没有覆盖任何负面示例</strong>。换句话说，<strong>ASPAL将搜索任务委托给ASP求解器。ASPAL使用ASP优化语句找到具有最少文字的假设。</strong></p><p id="303L2HT1">元级方法通常可以学习最优和递归程序。此外，元级方法使用多种技术和技术。例如，Metagol（Muggleton等人，2015; Cropper &amp; Muggleton, 2016）使用Prolog元解释器搜索元级Prolog程序的证明。ASPAL（Corapi等人，2011）、ILASP（Law等人，2014）、HEXMIL（Kaminski等人，2018）和Apperception Engine（Evans等人，2021）将ILP问题翻译成ASP问题，并使用强大的ASP求解器找到问题的模型——注意这些系统都采用了非常不同的算法。∂ILP（Evans &amp; Grefenstette, 2018）使用神经网络解决问题。<strong>总体而言，元级ILP方法的发展令人兴奋，因为它使ILP从早期系统的标凈子句细化方法多样化。</strong><br/></p><p id="303L2HT2">有关元级推理的更多信息，我们建议阅读Inoue（2016）的工作，他提供了元级推理和学习的介绍。Law等人（2020）还提供了冲突驱动ILP的概述，这是系统ILASP3（Law, 2018）和Popper（Cropper &amp; Morel, 2021）采用的。<br/></p><p id="303L2HT3"><strong>4.5.5 讨论</strong></p><p id="303L2HT4">上述讨论的不同搜索方法具有不同的优缺点，没有“最好”的方法。此外，正如Progol所示，自顶向下、自底向上和元级方法之间并没有明确的区分。然而，我们可以对不同方法进行一些一般性的观察。</p><p id="303L2HT5"><strong>自底向上方法可以被视为数据驱动或示例驱动的。这些方法的主要优点通常是它们非常快速。</strong>然而，正如Bratko（1999）所指出的，自底向上方法有几个<strong>缺点，例如（i）它们通常使用不必要地长且包含多个子句的假设，（ii）它们很难同时学习递归假设和多个谓词，以及（iii）它们不容易支持谓词发明。</strong><br/></p><p id="303L2HT6">自顶向下方法的主要<strong>优点是它们更容易学习递归程序和文本最小化程序</strong>。主<strong>要缺点是它们可能效率极低，因为它们可能生成许多甚至不覆盖单个正面示例的假设。自顶向下方法的另一个缺点是它们依赖于迭代改进</strong>。例如，TILDE不断特化每个子句，从而带来改进（即，一个子句覆盖的负面示例更少）。因此，如果必要子句非常长且中间特化不改善子句的得分（覆盖率），TILDE可能会陷入次优解决方案。为了避免这个问题，这些系统依赖于前瞻（Struyf等人，2006），这增加了学习的复杂性。<br/></p><p id="303L2HT7">元级方法的主要<strong>优点是它们可以学习递归程序和最优程序</strong>（Corapi等人，2011; Law等人，2014; Kaminski等人，2018; Evans &amp; Grefenstette, 2018; Evans等人，2021; Cropper &amp; Morel, 2021）。它们还<strong>可以利用约束求解中的最新技术，特别是在ASP中</strong>。然而，仍存在一些<strong>未解决的问题。一个关键问题是，许多方法将ILP问题编码为一个单一的（通常非常大的）ASP问题</strong>（Corapi等人，2011; Law等人，2014; Kaminski等人，2018; Evans等人，2021），因此在非常大的域的问题上难以扩展。此外，由于大多数ASP求解器只适用于地面程序（Gebser等人，2014），纯基于ASP的方法固有地限于具有小且有限grounding的任务。尽管初步工作试图解决这个问题（Cropper &amp; Morel, 2021; Cropper, 2022），但这些方法仍需工作以扩展到非常大的问题。许多方法还预先计算假设中的每个可能规则（Corapi等人，2011; Law等人，2014），因此难以学习具有大规则的程序，尽管初步工作试图解决这个问题（Cropper &amp; Dumančić, 2020）。<br/></p><p class="f_center"><img src="https://nimg.ws.126.net/?url=http%3A%2F%2Fdingyue.ws.126.net%2F2024%2F0903%2F9d012943j00sjld200dw009sg00dw009s.jpg&thumbnail=660x&quality=80&type=jpg"/><br/></p><p id="303L2HT9"><strong>5. ILP特性</strong><br/></p><p id="303L2HTA">表4在少数几个维度上比较了表3中的相同系统。这个表格排除了许多其他重要的比较维度，例如系统是否支持非观察谓词学习，其中目标关系的示例不是直接给出的（Muggleton, 1995）。我们依次讨论这些特性。<br/></p><p class="f_center"><img src="https://nimg.ws.126.net/?url=http%3A%2F%2Fdingyue.ws.126.net%2F2024%2F0903%2F31d54605j00sjigd200u000rcg00u000rc.jpg&thumbnail=660x&quality=80&type=jpg"/><br/></p><p id="303L2HTC"><strong>5.1 噪声处理</strong><br/></p><p id="303L2HTD">在机器学习（ML）中，噪声处理非常重要。在ILP中，我们可以区分三种类型的噪声：</p><p id="303L2HTE">- 噪声示例：示例被错误分类</p><p id="303L2HTF">- 错误的背景知识（BK）：应该不成立的关系却成立（或者应该成立的关系没有成立）</p><p id="303L2HTG">- 不完美的背景知识：缺少关系或有太多不相关的关系</p><p id="303L2HTH">我们讨论这三种类型的噪声。<br/></p><p id="303L2HTI">噪声示例。第3节中的问题定义对于解释噪声（错误标记）示例来说过于严格，因为它们期望一个假设能够蕴含所有正面示例而不蕴含任何负面示例。因此，大多数系统放宽了这一约束，接受一个不一定涵盖所有正面示例或涵盖一些负面示例的假设。大多数使用集合覆盖循环的系统自然支持噪声处理。例如，TILDE将决策树学习器（Quinlan, 1986, 1993）扩展到一阶设置，并使用相同的信息增益方法来归纳假设。ILASP的噪声容忍版本（Law, 2018）使用ASP的优化能力来可靠地学习具有**覆盖率的程序。<strong>总的来说，处理噪声示例是ILP中一个研究充分的主题。</strong><br/></p><p id="303L2HTJ">错误的背景知识。正如训练示例可能存在噪声/错误分类一样，背景知识中的事实/规则也可能是噪声/错误分类的。例如，如果在学习预测天气的规则时，背景知识可能包含关于历史天气的事实，这些事实可能不是100%准确的。然而，大多数系统假设背景知识是完美的，即原子是真的或假的，没有不确定性的余地。这一假设是一个主要限制，因为现实世界的数据，如图像或语音，并不总能轻易地转换为纯粹的无噪声符号表示。我们在<strong>第9.1节中更详细地讨论了这一限制。</strong><br/></p><p id="303L2HTK"><strong>∂ILP的一个关键吸引力在于它采用了ILP的可微分方法，并且可以接受模糊或不明确的数据。与原子真或假不同，∂ILP为原子提供了连续的语义</strong>，将原子映射到实数单位区间[0, 1]。作者成功地在MNIST数据集上展示了这种方法。<br/></p><p id="303L2HTL">不完美的背景知识。处理不完美的背景知识是ILP中一个<strong>未充分探索的话题。我们可以区分两种类型的不完美背景知识：缺失的背景知识和过多的背景知识，我们在第4.3.2节中讨论了这些。</strong><br/></p><p id="303L2HTM"><strong>5.2 优化性</strong></p><p id="303L2HTN">在许多情况下，解决ILP问题（或具有相同的训练误差）有多个（有时是无限多）假设。在这种情况下，我们应该选择哪个假设呢？</p><p id="303L2HTO"><strong>5.2.1 奥卡姆剃刀偏见</strong><br/></p><p id="303L2HTP">许多系统试图学习一个文本上最小的假设。这种方法是遵循奥卡姆剃刀偏见（Schaffer, 1993）。奥卡姆剃刀偏见最常见的解释是，在所有与数据一致的假设中，最简单的是最有可能的。大多数方法使用奥卡姆剃刀偏见来找到最小的假设，以子句（Muggleton等人，2015）、文字（Law等人，2014）或描述长度（Muggleton, 1995）来衡量。然而，大多数系统并不保证能够诱导出最小的程序。这种局限性的一个关键原因是，许多方法一次学习一个子句，导致构建的子程序在程序大小和覆盖范围方面是次优的。例如，下一节详细描述的Aleph，对于程序大小和覆盖范围没有保证。较新的系统通过元级推理（第4.5节）来解决这个局限性（Corapi等人，2011；Law等人，2014；Cropper &amp; Muggleton, 2016；Kaminski等人，2018；Cropper &amp; Morel, 2021）。例如，ASPAL（Corapi等人，2011）的输入是一个带有一组候选子句的假设空间。ASPAL的任务是找到最小的子句子集，这些子句能够推导出所有正面例子而不推导出任何负面例子。ASPAL利用ASP的优化能力，可以证明地学习最少文字的程序。<br/></p><p id="303L2HTQ"><strong>5.2.2 成本最小化程序</strong><br/></p><p id="303L2HTR">学习高效的逻辑程序一直被认为是一个难题（Muggleton &amp; De Raedt, 1994; Muggleton等人，2012），主要是因为高效程序（如归并排序）与低效程序（如冒泡排序）之间在声明性上没有区别。为了解决这个问题，Metaopt（Cropper &amp; Muggleton, 2019）学习高效程序。Metaopt在假设搜索过程中保持成本，并使用这个成本来剪枝假设空间。为了学习最小时间复杂度的逻辑程序，Metaopt最小化了解算步骤的数量。例如，想象学习一个查找重复程序，该程序在列表中找到一个重复的元素，例如 [p,r,o,g,r,a,m] ↦→ r 和 [i,n,d,u,c,t,i,o,n] ↦→ i。在给定合适的输入数据的情况下，Metagol诱导出程序：</p><p class="f_center"><img src="https://nimg.ws.126.net/?url=http%3A%2F%2Fdingyue.ws.126.net%2F2024%2F0903%2Ffd4ae2e1j00sj710a004td200u00089g00u00089.jpg&thumbnail=660x&quality=80&type=jpg"/><br/></p><p id="303L2HTT">该程序首先对输入列表进行排序，然后遍历列表以检查相邻的重复元素。虽然在子句和文字方面都更大，但由 Metaopt 学习的程序比由 Metagol 学习的程序更高效（O(n log n) 相对于 O(n²)）。</p><p id="303L2HTU">其他系统也可以学习最优程序（Schüller &amp; Benz, 2018）。例如，FastLAS（Law等人，2020）遵循这个理念，并接受一个自定义评分函数作为输入，为给定的评分函数计算最优解。作者展示了这种方法允许用户在现实世界的数据集上优化特定领域的性能指标，例如访问控制策略。<br/></p><p id="303L2HTV"><strong>5.3 无限域</strong></p><p id="303L2HU0">一些系统，<strong>主要是元级方法，无法处理无限域</strong>（Corapi等人，2011; Athakravi等人，2013; Evans &amp; Grefenstette, 2018; Kaminski等人，2018; Evans等人，2021）。基于纯ASP的系统（Corapi等人，2011; Kaminski等人，2018; Evans等人，2021）难以处理无限域，因为（大多数）当前的ASP求解器只适用于地面程序，即它们需要有限的接地。只要接地是有限的，ASP就可以处理无限域（？？？？）。这种有限接地限制通常是通过对程序施加语法限制来实现的，例如有限接地程序Calimeri等人（2008）。ASP系统（结合了一个接地器和求解器），如Clingo（Gebser等人，2014），首先接受一个一阶程序作为输入，使用ASP接地器进行接地，然后使用ASP求解器来确定接地问题是否可满足。这种方法<strong>导致了接地瓶颈问题（Balduccini等人，2013），接地可能如此之大以至于根本无法处理。当推理复杂数据结构时，如列表，这个问题尤其严重。例如，对ASCII字符上的排列关系进行接地将需要128!个事实</strong>。接地瓶颈在推理实数时尤其成问题。例如，ILASP（Law等人，2014）可以将实数表示为字符串，并通过Clingo的脚本功能委托推理给Python。然而，在这种方法中，数值计算是在接地输入时进行的，因此接地必须是有限，这使得它不切实际。这个接地问题不仅限于基于ASP的系统。例如，<strong>∂ILP是基于神经网络的ILP系统，但它只在有限集合的地面原子形式的BK上工作。这个接地问题本质上是我们在第4.3节讨论的基于表的机器学习方法所面临的问题。</strong></p><p id="303L2HU1">缓解这个问题的一个方法是使用上下文依赖的例子（Law等人，2016），其中BK可以与特定的例子相关联，以便ILP系统只需要接地BK的一部分。尽管这种方法被证明与不使用上下文依赖的例子相比，可以改善接地问题，但该方法仍然需要每个例子的有限接地，并且随着域大小的增加仍然存在困难（Cropper &amp; Morel, 2021）。</p><p id="303L2HU2"><strong>5.4 递归</strong></p><p id="303L2HU4">递归的力量在于可以通过有限的递归程序描述无限数量的计算（Wirth, 1985）。<strong>在ILP中，递归对于泛化通常至关重要。我们用两个例子来说明这种重要性。</strong></p><p id="303L2HU5">例5（可达性）。考虑学习图中的可达性概念。如果没有递归，ILP系统将需要学习一个单独的子句来定义不同长度的可达性。例如，定义1-4的可达性深度将需要程序：</p><p class="f_center"><img src="https://nimg.ws.126.net/?url=http%3A%2F%2Fdingyue.ws.126.net%2F2024%2F0903%2F591a5374j00sj710a003qd200u0004vg00u0004v.jpg&thumbnail=660x&quality=80&type=jpg"/><br/></p><p id="303L2HU7">这个程序没有泛化，因为它没有定义任意深度的可达性。此外，大多数系统需要每个深度的例子才能学习这样的程序。相比之下，支持递归的系统可以学习以下程序：</p><p class="f_center"><img src="https://nimg.ws.126.net/?url=http%3A%2F%2Fdingyue.ws.126.net%2F2024%2F0903%2F553ff502p00sj710b001ad200u0002qg00u0002q.png&thumbnail=660x&quality=80&type=jpg"/><br/></p><p id="303L2HU9">尽管更小，但这个程序将可达性泛化到任何深度。此外，系统可以从少量任意可达性深度的例子中学习这个定义。<br/></p><p id="303L2HUA">例6（字符串转换）。重新考虑第1.2节中介绍的字符串转换问题。与可达性示例一样，如果没有递归，系统将需要为每个长度为n的列表学习一个单独的子句来找到最后一个元素，例如：<br/></p><p class="f_center"><img src="https://nimg.ws.126.net/?url=http%3A%2F%2Fdingyue.ws.126.net%2F2024%2F0903%2F0f89696cj00sj710c004xd200u0007pg00u0007p.jpg&thumbnail=660x&quality=80&type=jpg"/><br/></p><p id="303L2HUC">由于符号表示和递归特性，这个程序泛化到任意长度的列表，并且包含任意元素（例如整数和字符）。<br/></p><p id="303L2HUD">没有递归，系统通常很难从小数量的例子中泛化（Cropper等人，2015）。此外，递归对于许多程序合成任务至关重要，例如介绍中的快速排序场景。尽管它很重要，但学习递归程序一直是一个难题（Muggleton等人，2012）。此外，关于递归程序的可学习性有许多负面的理论结果（Cohen, 1995d）。正如表4所示，许多系统无法学习递归程序，或者只能以有限的形式学习。<br/></p><p id="303L2HUE">一个常见的限制是，许多系统依赖于底部子句构造（Muggleton, 1995），我们在第6.1节详细讨论了这一点。在这种方法中，对于每个正面例子，系统创建一个最具体的子句来推导该例子，然后尝试泛化该子句以推导其他例子。然而，由于系统每个例子只学习一个子句，这种覆盖方法需要底部和归纳情况的例子，这意味着这样的系统在学习递归程序时遇到困难，尤其是从小数量的例子中学习。<br/></p><p id="303L2HUF">随着<strong>元解释学习（MIL）的引入，对递归的兴趣最近重新兴起（Muggleton等人，2014, 2015; Cropper等人，2020</strong>）和MIL系统Metagol（Cropper &amp; Muggleton, 2016）。MIL的<strong>关键思想是使用元规则（第4.4.2节）来限制可诱导程序的形式</strong>，从而限制假设空间。例如，链式元规则（P (A, B) ← Q (A, C), R (C, B)）允许Metagol诱导程序，例如：<br/></p><p id="303L2HUG">Metagol使用递归元规则来诱导递归程序，例如尾递归元规则<br/></p><p id="303L2HUH">。Metagol还可以学习相互递归的程序，例如通过发明并学习奇数（odd_1）的定义来学习偶数的定义：</p><p class="f_center"><img src="https://nimg.ws.126.net/?url=http%3A%2F%2Fdingyue.ws.126.net%2F2024%2F0903%2Fc1915b1bp00sj710d0019d200u0003pg00u0003p.png&thumbnail=660x&quality=80&type=jpg"/><br/></p><p id="303L2HUJ">现在许多系统都能学习递归程序（Law等人，2014; Evans &amp; Grefenstette, 2018; Kaminski等人，2018; Evans等人，2021; Cropper &amp; Morel, 2021）。<strong>有了递归，系统可以从少量例子中泛化，通常是一个单一的例子</strong>（Lin等人，2014; Cropper, 2019）。例如，Popper（Cropper &amp; Morel, 2021）可以从仅有的几个例子中学习列表转换程序，例如一个程序来删除列表的最后一个元素：<br/></p><p class="f_center"><img src="https://nimg.ws.126.net/?url=http%3A%2F%2Fdingyue.ws.126.net%2F2024%2F0903%2F37a08ccfp00sj710e001ed200u0002cg00u0002c.png&thumbnail=660x&quality=80&type=jpg"/><br/></p><p id="303L2HUL">学习递归程序的能力已经将归纳逻辑编程（ILP）扩展到新的应用领域，包括学习字符串转换程序（Lin等人，2014）、<strong>机器人策略（Cropper &amp; Muggleton, 2015）、上下文无关文法（Muggleton等人，2014）和答案集文法（</strong>Law等人，2019）。<br/></p><p id="303L2HUM"><strong>5.5 谓词发明</strong><br/></p><p id="303L2HUN">大多数系统假设给定的背景知识（BK）适合于归纳出解决方案。这个假设可能并不总是成立。谓词发明<strong>（PI）的目标不是期望用户提供所有必要的背景知识，而是让系统自动发明新的辅助谓词符号，即在假设中引入不在示例或背景知识中给出的新谓词符号。这个想法类似于人类在手动编写程序时创建新函数，例如为了减少代码重复或提高可读性。</strong>例如，要学习快速排序算法，学习器需要能够在给定枢轴元素的情况下对列表进行分区，并连接两个列表。如果分区和连接不在背景知识中提供，学习器需要发明它们。</p><p id="303L2HUO"><strong>谓词发明被反复声明为一个重要挑战</strong>（Muggleton &amp; Buntine, 1988; Stahl, 1995; Muggleton, 1994b; Muggleton等人，2012）。Russell（2019）甚至认为，<strong>自动发明新高层概念是达到人类水平人工智能所需的最重要步骤</strong>。谓词发明的一个经典例子是从仅包含母亲和父亲背景关系的示例中学习祖父母的定义。在给定合适的示例且没有其他背景关系的情况下，系统可以学习以下程序：<br/></p><p class="f_center"><img src="https://nimg.ws.126.net/?url=http%3A%2F%2Fdingyue.ws.126.net%2F2024%2F0903%2F1f395cabp00sj710e002ed200u00043g00u00043.png&thumbnail=660x&quality=80&type=jpg"/><br/></p><p id="303L2HUQ">尽管正确，但这个程序很大，包含4个子句和12个文字。相比之下，考虑一个支持谓词发明（PI）的系统学习到的程序：<br/></p><p class="f_center"><img src="https://nimg.ws.126.net/?url=http%3A%2F%2Fdingyue.ws.126.net%2F2024%2F0903%2F6c018156p00sj710f0017d200u0003cg00u0003c.png&thumbnail=660x&quality=80&type=jpg"/><br/></p><p id="303L2HUS">为了学习这个程序，系统发明了一个新的谓词符号 。<strong>这个程序在语义上等同于前一个程序，但在文字和子句的数量上都更短。发明的符号 可以被解释为 "parent"（父母）</strong>。换句话说，如果我们<strong>将 重命名为 ，我们就有了以下程序：</strong><br/></p><p class="f_center"><img src="https://nimg.ws.126.net/?url=http%3A%2F%2Fdingyue.ws.126.net%2F2024%2F0903%2Fa3p00sj710f001dd200u00036g00u00036.png&thumbnail=660x&quality=80&type=jpg"/><br/></p><p id="303L2HUU">正如这个例子所示，谓词发明（PI）可以帮助学习更小的程序，这通常是更可取的，<strong>因为大多数系统在学习大型程序时都会遇到困难</strong>（Cropper等人，2020b; Cropper &amp; Dumančić, 2020）。已经<strong>证明，谓词发明有助于减少程序的大小，这反过来又降</strong><strong>低了样本复杂性并提高了预测准确性</strong>（Dumančić &amp; Blockeel, 2017; Cropper, 2019; Cropper等人，2020; Dumančić等人，2019; Dumancic等人，2021）。</p><p class="f_center"><img src="https://nimg.ws.126.net/?url=http%3A%2F%2Fdingyue.ws.126.net%2F2024%2F0903%2Fbp00sj710g002jd200u00037g00u00037.png&thumbnail=660x&quality=80&type=jpg"/><br/></p><p class="f_center"><img src="https://nimg.ws.126.net/?url=http%3A%2F%2Fdingyue.ws.126.net%2F2024%2F0903%2F44f24e02p00sj710h001fd200u0002gg00u0002g.png&thumbnail=660x&quality=80&type=jpg"/><br/></p><p id="303L2HV1">为了学习这个程序，Metagolho发明了谓词符号 `droplasts1`，它在程序中被使用了两次：一次作为文字 `map(A,B,droplasts1)` 中的项，一次作为文字 `droplasts1(A,B)` 中的谓词符号。这个高阶程序使用 `map` 来抽象列表的操作，避免了学习显式递归程序的需要（递归在 `map` 中是隐式的）。</p><p id="303L2HV2">现在考虑学习一个双重 `droplasts` 程序（`ddroplasts`），它扩展了 `droplast` 问题，除了从每个子列表中删除最后一个元素外，它还删除最后一个子列表，例如 [alice,bob,carol] ↦→ [alic,bo]。在给定合适的示例、元规则和背景知识的情况下，Metagolho学习了以下程序：</p><p class="f_center"><img src="https://nimg.ws.126.net/?url=http%3A%2F%2Fdingyue.ws.126.net%2F2024%2F0903%2F23cf62d7p00sj710h001rd200u0002lg00u0002l.png&thumbnail=660x&quality=80&type=jpg"/><br/></p><p id="303L2HV4">这个程序与前面提到的 `droplasts` 程序类似，但此外还在文字 `ddroplasts1(C,B)` 中重用了发明的谓词符号 `ddroplasts1`。这个程序展示了谓词发明（PI）帮助学习更复杂程序的强大能力。<br/></p><p id="303L2HV5">大多数早期尝试谓词发明都未能成功，正如表4所示，大多数系统不支持它。正如Kramer（1995）所指出的，<strong>谓词发明之所以困难，至少有三个原因：<br/></strong></p><p id="303L2HV6"><strong>when- 我们什么时候应该发明一个新的符号？必须有发明新符号的理由；否则，我们永远不会发明一个。</strong></p><p id="303L2HV7"><strong>how- 你应该如何发明一个新的符号？它应该有多少个参数？</strong></p><p id="303L2HV8"><strong>what- 我们如何判断一个新符号的质量？什么时候我们应该保留一个发明的符号？</strong></p><p id="303L2HV9">有许多谓词发明技术。我们现在简要讨论一些方法。<br/></p><p id="303L2HVA"><strong>5.5.1 逆向解析</strong><br/></p><p id="303L2HVB">早期关于谓词发明的工作基于逆向解析（Muggleton &amp; Buntine, 1988）的思想，特别是W运算符。深入讨论逆向解析超出了本文的范围。我们建议读者参考Muggleton和Buntine（1988）的原始工作，或者Nienhuys-Cheng和Wolf（1997）以及De Raedt（2008）的综述书籍，以获取更多信息。尽管逆向解析方法可以支持谓词发明，但它们从未证明完整性，部分原因是缺乏声明性偏见来限定假设空间（Muggleton等人，2015）。</p><p id="303L2HVC"><strong>5.5.2 占位符</strong><br/></p><p id="303L2HVD">谓词发明的一种方法是通过模式声明预定义发明的符号，Leban等人（2008）称之为占位符，而Law（2018）称之为规范性谓词发明。例如，要发明 `parent` 关系，需要一个合适的 `modeh` 声明，例如：</p><p id="303L2HVF">然而，这种占位符方法是有限的，因为它要求用户手动指定符号的元数和参数类型（Law等人，2014），这反而违背了谓词发明的初衷，或者需要生成所有可能的发明谓词（Evans &amp; Grefenstette, 2018; Evans等人，2021），这在计算上是昂贵的。<br/></p><p id="303L2HVG"><strong>5.5.3 元规则</strong><br/></p><p id="303L2HVH">为了减少谓词发明的复杂性，Metagol使用元规则（第4.4.2节）来定义假设空间。例如，链式元规则允许Metagol诱导出如下程序：</p><p class="f_center"><img src="https://nimg.ws.126.net/?url=http%3A%2F%2Fdingyue.ws.126.net%2F2024%2F0903%2F1f58f8a2p00sj710i000ld200u0002ag00u0002a.png&thumbnail=660x&quality=80&type=jpg"/><br/></p><p id="303L2HVJ">这个程序从列表中删除前两个元素。为了诱导更长的子句，例如从列表中删除前三个元素，Metagol可以使用相同的元规则，但可以发明一个新的谓词符号，然后链式应用它们，例如诱导出以下程序：</p><p class="f_center"><img src="https://nimg.ws.126.net/?url=http%3A%2F%2Fdingyue.ws.126.net%2F2024%2F0903%2F09061fc2p00sj710j000kd200tg002eg00tg002e.png&thumbnail=660x&quality=80&type=jpg"/><br/></p><p id="303L2HVL">这种由元规则驱动的谓词发明方法的一个副作用是，问题被迫被分解成更小的问题。例如，假设你想要学习一个程序，它从列表中删除前四个元素，那么Metagol可以学习以下程序，其中发明的谓词符号 `inv` 被使用了两次：</p><p class="f_center"><img src="https://nimg.ws.126.net/?url=http%3A%2F%2Fdingyue.ws.126.net%2F2024%2F0903%2Fcfed4e32p00sj710j000zd200u0002lg00u0002l.png&thumbnail=660x&quality=80&type=jpg"/><br/></p><p id="303L2HVN">为了学习这个程序，Metagol发明了谓词符号 `inv` 并使用链式元规则为其诱导定义。Metagol在目标谓词 `f` 的定义中使用了这个新谓词符号。<br/></p><p id="303L2HVO"><strong>5.5.4 终身学习</strong><br/></p><p id="303L2HVP">上述谓词发明技术针对的是单一任务问题。谓词发明可以通过持续学习程序（元学习）来执行。例如，Lin等人（2014）使用一种称为依赖学习的技术，使Metagol能够随着时间学习字符串转换程序。给定一组17个字符串转换任务，他们的<strong>学习器自动识别出更简单的问题，学习它们的程序，然后重用这些已学习的程序来帮助学习更复杂问题的程序。为了确定哪些问题更容易解决</strong>，作者最初以非常强的偏见开始，只允许学习器使用一条规则来找到解决方案。然后他们逐步放宽这个限制，每次在解决方案中允许更多的规则。作者使用谓词发明来改革学习器的偏见，在学习到解决方案后，不仅将目标谓词添加到背景知识中，还将其构成的发明谓词也添加进去。作者通过实验表明，他们的<strong>多任务方法比单一任务方法表现得好得多，因为经常重用已学习的程序。此外，他们展示了这种方法导致了由可重用程序组成的背景知识层次结构，</strong>每个层次都建立在更简单程序的基础上。图4显示了这种方法。请注意，这种<strong>终身学习设置带来了挑战，我们将在第9.1节中讨论。</strong></p><p class="f_center"><img src="https://nimg.ws.126.net/?url=http%3A%2F%2Fdingyue.ws.126.net%2F2024%2F0903%2Fddj00sj710l00ccd200u000m0g00u000m0.jpg&thumbnail=660x&quality=80&type=jpg"/><br/></p><p id="303L2HVR"><strong>5.5.5 理论精炼</strong><br/></p><p id="303L2HVS">理论精炼（Wrobel, 1996）的目标是提高理论的质量。理论修订方法（Adé等人，1994；Richards &amp; Mooney, 1995）修订程序，使其包含缺失的答案或不包含不正确的答案。理论压缩（De Raedt等人，2008）方法选择一组子句，使得相对于某些例子，性能受到的最小影响。理论重构改变了逻辑程序的结构，以优化其执行或可读性（Flach, 1993; Wrobel, 1996）。我们讨论两种基于谓词发明的最近精炼方法。</p><p id="303L2HVT">自动编码逻辑程序。<strong>自动编码逻辑程序（ALPs）（Dumančić等人，2019）通过同时学习一对逻辑程序来发明谓词：（i）一个编码器</strong>，将给定的解释映射到完全用发明谓词定义的新解释，以及（ii）一个解码器，从发明的解释中重建原始解释。发明的解释压缩了给定的例子，并通过捕捉数据中的规律来发明有用的谓词。因此，ALPs改变了问题的表示。该<strong>方法最重要的含义是，通过发明的谓词更容易表达目标程序。</strong>作者通过实验表明，<strong>从ALPs发明的表示中学习提高了生成性马尔可夫逻辑网络（MLN）（Richardson &amp; Domingos, 2006）的学习性能</strong>。生成性MLN学习一个（概率性）逻辑程序，解释一个解释中的所有谓词，而不是单个目标谓词。因此，ALPs发明的谓词有助于学习背景知识中的所有谓词。<br/></p><p id="303L2HVU"><strong>程序重构。Knorf（Dumancic等人，2021）将ALPs的思想推向了更进一步</strong>。在终身学习环境中学习解决用户提供的任务后，Knorf通过<strong>移除其中的冗余来压缩学习到的程序。如果学习到的程序包含发明的谓词，Knorf会修订它们并引入新的谓词，以</strong>得到更小的程序。通过这样做，Knorf优化了获得的知识的表示。重构的程序在大小上更小，包含的冗余子句更少。作者通过实验证明，<strong>重构提高了终身学习中的学习性能。更确切地说，当使用重构的背景知识时，Metagol学习解决更多任务，特别是当背景知识很大时。此外，作者还证明Knorf大大减少了背景知识程序的大小，将程序中的文字数量减少了50%或更多。</strong><br/></p><p id="303L2HVV"><strong>6. ILP案例研究</strong><br/></p><p id="303L2I00">我们现在详细描述四个ILP系统：Aleph（Srinivasan, 2001）、TILDE（Blockeel &amp; De Raedt, 1998）、ASPAL（Corapi等人，2011）和Metagol（Cropper &amp; Muggleton, 2016）。这些系统不一定是最好或最受欢迎的，<strong>但使用了相当不同的技术，并且相对容易解释</strong>。Aleph基于<strong>逆向蕴含</strong>（Muggleton, 1995），并使用底部子句构造来限制假设空间。尽管Aleph已经有些年头，但它仍然是最受欢迎的系统之一。<strong>TILDE是决策树的一阶泛化，并使用信息增益来分割和征服训练例子</strong>。<strong>ASPAL是一个元级系统，它使用ASP求解器来解决ILP问题，</strong>这影响了后续的许多工作，特别是<strong>ILASP</strong>。最后，Metagol使用Prolog元解释器来构建一组例子的证明，并从证明中提取程序。我们依次讨论这些系统。</p><p id="303L2I01"><strong>6.1 Aleph</strong><br/></p><p id="303L2I02">Progol（Muggleton, 1995）可以说是最有影响力的ILP系统，影响了众多系统（Inoue, 2004; Srinivasan, 2001; Ray, 2009; Ahlgren &amp; Yuen, 2013），这些系统反过来又启发了许多其他系统（Katzouris等人，2015, 2016; Schüller &amp; Benz, 2018）。Aleph基于Progol。我们讨论Aleph而不是Progol，因为Aleph的实现是用Prolog编写的，更容易使用，手册也更详细。</p><p id="303L2I03"><strong>6.1.1 Aleph 设置</strong></p><p id="303L2I04">Aleph的问题设置是：</p><p class="f_center"><img src="https://nimg.ws.126.net/?url=http%3A%2F%2Fdingyue.ws.126.net%2F2024%2F0903%2F82d711ebj00sj710m001vd200u000bqg00u000bq.jpg&thumbnail=660x&quality=80&type=jpg"/><br/></p><p class="f_center"><img src="https://nimg.ws.126.net/?url=http%3A%2F%2Fdingyue.ws.126.net%2F2024%2F0903%2Ff97e00eaj00sj710n000pd200u0004mg00u0004m.jpg&thumbnail=660x&quality=80&type=jpg"/><br/></p><p id="303L2I07"><strong>6.1.2 Aleph 算法</strong></p><p id="303L2I08">Aleph从一个空的假设开始，并使用以下集合覆盖方法：<br/></p><p id="303L2I09">1. 选择一个正面例子进行泛化。如果不存在，则停止并返回当前假设；否则，继续下一步。</p><p id="303L2I0A">2. 构建与模式声明（第4.4.1节）一致且能推导例子的最具体子句（底部子句）（Muggleton, 1995）。</p><p id="303L2I0B">3. 搜索一个比底部子句更一般的子句，并具有**得分。</p><p id="303L2I0C">4. 将子句添加到假设中，并移除它所覆盖的所有正面例子。返回步骤1。</p><p id="303L2I0D">我们讨论步骤2和3的基本方法。</p><p id="303L2I0E">步骤2：底部子句构造</p><p id="303L2I0F">构造底部子句的目的是限制步骤3中的搜索。底部子句是能推导要泛化的例子的最具体子句。一般来说，底部子句可以有无限的基数。因此，Aleph使用模式声明（第4.4.1节）来限制它们。描述如何构造底部子句超出了本文的范围。参见Muggleton（1995）的论文或De Raedt（2008）的书了解对比方法。构建了底部子句后，Aleph可以忽略任何不比它更一般的子句。换句话说，Aleph只考虑底部子句的泛化子句，这些子句必须都能推导例子。我们使用De Raedt（2008）提供的底部子句定义：</p><p id="303L2I0G">定义4（底部子句）。让H是一个子句假设，C是一个子句。那么底部子句 ⊥(C) 是最具体的子句，使得：</p><p class="f_center"><img src="https://nimg.ws.126.net/?url=http%3A%2F%2Fdingyue.ws.126.net%2F2024%2F0903%2Ff912d752j00sj710o0053d200u000aig00u000ai.jpg&thumbnail=660x&quality=80&type=jpg"/><br/></p><p class="f_center"><img src="https://nimg.ws.126.net/?url=http%3A%2F%2Fdingyue.ws.126.net%2F2024%2F0903%2Fae395f79j00sj710p003vd200u000b9g00u000b9.jpg&thumbnail=660x&quality=80&type=jpg"/><br/></p><p id="303L2I0J">这个底部子句包含文字 rectangle(A)，因为它是由 square(A) 蕴含的。rectangle(A) 的包含反过来又意味着 polygon(A) 的包含。尽管 blue 和 triangle 出现在 B 中，它们与 e 无关，因此没有出现在底部子句中。<br/></p><p id="303L2I0K">任何不比底部子句更一般的子句都不能蕴含 e，因此可以忽略。例如，我们可以忽略子句 pos(A) :- blue(A)，因为它不比 ⊥(e) 更一般。</p><p id="303L2I0L">常量符号。注意 ⊥(e) 包含变量，而不是常量符号，这会使底部子句更加具体。原因是给定的模式声明禁止常量符号。如果在 M 中给出了 modeb(*,polygon(#shape))，那么 ⊥(e) 也会包含 polygon(s1)。</p><p id="303L2I0M"><strong>步骤3：子句搜索</strong><br/></p><p id="303L2I0N">构建了底部子句后，Aleph 搜索它的泛化。构建底部子句的重要性在于它从下面（底部子句）限制了搜索空间。图5说明了在给定我们之前形状示例中的底部子句 ⊥(e) 时 Aleph 的搜索空间。Aleph 执行有界的广度优先搜索，先枚举较短的子句，然后是较长的子句，尽管用户可以轻松更改搜索策略。搜索由几个参数限定，例如最大子句大小和最大证明深度。在这种情况下，Aleph 从 ⊥(e) 的最一般泛化 pos(A) 开始，它简单地表明一切都是真的。Aleph 评估（给分数）搜索中的每个子句，即格中的每个子句。Aleph 的默认评估函数是覆盖度，定义为 P - N，其中 P 和 N 分别是由子句蕴含的正面和负面例子的数量。然后 Aleph 尝试通过向其主体添加文字或通过实例化变量来专门化子句。每个子句的专门化称为细化。细化操作符（Shapiro, 1983）的性质在 ILP 中得到了很好的研究（Nienhuys-Cheng &amp; Wolf, 1997; De Raedt, 2008），但超出了本文的范围。关键是要理解 Aleph 的搜索是从上面（最一般的子句）和下面（最具体的子句）限定的。找到**子句后，Aleph 将其添加到假设中，移除新假设所覆盖的所有正面例子，然后返回步骤1。描述完整的子句搜索机制和如何计算分数超出了本文的范围，因此我们建议...</p>