Learning programs by learning from failures
https://github.com/logic-and-learning-lab/Popper
作者相关论文：
Code：最有前途的ARC-AGI比赛方法：关系分解，关系型表示胜过函数型表示
摘要 （GPT翻译，请参考原文）
我们描述了一种名为从失败中学习的归纳逻辑编程（ILP）方法。
在这种方法中，ILP系统（学习者）将学习问题分解为三个独立的阶段：生成、测试和约束。在生成阶段，学习者生成一个假设（一个逻辑程序），该假设满足一组假设约束（对假设的句法形式的约束）。在测试阶段，学习者将假设与训练示例进行对比测试。如果一个假设不能蕴含所有正例或蕴含了一个负例，那么这个假设就失败了。如果一个假设失败了，那么在约束阶段，学习者从失败的假设中学习约束，以修剪假设空间，即约束后续的假设生成。例如，如果一个假设过于泛化（蕴含了一个负例），那么约束就会修剪该假设的泛化版本。如果一个假设过于具体（不能蕴含所有正例），那么约束就会修剪该假设的特化版本。这个循环一直重复，直到（i）学习者找到一个蕴含所有正例且不蕴含任何负例的假设，或者（ii）没有更多的假设可以测试。
我们介绍了Popper，这是一个通过结合答案集编程和Prolog实现这种方法的ILP系统。Popper支持无限的问题域，对列表和数字进行推理，学习文本上最小的程序，以及学习递归程序。我们在三个领域（玩具游戏问题、机器人策略和列表转换）上的实验结果表明，（i）约束显著提高了学习性能，以及（ii）Popper在预测准确性和学习时间方面都能胜过现有的ILP系统。
关键词：归纳逻辑编程 · 程序合成 · 程序归纳
1 引言
归纳逻辑编程（ILP）(Muggleton 1991) 是一种机器学习方法。给定目标谓词的示例和背景知识（BK），ILP问题就是归纳出一个假设，这个假设与BK一起正确地概括了示例。ILP的一个关键特点是它将示例、BK和假设表示为逻辑程序（逻辑规则的集合）。
与大多数机器学习方法相比，ILP有几个优点（Cropper et al. 2020）。ILP系统可以从少量示例中泛化，通常是单个示例（Lin et al. 2014）。因为假设是逻辑程序，它们可以被人类阅读，这对于可解释的AI和超强机器学习至关重要（Michie 1988）。最后，由于它们的象征性质，ILP系统自然支持终身学习和迁移学习（Cropper 2020），这被认为是类人AI所必需的（Lake et al. 2016）。
ILP中的基本问题是高效地搜索一个大型假设空间（所有假设的集合）。一种流行的ILP方法是使用集合覆盖算法一次学习一个子句的假设（Quinlan 1990; Muggleton 1995; Blockeel和De Raedt 1998; Srinivasan 2001; Ahlgren和Yuen 2013）。实现这种方法的系统通常很高效，因为它们是示例驱动的。然而，这些系统倾向于学习过于具体的解决方案，并且在学习递归程序方面存在困难（Bratko 1999; Cropper et al. 2020）。
另一种越来越受欢迎的方法是将ILP问题编码为答案集编程（ASP）问题（Corapi et al. 2011; Law et al. 2014; Schüller和Benz 2018; Kaminski et al. 2018; Evans et al. 2019）。实现这种方法的系统通常可以学习最优和递归程序，并且可以利用最先进的ASP求解器，但通常在可扩展性方面存在困难，特别是在问题域大小方面。
在本文中，我们描述了一种称为从失败中学习（LFF）的ILP方法。在这种方法中，学习者（一个ILP系统）将ILP问题分解为三个独立的阶段：生成、测试和约束。在生成阶段，学习者生成一个满足一组假设约束（对假设句法形式的约束）的假设（一个逻辑程序）。在测试阶段，学习者将假设与训练示例进行测试。如果一个假设不能蕴含所有正例或蕴含了一个负例，那么这个假设就失败了。如果一个假设失败了，那么在约束阶段，学习者从失败的假设中学习假设约束，以修剪假设空间，即约束后续的假设生成。
与其他采用生成/测试/约束循环的方法相比（Law 2018），本文的一个关键思想是使用theta-蕴含（Plotkin 1971）将失败的假设转换为一组约束。例如，如果一个假设过于泛化（蕴含了一个负例），那么约束就会修剪该假设的泛化版本。如果一个假设过于具体（不能蕴含所有正例），那么约束就会修剪该假设的特化版本。这个循环一直重复，直到（i）学习者找到一个解决方案（一个蕴含所有正例且不蕴含任何负例的假设），或者（ii）没有更多的假设可以测试。图1说明了这个循环。
在测试阶段，学习者对假设进行测试，发现它失败了，因为它没有蕴含任何正例，因此过于具体。在约束阶段，学习者学习假设约束，以从假设空间中修剪
的特化版本
。现在的假设空间是：
学习者将假设与示例进行对比测试，发现它失败了，因为它蕴含了负例
，因此过于泛化。学习者学习约束以从假设空间中修剪
的泛化版本
。现在的假设空间是：
学习者生成了另一个假设，对其进行测试，发现它没有失败，并将其返回。
与许多迭代细化子句（Quinlan 1990; Muggleton 1995; De Raedt 和 Bruynooghe 1993; Blockeel 和 De Raedt 1998; Srinivasan 2001; Ahlgren 和 Yuen 2013）或细化假设（Shapiro 1983; Bratko 1999; Athakravi 等人 2013; Cropper 和 Muggleton 2016）的ILP方法不同，我们的方法通过学习假设约束来细化假设空间。换句话说，LFF不断构建一组约束。我们学到的约束越多，我们就减少的假设空间就越多。通过推理假设空间，我们的方法可以通过测试单个假设来大幅修剪假设空间的大部分。
我们在Popper中实现了我们的方法，Popper是一个结合了ASP和Prolog的新ILP系统。在生成阶段，Popper使用ASP来声明式地定义、约束和搜索假设空间。这个想法是将问题框架为一个ASP问题，其中答案集（一个模型）对应于一个程序，这也是其他最近的ILP方法所采用的方法（Corapi 等人 2011; Law 等人 2014; Kaminski 等人 2018; Schüller 和 Benz 2018）。通过后来学习假设约束，我们消除答案集，从而修剪假设空间。我们使用ASP的第一个动机是它的声明性质，这使我们能够定义约束来强制执行Datalog和类型限制，修剪不包含基本情况的递归假设的约束，以及修剪失败假设的泛化和特化版本的约束。我们使用ASP的第二个动机是利用最先进的ASP系统（Gebser 等人 2014）来有效解决我们复杂的约束问题。在测试阶段，Popper使用Prolog来测试假设与示例和BK。我们在这个阶段使用Prolog的主要动机是学习使用列表、数字和大域的程序。在约束阶段，Popper从失败的假设中学习假设约束（以ASP约束的形式）来修剪假设空间，即约束后续的假设生成。为了有效地结合这三个阶段，Popper使用ASP的多轮次求解（Gebser 等人 2019）来在三个阶段之间保持状态，例如记住对假设空间学到的冲突。
为了清楚地概述Popper，表1将Popper与Aleph（Srinivasan 2001），一个经典的ILP系统，以及Metagol（Cropper 和 Muggleton 2016），ILASP3（Law 2018），和∂ILP（Evans 和 Grefenstette 2018），分别基于Prolog、ASP和神经网络的三种最先进的ILP系统进行了比较。与Aleph相比，Popper可以学习最优和递归程序。与Metagol相比，Popper不需要元规则（Cropper 和 Touret 2020），因此可以学习具有任意元谓词的程序。与∂ILP相比，Popper支持非接地子句作为BK，因此支持大的和无限的域。与ILASP3相比，Popper不需要接地程序，因此随着域大小的增长，它的扩展性更好（第5.2节）。与所有系统相比，Popper支持假设约束，例如不允许程序中谓词符号的共现，不允许不包含基本情况的递归假设，或防止子蕴涵冗余假设。
ILASP3（Law 2018）是与Popper最相似的ILP方法，也采用了生成/测试/约束循环。我们在第2.6节详细讨论了ILASP3和Popper之间的差异，但现在简要总结它们。ILASP3学习ASP程序，并且可以处理噪声，而Popper学习Prolog程序，目前还不能处理噪声。ILASP3预先计算假设空间中的每个规则，因此在学习具有许多体文字的规则时会遇到困难（第5.1节）。相比之下，Popper不预先计算每个规则，这使得它能够学习具有许多体文字的规则。在每次迭代中，ILASP3找到它能够找到的最好的假设。如果假设没有覆盖其中一个示例，ILASP3找出原因，然后生成约束来指导后续搜索。这些约束是对假设空间中的规则的布尔公式，这种方法需要一组预先计算的规则，并且计算起来可能非常昂贵。另一种看待ILASP3的方式是，它使用反例引导（Solar-Lezama 等人 2008）的方法，将未覆盖的示例 e 转换为一个约束，如果且仅如果 e 被覆盖，则该约束被满足。相比之下，Popper的关键思想是，当一个假设失败时，Popper使用theta-蕴含（Plotkin 1971）将假设本身转换为一组假设约束，以排除它的泛化和特化版本，这不需要一组预先计算的规则，并且计算起来要快得多。
- 我们通过实验（第5节）在三个领域（玩具游戏问题、机器人策略和列表转换）上展示了：（i）约束显著减少了假设空间，（ii）Popper在最优解大小、背景关系数量、域大小、训练示例数量和训练示例大小方面都具有良好的扩展性，以及（iii）Popper在预测准确性和学习时间方面都能显著优于现有的ILP系统。
2 相关工作
2.1 归纳式程序合成
归纳式程序合成的目标是根据部分规范（通常是输入/输出示例）归纳出一个程序（Shapiro 1983）。这一主题引起了计算机科学许多领域研究者的兴趣，特别是机器学习（ML）和编程语言（PL）。
ML和PL方法之间的主要区别在于解决方案（合成程序）的通用性。PL方法通常旨在找到符合规范的任何程序，而不管它是否泛化。事实上，PL方法很少评估他们的系统合成泛化解决方案的能力，即他们不测量预测准确性（Feser 等人 2015; Polikarpova 等人 2016; Albarghouthi 等人 2017; Feng 等人 2018; Raghothaman 等人 2020）。相比之下，ML的主要挑战是学习能够泛化到未见示例的假设。事实上，对于ML系统来说，为给定问题学习一个过于具体的解决方案通常是微不足道的。例如，一个ILP系统可以为每个示例轻易地构造底部子句（Muggleton 1995）。由于这一主要区别，在本节的剩余部分，我们专注于ML方法在归纳式程序合成方面的研究。然而，我们首先简要介绍两种与我们的从失败中学习思想有相似之处的PL方法。
Neo（Feng 等人 2018）使用SMT编码的属性和三阶段循环合成非递归程序。Neo本质上需要SMT编码的属性来描述特定领域的函数（即其背景知识）。例如，他们对head属性的描述，它接受一个输入列表并返回一个输出列表，是公式
Neo的第一阶段构建部分构建的程序。它的第二阶段使用基于SMT的推理来检测部分程序属性的不一致性。第三阶段确定相关的部分程序必须是不一致的，因此可以被修剪。由于它通常使用过度近似的属性，Neo可能无法检测到与示例的不一致性，在这种情况下，没有程序被修剪。相比之下，我们的方法不需要任何背景谓词的属性。我们只检查假设是否蕴含示例，当假设失败时，总是修剪特化和/或泛化。Neo不能合成递归程序，也不能保证合成最优（文本上最小）程序。相比之下，Popper可以学习最优和递归逻辑程序。
ProSynth（Raghothaman 等人 2020）接收一组候选Datalog规则作为输入，并返回它们的一个子集。ProSynth学习约束以禁止某些子句组合，例如，防止蕴含负例的子句一起出现。Popper与ProSynth在几个方面有所不同。ProSynth接收完整的假设空间（候选规则集）作为输入。相比之下，Popper不完全构建假设空间。这一区别很重要，因为预先计算完整的假设空间通常是不可行的。
例如，在ProSynth实验中考虑的候选规则数量最大为1000。相比之下，在我们前两个实验（第5.1节）中，假设空间包含大约\(10^6\)和\(10^{16}\)条规则。ProSynth对解决方案的大小没有保证。相比之下，Popper保证学习到一个最优（最小）解决方案（定理1）。此外，虽然ProSynth合成Datalog程序，Popper还学习确定性程序，因此支持学习具有无限域的程序。
2.2 归纳逻辑编程
归纳程序合成有多种机器学习方法，包括神经方法（Balog 等人 2017; Ellis 等人 2018, 2019）。我们关注归纳逻辑编程（ILP）（Muggleton 1991; Cropper 和 Dumancic 2020）。与其他形式的机器学习一样，ILP系统的目标是学习一个正确泛化给定训练示例的假设。然而，与大多数机器学习形式不同，ILP将数据（示例和假设）表示为逻辑程序。此外，与大多数机器学习形式不同，ILP学习的是关系，而不仅仅是函数。
我们的方法不是细化一个子句（Quinlan 1990; Muggleton 1995; De Raedt 和 Bruynooghe 1993; Blockeel 和 De Raedt 1998; Srinivasan 2001; Ahlgren 和 Yuen 2013），或一个假设（Shapiro 1983; Bratko 1999; Athakravi 等人 2013; Cropper 和 Muggleton 2016），而是通过学习假设约束来细化假设空间。换句话说，我们的方法不断构建一组约束。我们学到的约束越多，我们减少的假设空间就越多。通过推理假设空间，我们的方法可以通过测试单个假设来大幅修剪假设空间的大部分。
Atom（Ahlgren 和 Yuen 2013）使用SAT求解器学习确定性程序，并且也学习约束。然而，因为它基于Progol Muggleton（1995），并且因此采用逆蕴含，Atom在学习递归程序时遇到困难，因为它需要递归程序的基础和步骤案例的示例。出于同样的原因，Atom在学习最优解时也遇到困难。相比之下，Popper可以学习递归和最优解决方案，因为它学习的是程序而不是单独的子句。
2.3 递归
在ILP中学习递归程序一直被认为是一个难题（Muggleton 等人 2012）。没有递归，ILP系统通常很难从少量示例中泛化（Cropper 等人 2015）。事实上，许多流行的ILP系统，如FOIL（Quinlan 1990）、Progol（Muggleton 1995）、TILDE（Blockeel 和 De Raedt 1998）和Aleph（Srinivasan 2001）在学习递归程序方面都存在困难。原因是它们采用集合覆盖方法逐个子句构建假设。每个子句通常是通过搜索子句的顺序来找到的。一种常见的方法是选择一个未覆盖的示例，为这个示例生成底部子句（Muggleton 1995），即逻辑上最具体的子句，蕴含该示例，然后搜索由这个底部子句界定的子蕴涵格（自顶向下或自底向上）。实现这种方法的系统通常很高效，因为假设搜索是示例驱动的。然而，这些系统倾向于学习过于具体的解决方案，并且在学习递归程序方面存在困难（Bratko 1999; Cropper 等人 2020）。为了克服这个限制，Popper搜索逻辑程序（子句集），这是其他ILP系统使用的技术（Bratko 1999; Athakravi 等人 2013; Law 等人 2014; Cropper 和 Muggleton 2016; Evans 和 Grefenstette 2018; Kaminski 等人 2018）。
2.4 最优性
通常有多个（有时是无限多个）假设可以解释数据。决定选择哪个假设是一个难题。许多ILP系统（Muggleton 1995; Srinivasan 2001; Blockeel 和 De Raedt 1998; Ray 2009）不能保证学习到最优解，其中最优通常意味着最小的程序或具有最小描述长度的程序。学习最优解的声称优势是更好的泛化能力。最近的元级ILP方法通常学习最优解，例如具有最少子句数（Muggleton 等人 2015; Cropper 和 Muggleton 2016; Kaminski 等人 2018）或文字数（Corapi 等人 2011; Law 等人 2014）的程序。Popper也学习最优解，以假设中文字总数来衡量。
2.5 语言偏见
ILP方法使用语言偏见（Nienhuys-Cheng 和 de Wolf 1997）来限制假设空间。语言偏见可以分为句法偏见，它限制假设的句法，如子句中允许的变量数量，以及语义偏见，它基于假设的语义来限制，例如它们是否是函数的、非自反的等。
模式声明（Muggleton 1995）是一种流行的语言偏见（Blockeel 和 De Raedt 1998; Srinivasan 2001; Ray 2009; Corapi 等人 2010, 2011; Athakravi 等人 2013; Ahlgren 和 Yuen 2013; Law 等人 2014）。模式声明规定了哪些谓词符号可能出现在一个子句中，它们可能出现的频率，它们的参数类型，以及它们的参数是否必须是具体的。我们不使用模式声明。我们使用的是一种我们称之为谓词声明的简单语言偏见（第3节），用户只需要声明一个谓词符号是否可以出现在子句的头部和/或体部。谓词声明与Aleph中的决定几乎相同（Srinivasan 2001）。唯一的区别是一个小小的句法上的。除了谓词声明，用户还可以提供其他语言偏见，如类型信息，作为假设约束（第2.7节）。
元规则（Cropper 和 Tourret 2020）是许多ILP方法使用的另一种流行的句法偏见（De Raedt 和 Bruynooghe 1992; Wang 等人 2014; Albarghouthi 等人 2017; Kaminski 等人 2018），包括Metagol（Muggleton 等人 2015; Cropper 等人 2020; Cropper 和 Muggleton 2016）以及在某种程度上的∂ILP（Evans 和 Grefenstette 2018）。元规则是一种高阶子句，它定义了假设空间中子句的确切形式。例如，链式元规则的形式是，其中P、Q和R表示谓词变量，允许实例化子句如
。与谓词（和模式）声明相比，元规则是一种更强的归纳偏见，因为它们指定了假设空间中子句的确切形式。然而，元规则的主要问题是确定使用哪些元规则（Cropper 和 Tourret 2020）。用户必须要么（i）提供一组元规则，要么（ii）使用限制在逻辑的某个片段上的元规则集，例如二元Datalog（Cropper 和 Tourret 2020）。这种限制意味着使用元规则的ILP系统难以使用，特别是当BK包含元数大于二的谓词符号时。如果已知合适的元规则，那么，正如我们在“附录A”中所示，Popper可以通过假设约束来模拟元规则。
2.6 答案集编程
近期许多ILP领域的工作使用ASP来学习Datalog（Evans 等人 2019）、确定性（Muggleton 等人 2014; Kaminski 等人 2018; Cropper 和 Dumancic 2020）、规范（Ray 2009; Corapi 等人 2011; Athakravi 等人 2013）和答案集程序（Law 等人 2014）。ASP是一种声明式语言，支持诸如聚合和弱与硬约束等语言特性。大多数ASP求解器只处理接地程序（Gebser 等人 2014），因此，大多数纯ASP基础的ILP系统的一个主要限制是内在的接地问题，尤其是在大域上，例如对列表或数字进行推理——大多数ASP实现不支持列表或实数。例如，ILASP（Law 等人 2014）可以将实数表示为字符串，并通过Clingo的脚本特性将推理委托给Python（Gebser 等人 2014）。然而，在这种方法中，数值计算是在接地输入时执行的，因此接地必须是有限。难以处理大（或无限）域的问题并不是ASP特有的。例如，∂ILP使用神经网络来归纳程序，但只在由有限集合的接地原子形成的BK上工作。为了克服这个接地限制，Popper结合了ASP和Prolog。Popper使用ASP生成确定性程序，这使得它可以对大的和无限的问题域进行推理，例如对列表和实数进行推理。
ILASP3（Law 2018）是一个纯ASP基础的ILP系统，也采用了约束循环。ILASP3学习非分层ASP程序，包括具有选择规则和弱与硬约束的程序，并且可以处理噪声。相比之下，Popper学习Prolog程序，包括在列表和实数上操作的程序，但不能处理噪声。ILASP3预先计算了由一组给定的模式声明定义的假设空间中的每个子句。正如我们在实验1（第5.1节）中所示，这种方法在学会具有许多体文字的子句方面存在困难。相比之下，Popper不预先计算每个子句，这使得它能够学会具有许多体文字的子句。在每次迭代中，ILASP3找到它能够找到的最好的假设。如果假设没有覆盖其中一个示例，ILASP3找出原因，然后生成约束以指导后续搜索。这些约束是假设空间中的规则上的布尔公式，这种方法需要一组预先计算的规则。在最坏情况下，ILASP3可能需要考虑每个假设来构建一个约束（尽管这种最坏情况不太可能发生）。另一种看待ILASP3的方式是，它使用反例引导（Solar-Lezama 等人 2008）的方法，将未覆盖的示例 e转换为一个约束，如果且仅如果e 被覆盖，该约束才被满足。相比之下，当一个假设失败时，Popper将假设本身转换为一组假设约束。Popper的约束不针对特定子句（因为我们不预先计算假设空间），而是使用theta-蕴含对假设的句法进行推理，因此计算起来很快。另一个微妙的区别是ILASP3和Popper中约束循环的使用频率。ILASP3的约束循环最多需要 |E| 次迭代，其中 |E| 是ILASP示例的数量，这些示例是部分解释。因为ILASP3的示例是部分解释（Law 等人 2014），有可能用一个部分解释示例表示多个原子示例。事实上，本文中的每个学习任务都可以表示为一个ILASP正例（Law 等人 2014）。如果以这种方式表示，ILASP3将最多生成一个约束（如果且仅如果一个假设覆盖了示例，该约束将被满足）。因此，如果将示例拆分为每个原子示例一个（部分解释）示例，ILASP3的性能会更好。相比之下，Popper的约束循环不受示例数量的限制，而是由假设空间的大小决定。
2.7 假设约束
约束是我们理念的基础。许多ILP系统允许用户通过子句约束来限制假设空间（Muggleton 1995; Srinivasan 2001; Blockeel 和 De Raedt 1998; Ahlgren 和 Yuen 2013; Law 等人 2014）。例如，Progol、Aleph 和 TILDE 允许用户提供不应违反的子句约束。Popper 也允许用户提供子句约束。此外，Popper 还允许用户提供假设约束（或元约束），这些是针对整个假设（一组子句），而不仅仅是单个子句的约束。作为一个简单的例子，假设您想要禁止两个谓词符号 p/2 和 q/2 同时出现在程序中（在任何子句的任何体文字中）。那么，由于 Popper 在元层面进行推理，这种限制很容易表达：
这个约束修剪了在假设的体部中同时出现谓词符号 p/2 和 q/2 的假设（可能在不同的子句中）。关键要注意的是表达约束的简便性、一致性和简洁性。我们在第4节介绍了我们的完整元级编码。
声明式假设约束有许多优点。例如，通过假设约束，Popper 可以强制执行（可选的）类型、元规则、召回和功能性限制。此外，假设约束允许我们修剪没有基本情况的递归程序和子蕴涵冗余程序。最后，也是最重要的，假设约束允许我们修剪失败假设的泛化和特化版本，我们将在下一节讨论这一点。
Athakravi 等人（2014）引入了领域依赖的约束，这些是由用户提供的对假设空间的约束。INSPIRE（Schüller 和 Benz 2018）也使用预定义的约束来从假设空间中移除冗余（在 INSPIRE 的情况下，每个假设是一个单一的子句）。Popper 也支持这样的约束，但通过从失败的假设中学习约束更进一步。
3 问题设置 （gpt翻译 ，请参考原文）
现在我们定义我们的问题设置。
3.1 逻辑基础知识
我们假设读者熟悉逻辑编程符号（Lloyd 2012），但我们重申一些关键术语。除非另有说明，所有集合都是有限集。一个子句是一组文字。一个子句理论是一组子句。一个Horn子句是一个最多只有一个正文字的子句。
一个Horn理论是一组Horn子句。一个确定性子句是恰好有一个正文字的Horn子句。一个确定性理论是一组确定性子句。如果一个Horn子句不包含函数符号，并且出现在子句头部的每个变量也出现在子句体部，则该Horn子句是Datalog子句。一个Datalog理论是一组Datalog子句。同时用术语替换子句中的变量
是一个替换（substitution），表示为
。当
时，
3.2问题设置
我们的问题设置基于从蕴含中学习的归纳逻辑编程（ILP）设置（De Raedt 2008）。
我们的目标是将目标谓词的正例和负例、背景知识（BK）作为输入，并返回一个假设（逻辑程序），该程序结合BK能够蕴含所有正例且不蕴含任何负例。在本文中，我们专注于学习确定性程序。我们将在未来的工作中将方法推广到非单调程序。
ILP方法搜索假设空间，即可学习的假设集合。ILP方法通过语言偏见（第2.5节）来限制假设空间。存在几种形式的语言偏见，如模式声明（Muggleton 1995）、语法（Cohen 1994）和元规则（Cropper和Tourret 2020）。我们使用一种简单的语言偏见，我们称之为谓词声明。谓词声明简单地声明哪些谓词符号可能出现在假设中子句的头部（头部声明）或体部（体部声明）：
定义1（头部声明）：头部声明是一个形式为head_pred(p,a)的基原子，其中p是具有a元数的谓词符号。
定义2（体部声明）：体部声明是一个形式为body_pred(p,a)的基原子，其中p是具有a元数的谓词符号。
谓词声明几乎与Aleph的确定性（Srinivasan 2001）相同，但存在一个小的语法差异，因为确定性的形式是：
determination(TargetName/Arity,BackgroundName/Arity)。
声明偏见D是一对头部（D h）和体部（D b）声明集合的组合。
我们定义一个声明一致的子句：
声明偏见D是一个由头部（D h）和体部（D b）声明集合组成的对（D h , D b）。
我们定义一个声明一致的子句：
定义3（声明一致的子句）：设D = (D h , D b)是一个声明偏见，C = h ← b1, b2, ..., b n是一个确定性子句。那么C与D声明一致当且仅当：
- h是一个形式为p(X1, ..., X n)的原子，并且head_pred(p,n)在D h中
- 每一个bi是一个形式为p(X1, ..., X n)的文字，并且body_pred(p, n)在D b中
- 每一个X i是一个一阶变量
示例2（声明一致性）：设D是声明偏见：
({head_pred(targ,2)}, {body_pred(head,2), body_pred(tail,2)})
那么以下子句都与D一致：
相比之下，下列子句与D不一致:
我们定义一个声明一致的假设：
定义4（声明一致的假设）：一个声明一致的假设H是一组确定性子句，其中每个C ∈ H都与D声明一致。
示例3（声明一致的假设）：设D是声明偏见：
({head_pred(targ,2)}, {body_pred(head,2), body_pred(tail,2)})
那么两个声明一致的假设是：
除了声明偏见之外，我们还通过假设约束来限制假设空间。我们首先澄清我们所说的约束是什么意思：
定义5（约束）：约束是一个没有头部的Horn子句，即一个否认。我们说如果约束的所有体文字都为真，则约束被违反。
我们不是为特定编码（例如我们在第4节中使用的编码）定义假设约束，而是使用一个更一般的定义：
定义6（假设约束）：设L是一种定义假设的语言，即一种元语言。那么，一个假设约束就是在L中表达的约束。
示例4 在第4节中，我们引入了一种用于确定性程序的元语言。在我们的编码中，原子head_literal(Clause, Pred, Arity, Vars)表示子句Clause有一个头部文字，谓词符号为Pred，具有Arity元数，并且有参数Vars。这种语言中的一个示例假设约束是：
这个约束表明，具有2元数的谓词符号p不能出现在任何假设中子句的头部。
示例5 在我们的编码中，原子body_literal(Clause, Pred, Arity, Vars)表示子句Clause具有一个体文字，谓词符号为Pred，具有Arity元数，并且有参数Vars。这种语言中的一个示例假设约束是：
这个约束表明，如果谓词符号p出现在子句的头部（不一定是同一个子句），则它不能出现在子句的体部。
我们定义一个约束一致的假设：
3.3 假设空间
LFF的目的是通过学习假设约束来减少假设空间的大小。未受约束的假设空间的大小是声明偏见和额外边界变量的函数：
命题1（假设空间大小）：设是一个具有最大元数a的声明偏见，v是子句中允许的最大唯一变量数，m是子句中允许的最大体文字数，n是假设中允许的最大子句数。那么未受约束的假设空间中假设的最大数量是：
正如这个结果所示，对于非平凡的输入，假设空间是巨大的，这激发了我们使用学习到的约束来修剪假设空间。
3.4 泛化和特化
为了修剪假设空间，我们学习约束来移除失败假设的泛化和特化。我们通过θ-包含（或简称包含）（Plotkin 1971）从句法上讨论假设的一般性：
3.5 从失败中学习约束
在LFF的测试阶段，学习器会将假设与示例进行对比测试。当假设不完整或不一致时，假设就会失败。如果假设失败，学习器会从不同类型的失败中学习假设约束。我们定义了两种通用类型的约束，泛化和特化，它们适用于任何子句理论，并表明它们是合理的，因为它们不会修剪解决方案。我们还定义了一种消除约束，它在某些假设下允许我们修剪泛化和特化约束不修剪的程序，并且我们表明它是合理的，因为它不会修剪最优解决方案。我们依次描述这些约束。
3.5.1 泛化和特化
为了说明泛化和特化，假设我们有正例E+、负例E−、背景知识B和一个假设H。首先考虑将H与E−对比测试的结果：
3.5.2 消除
假设结果是 Pnone，即 H 是完全不完备的。那么 H 过于具体，因此与 P some 一样，我们可以修剪 H 的特殊化。然而，由于 H 是完全不完备的（即不蕴涵任何正例），在某些假设下，我们可以修剪更多。如果 H 是完全不完备的，那么 H 不需要出现在一个完备且可分离的假设中：
消除约束不像泛化和特化约束那样在相同的意义上是合理的，因为它们会从假设空间中修剪解决方案（定义11）。
然而，对于可分离的确定性程序，消除约束在最优解方面是合理的，即它们只从假设空间中修剪非最优解。为了展示这一结果，我们首先引入一个引理：
这个证明依赖于假设H是（i）一个确定性程序和（ii）可分离的。条件（i）很清楚，因为证明依赖于确定性程序的单调性。为了说明条件（ii），我们给出一个反例来展示为什么我们不能使用消除约束来修剪不可分离的假设：
那么h是完全不一致的，因此没有理由让h出现在一个可分离的假设中。
然而，h仍然可以出现在一个递归假设中，其中子句相互依赖，例如h 2：
3.5.3 约束总结
总结来说，这些不同结果的组合意味着不同的约束组合，如表2所示。在下一节中，我们将介绍Popper，它使用这些约束来学习确定性程序。
4 Popper
Popper实现了LFF方法，并且分为三个独立的阶段：生成、测试和约束。算法1概述了结合这三个阶段的Popper算法。为了学习最优解（定义14），Popper搜索越来越大的程序。
我们详细描述生成、测试和约束阶段，我们如何使用ASP的多轮次求解（Gebser等人，2019）在这三个阶段之间保持状态，然后证明Popper的合理性和完整性。
Popper的生成步骤接收以下输入：（i）谓词声明，（ii）假设约束，以及（iii）假设中变量、文字和子句的最大数量限制，并返回一个代表确定性程序的答案集（如果存在）。这个想法是定义一个ASP问题，其中答案集（一个模型）对应于一个确定性程序，这是其他最近的ILP方法也采用的方法（Corapi等人，2011；Law等人，2014；Kaminski等人，2018；Schüller和Benz，2018）。换句话说，我们在ASP中定义了一种元语言来表示确定性程序。Popper使用ASP约束来确保确定性程序与声明一致并遵守假设约束，例如执行类型限制或禁止相互递归。通过后来添加学习到的假设约束，我们消除答案集，从而减少假设空间。换句话说，我们学到的约束越多，我们减少的假设空间就越多。
图2显示了生成程序的基础ASP程序。这个想法是找到一个具有适当头部和体部文字的答案集，它们都有参数（Clause, Pred, Arity, Vars）来表示在子句Clause中有一个文字，具有谓词符号Pred、元数Arity和变量Vars。例如，head_literal(0, p, 2, (0, 1))表示子句0有一个头部文字，谓词符号为p，元数为2，变量为(0, 1)，我们将其解释为(A, B)。同样，body_literal(1, q, 3, (0, 0, 2))表示子句1有一个体文字，谓词符号为q，元数为3，变量为(0, 0, 2)，我们将其解释为(A, A, C)。头部和体部文字分别受到head_pred和body_pred声明的限制。表3显示了答案集与确定性程序之间的对应关系示例，我们将确定性程序表示为Prolog程序。
4.1 有效性、冗余性和效率约束
Popper使用假设约束（以ASP约束的形式）来消除答案集，即修剪假设空间。Popper使用约束来修剪无效的程序。例如，图3显示了针对递归程序的特定约束，比如防止没有基本情况的递归。Popper还使用约束来减少冗余。例如，Popper修剪包含包含冗余的程序，比如修剪以下程序，因为第一个子句包含第二个子句：
最后，Popper使用约束来提高效率（主要是通过消除冗余）。
例如，Popper使用约束来按顺序使用变量，这可以修剪程序p(B):- q(B)，因为我们本可以生成p(A):- q(A)。
4.2语言偏见的制约
Popper 支持可选的假设约束来剪枝假设空间。图 4 显示了示例语言偏见约束，例如防止单一变量并强制执行 Datalog 限制（头部变量必须出现在主体中）。声明式约束有许多好处，尤其是定义它们的简便性。例如，向 Popper 添加简单类型只需要图 4 所示的单个约束。通过约束，Popper 还支持模式声明的召回和输入/输出参数的标准概念（Muggleton 1995）。Popper 还支持功能性和不可反身性约束，以及对递归程序的约束，例如不允许左递归或相互递归。最后，正如我们在“附录 A”中展示的，Popper 还可以使用约束来强制实施元规则，这是许多 ILP 系统使用的子句模板（Cropper 和 Tourret 2020），这确保了程序中的每个子句都是元规则的一个实例。
与许多 ILP 系统（Muggleton 1995; Srinivasan 2001; Athakravi 等人 2014; Law 等人 2014; Schüller 和 Benz 2018）一样，Popper 支持子句约束，这允许用户从假设空间中剪枝特定的子句。Popper 还支持更一般的概念——假设约束（定义 6），这些约束是针对整个程序（一组子句）而不是单个子句定义的（也在先前的工作（Athakravi 等人 2014）中使用）。例如，假设约束允许我们剪枝不包含基本情况子句的递归程序（图 3），剪枝左递归或相互递归的程序，或者剪枝子句之间存在包含冗余的程序。
作为一个玩具示例，假设你想要禁止两个谓词符号 p/2 和 q/2 同时出现在一个程序中。那么这个假设约束在 Popper 中表达起来是很简单的：
正如我们在“附录 A”中展示的，Popper 可以通过假设约束来模拟元规则。我们不知道有任何其他 ILP 系统支持假设约束，至少没有像 Popper 那样易于使用和灵活。
4.4 测试
在测试阶段，Popper 将答案集转换为一个确定性程序，并将其与训练示例进行测试。正如表 3 所示，这种转换是直接的，除非给出了输入/输出参数方向，在这种情况下，Popper 会排列子句的体文字。为了评估一个假设，我们使用 Prolog 解释器。对于每个示例，Popper 检查该示例是否由假设和背景知识所蕴含。我们强制执行一个超时时间来停止不终止的程序。如果一个假设失败，那么 Popper 会识别出发生了哪种类型的失败以及生成哪些约束（使用第 3.5 节中的失败和约束）。
4.5 约束
如果一个假设失败，那么在约束阶段，Popper 推导出 ASP 约束，这些约束剪枝假设，从而限制后续的假设生成。具体来说，我们描述了我们如何将一个失败的假设（一个确定性程序）转换为一个假设约束（一个用第 4 节中编码编写的 ASP 约束）。我们描述了 Popper 使用的泛化、特化和消除约束，基于第 3.5 节中的定义。由于我们的实验考虑了一个没有约束剪枝的 Popper 版本，我们还描述了 banish 约束，它剪枝一个特定的假设。为了区分 Prolog 和 ASP 代码，我们用打字机字体表示确定性程序的代码，用粗体打字机字体表示 ASP 代码。
4.5.1 编码原子
在我们的编码中，原子 f(A, B) 被表示为 head_literal(Clause, f, 2, (V0, V1)) 或 body_literal(Clause, f, 2, (V0, V1))。常数 2 是谓词的参数数量，变量 Clause 表示子句索引未确定。两个函数将原子编码为 ASP 文字。函数 encodeHead 编码头部原子，encodeBody 编码体部原子。第一个参数指定原子所属的子句。第二个参数是原子本身。原子的变量通过 encodeVar 函数转换为我们 ASP 编码中的变量。
4.5.2 编码子句
我们通过构建原子的编码来编码子句。设 Cl 为子句索引变量。考虑子句 last(A, B) :- reverse(A, C), head(C, B)。以下 ASP 文字编码了这些原子在单个子句中的位置：
由于子句可以出现在多个假设中，因此使用标识符来引用子句是方便的。函数 clauseIdent 将子句映射到唯一的 ASP 常量。我们使用 ASP 文字 included_clause(cl, id) 来表示索引为 cl 的子句包含由 id 标识的子句的所有文字。inclusionRule 函数生成一个包含规则，即当提供的子句的所有文字一起出现在一个子句中时，其头部为真的 ASP 规则：
4.5.3 泛化约束
给定一个假设 H，根据定义 17，任何包含 H 所有子句的假设都是 H 的泛化。我们利用这一事实来定义函数 generalisationConstraint，它将一组子句转换为 ASP 编码的子句包含检查规则以及一个泛化约束（定义 19）。我们使用 exactClause 来强制执行一个子句不被特化。每个子句都被赋予自己的 ASP 变量，这意味着子句可以以任何顺序出现。
图 5 展示了 generalisationConstraint 派生出一个包含规则和一个泛化约束。
4.5.4 特化约束
给定一个假设 H，根据定义 18，任何包含 H 的每个子句的假设，其中每个子句可以被特化，并且不包含其他子句，都是 H 的特化。函数 specialisationConstraint 利用这一事实来派生一个 ASP 编码的特化约束（定义 20）以及包含规则。当 included_clause(cl, id) 为真时，可以在子句 cl 中出现额外的原子。文字 not clause(n) 确保不会向提供的假设的 n 个不同子句中添加额外的子句。
的第一个子句特化了
中的两个子句，然而
并不是
的特化。
根据定义 18，每个子句都需要被提供的子句所包含。请注意，specialisationConstraint 只考虑最多有 n 个子句的假设。这些子句中的任何一个不可能是非特化的，因为原始的 n 个子句中的每一个都需要通过一个不同的子句来特化。
图 6 展示了由 specialisationConstraint 派生的特化约束。
4.5.5 消除约束
根据命题 5，给定一个完全不确定的假设 H，任何包含 H 所有子句的可分离假设，其中每个子句可以被特化，都不能是最优解。我们在 Popper 编码中添加以下代码来检测可分离的假设：
4.5.6消除约束
在实验中，我们将 Popper 与没有约束剪枝的版本进行比较。为此，我们需要从假设空间中移除单个假设。我们引入了驱逐约束来达到这个目的。为了剪枝特定的假设，不应该剪枝具有不同变量的假设。我们通过以下定义改变了 encodeVar 函数的行为来实现这个条件。通常，encodeVar 返回 ASP 变量，然后这些变量被具体化为对应于假设变量的索引。相反，根据以下定义，encodeVar 直接为假设变量分配相应的索引：
对于驱逐约束，不允许在子句中添加额外的文字，也不允许添加额外的子句。
下面的函数 banishConstraint 在将假设转换为 ASP 编码的驱逐约束时确保了这两个条件。exactClause 确保提供的子句不特化。文字 not clause(n) 断言没有超过原始数量的子句。
4.6 Popper 循环和多轮次求解
如果按照算法 1 的简单实现，比如在程序大小上执行迭代加深，会在生成步骤中重复进行归一化和求解。为了提高效率，我们使用 Clingo 的多轮次求解（Gebser 等人，2019）来在三个阶段之间保持状态。多轮次求解的思想是，ASP 程序的求解过程的状态可以被保存，以帮助求解该程序的修改版本。多轮次循环的本质是，将一个归一化程序提供给 ASP 解算器，产生一个答案集，其处理会导致程序的（一阶）扩展。只有这个扩展然后需要归一化并添加到运行中的 ASP 实例中，这意味着运行中的求解器可以，例如，保持学习到的冲突。
Popper 如下使用多轮次求解。初始 ASP 程序是第 4 节中描述的编码。Popper 要求 Clingo 对初始程序进行归一化并准备求解。在生成阶段，求解器被要求返回当前程序的一个答案集，即模型。Popper 将这样的一个答案集转换为确定性程序，并将其与示例进行测试。如果一个假设失败，Popper 使用第 4.5 节中的函数生成 ASP 约束，并将它们添加到运行中的 Clingo 实例中，该实例归一化约束并添加新的（命题）规则到运行中的求解器。我们对程序大小施加了一个硬约束，该约束涉及一个外部原子（Gebser 等人，2019）size(N)。最初，程序只需要包含一个字面量。当没有更多答案集时，我们增加程序大小。每次我们增加程序大小时，例如从 N 增加到 N+1，我们添加一个新的原子 size(N+1) 和一个新的强制执行这个程序大小的约束。此时只有新约束被归一化。我们通过将外部原子 size(N) 设置为 false 来禁用以前的约束。求解器知道哪些搜索空间（即假设空间）的部分已经被考虑过，并且不会再次访问它们。这个循环一直重复，直到（i）Popper 找到一个最优解，或者（ii）没有更多假设需要测试。
4.7 实例演示
为了说明 Popper 的工作原理，让我们重新考虑引言中学习 last/2 假设以找到列表最后一个元素的例子。为了简化，假设初始假设空间 H1：
Popper 将这个约束添加到元级 ASP 程序中，从而从假设空间中剪枝了 h2 和 h5。此外，由于 h1 不蕴含任何正例（完全不完整），Popper 还生成了一个消除约束：
4.8 正确性
我们现在展示 Popper 的正确性。然而，我们只能展示当假设空间仅包含可判定程序时这一结果，例如 Datalog 程序。当假设空间包含任意确定性程序时，这些结果就不成立，因为检查任意确定性程序的蕴含性只是半可判定的（Tärnlund 1977）。换句话说，本节中的结果只有在假设空间中的每个假设都保证会终止时才成立。
我们首先展示 Popper 的基础编码（图 2）能够生成每个声明一致的假设（定义 4）。
命题 8（完备性）如果存在解决方案，Popper 将返回一个解决方案。
证明 假设，出于矛盾，Popper 没有返回解决方案，这意味着
(1) Popper 返回了一个不是解决方案的假设，或者 (2) Popper 没有返回解决方案。
情况 (1) 不可能成立，因为命题 7 表明 Popper 返回的每个假设都是解决方案。对于情况 (2)，根据命题 6，Popper 可以生成每个假设，所以必须是 (i) Popper 没有终止，(ii) 解决方案没有通过测试阶段，或者 (iii) 每个解决方案都被错误地剪枝了。情况 (i) 不可能成立，因为命题 1 表明假设空间是有限的，所以只有有限多的假设需要生成和测试。情况 (ii) 不可能成立，因为根据定义，解决方案是一个通过测试阶段的假设。情况 (iii) 不可能成立，因为引理 2 表明 Popper 从不剪枝最优解决方案。这些情况是穷尽的，所以假设不能成立，因此如果存在解决方案，Popper 将返回一个解决方案。
5 实验
我们现在评估 Popper。Popper 从失败的假设中学习约束，以剪枝假设空间，以提高学习性能。因此，我们声称，与无约束学习相比，约束可以提高学习性能。人们可能会认为这种改进是显而易见的，即约束肯定会提高性能。然而，实际上是否如此，以及约束在多大程度上会提高学习性能并不清楚，因为 Popper 需要 (i) 分析失败的假设，(ii) 从它们生成约束，以及 (iii) 将约束传递给 ASP 系统，然后 ASP 系统需要归一化并解决它们，这可能都有一定的计算开销。因此，我们的实验旨在回答以下问题：
Q1 约束能否提高与无约束学习相比的学习性能？
为了回答这个问题，我们比较有无约束阶段的 Popper。换句话说，我们将 Popper 与一种蛮力生成和测试方法进行比较。为此，我们使用一个只启用了驱逐约束的 Popper 版本，以防止重复生成失败的假设。我们称这个系统为 Enumerate。
命题 1 表明，从失败中学习的假设空间的大小是许多参数的函数，包括谓词声明的数量、子句中唯一变量的数量，以及假设中子句的数量。为了探索这个结果，我们的实验旨在回答以下问题。
Q2 Popper 的扩展性如何？
为了回答这个问题，我们评估在变化 (i) 最优解的大小，(ii) 谓词声明的数量，(iii) 问题中的常数数量，(iv) 子句中唯一变量的数量，(v) 子句中最大文字数量，以及 (vi) 假设中允许的最大子句数量时 Popper 的性能。
我们还将 Popper 与现有的 ILP 系统进行比较。因此，我们的实验旨在回答以下问题。
Q3 与其他 ILP 系统相比，Popper 的性能如何？
为了回答这个问题，我们将 Popper 与 Aleph (Srinivasan 2001)、Metagol、ILASP2i (Law et al. 2016) 和 ILASP3 (Law 2018) 进行比较。然而，需要注意的是，直接比较 ILP 系统是困难的，因为不同的系统在不同的问题上表现出色，并且通常采用不同的偏见。例如，直接比较基于 Prolog 的 Metagol 与基于 ASP 的 ILASP 是困难的，因为 Metagol 通常用于学习递归列表操作程序，如字符串转换和排序算法，而 ILASP 不支持显式列表，因为 ILASP 构建的 ASP 系统 Clingo (Gebser et al. 2014) 不允许显式列表。同样，Aleph 和 ILASP3 支持噪声，而 Metagol 和 Popper 不支持。此外，由于 ILP 系统有许多学习参数，通常可以展示存在某些参数设置，使得系统 X 在特定问题上的性能优于系统 Y。总体而言，直接比较 ILP 系统是困难的，因此读者不应将结果解释为系统 X 比系统 Y 更好。
5.1 按钮
第一个实验的目的是评估 Popper 在最优解大小变化时的扩展性。因此，我们需要一个我们可以控制最优解大小的问题。我们考虑一个基于 IGGP 游戏按钮和灯光（Cropper 等人，2020）的问题，但故意简化：给定 p 个按钮，学习需要按下哪些 n 个按钮才能获胜。例如，对于 n = 3，一个解决方案可能是：
win(A) :- button6(A), button4(A), button7(A)
变量 A 表示玩家，button p 表示玩家 A 按下了按钮 p。
在这个实验中，我们固定 p（按钮的数量），并变化 n（需要按下的按钮数量），这直接对应于最优解的大小。
5.1.1 材料
我们考虑问题的两种变体，其中 p = 20 和 p = 200，我们分别称之为 small 和 big。我们比较 Popper、Enumerate、Metagol、ILASP2i、ILASP3 和 Aleph。为了比较这些系统，我们尝试使用设置，使得每个系统大约搜索相同的假设空间。然而，确保系统搜索相同的假设空间几乎是不可能的。例如，Metagol 执行自动谓词发明，因此考虑的假设空间与其他系统不同。确切使用的语言偏见在“附录 B”中。
ILASP 设置 我们向 ILASP 的作者 Mark Law 请教了如何最好地使用 ILASP2i 和 ILASP3 解决这个问题。14 我们使用相同的设置运行 ILASP2i 和 ILASP3，因此我们简单地将两者都称为 ILASP。我们使用‘no constraints’（无约束）、‘no aggregates’（无聚合）、‘disable implication’（禁用蕴含）、‘disable propagation’（禁用传播）和‘simple contexts’（简单上下文）标志运行 ILASP。我们告诉 ILASP 每个 BK 关系是积极的，这阻止了它使用否定来生成体文字。我们还使问题成为命题性的，并使用上下文依赖的示例（Law 等人，2016），其中每个示例的上下文依赖 BK 包含该示例中按下的按钮。我们最初尝试使用最多十个体文字运行 ILASP（‘-ml = 10’ 和 ‘–max-rule-length = 11’），但是给定这个参数时，ILASP 会因为预先计算假设空间中的每条规则而无法在时限内终止。因此，对于每个按钮数量 n，我们将最大体文字数量设置为 n（‘-ml = n’ 和 ‘–max-rule-length = n + 1’），以确保 ILASP 在一些问题上能够终止。
Metagol 设置 Metagol 需要元规则（第 2.5 节）来指导证明搜索。我们为 Metagol 提供了以下两个元规则：
Popper 和 Enumerate 设置 我们将 Popper 和 Enumerate 设置为最多使用 1 个唯一变量，最多 1 个子句，以及最多 n 个体文字。这些设置与 Metagol 的元规则所施加的设置相匹配，也与 ILASP 的命题表示大致相符。我们限制子句最多有 n 个体文字，以匹配 ILASP 的设置。当允许多达十个体文字时，Popper 的表现几乎相同。
Aleph 设置 我们还设置了最多搜索节点数为 5000。与 Popper、Enumerate 和 ILASP 一样，我们为 Aleph 的每个值 n 增加了最大子句长度。
5.1.2 方法
对于 {1, 2, ..., 10} 中的每个 n，我们生成 200 个正面和 200 个负面示例。正面示例是按下了正确 n 个按钮的玩家。为了生成正面示例，我们从不重复抽取 n 个整数从集合 {1, ..., p} 中，这些整数对应于必须按下的 n 个按钮。我们还抽取了其他也被按下的按钮，但这些按钮不一定在所有正面示例中都被按下。负面示例是没有按下正确 n 个按钮的玩家。为了生成负面示例，我们从不必须按下的集合中抽取最多 n-1 个按钮。然后我们抽取其他不应该被按下的按钮。通过包含所有 n 个负面示例和 n-1 个正确按钮，我们保证只有一个正确的解决方案。我们测量学习时间为学习解决方案的时间。我们对每个任务强制执行每分钟的超时时间。我们重复每次实验十次并绘制标准误差。
5.1.3 结果
图 9 显示，Popper 在两个数据集上都明显优于 Enumerate。在小数据集（p = 20）上，Enumerate 只在必须按下三个按钮时（n = 3）学习程序。在大数据集（p = 200）上，Enumerate 只在必须按下一个按钮时（n = 1）学习程序。相比之下，在两个数据集上，Popper 都能学习到必须按下十个按钮时（n = 10）的程序，即具有十个体文字的程序。此外，Popper 总是在时限内轻松学习到解决方案。这一结果强烈表明，问题 Q1 的答案是肯定，约束可以显著提高学习性能。
Popper 在两个数据集上都优于 Metagol。对于小数据集，Metagol 学习的最大程序是当 n = 4 时，学习时间为 50 秒，而 Popper 为 1 秒。对于大数据集，Metagol 学习的最大程序是当 n = 3 时，学习时间为 57 秒，而 Popper 为 8 秒。Metagol 因为其低效的搜索而挣扎。Metagol 通过对解决方案中允许的子句数量进行迭代加深（Muggleton 等人，2015）。然而，如果在搜索过程中某个子句或文字失败，Metagol 不会记住这个失败，并会在每个深度（甚至在同一深度多次）重试已经失败的子句和文字。相比之下，如果某个子句失败，Popper 从失败中学习约束，所以它不会再尝试那个子句（或其特化）。
Popper 在两个数据集上都优于 ILASP2i 和 ILASP3。ILASP2i 只在小数据集上学习了具有四个（小数据集）和一个大数据库集上的一个体文字的程序。ILASP3 也只在小数据集上学习了具有四个（小数据集）和一个大数据库集上的一个体文字的程序。ILASP2i 和 ILASP3 都在这个问题上挣扎，因为它们预先计算了假设空间中的每个子句，这意味着它们难以学习具有许多体文字的子句。相比之下，Popper 可以在两个数据集上学习具有十个体文字的程序。
当 n > 8 时，Aleph 在小数据集上优于 Popper。然而，在大数据集上，当 n > 3 时，Popper 优于 Aleph。
总体而言，这个实验的结果表明：（i）问题 Q1 的答案是肯定的，约束提高了学习性能；（ii）问题 Q2 的答案是 Popper 在解决方案的体文字数量和背景关系数量方面扩展良好；（iii）问题 Q3 的答案是 Popper 在变化最优解大小和背景关系数量时可以优于其他 ILP 系统。
5.2 机器人
这个第二个实验的目的是评估 Popper 在领域规模（即常量签名）方面的扩展能力。因此，我们需要一个可以控制领域规模的问题。我们考虑一个机器人策略学习问题（Cropper 和 Muggleton 2015）。在一个 n × n 的网格世界中有一个机器人。给定一个任意的起始位置，目标是学习一个通用策略，将机器人移动到网格中的最顶端行。例如，在一个 10 × 10 的世界中，起始位置为 (2, 2)，目标是移动到位置 (2, 10)。该领域包含所有可能的机器人位置。因此，我们通过改变 n（即世界的大小）来改变领域的规模。最优解决方案是一个递归策略，持续向上移动，直到到达最顶端行。重申一下，我们故意固定最优解决方案，以便实验中的唯一变量是领域规模（即网格世界的大小），我们逐步增加其规模来评估系统的扩展能力。
5.2.1 材料
我们考虑两种表示方法：一种用于 Popper、Enumerate、Metagol 和 Aleph 的表示方法，然后是为帮助 ILASP 解决问题而设计的一种表示方法。在给定 Prolog 表示时，由于归一化问题，ILASP2i 和 ILASP3 都无法解决任何问题。在这两种表示中，我们都提供了作为背景知识（BK）的四个二元关系：move_right、move_left、move_up 和 move_down，它们改变了状态，例如 move_right((2,2),(3,2))，以及四个一元关系：at_top、at_bottom、at_left 和 at_right，它们检查状态。使用的确切语言偏见可以在“附录 C”中找到。
Prolog 表示 在 Prolog 表示中，一个示例是一个形式为 f(s1, s2) 的原子，其中 s1 和 s2 分别代表起始状态和结束状态。状态是一对离散坐标 (x, y)，表示机器人的列（x）和行（y）位置。
ILASP 表示 当给定 Prolog 表示时，由于归一化问题，ILASP2i 和 ILASP3 都无法解决这个实验中的任何问题。因此，我们请 Mark Law 帮助我们设计了一种更合适的表示方法。在这种表示中，一个示例是一个形式为 f(s2) 的原子，其中 s2 代表结束状态。每个示例都是一个独特的 ILASP 示例（一个部分解释），它有自己的上下文，其中起始状态在上下文中以 start_state(s1) 的形式给出。这种表示减轻了 Prolog 表示的归一化问题。
ILASP2i 和 ILASP3 设置 我们使用相同的设置运行 ILASP2i 和 ILASP3，因此我们再次将两者统称为 ILASP。我们使用‘无约束’、‘无聚合’、‘禁用蕴含’、‘禁用传播’和‘简单上下文’标志运行 ILASP。我们告诉 ILASP 每个 BK 关系是积极的、反自反的和对称的。我们还采用一组‘偏见约束’来减少假设空间。我们还限制了 BK 关系的一些召回值。我们将 ILASP 设置为最多使用四个唯一变量和三个体文字（‘-ml=3’ 和 ‘–max-rule-length=4’）。完整的语言偏见限制可以在“附录 C”中找到。
Metagol 设置 我们为 Metagol 提供了图 10 中的元规则。这些元规则构成了单体自由片段的一元和二元 Datalog 的几乎完整的元规则集（Cropper 和 Tourret 2020）。
Popper 设置 我们允许 Popper 和 Enumerate 每个子句最多使用四个唯一变量，最多三个体文字（与 ILASP 设置匹配），以及最多三个子句。
Aleph 设置 我们将最大变量深度和子句长度设置为六，并将最大搜索节点数设置为 30,000。
5.2.2 方法
我们在每个 n × n 网格世界中运行实验，其中 n 是 {10, 20, ..., 100} 中的每个数。为了生成示例，对于起始状态，我们均匀地采样那些不在世界顶部的位置。对于正面示例，结束状态是最顶部的位置，例如 (x, n)，其中 n 是网格大小。对于负面示例，我们随机采样起始和结束状态，并在示例是正面示例时拒绝该示例。为了确保有一些负面示例具有最顶部的位置，在 25% 的示例中，我们将结束位置设置为列 y 的最顶部行，但确保起始位置不是 y。我们替换采样 20 个正面和 20 个负面训练示例，以及 1000 个正面和 1000 个负面测试示例。因此，默认的预测准确率是 50%。我们测量预测准确率和学习时间。我们对每个任务强制执行每分钟的超时时间。如果一个系统在给定时间内未能学习到解决方案，则它只达到默认预测准确率（50%）。我们重复每次实验十次并绘制标准误差。
5.2.3 结果
图 11 显示了结果。Popper 达到了所有系统中最好的预测准确率。Enumerate 是表现第二好的系统，尽管它并不总是学习到最优解。Popper 比 Enumerate 快得多（平均大约快 40 倍），并且是所有系统中最快的。Popper 的学习时间随着网格大小的增长而略微减少。这一现象的原因有两个。首先，当网格世界较小时，通常有许多小型程序覆盖了一些正面示例但没有任何负面示例，例如：
由于它们覆盖了一些示例，Popper 无法完全排除它们。然而，随着网格大小的增加，这些较小的程序覆盖示例的可能性较小，因为示例在网格上的分布更加分散。第二，解决方案要么有五个要么有六个文字，随着世界大小的增加，较小的解决方案变得更有可能。这些原因解释了为什么 Enumerate 的预测准确率随着网格大小的增加而提高。
Popper 学习时间不增加的原因是域大小对从失败中学习假设空间的大小没有影响（命题 1）。网格大小的唯一影响是在较大的网格上执行诱导的 Prolog 程序的任何开销。这一结果表明 Popper 可以很好地适应域大小。
Popper 在所有情况下都优于 Metagol。对于一个小的 10x10 网格世界，Metagol 学习了最优解，并且比 Popper 学得更快（Metagol 花了 1 秒，而 Popper 花了 9 秒）。然而，随着网格大小的增加，Metagol 的性能迅速下降。对于大于 20 的网格大小，Metagol 几乎总是在找到解决方案之前就超时了。原因是 Metagol 通过诱导和执行示例上的部分程序来搜索假设。换句话说，Metagol 使用示例来指导假设搜索。随着网格大小的增加，需要构建的部分程序更多，因此它的性能受到影响。请注意，当 Metagol 学习到解决方案时，它总是一个准确的解决方案。
Popper 在预测准确率和学习时间方面都优于 ILASP2i 和 ILASP3。ILASP3 甚至在给定的时间内无法学习任何解决方案，即使是对于 10x10 的世界。ILASP2i 最初在给定的时间限制内学习解决方案，但随着网格大小的增加而挣扎。请注意，当 ILASP2i 学习到解决方案时，它总是一个准确的解决方案。
ILASP2i 优于 ILASP3，因为一旦 ILASP2i 找到解决方案，它就会终止。相比之下，ILASP3 找到了一个保证覆盖示例的假设模式（在这个特殊情况下，也意味着找到了解决方案），然后继续寻找替代的假设模式。ILASP3 所做的额外工作在学习一般 ASP 程序时是必要的，但在这种特殊情况下（没有 ILASP 负面示例）它是不必要的，并且计算成本很高。我们建议读者参考 Law 的论文（Law 2018）以获取 ILASP2i 和 ILASP3 的详细比较。
Popper 优于 Aleph。对于小网格世界，Aleph 有时会学习推广到训练集的程序（例如，向上移动三次）。但随着网格大小的增加，Aleph 挣扎，因为它难以学习递归程序。
总体而言，这个实验的结果表明：（i）问题 Q1 的答案是肯定的，约束提高了学习性能；（ii）问题 Q2 的答案是 Popper 在领域大小方面扩展良好；（iii）问题 Q3 的答案是 Popper 在变化领域大小时可以优于其他 ILP 系统。
5.3 列表转换问题
这个第三个实验的目的是评估 Popper 在困难的（主要是递归的）列表转换问题上的表现。学习递归程序一直是 ILP 中的一个难题（Muggleton 等人，2012），大多数 ILP 和程序合成系统无法学习递归程序。由于 ILASP2i 和 ILASP3 不支持列表，我们只比较 Popper、Enumerate、Metagol 和 Aleph。
5.3.1 材料
我们在表 4 所示的十个列表转换任务上评估系统。这些任务包括单体（例如 evens 和 sorted）、二元（例如 droplast 和 finddup）和三元（dropk）目标谓词的混合。任务还包括功能性（例如 last 和 len）和关系性问题（例如 finddup 和 member）的混合。这些任务对 ILP 系统来说极其困难。为了学习泛化的解决方案，ILP 系统需要支持递归和大域。据我们所知，没有任何现有的 ILP 系统能够在没有提供强大的归纳偏见的情况下学习所有这些任务的最优解。
我们为每个系统提供以下二元关系：head、tail、decrement、geq 以及一元关系：empty、zero、one、even 和 odd。我们还在 len 实验中包括了二元关系 increment。我们不得不在其他实验中从 BK 中移除这个关系，因为当给出这个关系时，Metagol 几乎在每个问题上都会陷入无限递归，无法找到任何解决方案。我们还在 find duplicate 问题中包括了 member/2。我们还在 addhead、dropk 和 droplast 实验中包括了 cons/3。我们从其他实验中排除了这个关系，因为 Metagol 不容易支持三元关系。使用的确切语言偏见可以在附录 D 中找到。
Metagol 设置 对于 Metagol，我们使用与之前机器人实验几乎相同的元规则（图 10）。然而，当给出逆元规则 P(A, B) ← Q(B, A) 时，Metagol 无法学习任何解决方案，再次是因为无限递归。为了帮助 Metagol，我们因此用恒等元规则替换了逆元规则，即 P(A, B) ← Q(A, B)。此外，当我们最初用随机排序的示例进行实验时，我们发现 Metagol 很难找到所有问题（除了 member）的解决方案。原因是 Metagol 对示例的顺序敏感，因为它按照给出的顺序使用示例来引导假设。因此，为了帮助 Metagol，我们按递增的大小（即输入列表的长度）提供示例。
Popper 和 Enumerate 设置 我们将 Popper 和 Enumerate 设置为最多使用五个唯一变量，最多五个体文字，最多两个子句。在 5.5 节中，我们将评估 Popper 对这些参数的敏感性。对于每个 BK 关系，我们还为这两个系统提供了简单类型和参数方向（无论是输入还是输出）。因为 Popper 和 Enumerate 可以生成非终止的 Prolog 程序，我们将两个系统的测试超时设置为每个示例 0.1 秒。如果程序超时，我们将其视为失败。
Aleph 设置 我们为 Aleph 提供与 Popper 和 Enumerate 相同的模式声明和决定。我们将最大变量深度和子句长度设置为六，并将最大搜索节点数设置为 30,000。
5.3.2 方法
对于每个问题，我们生成 10 个正面和 10 个负面的训练示例，以及 1000 个正面和 1000 个负面的测试示例。因此，默认的预测准确率为 50%。每个列表都是随机生成的，最大长度为 50。我们从集合 {1, 2, ..., 100} 中均匀随机抽样列表元素。我们测量预测准确率和学习时间。我们对每个任务强制执行五分钟的超时时间。我们重复每次实验 10 次并绘制标准误差。
5.3.3 结果
表 5 显示，在预测准确率方面，Popper 在所有任务上都等于或优于 Enumerate。当一个系统的准确率为 50% 时，意味着该系统在给定的时间内未能学习到程序，因此达到了默认的准确率。表 6 显示，在学习能力方面，Popper 大幅度优于 Enumerate。例如，Enumerate 需要 159 秒才能找到 evens 程序，而 Popper 只需要四秒。表 7 分解了 Popper 的学习时间。
表 5 还显示，在预测准确率方面，Popper 在所有任务上都等于或优于 Metagol，除了 finddup 问题，Metagol 的预测准确率提高了 2%。表 5 还显示，Aleph 很难学习这些问题的解决方案。例外的是 addhead 和 threesame，它们不需要递归。
总体而言，这个实验的结果表明：（i）问题 Q1 的答案再次是肯定的，约束提高了学习性能，以及（ii）在学习复杂和递归的列表转换程序时，Popper 可以优于其他 ILP 系统。
5.4 可扩展性
我们的按钮实验（实验 5.1）表明 Popper 在最优解的大小和背景关系的数量方面扩展良好。我们的机器人实验（实验 5.2）表明 Popper 在领域大小方面扩展良好。这个实验的目的是评估 Popper 在（i）示例数量和（ii）示例大小方面的扩展性。为此，我们重复了第 5.3 节中的最后一个实验，其中 Popper 和 Metagol 取得了相似的性能。
5.4.1 材料
我们使用第 5.3 节中相同的材料。
5.4.2 设置
我们进行两个实验。在第一个实验中，我们变化示例的数量。在第二个实验中，我们变化示例的大小（输入列表的大小）。对于每个实验，我们测量在 10 次重复中平均的预测准确率和学习时间。
示例数量 对于 {1000, 2000, ..., 10,000} 中的每个 n，我们生成 n 个正面和 n 个负面的训练示例，以及 1000 个正面和 1000 个负面的测试示例，每个元素是从 1-1000 的范围内随机抽取的整数。
示例大小 对于 {50, 100, 150, ..., 500} 中的每个 s，我们生成 10 个正面和 10 个负面的训练示例，以及 1000 个正面和 1000 个负面的测试示例，其中每个列表的长度为 s，每个元素是从 1-1000 的范围内随机抽取的整数。
5.4.3 结果
图 12 显示了变化训练示例数量时的结果。在大约 10,000 个示例之前，Popper 和 Metagol 的预测准确率几乎相同。给定这么多示例，Metagol 很难在一分钟内找到解决方案，最终达到默认的预测准确率（50%）。相比之下，即使给定 20,000 个示例，Popper 也能找到解决方案。图 12 显示了两个系统的学习时间。
Popper 的学习时间随着测试更多示例的开销而线性增加。这个实验的结果表明，问题 Q2 的答案是 Popper 在示例数量方面扩展良好。
图 13 显示了变化输入大小（即输入列表的大小）时的结果。Popper 在所有情况下都优于 Metagol。Popper 对于长度为 50 和 500 的示例的平均学习时间都不到一秒钟。原因是 Popper 仅使用示例来测试假设，因此任何运行时间的增加仅仅是来自使用 Prolog 执行假设。相比之下，随着示例大小的增长，Metagol 的性能急剧下降。Metagol 对于长度为 50 和 500 的示例的平均学习时间分别为 20 秒和 54 秒。原因是 Metagol 使用示例通过诱导和执行示例上的部分程序来搜索假设。这些结果表明，问题 Q3 的答案是肯定，问题 Q2 的答案是 Popper 在示例大小方面扩展良好。
5.5 敏感性
从失败中学习的假设空间（命题 1）是谓词声明数量和其他三个变量的函数：
- 子句中允许的最大唯一变量数量
- 子句中允许的最大体文字数量
- 假设中允许的最大子句数量
这个实验的目的是评估 Popper 对这些参数的敏感性。为此，我们重复第 5.3 节中的 len 实验，使用相同的背景知识、设置和方法，只是我们进行三个独立的实验，分别变化上述三个参数。
5.5.1 结果
图 14 显示了实验结果。结果显示 Popper 对最大唯一变量数量敏感，这对学习时间有很大影响。这一结果源于命题 1，因为更多的变量意味着在子句中形成文字的方式更多。有些令人惊讶的是，将变量数量从 4 翻倍到 8 对性能影响很小，这表明 Popper 对不完美的参数具有鲁棒性。结果表明 Popper 对子句中的最大体文字数量大多不敏感。主要原因是 Popper 不会预先计算假设空间中所有可能的子句，例如 ILASP2i 和 ILASP3 的情况。结果表明 Popper 随着最大子句数量线性扩展。总体而言，这些结果表明 Popper 在最大体文字数量方面扩展良好，但可能在最大唯一变量和子句数量的非常大值下挣扎。
6 结论与局限性
我们描述了一种名为“从失败中学习”的 ILP 方法，它将 ILP 问题分解为三个独立的阶段：生成、测试和约束。在生成阶段，学习者生成一个满足假设约束集（定义6）的假设。在测试阶段，学习者根据训练示例测试假设。如果假设失败，那么在约束阶段，学习者从失败的假设中学习假设约束，以修剪假设空间，即约束后续的假设生成。
在第3.5节中，我们基于theta-子包含性介绍了三种约束类型：泛化、特殊化和消除，并证明了它们的正确性，即它们不会修剪最优解（定义14）。该循环重复进行，直到（i）学习者找到最优解，或（ii）没有更多的假设可供测试。我们在 ILP 系统 Popper 中实现了这种方法，该系统学习确定性程序。Popper 结合了 ASP 和 Prolog，以支持类型、学习最优解、学习递归程序、处理列表和无限域以及假设约束。我们在三个不同领域（玩具游戏问题、机器人策略和列表转换）中评估了我们的方法。实验结果表明：（i）约束极大地减少了假设空间；（ii）Popper 在最优解的规模、背景关系的数量、领域规模、训练示例的数量和训练示例的规模方面具有良好的扩展性；（iii）Popper 在预测准确性和学习时间方面能大幅优于现有的 ILP 系统。
6.1 局限性和未来工作
本文实现的 Popper 有几个局限性，未来的工作应该解决这些问题。
6.1.1 特性
非观察性谓词学习 与一些 ILP 系统（Muggleton 1995; Katzouris 等人 2016）不同，Popper 不支持非观察性谓词学习（non-OPL）（Muggleton 1995），即不直接给出目标谓词的示例。未来的工作应该解决这个局限性。
谓词发明 谓词发明已被证明有助于减少目标程序的大小，这反过来又降低了样本复杂性并提高了预测准确性（Cropper 2019; Dumancic 等人 2019）。Popper 目前不支持谓词发明。
有两种直接的方法可以支持谓词发明。Popper 可以通过施加元规则来限制假设中子句的形式并指导新谓词符号的发明，模仿 Metagol —— 这很容易做到，因为正如我们在“附录 A”中所示，Popper 可以通过假设约束来模拟元规则。或者，Popper 可以模仿 ILASP 支持规范性谓词发明（Law 2018），其中参数和（在 ILASP 的情况下，参数类型）由用户预先指定。本文的大多数结果应该可以扩展到这两种方法。
否定 Popper 学习确定性程序并使用 Prolog 进行测试。Popper 也可以轻松学习 Datalog 程序并使用 ASP 进行测试。在未来的工作中，我们想考虑学习其他类型的程序。例如，我们的大多数剪枝技术（除了消除约束）应该可以扩展到学习非单调程序，如带有分层否定的 Datalog。
噪声 大多数 ILP 系统处理噪声（错误分类）示例（表 1）。Popper 目前不支持噪声示例。我们可以通过放宽应用学习到的假设约束的时机，并通过维护学习过程中测试的最佳假设来解决这个问题，即假设最多地蕴含正面示例且最少地蕴含负面示例。然而，噪声处理可能会增加学习时间，未来的工作应该探索这种权衡。
6.1.2 更好的搜索
分解学习问题的一个优点是，它允许使用各种算法和实现，每个阶段都可以独立于其他阶段进行改进。例如，对生成程序的 Popper ASP 编码的任何改进都会对学习时间产生重大影响，因为它会减少需要测试的程序数量。同样，我们也可以优化测试步骤。未来的工作应该考虑更好的搜索技术。
6.1.3 更好的约束
假设约束是我们想法的核心。Popper 使用预定义和学习到的约束来提高性能。Popper 使用预定义约束来剪枝假设空间中的冗余程序（第 4 节），例如没有基本情况的递归程序和包含冗余的程序。Popper 还从失败中学习约束。我们认为，未来工作最有希望的发展方向是改进这两种类型的约束（预定义和学习到的）。
类型 像许多 ILP 系统（Muggleton 1995; Blockeel 和 De Raedt 1998; Srinivasan 2001; Law 等人 2014; Evans 和 Grefenstette 2018）一样，Popper 支持简单类型来剪枝假设空间。然而，更复杂的类型，如多态类型，可以在结构化数据上的程序中实现更好的剪枝（Morel 等人 2019）。例如，多态类型将允许我们区分在整数列表和字符列表上使用谓词。带有限制谓词的细化类型（Polikarpova 等人 2016）可以让用户提供更强大的程序属性（除了示例之外），例如要求 reverse 程序可证明具有输入和输出长度相同的属性。在未来的工作中，我们想探索是否可以将这些复杂类型表达为假设约束。
学习到的约束 第 3.5 节中描述的约束剪枝了失败假设的特化和泛化。然而，我们只是简要分析了这些约束的属性。我们展示了这些约束是合理的（命题 3 和 4），因为它们不会剪枝最优解。然而，我们还没有考虑它们的完备性，即它们剪枝了所有非最优解。事实上，我们的消除约束在可分离确定性程序的特殊情况中，剪枝了泛化和特化约束遗漏的假设。换句话说，关于使用哪些约束的理论还有待发展，可能还有更多的约束可以从失败的假设中学习到，所有这些都应该会显著提高学习性能。相比之下，子句（Shapiro 1983; De Raedt 和 Bruynooghe 1993; Nienhuys-Cheng 和 de Wolf 1997）和理论（Nienhuys-Cheng 和 de Wolf 1997; Midelfart 1999; Badea 2001）的细化运算符在 ILP 中已经得到了详细的研究。因此，我们认为本文开启了一个新的研究方向，即识别和分析我们可以从失败的假设中学习到的不同约束。
https://link.springer.com/article/10.1007/s10994-020-05934-z
https://arxiv.org/abs/2005.02259
