Learning logic programs by combining programs通过组合程序来学习逻辑程序
https://github.com/logic-and-learning-lab/ecai23-combo
作者相关工作：
Code：最有前途的ARC-AGI比赛方法：关系分解，关系型表示胜过函数型表示
摘要
归纳逻辑编程的目标是归纳出一个逻辑程序（一组逻辑规则），这些规则能够概括训练示例。归纳出包含许多规则和文字的程序是一个主要的挑战。为了应对这一挑战，我们引入了一种方法，我们学习小的不可分割程序并将它们组合起来。我们在约束驱动的ILP系统中实现了我们的方法。我们的方法可以学习最优和递归程序，并执行谓词发明。我们在多个领域的实验，包括游戏玩法和程序合成，表明我们的方法在预测准确性和学习时间方面可以大幅超越现有方法，有时将学习时间从一个多小时减少到几秒钟。
1 引言
归纳逻辑编程（ILP）[29, 8]的目标是归纳出一个逻辑程序（一组逻辑规则），这些规则能够概括示例和背景知识（BK）。挑战在于有效地搜索一个大型假设空间（所有程序的集合）以找到解决方案（一个正确概括示例的程序）。
为了应对这一挑战，分而治之的方法[4]将示例分成子集，并为每个子集搜索一个程序。分而治之的方法[30]搜索一个规则来覆盖（概括）示例的一个子集，然后将这些示例分开，并搜索更多的规则来覆盖剩余的示例。两种方法都可以学习包含许多规则和文字的程序。然而，由于它们只从示例的一个子集中学习，它们无法执行谓词发明，并且在学习递归和最优程序方面存在困难，因此倾向于过拟合。
为了克服这些限制，最近的方法[26, 24, 10, 16]使用元级搜索[8]来学习最优和递归程序。然而，大多数最近的方法在学习程序中包含许多规则、规则中包含许多文字，或两者兼有的情况下都存在困难。例如，ASPAL[6]预计算程序中允许的每个可能的规则，并使用答案集求解器找到覆盖示例的子集。然而，这种现在广泛采用的预计算方法[26, 24, 40, 37]不适用于包含超过几个文字的规则。
同样，许多最近的方法在学习包含几个规则的程序方面也存在困难[15, 13, 10, 36, 21]。
在本文中，我们的目标是克服最近方法的可扩展性限制，同时保持学习递归和最优程序以及执行谓词发明的能力。关键思想是首先学习一些覆盖部分示例的小的不可分割程序，然后搜索这些程序的组合（一个并集），以覆盖所有示例。
不可分割程序可以被视为构建更大程序的基石。当一个程序h满足以下条件时，它是可分割的：（i）它至少包含两条规则，以及（ii）在h中某条规则的头部出现的谓词符号没有在该规则的主体中出现。如果一个程序不是可分割的，那么它就是不可分割的。例如，考虑程序p1：
这个程序包含三条可以分别学习并组合的规则。换句话说，每条规则的逻辑后果的并集等同于程序p1的逻辑后果。因此，p1是可分割的。相比之下，考虑程序p2：
这个程序包含两条不能单独学习的规则，因为第二条递归规则依赖于第一条规则。换句话说，每条规则的逻辑后果的并集并不等同于程序p2的后果。因此，p2是不可分割的。
为了探索这个想法，我们基于从失败中学习（Learning from Failures, LFF）[10]进行构建。LFF将学习问题框架化为一个约束满足问题（Constraint Satisfaction Problem, CSP），其中CSP的每个解决方案都代表一个程序。LFF学习者的目标是积累约束以限制假设空间。例如，POPPER，一个LFF学习者，使用生成、测试和约束循环来生成程序并用示例测试它们。如果一个程序不是解决方案，POPPER构建约束来解释原因，并使用这些约束来限制未来的程序生成。我们使用LFF来探索我们的想法，因为它支持从无限域中学习最优和递归程序。此外，由于其声明式的约束驱动方法，它很容易适应。我们通过（i）在生成阶段只生成不可分割的程序，以及（ii）添加一个组合阶段来搜索不可分割程序的组合，来构建在LFF之上。
动机示例
我们通过一个简单的例子来说明我们的方法。假设我们想要学习一个程序，来概括以下数字列表的正面（E+）和负面（E-）示例：
在测试阶段，我们用示例测试程序。如果一个程序覆盖了一个负例，那么我们构建一个概括约束来从假设空间中剪枝更一般的程序，因为它们也会覆盖负例。例如，由于h2覆盖了第一个负例（f([2,3,1])），我们剪枝h2及其概括，如h4：
如果一个程序没有覆盖任何正例，那么我们构建一个专门化约束来从假设空间中剪枝更具体的程序，因为它们也不会覆盖任何正例。例如，由于我们没有一个正例，其中第一个元素是3，我们剪枝h3及其专门化，如h5：
如果一个程序至少覆盖了一个正例且没有覆盖负例，我们将其添加到一组有前景的程序中。例如，在生成大小为五的程序时，假设我们生成了以下递归程序：
由于h6至少覆盖了一个正例（f([1,3,5,7])）且没有覆盖负例，我们认为它是一个有前景的程序。
在我们的新颖组合阶段，我们随后搜索一个有前景程序的组合，该组合覆盖所有正例且在大小上是最小的。我们将这个组合问题表述为一个答案集编程（Answer Set Programming, ASP）问题[18]，对于这个问题，有高性能的求解器，如Clingo[19]。如果我们找不到一个组合，我们就进入约束阶段，在那里我们使用任何发现的约束来生成新的程序。如果我们找到了一个组合，我们就认为它是目前最好的解决方案。例如，假设在考虑大小为七的程序后，我们看到了以下程序：
那么，h6 ∪ h7 ∪ h8 的组合就是我们要学习的解决方案h0。关键的是，我们通过只生成最多包含2条规则和7个文字的程序，学习了一个包含4条规则和13个文字的程序。由于ILP方法的搜索复杂度通常是指数级的，与要学习的程序大小成比例，这种减少可以显著提高学习性能。
到目前为止，我们还没有证明这种组合在程序大小方面是最优的。换句话说，我们还没有证明没有更小的解决方案。因此，为了学习一个最优的解决方案，我们继续进入约束阶段，并在未来的迭代中添加一个关于最大程序大小（最多12个文字）的约束。这个约束禁止（i）在生成阶段生成超过12个文字的任何程序，以及（ii）在组合阶段找到超过12个文字的有前景程序的任何组合。我们重复这个循环，直到我们证明了一个解决方案的最优性。
新颖性、影响和贡献。本文的主要新颖之处在于学习覆盖部分示例的小的不可分割程序，并组合这些程序来学习包含许多规则和文字的大型程序的想法。我们在第2节中扩展了这种新颖性。我们实验在许多不同领域，包括游戏玩法和程序合成，明确显示了这种影响，大大提高了学习性能，无论是在预测准确性还是学习时间方面，有时将学习时间从一个多小时减少到几秒钟。此外，由于这个想法连接了人工智能的许多领域，包括程序合成、约束满足和逻辑编程，这个想法应该会引起广泛的关注。
总体而言，我们做出了以下贡献：
• 我们引入了一种生成、测试、组合和约束的ILP方法。
• 我们在COMBO中实现了我们的想法，COMBO是一个新系统，学习最优和递归程序，并支持谓词发明。我们证明，如果存在一个最优解决方案，COMBO总是返回一个最优解决方案。
• 我们在许多不同领域，包括游戏玩法和程序合成，通过实验表明，我们的方法可以大幅超越其他方法，特别是在学习时间方面。
2 相关工作
规则挖掘。归纳逻辑编程是一种形式的规则挖掘。一个值得注意的规则挖掘方法是AMIE+[17]。将COMBO与AMIE+进行比较是困难的。AMIE+采用开放世界假设。相比之下，COMBO采用封闭世界假设。此外，COMBO可以学习关系元组大于二的程序，而AMIE+不能，即AMIE+只能使用一元和二元关系。这个区别很重要，因为AMIE+不能用于我们实验中的大多数数据集。例如，所有的IGGP任务[9]和许多程序合成任务都使用元组大于2的关系，如iggp-coins任务中的next_cell/3、true_cell/3和does_jump/4。同样，许多程序合成任务使用append/3或sum/3。最后，AMIE+需要事实作为输入，这可能很难提供，特别是当从无限域如程序合成域学习时。相比之下，COMBO以确定的程序作为BK输入。
经典ILP。TILDE[4]是一种分而治之的方法。PROGOL[30]是一种分而治之的方法，启发了许多其他方法[38, 2, 39]，特别是ALEPH[41]。尽管这两种方法都可以学习包含许多规则和文字的程序，但它们在学习递归和最优程序以及进行谓词发明方面存在困难[42]。
可扩展性。可扩展性可以在许多维度上进行。例如，许多系统，如QuickFOIL[44]，专注于扩展以处理数百万的训练示例和背景事实。将扩展到数百万示例的目标不是这项工作的目标（尽管我们展示了COMBO可以处理数十万的示例）。相反，我们的目标是扩展到大型假设空间，这对于许多现有系统来说是很困难的，特别是规则选择方法，如下一段中概述。
规则选择。许多系统将ILP问题表述为规则选择问题[6, 26, 15, 24]。这些方法预计算假设空间中的每个可能规则，然后搜索一个子集来覆盖示例，通常使用ASP来执行搜索。预计算方法的主要限制是可扩展性，包括（i）规则的大小，以及（ii）可能规则的数量。由于这些方法预计算每个可能的规则，它们不能扩展到具有多个主体文字的规则，因为规则的数量是主体文字数量的指数。同样，由于它们对每个可能的规则执行组合搜索，它们不能扩展到具有许多可能规则的问题。例如，PROSYNTH[37]和DIFFLOG[40]分别最多考虑1000和1267个候选规则。然而，我们最简单的实验（trains1）需要31,860个候选规则。我们的coins-goal实验需要大约10^15个候选规则，这对于这些方法来说是不可行的。此外，我们的方法在许多方面都不同。我们不预计算每个可能的规则，这使我们能够学习具有许多主体文字的规则。此外，我们只搜索有前景的程序（已知至少覆盖一个正例且没有负例的程序），这使我们能够扩展到具有许多可能规则的问题。
LFF。与预计算每个可能的规则不同，POPPER的关键思想是从较小的程序（可能有多个规则）中发现约束，以排除更大的程序。然而，POPPER在学习包含许多规则和文字的大型程序方面存在困难，因为它试图生成一个覆盖所有示例的单一程序。我们的方法不同，（i）在生成步骤中只生成不可分割的程序，以及（ii）添加一个组合步骤。DCC[7]将经典的分而治之搜索与现代约束驱动的ILP相结合。DCC为每个示例单独学习一个程序。由于这些程序可能过于具体，DCC迭代地尝试学习更一般的程序。为了提高性能，DCC在迭代之间重用知识。我们的方法与DCC完全不同。DCC试图生成一个单一的程序，可能是可分割的，覆盖所有示例，并且没有组合阶段。相比之下，COMBO从不生成可分割的程序，并在组合阶段搜索程序的组合。HOPPER[36]扩展了POPPER以学习高阶程序。尽管我们的实现只学习一阶程序，但这种方法应该可以直接转移到HOPPER。
3 问题设定
我们现在描述我们的问题设定。假设读者熟悉逻辑编程 [27] 和 ASP [18]，但在附录中我们提供了一个总结。
我们使用 LFF 设定。假设是一组确定的子句，即我们学习具有最小 Herbrand 模型语义的确定性程序。我们将术语“程序”和“假设”互换使用。假设空间 H 是一组假设。LFF 使用假设约束来限制假设空间。设 L 为定义假设的元语言。例如，考虑由两个文字 h_lit/3 和 b_lit/3 组成的元语言，它们分别表示头部和身体文字。使用这种语言，我们可以将规则 last(A,B) ← tail(A,C), head(C,B) 表示为一组文字 {h_lit(0,last,(0,1)), b_lit(0,tail,(0,2)), b_lit(0,head,(2,1))}。每个文字的第一个参数是规则索引，第二个是谓词符号，第三个是文字变量，其中 0 代表 A，1 代表 B 等。假设约束是用 L 表示的约束（无头规则）。设 C 为用语言 L 表示的一组假设约束。当假设写成 L 时，如果它不违反 C 中的任何约束，则该假设与 C 一致。例如，规则 last(A,B) ← last(B,A) 违反了约束 ← h_lit(0,last,(0,1)), b_lit(0,last,(1,0))。我们用 HC 表示不违反 C 中任何约束的假设空间 H 的子集。
我们定义 LFF 输入：
4 算法
现在我们描述我们的COMBO算法。为了帮助解释我们的方法并界定新颖性，我们首先描述POPPER。
POPPER。POPPER（算法1）解决了LFF问题。POPPER接收背景知识（bk）、正例（pos）和负例（neg），以及假设大小的上限（max_size）作为输入。POPPER使用生成、测试和约束循环来找到最优解。POPPER从ASP程序P（隐藏在生成函数中）开始。P的模型对应于假设（确定的程序）。在生成阶段（第5行），POPPER使用Clingo[19]，一个ASP系统，来搜索P的模型。如果没有模型，POPPER增加假设大小（第7行）并再次循环。如果有模型，POPPER将其转换为假设h。在测试阶段（第9行），POPPER使用Prolog在训练示例上测试h。我们使用Prolog是因为它能够处理列表和大型、潜在无限的域。如果h是解决方案，那么POPPER返回它。如果h失败，则在约束阶段（第12行），POPPER从失败中构建假设约束（表示为ASP约束）。POPPER将这些约束添加到P中以剪枝模型，从而减少假设空间。例如，如果h不完整，POPPER构建一个专门化约束来剪枝其专门化。如果h不一致，POPPER构建一个概括约束来剪枝其概括。POPPER重复这个循环，直到它找到最优解或没有更多的假设要测试。
4.1 COMBO
COMBO（算法2）在算法1的基础上构建，但有所不同，（i）在生成阶段只构建不可分割的程序，以及（ii）增加了一个组合阶段，尝试组合有前景的程序。我们描述这些新颖之处。
4.1.1 生成
在生成阶段，COMBO只生成不可分割的程序（第7行）。一个程序h是可分割的，当且仅当（i）它至少包含两条规则，并且（ii）在h中某条规则的头部出现的谓词符号没有在该规则的主体中出现。如果一个程序不是可分割的，那么它就是不可分割的。例如，COMBO不能生成以下可分割的程序：
通过只生成不可分割的程序，我们减少了生成阶段的复杂性。具体来说，COMBO不是搜索所有可能的程序，而是只搜索不可分割的程序，这是一个小得多的空间，特别排除了所有包含多条规则的程序，除非它们是递归的或使用谓词发明。例如，假设，为了简单起见，我们有一个没有递归或谓词发明的问题，规则空间包含m条规则，并且我们允许程序中最多有k条规则。那么在生成阶段，POPPER搜索大约m^k个程序。
相比之下，COMBO只搜索m个程序。
需要明确的是，算法2遵循算法1，并使用ASP求解器来搜索符合约束（不可分割）的程序。换句话说，算法2中的generate_non_separable函数与算法1中的generate函数相同，只是它还告诉ASP求解器使用附录B.1中描述的编码忽略可分割的程序。
4.1.2 测试和约束
如果一个程序部分完整（至少覆盖了一个正例）且一致，COMBO将其添加到一组有前景的程序中（第13行）。如果一个程序不一致，COMBO构建一个概括约束，以从假设空间中剪枝其概括，这与POPPER相同。如果一个程序部分完整且不一致，那么与POPPER不同，COMBO不会构建一个专门化约束来剪枝其专门化，因为我们可能想要专门化它。例如，考虑学习一个程序来确定某人是否快乐。假设COMBO生成了以下程序：
这个程序现在可能是部分完整且一致的，因此是一个有前景的程序。因此，COMBO只在程序（i）完全不一致时构建专门化约束，因为其任何专门化都不可能是部分完整的，或者（ii）一致时，因为没有必要专门化一个一致的程序，因为它只能覆盖更少的正例。我们在附录中证明了这些约束不会剪枝最优假设。
4.1.3 组合
在新颖的组合阶段（第14行），COMBO搜索有前景程序的组合（一个并集），该组合覆盖正例且在大小上是最小的。我们在下一段描述我们的组合算法。如果我们找不到组合，我们就进入约束阶段，在那里我们使用任何发现的约束来生成新的程序（第18行）。如果我们找到了一个组合，我们就认为它是到目前为止最好的解决方案（第16行）。为了可证明地学习最优解，我们更新最大程序大小（第17行），这禁止在生成阶段生成超过max_size文字的任何程序，或在组合阶段考虑超过max_size文字的任何有前景程序的组合。我们重复这个循环，直到我们证明解决方案的最优性。
算法3显示了组合算法。为了找到有前景程序的组合，我们遵循ASPAL并将这个组合问题表述为ASP问题。函数build_encoding构建编码（第5行）。我们简要描述我们的编码。附录包含更多细节和一个示例编码。我们为每个正例分配一个唯一的ID。对于有前景程序中的每条规则，我们创建一个选择规则来指示它是否应该在解决方案中。对于每个有前景的程序，我们添加有关其示例覆盖和大小的事实。我们要求Clingo为编码找到一个模型（规则的组合）（第6行），以便它（i）尽可能多地覆盖正例，并且（ii）在大小上是最小的。如果没有模型，我们返回到目前为止最好的解决方案；否则，我们将模型转换为程序（第6行）。每个没有递归或谓词发明的组合程序都保证是一致的（这个结果是附录中定理1证明中的一个中间结果）。然而，如果组合程序有递归或谓词发明，那么它可能是不一致的。在这种情况下，我们对负例进行测试以确保一致性。如果它不一致，我们向编码添加约束（第10行），以从组合编码中排除这个程序及其任何概括。然后我们再次循环。
我们方法的一个关键优势在于，与大多数规则选择方法（第2节）包括ASPAL不同的是，这些方法会为假设空间中的每一个可能规则分配一个选择规则，而我们只为有前途的程序中的规则分配选择规则。这一差异对COMBO的性能至关重要，因为它极大地降低了组合问题的复杂性。例如，设m为可能规则的总数，n为有前途的程序数量。则预计算方法需要搜索个程序，而COMBO只需搜索
个程序。实际上，n远小于m，因此我们的组合阶段非常高效。例如，在我们最简单的实验（trains1）中，有31,860个候选规则，因此预计算方法需要搜索
个程序。相比之下，COMBO仅需在10个有前途的程序上进行搜索，即搜索2^10个程序，并在四秒内找到最佳解决方案。
正确性。我们证明了COMBO的正确性：
5 实验
我们的实验旨在回答以下问题：
Q1 组合不可分割程序能否提高预测准确性和学习时间？
为了回答Q1，我们比较COMBO与POPPER的性能。由于COMBO基于POPPER构建，这种比较直接衡量了我们的新想法的影响，即它是两个系统之间唯一的区别。
为了看看COMBO是否与其他方法具有竞争力，
我们的实验旨在回答以下问题：
Q2 COMBO与其他方法相比如何？
为了回答Q2，我们还比较了COMBO与DCC、ALEPH和METAGOL[32]的性能。我们使用这些系统是因为它们可以学习递归的确定性程序。DCC、POPPER和COMBO使用相同的偏好，因此它们之间的比较是公平的。ALEPH使用类似的偏好，但也有额外的设置。我们尽力进行公平比较，但可能会有不同的设置可以提高ALEPH的性能。METAGOL的结果在附录中。
方法
我们在最大学习时间为60分钟的情况下测量预测准确性和学习时间。如果一个系统在时间限制内没有终止，我们取该系统在该点找到的最佳解决方案。我们重复所有实验10次，并计算平均值和标准误差。表格中的误差线表示标准误差。我们将超过一秒的学习时间四舍五入到最接近的秒，因为差异足够大，不需要更精细的精度。我们使用的是3.8 GHz 8核Intel Core i7处理器和32GB内存。所有系统都使用单个CPU。
领域
我们使用以下领域。附录包含更多细节，例如每个任务的示例解决方案和有关问题大小的统计数据。
火车。目标是找到一个假设，以区分东行和西行的火车[25]。
国际象棋。任务是学习在国际象棋的王-车-王（krk）残局中的模式[22]。这个数据集包含元组大于二的关系，例如distance/3和cell/4。
Zendo。Zendo是一个多人游戏，玩家必须通过构建结构来发现一个秘密规则。Zendo是一个具有挑战性的游戏，它在认知科学中吸引了很多兴趣[5]。
IMDB。这个现实世界的数据集[28]包含电影、演员和导演之间的关系。这个数据集经常用来评估规则学习系统[14]。注意，这个数据集有非平凡的训练示例数量。例如，imdb3任务有121,801个训练示例。
IGGP。归纳性通用游戏玩法（IGGP）的目标是从通用游戏玩法竞赛[20]中归纳出解释游戏轨迹的规则。这个数据集对ILP系统来说非常困难：目前表现最好的系统只能为40%的任务学习出完美的解决方案。而且，尽管看似是一个玩具问题，IGGP代表了现实世界中的许多问题，例如归纳编程语言的语义[3]。我们使用了六款游戏：最小衰减（md）、石头-剪刀-布（rps）、按钮、消耗战、蜈蚣和硬币。这些任务都需要学习元组大于二的关系的规则，这对于某些规则学习方法[17]来说是不可能的。
图型问题。我们使用常用的图问题[15, 21]。所有这些任务都需要学习递归程序的能力。
程序合成。归纳复杂的递归程序是一个困难的问题[31]，大多数ILP系统无法学习递归程序。我们使用了一个程序合成数据集[10]，并增加了两个新任务contains和reverse。引言中的动机示例描述了contains任务。所有这些任务都需要学习递归程序的能力，以及从非事实数据中学习的能力。
5.1 实验结果
Q1. 组合不可分割程序能否提高预测准确性和学习时间？
表1显示，COMBO（i）在所有任务上的预测准确性等于或高于POPPER，并且（ii）在许多任务上可以提高预测准确性。McNemar检验确认了差异在p < 0.01水平上的显著性。当学习包含许多规则和文字的程序时，COMBO全面超越了POPPER。
例如，buttons问题的解决方案（包含在附录中）有10条规则和61个文字。对于这个问题，POPPER在一小时内无法学习到解决方案，因此默认准确性。相比之下，COMBO在23秒内学习到了一个准确和最优的解决方案。
表2显示，COMBO在所有任务上的学习时间都比POPPER短。配对t检验确认了差异在p < 0.01水平上的显著性。COMBO在学习小型程序时也优于POPPER。例如，在centipede任务中，两个系统都学习到了具有2条规则和8个文字的相同解决方案。然而，POPPER需要1102秒（18分钟）来学习解决方案，而COMBO只需要9秒，减少了99%。COMBO在学习递归程序时也优于POPPER。例如，在reverse任务中，POPPER需要1961秒（30分钟）来学习一个具有8个文字的递归程序，而COMBO只需要44秒，减少了98%。
为了说明COMBO的效率，考虑coins-goal任务。对于这个任务，大约有个可能的规则，因此有
个具有k条规则的程序——这就是为什么这个任务对大多数规则选择方法来说是不可行的。尽管假设空间很大，COMBO还是在不到两分钟的时间内找到了最优解。此外，组合阶段对学习时间的贡献可以忽略不计。例如，在一次COMBO学习解决方案用了97秒的试验中，只有0.07秒花在了组合阶段。
总的来说，这些结果强烈表明对Q1的回答是肯定的：学习不可分割的程序并将它们组合起来可以显著提高学习性能。
Q2. COMBO与其他方法相比如何？
表1显示，COMBO在所有任务上的准确性等于或高于DCC。McNemar检验确认了差异在p < 0.01水平上的显著性。COMBO在iggp和zendo任务上的准确性显著更高。表2显示，COMBO在所有任务上的学习时间都比DCC短。配对t检验确认了差异在p < 0.01水平上的显著性。COMBO在时间限制内为几乎所有任务找到了解决方案。相比之下，DCC在12个任务上超时。例如，在buttons-g任务中，DCC需要超过一个小时来学习一个准确率为86%的解决方案。相比之下，COMBO在3秒内找到了一个完美的解决方案，减少了99%。附录包括了COMBO在这项任务上的学习输出。
表1显示，ALEPH有时在准确性方面高于COMBO，特别是在krk任务上。然而，COMBO在大多数任务上轻松超越ALEPH，尤其是在需要递归的图和合成任务上。COMBO在不需要递归的iggp任务上显著优于ALEPH。例如，在coins任务中，ALEPH在一小时内找不到解决方案。相比之下，COMBO只需要105秒就能学习到一个100%准确的解决方案。附录包括了COMBO在这项任务上的输出跟踪。
表2显示，ALEPH有时在学习时间上低于COMBO。原因是，与COMBO不同，ALEPH不保证找到最优解，也不尝试这样做，因此更快地终止。例如，在rps任务中，ALEPH比COMBO快（20秒对87秒）。然而，COMBO只需要2秒就能找到与ALEPH相同的解决方案，但需要87秒来证明它是最优的。
附录中的结果显示，COMBO在所有任务上也优于METAGOL。
总体而言，这些结果强烈表明对Q2的回答是，COMBO与现有方法相比具有优势，并且可以在预测准确性和学习时间方面显著提高学习性能。
6 结论和局限性
我们介绍了一种方法，它学习覆盖一些训练示例的小的不可分割程序，然后尝试将它们组合起来，以学习包含许多规则和文字的程序。我们在COMBO中实现了这个想法，COMBO是一个新系统，可以学习最优的、递归的和大型的程序，并进行谓词发明。我们展示了COMBO总是返回一个最优解（如果存在的话）。我们在许多领域的实证结果表明，我们的方法可以显著提高预测准确性并减少学习时间，与其他方法相比，有时将学习时间从60多分钟减少到几秒钟。换句话说，COMBO可以为其他系统无法解决的问题学习准确的解决方案。这些显著的改进应该直接帮助许多应用领域，如药物设计[23]、路径查找[1]和学习高阶程序[36]。
https://arxiv.org/pdf/2206.01614
