通过否定和谓词发明实现泛化

Generalisation Through Negation and Predicate Invention

通过否定和谓词发明实现泛化

https://arxiv.org/pdf/2301.07629

摘要

从小数量的示例中进行泛化是机器学习中的一个基本挑战。为了应对这一挑战，我们引入了一种结合了否定和谓词发明的归纳逻辑编程（ILP）方法。结合这两个特性，可以让ILP系统通过学习只有普遍量化的体变量的规则来更好地泛化。我们在NOPI中实现了我们的想法，它可以学习带有谓词发明的正常逻辑程序，包括具有分层否定的Datalog程序。我们在多个领域的实验结果表明，我们的方法可以提高预测准确性和学习时间。

1 引言

Zendo是一个游戏，其中一个玩家（老师）为结构创建一个隐藏规则。其他玩家（学生）通过构建结构来尝试发现规则。老师通过标记哪些结构遵循或违反规则来提供反馈，但不做进一步解释。学生们继续猜测规则。第一个正确猜测规则的学生获胜。例如，考虑图1中显示的示例。这些示例的一个可能规则是“有两个红色的圆锥体”。

假设我们想使用机器学习来玩Zendo，即从示例中学习规则。那么我们需要一种方法，能够（i）学习可解释的规则，以及（ii）从小数量的示例中泛化。尽管这些要求对于许多问题至关重要，但对于标准机器学习技术来说却很困难（Cropper等人，2022年）。

归纳逻辑编程（ILP）（Muggleton，1991年）是一种可以从少量示例中学习可解释规则的机器学习方法。例如，一个ILP系统可以从图1中的示例中学习以下假设（一组逻辑规则）：

这个假设表明，当存在两个不同的红色圆锥体A和B时，关系f适用于状态S，即这个假设表明有两个红色圆锥体。

假设我们得到了图2中显示的两个新示例。我们之前的假设不能正确解释这些新示例，因为它涉及了新的负面示例。为了正确解释所有示例，我们需要一个析取假设，即“[正好有两个红色圆锥体]或[正好有三个红色圆锥体]”。给定一个新的有四个红色圆锥体的正面示例和一个有三个红色和一个绿色圆锥体的负面示例，我们需要学习另一个规则，即“正好有四个红色圆锥体”。

正如希望明确的那样，使用这种方法我们很难泛化到训练示例之外，因为我们需要为每个圆锥体的数量学习一个规则。我们理想的情况是学习一个单一的规则，即“所有的圆锥体都是红色的”。然而，大多数ILP方法很难学习这种形式的规则，因为它们只学习Datalog或确定性程序，因此只学习具有存在量化的体变量的规则（Apt和Blair，1991年；Dantsin等人，2001年）。

为了克服这个限制，我们结合了否定作为失败（NAF）（Clark，1977年）和谓词发明（PI）（Stahl，1995年），以学习具有普遍量化的体变量的规则。结合NAF和PI的主要原因是，许多概念只能在这个更具表现力的语言中表达（Stahl，1995年；Dantsin等人，2001年）。例如，对于Zendo场景，我们的方法结合了否定和PI，学习了以下假设：

这个假设表示“所有的圆锥体都是红色的”。谓词符号inv1不是作为输入提供的，而是由我们的方法发明的。由inv1定义的规则表示“有一个圆锥体不是红色的”。由f定义的规则否定了这个规则，表示“并非有一个圆锥体不是红色的”。因此，这个假设声明“不存在不是红色的圆锥体”，根据一阶逻辑的等价性（∀ ≡ not ∃ not），这与“所有的圆锥体都是红色的”是相同的。

为了结合否定和PI，我们基于从失败中学习（LFF）（Cropper和Morel 2021）。一个LFF学习器不断地生成和测试假设，从中推断出约束。例如，如果一个假设过于泛化，即涉及一个负面示例，一个LFF学习器，如POPPER，就会构建一个泛化约束，以从假设空间中剪枝更泛化的假设。我们将LFF从学习确定性（单调）程序扩展到学习极性程序，这是正常（非单调）程序的一个片段。极性程序的关键好处是我们可以在我们的学习算法中高效地推理它们之间的包含关系。此外，我们展示了（定理2）极性程序可以捕捉分层否定的Datalog（Dantsin等人，2001）。

我们在NOPI中实现了我们的想法，它建立在POPPER之上，支持学习递归和最优程序。创新性、影响力和贡献。我们方法的关键创新是能够学习带有发明谓词符号的正常逻辑程序。我们在第2节中扩展了这一创新。其影响是我们的方法可以学习现有方法无法学习的程序。具体来说，我们声称结合否定和PI可以通过允许我们学习具有普遍量化的体变量的规则来提高学习性能。我们在多个领域的实验支持了我们的主张，并表明我们的方法导致预测准确性和学习时间大大改善。

总体而言，我们做出了以下贡献：

1. 我们引入了极性程序，这是分层逻辑程序的一个片段。我们展示了（定理2）这个正常逻辑程序的片段可以捕捉分层否定的Datalog（Dantsin等人，2001）。

2. 我们为这个非单调设置引入了LFF约束，并证明了它们的合理性（命题1和2）。

3. 我们引入了NOPI，这是一个可以学习带有PI和递归的正常逻辑程序的ILP系统，例如分层否定的Datalog程序。

4. 我们在多个领域上的经验表明（i）NOPI可以胜过现有方法，以及（ii）我们的非单调约束可以减少学习时间。

2 相关工作

程序合成。归纳逻辑编程（ILP）是一种程序合成形式（Shapiro，1983），吸引了广泛的研究者群体（Evans和Grefenstette，2018；Ellis等人，2018；Silver等人，2022）。许多最近的方法合成单调的Datalog程序（Si等人，2019；Raghothaman等人，2020；Bembenek，Greenberg和Chong，2023）。我们在许多方面有所不同，包括通过学习非单调程序。

否定。许多ILP方法学习非单调程序（Quinlan，1990；Srinivasan，Muggleton和Bain，1992；Dimopoulos和Kakas，1995；Sakama，2001；Sakama和Inoue，2009；Ray，2009）。大多数使用否定来处理例外情况，如“鸟类飞翔，除了企鹅”，因此需要负面示例。例如，Inoue和Kudoh（1997）通过首先学习覆盖正面示例的程序，然后添加异常（使用NAF）来解释负面示例，从而学习正常逻辑程序。相比之下，我们结合NAF和PI来提高泛化能力，不需要负面示例——正如Bekker和Davis（2020）所说，有时仅从正面示例学习是必要的。此外，大多数方法基于逆蕴含（Muggleton，1995），因此它们难以学习递归和最优程序。相比之下，我们的方法可以学习递归和最优程序，因为我们基于LFF。正如Fogel和Zaverucha（1998）所说，学习非单调程序是困难的，因为标准的包含关系通常不适用于正常程序。为了克服这一挑战，作者基于程序中谓词符号的依赖图引入了正常程序的包含关系。我们的方法不同，因为我们引入了与分层逻辑程序相关的正常逻辑程序的一般片段。此外，我们的方法支持PI。

谓词发明。尽管对于许多任务至关重要，例如规划（Silver等人，2022）和学习复杂算法（Cropper和Muggleton，2019），但大多数ILP系统不支持PI（Muggleton，1995；Srinivasan，2001；Blockeel和De Raedt，1998；Corapi，Russo和Lupu，2011；Zeng，Patel和Page，2014；Inoue，Ribeiro和Sakama，2014）。支持PI的方法通常需要元规则来限制假设的语法（Muggleton，Lin和TamaddoniNezhad，2015；Evans和Grefenstette，2018；Kaminski，Eiter和Inoue，2019；Hocquette和Muggleton，2020；Dai和Muggleton，2021；Glanois等人，2022），在某些情况下，这些规则无法提供（Cropper和Tourret，2020）。相比之下，我们不需要元规则。

3 问题设定

我们假设读者已经熟悉逻辑编程（Lloyd 2012）和ASP（Gebser等人 2012），但在附录A中包含了总结。为了清晰起见，我们定义了一些关键术语。一个正常规则的形式为： h ← b1, · · · , bn, not bn+1, · · · , not bn+m 其中h是头原子，每个bi是一个文字，b1, · · · , bn, not bn+1, · · · , not bn+m是体。符号not表示失败否定（Clark 1977）。一个文字是一个原子（一个非否定文字）或一个原子的否定（一个否定文字）。一个正常逻辑程序是一组正常规则。一个子句是一组文字。一个肯定子句是一个具有且只有一个非否定文字的子句。一个替换θ = {v1/t1, ..., vn/tn}表示将每个变量vi同时替换为其对应的项ti。

子句C1当且仅当存在替换θ使得C1θ ⊆ C2时，称为C1包含C2（Plotkin 1971）。肯定理论P包含肯定理论Q（P ⪯θ Q）当且仅当 ∀r2 ∈ Q, ∃r1 ∈ P 满足r1包含r2。肯定理论P是肯定理论Q的专门化当且仅当Q ⪯θ P。肯定理论P是肯定理论Q的泛化当且仅当P ⪯θ Q。

3.1 极性程序

为了学习正常程序，我们需要超越确定性程序和标准的包含关系。为此，我们引入了极性程序，这是谓词符号具有极性的正常程序。我们首先定义顶级符号，这些是在程序中仅以肯定方式使用的头部谓词符号：

在正常程序P中，每个头部谓词符号p的极性是积极的（pos(p)）或消极的（neg(p)）。顶级符号top(P)中的符号的极性是积极的。相比之下，defs(P)中符号的极性取决于该符号是被积极使用还是消极使用：

我们可以使用标准包含关系比较积极规则。对于消极规则，我们需要翻转比较的顺序。为此，我们引入了极性包含关系：

我们展示了极性包含关系意味着蕴含。注意，为了证明以下两个定理，我们所需的否定属性在NAF的常用语义中成立（例如稳定和良基），当不发生未分层的否定使用时。分层和极性逻辑程序都不允许未分层的否定使用。

3.2 从失败中学习 (LFF)

LFF 在假设空间（假设的集合）中搜索一个能泛化示例和背景知识的假设。在现有文献中，LFF 假设是一个确定的（单调的）程序。LFF 使用假设约束来限制假设空间。设L为定义假设的语言。假设约束是用L表示的约束。设C为用语言L书写的一组假设约束。假设H与C一致，当且仅当H用L书写时不违反C中的任何约束。我们用HC表示假设空间H中不违反C中任何约束的子集。

3.3 LFFN

我们扩展LFF以学习极性程序，我们称这种设置为带否定的失败学习（LFFN）。我们定义LFFN的输入：

3.4 LFFN约束

LFF学习器从失败的假设中学习假设约束。Cropper和Morel（2021）基于包含关系引入了假设约束。专门化约束会剪枝一个假设的专门化。泛化约束会剪枝泛化。现有的LFF约束只对单调程序有效，即在学习非单调程序时可能会错误地剪枝最优解，因此在LFFN设置中是不健全的。不健全的原因是，在非单调设置中，蕴含不是包含关系的结果，即使是在命题逻辑的情况下，以下示例说明了这一点。

总之，极性包含关系允许我们在学习非单调程序时健全地剪枝假设空间。在接下来的部分中，我们将介绍一个使用极性包含关系高效学习极性程序的算法。

4 算法

现在我们描述我们的NOPI算法。为了帮助解释，我们首先描述POPPER（Cropper和Morel 2021）。

POPPER POPPER 以 LFF 输入为输入，并学习作为确定性程序的假设，不使用 NAF（失败否定）。为了生成假设，POPPER 使用一个 ASP 程序 P，其中 P 的每个模型（解答集）都表示一个假设。POPPER 通过生成、测试和约束的循环来寻找解决方案。首先，它使用 ASP 系统 Clingo（Gebser 等人，2019）生成一个作为 P 的解的假设。然后，POPPER 根据背景知识和训练示例，通常使用 Prolog 测试该假设。如果该假设是解，POPPER 就返回它。否则，假设是失败的：POPPER 确定失败的类型并相应地构建约束。例如，如果假设不一致，POPPER 会构建一个泛化约束。POPPER 将这些约束添加到 P 中，以约束后续的生成步骤。该循环会一直重复，直到求解器找到解决方案或 P 没有更多模型。

4.1 NOPI

NOPI 基于 POPPER，并遵循生成、测试和约束的循环。NOPI 的两个关键创新是它能够：(i) 学习极性程序，(ii) 使用非单调的泛化和专门化约束来有效修剪假设空间。我们依次描述这些进展。

极性程序 为了学习极性程序，我们扩展了生成 ASP 程序以生成正常逻辑程序，即带有否定文字的程序。为了只生成极性程序，我们将定义 1 和定义 2 的规则和约束添加到 ASP 程序中，以消除谓词符号具有多重极性的模型。完整的 ASP 编码在附录 F 中，但我们在高层次上简要解释一下。如果一个谓词符号 p 出现在一个头符号为 q 的规则的体中，我们称 q 调用 p，我们称之为调用关系。谓词可以被正向或负向调用。我们计算调用关系的传递闭包，跟踪每条路径上的负向调用次数。如果一个符号在到达顶层符号的路径上有偶数次负向调用，我们称其相关规则为正极性，否则为负极性。如果任何规则被标记为同时具有正极性和负极性，则该程序为非极性程序。计算调用关系时，我们忽略背景知识中的谓词。

极性约束 NOPI 使用两种类型的约束来剪枝模型，从而剪枝假设。我们称这些约束为极性专门化和极性泛化约束。这些约束与 POPPER 使用的约束不同，因为 (i) 它们使用额外的文字来为规则分配极性，以及 (ii) 它们使用极性包含关系（定义 4）而不是标准包含关系。在学习极性程序时，极性很重要，因为极性泛化约束剪枝正面极性规则的泛化和负面极性规则的专门化。极性专门化约束剪枝正面极性规则的专门化和负面极性规则的泛化。

示例 9. 重新考虑引言中的Zendo场景（图1和图2）。以下假设是不完整的，因为每个正面示例都至少包含一个圆锥体：

5 实验

为了评估结合否定和谓词发明（PI）的影响，我们的实验旨在回答以下问题：

Q1 否定和PI能否提高学习性能？

为了回答Q1，我们将NOPI的性能与不能否定发明谓词符号的POPPER进行比较。将NOPI与具有不同偏好的不同系统进行比较，将无法回答这个问题，因为我们将无法确定任何性能差异的原因。

为了回答Q1，我们使用否定和PI应该有帮助的任务，例如学习Zendo的规则（Bramley等人，2018）。我们在下一节中描述这些任务。

我们为极性程序引入了健全的约束，以从假设空间中剪枝非最优解决方案。为了评估这些约束是否提高了性能，我们的实验旨在回答以下问题：

Q2 极性约束能否提高学习性能？

为了回答Q2，我们比较了使用和不使用这些约束的NOPI的性能。

我们引入NOPI，通过结合否定和PI超越现有方法。因此，我们的实验旨在

回答以下问题：

Q3 NOPI与现有方法相比如何？

为了回答Q3，我们将NOPI与POPPER、ALEPH和METAGOLSN进行比较。我们在下面描述这些系统。

问题Q1-Q3集中在否定和PI应该有帮助的任务上。然而，否定和PI并不总是必要的。在这种情况下，否定和PI会有害吗？我们的实验试图回答以下问题：

Q4 否定和PI会降低学习性能吗？

为了回答Q4，我们在否定和PI应该不必要的任务上评估NOPI。

可复制性。实验代码可以在以下仓库中找到：github.com/Ermine516/NOPI

领域 我们简要描述我们的领域。精确问题见附录D。

基础（B）。由Siebers和Schmid（2018）以及Purgał、Cerna和Kaliszyk（2022）引入的非单调学习任务，例如学习闰年的定义。

Zendo（Z）。Bramley等人（2018）引入了与引言中类似的Zendo任务。

图（G）。我们使用常用的图问题（Evans和Grefenstette 2018；Glanois等人，2022），如支配集、独立集和连通性。

集合（S）。这些基于集合的任务包括对称差集、分解为子集和相互独立性。

系统 我们将NOPI与POPPER（Cropper和Morel 2021；Cropper和Hocquette 2023）、ALEPH（Srinivasan 2001）和METAGOLSN（Siebers和Schmid 2018）进行比较。

我们给NOPI和POPPER相同的输入。唯一的实验区别是NOPI能够否定发明的谓词符号。ALEPH可以学习正常逻辑程序，但使用与NOPI不同的偏好，因此比较应被视为指示性的。此外，我们使用ALEPH的默认设置，但这些数据集上可能有更好设置（Srinivasan和Ramakrishnan 2011）。METAGOLSN可以学习正常逻辑程序，但需要元规则来定义假设空间。我们使用Siebers和Schmid（2018）使用的元规则，并补充了一组通用元规则（Cropper和Tourret 2020）。

实验设置 我们为每个任务使用300秒的学习超时时间，并将准确率和学习时间四舍五入到整数值。我们绘制99%的置信区间。附录B中有额外的实验细节。

Q1. 我们允许所有系统否定给定的背景关系。例如，在Zendo任务中，每个系统都可以否定颜色，如红色。因此，NOPI的任何改进都不是来自否定的使用，而是来自否定和PI的结合。

Q2. 我们需要一个基线来评估我们的极性约束。正如第3节所讨论的，POPPER在学习极性程序时使用不健全的约束。如果程序h不是解决方案并且有否定的发明符号，POPPER唯一健全的选择是从假设空间中剪枝h，但重要的是，不要剪枝其泛化或专门化。为了评估我们的极性约束，我们将它们与这种更简单的（放逐）方法进行比较，我们称之为NOPIbn。换句话说，为了回答Q2，我们将NOPI与NOPIbn进行比较。

5.1 结果

Q1. 否定和PI能否提高性能？表1显示了NOPI和POPPER的预测准确率。结果表明，NOPI在预测准确率方面大大优于POPPER。例如，对于所有红色（Z2）任务，POPPER学习到的是：

表2显示了相应的学习时间。结果表明，NOPI很少需要超过40秒就能学习到解决方案。其中一个较难的问题（学习时间为30秒）是“最大的是红色”（Z6），它涉及发明两个谓词符号并且有两层否定，据我们所知，这超出了现有文献中的任何内容：

表2显示了相应的学习时间。结果显示，NOPI很少需要超过40秒就能学习到解决方案。其中一些更困难的问题（例如学习时间为30秒的“最大的是红色”（Z6）），涉及发明两个谓词符号并且有两层否定，据我们所知，这超出了现有文献中的任何内容：

POPPER有时在不到一秒钟内就终止了。原因是在一些问题上，由于其高效的搜索，POPPER几乎立即证明了没有单调解决方案。

总体而言，本节的结果表明，对于Q1的回答是，结合否定和PI可以显著提高学习性能。

Q2. 极性约束能否提高性能？表3显示了NOPI和NOPIbn的学习时间。结果显示，NOPI的学习时间比NOPIbn短。换句话说，结果表明，极性约束可以大幅减少学习时间。Wilcoxon符号秩检验确认了差异的显著性，p值小于10^-8。对于较简单的任务，极性约束几乎没有好处，因为构建和添加它们到求解器的开销抵消了剪枝的好处。对于更困难的任务，差异是显著的。例如，在对称差（S4）任务上，NOPI和NOPIbn的学习时间分别为31秒和72秒，减少了57%。总体而言，结果表明，对于Q2的回答是，我们的极性约束可以大幅减少学习时间。

Q3. NOPI与现有方法相比如何？表1显示了系统的预测准确率。显然，NOPI以压倒性优势胜过其他系统。这个结果是意料之中的。除了METAGOLSN，其他系统无法学习带有PI的正常逻辑程序。ALEPH可以学习带有NAF的程序，有时能学习到合理的解决方案。然而，ALEPH无法执行PI，因此，由于其受限的语言，它在泛化方面遇到困难。在许多情况下，ALEPH只是记住了训练示例。由于依赖用户提供的元规则，METAGOLSN只能学习具有非常受限句法结构的正常逻辑程序，因此在我们几乎所有的任务上都表现不佳。

总体而言，本节的结果表明，对于Q3的回答是，NOPI在需要否定和PI的问题上与其他方法相比表现良好。

Q4. 否定和PI会降低性能吗？附录包括显示系统预测准确率和学习时间的表格。结果显示，NOPI在这些任务上的表现不如POPPER。Blumer界限（Blumer等人，1987）有助于解释原因。根据界限，给定两个大小不同的假设空间，如果目标假设在两者中都存在，那么搜索较小空间应该比搜索较大空间得到更高的预测准确率。NOPI考虑了带有否定和PI的程序，因此搜索的假设空间比POPPER和其他系统大得多。Q4中的任务不需要否定和PI，因此解释了差异。

6 结论和局限性

我们介绍了一种结合否定和谓词发明（PI）的方法。我们的方法可以学习极性程序，包括分层Datalog程序（定理2）。我们为这个非单调片段引入了泛化和专门化约束，并展示了它们是最优的（定理1）。我们引入了NOPI，这是一个可以学习带有PI的正常逻辑程序的归纳逻辑编程系统，包括递归程序。

我们在多个领域经验性地展示了（i）NOPI可以胜过现有方法，以及（ii）我们的非单调约束可以减少学习时间。

局限性和未来工作

低效的约束。NOPI 有时会将 30% 的学习时间花在构建极性约束上。这种低效是实现问题，而非理论问题。因此，我们的实验结果可能低估了 NOPI 的性能，特别是使用极性约束所带来的改进。

不必要的否定和 PI。我们的结果表明，结合否定和 PI 使 NOPI 能够学习其他方法无法学习的程序。然而，结果也表明，当否定和 PI 的结合不必要时，这种表达能力的增强可能是有害的。因此，这项工作的主要局限性以及未来研究的方向是自动检测何时问题需要使用否定和 PI。

原文链接：https://arxiv.org/pdf/2301.07629