Relational program synthesis with numerical reasoning
基于数值推理的关系程序综合
https://arxiv.org/pdf/2210.00764
摘要
程序合成方法在学习带有数值的程序时面临挑战。特别困难的问题是学习多个示例上的连续值，例如区间。为了克服这个限制，我们引入了一种结合关系学习和数值推理的归纳逻辑编程方法。我们的方法，称为NUMSYNTH，使用可满足性模理论（SMT）求解器来高效地学习带有数值的程序。我们的方法可以在线性算术片段中识别数值，例如实数差分逻辑，以及来自无限域的数值，例如实数或整数。我们在四个不同领域的实验，包括游戏玩法和程序合成，表明我们的方法可以（i）通过线性算术推理学习带有数值的程序，以及（ii）在预测准确性和学习时间方面胜过现有方法。
1 引言
Zendo是一个游戏，其中一个玩家（大师）为结构创建规则，其他玩家（学生）通过构建和研究遵循或违反规则的结构来尝试发现这个规则。第一个正确猜出规则的学生获胜。例如，假设图1a中的结构遵循秘密规则，而右侧的则不遵循。图1b显示了一个可能的秘密规则。它规定结构必须有两块接触，其中一块的大小至少为7。发现这个规则涉及识别数值7。
假设我们想使用机器学习来玩Zendo，即从结构示例中学习秘密规则。那么我们需要一种方法，能够（i）学习可解释的规则，以及（ii）从少量示例中泛化。然而，这些要求对于标准机器学习技术来说很难，但对于许多现实世界的问题（Cropper等人，2022）至关重要。
归纳逻辑编程（ILP）（Muggleton，1991）是一种可以从少量示例中学习可解释规则的机器学习方法。现有的ILP技术可以学习简单的Zendo问题的规则。然而，现有方法在学习需要从无限域中识别数值的规则时面临挑战（Corapi、Russo和Lupu，2011；Evans和Grefenstette，2018；Cropper和Morel，2021）。此外，尽管一些ILP方法可以学习带有数值的程序（Muggleton，1995；Hocquette和Cropper，2022），但它们无法执行复杂的数值推理，例如通过联合推理多个示例来识别数值。例如，它们难以学习一块的大小必须大于某个特定数值，或者描述一块位置的坐标之和必须低于某个特定数值。这些限制不特定于ILP，据我们所知，适用于所有当前的程序合成方法（Raghothaman等人，2019；Ellis等人，2018；Shi等人，2022）。
为了克服这些限制，我们引入了一种可以从无限域中识别数值并从多个示例中推理的方法。我们方法的关键思想是将学习任务分解为两个阶段（i）程序搜索，以及（ii）数值搜索。
在程序搜索阶段，学习者搜索带有数值符号位置的变量的部分假设（规则集）。这一步遵循ALEPH的延迟评估程序（Srinivasan和Camacho，1999）。例如，为了学习Zendo的规则，学习者可能会生成图1c中显示的部分假设。在这个假设中，一阶变量N被标记为带有谓词符号@numerical的数值变量，但尚未绑定到任何特定值。
在数值搜索阶段，学习者使用训练示例搜索数值变量的值。我们将数值搜索编码为可满足性模理论（SMT）公式。例如，为了找到图1c中假设的N的值，学习者执行不带数值字面量geq(D,N)的部分假设，针对示例找到变量D的可能替换，从中构建线性不等式系统。这些不等式约束了数值变量N的搜索，使用了从示例中获得的D的值。
最后，学习者用不等式找到的任何解替换部分程序中的N。
为了实现我们的想法，我们基于最新的从失败中学习（LFF）（Cropper和Morel，2021）ILP方法。LFF是一种约束驱动的ILP方法，目标是积累对假设空间的约束。LFF学习者不断地生成和测试假设，并从中推断出约束。我们在NUMSYNTH中实现了我们的数值推理方法，它建立在LFF学习者POPPER之上，支持谓词发明和学习递归和最优（在文本复杂性上）程序。NUMSYNTH使用内置的数值字面量，额外支持实数和整数的线性算术推理。
与现有方法相比，我们方法的主要创新点是表达能力：NUMSYNTH可以学习需要在线性算术片段中对多个示例进行推理的带有数值的程序。换句话说，我们的方法可以学习现有方法无法学习的程序。例如，我们的实验表明，我们的方法可以学习图1b中所示形式的程序。此外，我们的方法可以（i）在实数或整数等无限域中高效地搜索数值，（ii）识别可能未出现在背景知识中的数值，以及（iii）学习带有多个链式数值字面量的程序。例如，它可以学习两个变量的和低于某个特定数值。据我们所知，没有现有的方法可以高效解决这类问题。总体而言，我们做出了以下贡献：
1. 我们引入了一种无限域中的数值推理方法。我们的方法支持在线性算术片段中的数值推理。
2. 我们在NUMSYNTH中实现了我们的方法，它可以学习带有数值的程序，执行谓词发明，并学习递归和最优程序。
3. 我们在四个领域（几何、生物学、游戏玩法和程序合成）上通过实验表明，我们的方法可以（i）学习需要数值推理的程序，以及（ii）在学习和预测准确性方面胜过现有的ILP系统。
2 相关工作
程序合成。枚举搜索空间的程序合成方法（Raghothaman等人，2019；Ellis等人，2018；Evans等人，2021）只能从小的有限域中学习，不能从无限域中学习。几个程序合成系统将程序搜索委托给SMT求解器（Jha等人，2010；Gulwani等人，2011；Reynolds等人，2015；Albarghouthi等人，2017）。相比之下，我们将数值搜索委托给SMT求解器。此外，NUMSYNTH可以从无限域中学习带有数值的程序。Sketch（Solar-Lezama，2009）使用SAT求解器在给定部分程序的情况下搜索合适的常数，其中常数可以是数值。这种方法与我们的数值搜索阶段类似。然而，Sketch不学习程序的结构，而是期望作为输入一个解决方案的骨架：它需要一个部分程序，其任务是用常数符号填充缺失的值。相比之下，NUMSYNTH学习程序和数值。
ILP。许多ILP方法（Muggleton，1995；Srinivasan，2001）使用底部子句构造来搜索程序。然而，这些方法只能识别出现在单个示例底部子句中的数值。它们不能联合推理多个示例，这在例如学习不等式时是必要的。
约束归纳逻辑编程（Sebag和Rouveirol，1996）使用约束逻辑编程来学习带有数值的程序。这种方法概括了在给定一些负面示例的情况下，单个正面示例，并限制在差分逻辑中的数值推理。
Anthony和Frisch（1997）提出了一种学习带有数值字面量的假设的算法。FORS（Karaliˇc和Bratko，1997）在仅限正面示例的设置中，将回归线拟合到正面示例的子集上。与NUMSYNTH相比，这两种方法允许数值字面量预测的数值有一定误差。然而，这两种方法采用自顶向下的细化，每次只进行一次专门化步骤，这阻止了它们学习带有多个链式数值字面量的假设。
TILDE（Blockeel和De Raedt，1998）使用离散化程序来寻找候选数值常数，同时使归纳过程更高效（Blockeel和De Raedt，1997）。然而，TILDE不能学习递归程序，并且在从少量示例中学习时遇到困难。
许多最近的ILP系统枚举了搜索空间中的所有可能规则（Corapi、Russo和Lupu，2011；Kaminski、Eiter和Inoue，2018；Evans和Grefenstette，2018；Sch¨uller和Benz，2018）或所有常数符号作为一元谓词符号（Evans和Grefenstette，2018；Cropper和Morel，2021；Purgał、Cerna和Kaliszyk，2022），因此无法处理无限域。
LFF。最近的LFF系统使用一元谓词符号表示常数符号（Cropper和Morel 2021；Purgał、Cerna和Kaliszyk 2022），这阻止了它们在无限域中学习。MAGICPOPPER（Hocquette和Cropper 2022）可以从无限域中识别常数符号。与ALEPH的延迟评估方法和我们的程序搜索方法类似，MAGICPOPPER构建了用变量代替常数符号的部分假设。然后，它通过在每个示例上独立执行部分假设来识别特定的候选常数符号。然而，当测试具有大量或无限数量答案替换的非确定性谓词的假设时，例如大于，它可能会找到难以处理的候选常数数量。此外，它不能从多个示例联合进行数值推理。相比之下，NUMSYNTH在推理数值时同时使用所有示例，因此它可以学习区间，而MAGICPOPPER不能。
延迟评估。最相关的工作是支持延迟评估的ALEPH的扩展（Srinivasan和Camacho 1999）。在构建底部子句期间，ALEPH用存在量词化的变量替换数值。在底部子句的细化搜索期间，ALEPH通过在示例上执行部分假设来找到这些变量的替换。这个程序可以使用定制的损失函数预测输出数值变量，以衡量错误（Srinivasan等人，2006），而NUMSYNTH不能。然而，ALEPH需要用户编写背景定义来找到数值，例如从数据中计算阈值或线性回归系数的定义。相比之下，NUMSYNTH内置了数值字面量。此外，ALEPH在延迟评估期间独立执行每个定义，这阻止了它学习需要共享变量的延迟评估的多个字面量，例如同一变量的上限和下限。相比之下，NUMSYNTH可以学习带有多个链式数值字面量的假设。
最后，ALEPH不支持谓词发明，不能保证学习最优（文本最小）程序，并且在学习递归程序方面存在困难。
3 问题设置
现在我们描述我们的问题设置。我们假设对逻辑编程（Lloyd 2012）有所了解。我们的问题设置是基于归纳逻辑编程（ILP）的从失败中学习（LFF）（Cropper和Morel 2021）设置，它基于ILP的从蕴涵中学习设置（Muggleton和De Raedt 1994）。LFF假设了一个元语言L，这是关于假设的语言。LFF使用假设约束来限制假设空间。假设约束用L表达。LFF输入定义为：
给定一组假设约束C，我们说一个假设H与C一致，如果H用L语言表达时，不违反C中的任何约束。我们称与C一致的H的子集为HC。我们定义一个LFF解决方案：
一般来说，给定一个LFF输入，可能会有多个解决方案。我们为每个假设关联了一个成本，并倾向于选择最优解决方案，即成本最小的解决方案。在以下内容中，我们使用假设的大小作为成本函数，以其中的文字数量来衡量。
不是解决方案的假设称为失败。LFF学习器从失败中识别约束以限制假设空间。例如，如果一个假设不一致，泛化约束就会剪枝其泛化，因为它们也被证明是不一致的。
4 数值推理
我们将前一节的框架扩展到允许在可能是无限的域中进行数值推理。我们假设对SMT理论（De Moura和Bjørner 2011）有所了解。我们的想法是将搜索分为两个阶段（i）程序搜索，以及（ii）数值搜索。首先，学习者生成用变量（称为数值变量）代替数值的部分程序。然后，学习者搜索数值来填充数值变量。
4.1 程序搜索
学习者首先搜索用变量代替数值的部分程序，这些变量称为数值变量。
数值变量。我们将LFF的元语言L扩展为包含数值变量。数值变量是一个可以用数值替换的一阶变量，即数值变量作为数值符号的占位符。在以下内容中，我们用一元谓词符号@numerical表示数值变量。例如，在图1c中的程序中，用语法@numerical标记的变量N是一个数值变量。
数值字面量。数值字面量是一种需要数值推理的字面量，其所有参数都是数值。数值字面量可以包含数值变量作为参数。在程序搜索阶段，学习者构建的部分假设中，数值字面量的数值变量位置用变量代替。例如，学习者可能会生成以下程序，其中字面量leq(B,N)是一个包含数值变量N的数值字面量：
相关变量。相关变量是同时出现在数值字面量和普通字面量中的变量。相关变量作为关系学习和数值推理之间的桥梁。例如，在上述程序H中，变量B是与数值变量N相关的变量。
通过在正面和负面示例上执行不带数值字面量的假设，可以确定相关变量的可能替换。例如，给定正面示例{f([a, b]), f([])}和负面示例{f([b, c, a, d, e, f]), f([c, e, d, a, b])},上述假设H对相关变量B有以下正面SP (B)和负面SN (B)替换：SP (B) = {2, 0}和SN (B) = {6, 5}。
4.2 数值搜索
在数值搜索阶段，学习者根据数值字面量的定义和相关变量的可能替换构建一个SMT公式。它为每个正面示例生成一个约束，以确保学习到的假设覆盖它。它为每个负面示例生成一个约束，以确保学习到的假设不覆盖它。例如，学习者将上述假设中的数值搜索转换为以下SMT公式：
附录中包含了NUMSYNTH如何构建SMT公式的详细信息。公式的解代表了测试的部分程序的可能数值。换句话说，如果公式是可满足的，任何解都是部分程序中数值变量的替换，使得得到的程序是LFF输入的解决方案。例如，替换N = 3是上述公式的一个解。将这个替换应用到上述的程序H中，形成了以下LFF解决方案：
在实践中，为了处理非确定性字面量，我们从为相关变量找到的替换中构建一个表达式。约束断言对于每个正面示例至少有一个表达式被验证，而对于任何负面示例都没有表达式被验证。换句话说，通过一个析取，多实例问题（Dietterich、Lathrop和Lozano-Pérez 1997）被委托给求解器。结果SMT公式中的文字数量由 ne × s × nv 上限界定，其中 ne 是示例的数量，s 是每个示例的最大替换数量，nv 是候选假设中的变量数量。这个结果的证明在附录中。
4.3 约束
如果一个候选程序不是LFF输入的解决方案，我们生成约束来从假设空间中剪枝其他程序，并约束后续的程序搜索阶段。遵循 Hocquette 和 Cropper（2022），我们使用以下约束。给定一个在程序搜索阶段生成的带有数值变量的部分程序P：
1. 如果在数值搜索阶段没有解决方案，那么P不能覆盖任何正面示例，因此P太具体了。我们剪枝包括P的一个专门化作为子集的程序。
2. 如果在数值搜索阶段找到的所有解决方案产生的程序都太具体了，那么P太具体了。我们剪枝没有额外数值字面量的P的专门化。
3. 如果在数值搜索阶段找到的所有解决方案产生的程序都太泛化了，那么P太泛化了。我们剪枝P的非递归泛化。
这些约束是最优的（Hocquette和Cropper 2022），因为它们不会从假设空间中剪枝最优解决方案。附录包含了关于约束的更多细节。
5 实现
我们介绍我们的实现，称为NUMSYNTH。我们首先简要描述POPPER（Cropper和Morel 2021），NUMSYNTH是基于POPPER的。
5.1 POPPER
POPPER接收一个LFF输入，其中包含一组正面和负面示例、背景知识B、允许的假设大小的界限H，以及一组假设约束C。为了生成假设，POPPER使用一个ASP程序P，其模型是以元语言L表示的假设解决方案。换句话说，P的每个模型（答案集）代表一个假设。
POPPER遵循生成、测试和约束循环来找到一个解决方案。首先，它使用ASP系统Clingo（Gebser等人，2014）生成ASP程序P的一个假设作为解决方案。POPPER使用Prolog（通常）根据背景知识对这些示例测试这个假设。如果假设是解决方案，POPPER返回它。否则，假设是失败的：POPPER识别失败的类型，并相应地构建约束。例如，如果假设不一致，POPPER构建一个泛化约束。POPPER将这些约束添加到ASP程序P中，以约束后续的生成步骤。这个循环重复进行，直到找到假设解决方案，或者直到ASP程序P没有更多的模型为止。
5.2 NUMSYNTH
NUMSYNTH基于POPPER。它也遵循生成、测试和约束循环。
部分程序。首先，NUMSYNTH生成可能包含数值字面量的部分程序。一个子句中数值字面量的最大数量是一个用户参数，默认值为2。此设置表达了搜索复杂性和表达能力之间的权衡。
数值字面量。NUMSYNTH支持图2中显示的内置数值字面量。虽然添加了来自常规数值一阶变量的原因，并且没有用常数符号替换的数值变量，但其他字面量有这样的数值变量，由N表示。
如图3所示，NUMSYNTH中的数值字面量足以对标准线性算术片段进行推理。由于复杂性原因，NUMSYNTH目前不支持的其他片段包括非线性算术。关于数值字面量的更多细节在附录中提供。如果已知，用户可以指定要使用的这些数值字面量的子集。否则，NUMSYNTH自动确定要使用哪些字面量，这需要更多的搜索。如果已知，用户还可以选择指定数值变量的参数类型（实数或整数）和域，以限制搜索。
数值推理。NUMSYNTH在测试阶段执行数值推理。它首先确定相关变量的可能替换。为此，它将数值字面量中的相关变量作为新参数添加到头部字面量。然后，它从假设中移除数值字面量。例如，以下假设H变为H0：
NUMSYNTH使用Prolog执行生成的假设，对示例进行测试。我们使用Prolog是因为它能够处理列表和大的、潜在无限的域。NUMSYNTH保存为新添加的头部变量找到的替换。然后，它根据数值字面量的定义和为相关变量找到的值构建一个SMT公式。最后，NUMSYNTH使用SMT求解器Z3（Moura和Bjørner 2008）来确定结果SMT公式的可满足性。如果存在解决方案，它保存每个数值变量的一个可能值，并将这些值替换到原始程序中。否则，它重复循环以生成更多程序。
我们将SMT求解器设置为返回公式的任何解决方案。我们不优化数值选择，因为不清楚如何在学习文本最小程序和学习最优数值（程序中可能多个）之间进行权衡。解决这个限制是未来的工作。
6 实验
我们声称NUMSYNTH可以从数值推理中学习带有数值的程序。因此，我们的实验旨在回答以下问题：
Q1 NUMSYNTH能否学习带有数值的程序？
为了回答Q1，我们评估NUMSYNTH在需要数值推理的各种任务上的表现。
我们还声称我们的方法可以降低搜索复杂性，从而提高学习性能。因此，我们的实验旨在回答以下问题：
Q2 NUMSYNTH与其他方法相比表现如何？
为了回答Q2，我们将NUMSYNTH与ALEPH和MAGICPOPPER系统进行比较，它们是唯一能够学习带有数值常数符号的程序合成系统。
如第4.2节所述，NUMSYNTH构建的SMT公式的大小是示例数量的增函数。因此，为了评估我们的系统如何扩展，我们研究以下问题：
Q3 NUMSYNTH随着示例数量的增加表现如何？
为了回答Q3，我们改变示例数量并评估NUMSYNTH的性能。
领域 我们考虑四个领域来评估我们的主张。
附录中包含了关于领域和任务的更多细节。
几何。这些任务涉及学习点是否属于几何对象（区间、半平面），其参数是待学习的数值。图4显示了半平面任务的一个示例假设。
Zendo。Zendo是一个多人游戏，玩家的目标是识别由一组具有不同属性的部件制成的结构必须遵循的规则。我们考虑四个逐渐复杂的任务。图1b和5分别显示了任务1和2的目标假设示例。
药效团。目标是识别负责药物活性的药效团的属性（Finn等人，1998）。这个领域需要推理不同属性的原子之间的距离以及连接彼此的键。我们考虑四个逐渐复杂的任务。图6显示了任务4的目标假设示例。
程序合成。我们考虑三个程序合成任务。这些任务是列表转换任务，涉及学习递归程序和数值推理。
系统 为了评估Q2，我们将NUMSYNTH与MAGICPOPPER和ALEPH进行比较。我们简要描述每个系统。附录中包含了更多细节。
MAGICPOPPER和NUMSYNTH。我们为NUMSYNTH和MAGICPOPPER提供相同的输入。我们允许MAGICPOPPER在具有有限答案替换数量的字面量中为类型为实数或整数的变量学习常数符号。实验的区别在于NUMSYNTH执行数值推理的能力。
ALEPH。我们为ALEPH提供从NUMSYNTH的数值字面量适应而来的定义，以适应其延迟评估程序。ALEPH使用与NUMSYNTH不同的偏好来限制假设空间。因此，比较不太公平，应被视为指示性的。
实验设置 我们为每个任务强制执行10分钟的超时。我们测量预测准确性和学习时间。我们在10次试验中测量平均值和标准误差。我们使用8核3.2 GHz苹果M1和单个CPU。
6.1 实验1：与最新技术的比较
表1和表2显示了结果。它们表明，NUMSYNTH在所有任务上都实现了高准确率。准确率不是最大值，因为在给定训练集的情况下，可能有多个数值可以导致一个完整且一致的假设，而NUMSYNTH并不优化数值选择。例如，在给定SMT公式 2 ≤ N ∧ 0 ≤ N ∧ ¬(6 ≤ N) ∧ ¬(5 ≤ N) 时，NUMSYNTH可以返回任何满足 2 ≤ N < 5 的值N。
这些结果表明，NUMSYNTH可以在合理时间内（少于80秒）在多个领域学习带有数值的程序。NUMSYNTH可以识别需要从多个示例中推理的数值，这些数值可能不会出现在背景知识中。例如，它可以解决涉及学习两个原子之间的距离必须小于特定值的pharma1任务。它还可以从无限域（如实数或整数）中学习带有数值的程序。最后，它可以学习具有多个相关数值字面量的假设，例如halfplane或pharma4（图4和图6）。鉴于这些结果，我们对Q1给出肯定的回答。
我们将NUMSYNTH与ALEPH和MAGICPOPPER进行比较。表1显示，NUMSYNTH实现了高于或等于ALEPH和MAGICPOPPER的准确率。独立t检验确认了除halfplane和zendo1外所有任务在p < 0.01水平上差异的显著性。
这些结果表明，NUMSYNTH可以解决其他系统难以解决的任务。例如，ALEPH在学习具有多个共享变量的数值字面量的假设方面存在困难，这对于zendo2或zendo3是必要的。ALEPH对所有正面和负面示例的替换执行延迟评估，因此难以学习具有析取（如zendo2或pharma2）的数值假设。在这些情况下，ALEPH可能将假设作为事实学习，这些事实不会推广到测试集。最后，ALEPH在递归程序的学习上存在困难，在程序合成任务上表现不佳。否则，ALEPH在其他任务上表现良好，例如halfplane或zendo1。
MAGICPOPPER可以学习具有来自无限域的常数符号的程序，潜在地是递归程序。然而，它不能从多个示例中联合推理，也不能识别具有大量或无限数量替换的字面量中的常数，例如大于。这些限制阻止了它学习不等式，例如在pharma2中。
表2显示了学习时间。它表明ALEPH的学习时间可能比NUMSYNTH长。例如，ALEPH解决zendo1任务需要25秒，而NUMSYNTH只需要10秒。然而，与ALEPH不同的是，NUMSYNTH寻找文本最优解决方案。在学习时间方面，NUMSYNTH也优于MAGICPOPPER。由于缺乏数值推理能力，MAGICPOPPER无法在某些任务上表达简洁的假设，因此搜索到更大的深度。此外，MAGICPOPPER采用生成和测试方法来识别数值：它首先从单个示例执行部分程序生成候选数值。然后，它在所有示例上测试候选值。相反，NUMSYNTH使用所有示例共同解决单一问题。因此，它避免了考虑可能的许多候选值的需要，可以更高效。鉴于这些结果，对Q2的回答是，在学习带有数值的程序时，NUMSYNTH在学习和预测准确性方面可以胜过现有方法。
6.2 实验2：可扩展性
我们比较了在变化训练示例数量时NUMSYNTH与ALEPH和MAGICPOPPER的性能。我们使用其他系统可以解决的zendo1任务。然而，我们方法的主要优势在于它能够学习现有方法无法学习的概念。因此，我们还评估了在现有系统难以解决的pharma2任务上的可扩展性。图7和图8显示了学习时间与示例数量的关系。附录显示了预测准确性。它们在pharma2上对MAGICPOPPER和ALEPH来说不是最大的。
随着示例数量的增加，学习任务的复杂性，因此学习时间也随之增加。当学习时间达到超时时（即对ALEPH和MAGICPOPPER而言），预测准确性会降低。NUMSYNTH在两项任务上都有比MAGICPOPPER更短的学习时间，并且它的学习时间增长得更慢。MAGICPOPPER生成从单个示例可推导出的所有候选数值，然后将其与其余示例进行测试。相反，NUMSYNTH在解决SMT公式之前从所有示例生成约束。它可以更早地传播信息，从而实现更短的学习时间。然而，由于SMT问题的复杂性，NUMSYNTH在处理大量示例时可能会遇到困难。例如，在非确定性字面量的情况下，SMT公式可能包括析取，这进一步增加了复杂性。
附录包括NUMSYNTH学习时间的分解。它显示其学习时间主要由构建和解决SMT公式所主导。最后，NUMSYNTH在pharma2上比ALEPH更好地扩展，但在zendo1上扩展得更差。因此，对Q3的回答是，NUMSYNTH在示例数量上比MAGICPOPPER更好地扩展，并且可以比ALEPH更好地扩展。然而，可扩展性受到数值推理阶段复杂性的限制。这一结果突出了NUMSYNTH的一个限制。
7 结论和未来工作
学习带有数值的程序对于许多AI应用至关重要。然而，现有的程序合成系统难以从无限域中识别数值并推理多个示例。为了克服这些限制，我们引入了NUMSYNTH，这是一个结合了关系学习和数值推理的ILP系统，可以高效地学习带有数值的程序。我们方法的关键思想是将学习分解为两个阶段：（i）程序搜索，以及（ii）数值搜索。在程序搜索期间，NUMSYNTH构建用变量代替数值的部分程序。然后，给定一个部分程序，NUMSYNTH通过使用训练示例构建SMT公式来搜索数值。NUMSYNTH使用一组内置的数值字面量（图2）来支持大量算术片段（图3），如线性整数算术。我们在四个领域（几何、游戏玩法、生物学和程序合成）上的实验表明，我们的方法可以（i）学习带有数值的程序，以及（ii）与最先进的ILP系统相比提高预测准确性并减少学习时间。特别是，它可以学习具有多个数值的程序，包括递归程序。换句话说，我们已经展示了NUMSYNTH可以解决现有系统无法解决的数值任务。在更高的层次上，我们认为这篇论文有助于桥接关系和数值学习。
局限性和未来工作
可扩展性。我们方法的一个可扩展性限制是数值推理阶段的复杂性，这是（i）示例数量和（ii）数值变量数量的函数。未来的工作将旨在识别足以确定合适数值的示例子集（Anthony和Frisch 1997）。
成本函数。NUMSYNTH学习最优程序，其中成本函数是假设的大小（其中的字面量数量）。然而，可能更希望根据不同的标准来优先选择假设，例如在数值预测的情况下的最大边缘或均方误差（Srinivasan和Camacho 1999）。未来的工作应该探索使用替代成本函数的学习。
噪声。与其他ILP系统（Karaliˇc和Bratko 1997；Blockeel和De Raedt 1998；Srinivasan 2001）相比，NUMSYNTH无法从带噪声的示例中识别数值。Wahliga（2022）扩展了LFF以支持从带噪声的示例中学习。这个扩展应该可以直接应用于NUMSYNTH。
