亲爱的，我缩小了假设空间（通过逻辑预处理）

https://arxiv.org/abs/2506.06739

亲爱的，我缩小了假设空间（通过逻辑预处理）

Honey, I shrunk the hypothesis space (through logical preprocessing)

归纳逻辑编程 （Inductive Logic Programming, ILP）是一种形式化的机器学习方法。其目标是在假设空间中搜索一个能够概括训练样例和背景知识的假设。我们提出了一种在ILP系统搜索之前先缩小假设空间的方法。我们的方法利用背景知识来找出那些无论训练样例如何都不可能出现在最优假设中的规则。例如，我们的方法可以发现诸如“偶数不可能是奇数”以及“大于2的质数一定是奇数”这样的关系。然后从假设空间中移除违反这些规则的候选规则。

我们使用回答集编程 （Answer Set Programming, ASP）实现该方法，并将其用于缩减基于约束的ILP系统的假设空间。我们在多个领域进行了实验，包括视觉推理和游戏对弈，结果表明我们的方法可以显著减少学习时间，同时保持预测准确性。例如，仅用10秒的预处理时间，我们的方法就能将学习时间从超过10小时缩短到仅需2秒。

1 引言

归纳逻辑编程（ILP）[9, 51] 是一种逻辑机器学习的形式。其目标是在假设空间中寻找一个能够概括训练样例和背景知识（BK）的假设。ILP 的显著特点是使用逻辑规则来表示假设、样例和背景知识。

与所有形式的机器学习一样，ILP面临的一个主要挑战是如何在巨大的假设空间中进行高效搜索。为了说明这一挑战，考虑这样一个学习任务：我们需要对一个任意关系 h 的样例进行泛化。假设我们可以使用一元关系 odd（奇数）、even（偶数）和 int（整数），以及二元关系 head（头）、tail（尾）、len（长度）、lt（小于）和 succ（后继）来构建规则。那么规则空间（即所有可能规则的集合）中将包含如下规则：

假设空间是规则空间的幂集，因此它极其庞大。例如，在这个简单的场景中，如果我们允许每条规则最多包含四个文字（literal）和四个变量，则可能存在超过3,183,545条不同的规则，从而产生 2^3,183,545 个可能的假设。

大多数研究通过开发高效的搜索技术来应对这一挑战 [1, 3, 13, 52, 53, 57, 64, 70]。换句话说，大多数研究都假定假设空间是固定的，并专注于如何高效地在该空间中进行搜索。

我们并未设计新的搜索算法，而是提出了一种方法：在将假设空间交给ILP系统之前先对其进行缩减。其核心思想是利用给定的背景知识（BK），找出那些无论我们要学习什么概念都不可能出现在最优假设中的规则，我们将这些规则称为无意义规则 （pointless rules）。一个最优假设是在训练数据上最小化某个代价函数的结果，例如找到能够蕴含所有正例而不蕴含任何负例的最小假设 [53]，或找到具有最小描述长度的假设 [36]。

为了说明我们的思路，请考虑前面提到的场景。假设我们拥有的背景知识仅包含以下事实：

我们利用这些背景知识（BK）识别出四种类型的无意义规则：不可满足规则 （unsatisfiable）、蕴含可约规则（implication reducible）、召回可约规则 （recall reducible）和单例可约规则 （singleton reducible）。

不可满足规则 是指无论我们要学习什么概念，它都不可能为真，也就是说，不论具体的训练样例如何，它都无法被满足。例如，在给定此背景知识的情况下，如果我们采用封闭世界假设 [60]，由于不存在形式为 tail(A,A) 的事实，我们可以推断出 tail/2 是一个反自反关系 （irreflexive），因此可以从规则空间中移除规则 r₂ 和 r₆，因为它们的条件体（body）是不可满足的。此时的规则空间变为：

同样地，我们可以推断出 tail/2 是非对称的 （asymmetric）和反传递的 （antitransitive），因此可以从规则空间中移除规则 r₃ 和 r₅。此时的规则空间变为：

最后，单例可约规则 （singleton reducible rule）是指包含一个始终为真 的文字（literal）的规则。例如，如果变量 始终是一个列表（list），那么规则 r₁ 中的文字 len(A,B) 就总是成立，因为每个列表都有长度，而变量 没有受到任何限制。换句话说，由于变量 在这条规则中只出现一次，因此文字 len(A,B) 是冗余的，因为它没有任何区分能力（no discriminatory power）。因此，我们可以从假设空间中移除规则 r₁。此时的规则空间已为空。

正如我们在本文中所展示的那样，我们可以自动识别并移除假设空间中所有四种类型的无意义规则，同时不会删除最优假设。如上述场景所示，在尚未查看任何训练样例之前，移除这些无意义规则就可以大幅缩减假设空间。换句话说，我们的方法可以在搜索假设之前就先确定哪些地方是无需搜索的 。

为了识别不可满足规则 和蕴含可约规则 ，我们使用了回答集编程 （Answer Set Programming, ASP）[27]。具体来说，我们构造一些小的规则，并利用 ASP 来判断这些规则是否相对于背景知识（BK）是不可满足的或蕴含可约的。我们重复这一过程，直到达到用户设定的超时时间为止。此阶段的输出是一组被判定为不可满足或蕴含可约的规则。

为了识别召回可约规则 （recall reducible rules），我们采用了一种类似于 Savnik 和 Flach [62] 提出的方法（用于在数据库中发现函数依赖）以及 Struyf 和 Blockeel [66] 提出的方法（用于构建高效查询）的自底向上方式 。对于每一个背景关系及其参数的任意子序列，我们计算其可能产生的最大答案替换数量（answer substitutions）。例如，在上面给出的 BK 中，succ/2 最多只有三个实例化情况（ground instances），因此它最多有三个答案替换。同样地，对于文字 succ(A,B)，如果变量 是已知的（ground），那么变量 最多只有一个答案替换。

此阶段的输出是一组被判定为召回可约的规则。

为了识别单例可约规则 ，我们使用 ASP 来判断一个关系是部分函数 （partial）还是全函数 （total），并利用这些信息来推导出单例可约规则。此阶段的输出是一组被判定为单例可约的规则。

我们将所有这些无意义规则集合起来，用于缩减一个基于约束的 ILP 系统 [13, 36] 的假设空间。例如，如果我们发现 even（偶数）和 odd（奇数）是互斥的，我们会构建相应的约束，以移除那些在规则体中同时包含 odd(A) 和 even(A) 的规则。同样地，如果我们发现文字 succ(B,C)、succ(C,D) 和 lt(B,D) 是蕴含可约的，那么我们的约束将移除包含这些文字的规则。这些约束会从假设空间中移除非最优的假设，从而确保系统在搜索假设时永远不会考虑它们。

我们的假设空间缩减方法具有诸多优势：

• 该方法与具体的 ILP 系统无关，可以被任何 ILP 系统所使用。例如，Aleph 的规则剪枝机制 [64] 也可以利用这些约束。

• 该方法是一个独立的预处理步骤，不依赖于特定的学习算法或学习任务。

• 因此，我们可以将该方法作为预处理步骤，应用于多个任务共享的一组背景知识（BK）之上。

其主要好处是显著减少学习时间，而不会降低预测准确性 。例如，在仅给予10秒的预处理时间的情况下，我们的方法可以将学习时间从超过10小时减少到仅仅几秒钟。

新颖性和贡献

本文的核心创新在于提出了一种新的方法：作为一种预处理步骤，通过自动识别无意义规则，来自动缩减 ILP 系统的假设空间 。这种方法的影响是大幅减少学习时间 ，并在多个不同领域得到了验证。例如，我们的方法可以将学习时间减少高达99%。

本文在我们早期工作 [12] 的基础上进行了实质性扩展。在初步工作中，我们首次提出了利用背景知识（BK）发现对假设的约束的想法，例如“一个数不能同时是偶数和奇数”。但当时的工作依赖于人工提供的预定义属性集合，如反传递性（antitransitivity）和非自反性（irreflexivity）。而在本文中，我们将这一思想推广至四种任意类型的无意义规则，其中两种（蕴含可约和单例可约）是全新的概念，并且本文几乎所有的内容都是新增的。

总体而言，我们的主要贡献包括：

• 提出假设空间缩减问题

  ：其目标是找到原假设空间的一个子集，该子集仍然包含所有最优假设。

• 定义无意义规则

  ：包括不可满足规则、蕴含可约规则、召回可约规则和单例可约规则。我们证明了包含无意义规则的假设不可能是最优的（命题 2、4、6 和 9）。

• 描述一种假设空间缩减方法

  ，并实现为一个名为 shrinker 的系统。我们证明了 shrinker 只会从假设空间中移除非最优假设（命题 10）。

• 使用 shrinker 启动一个基于约束的 ILP 系统

  [13, 36]。

• 在多个领域进行实验验证

  ：结果表明，在仅给予10秒预处理时间的情况下，shrinker 能够显著缩短 ILP 的学习时间，有时甚至可以从超过10小时缩短到仅需2秒。

程序综合 （Program Synthesis）
归纳逻辑编程（ILP）是一种程序综合的形式，其目标是从示例中自动生成计算机程序。Gulwani 等人 [32] 认为这是人工智能的“圣杯”问题，引起了广泛的研究兴趣 [21, 22]。虽然我们的方法可以应用于任何形式的程序综合，但它特别适合 ILP，因为 ILP 的逻辑表示形式天然地通过逻辑约束支持声明性知识。

规则归纳 （Rule Induction）
ILP 方法从数据中归纳出规则，这与规则学习方法 [25] 类似。将 ILP 方法与最近的规则挖掘技术（如 AMIE+ [26] 和 RDFRules [69]）进行比较是困难的。大多数规则挖掘方法仅限于一元和二元关系，并且需要以事实作为输入。它们通常还在开放世界假设 （open-world assumption）下运行。相比之下，ILP 通常在封闭世界假设 （closed-world assumption）下运行，支持任意元数（arity）的关系，并且可以从确定性程序（definite programs）作为背景知识中进行学习。

约束

许多系统使用约束来限制假设空间 [1, 7, 13, 37, 40, 42, 47, 63]。例如，Apperception 引擎 [23] 包含几个内置约束，如统一性条件（unity condition），要求对象必须通过二元关系链连接起来。相比之下，我们是在搜索假设之前自动发现约束条件 。

用户可以向许多系统提供约束。例如，如果用户知道两个文字是不可满足的，他们可以将这些信息作为元约束提供给 ilasp，或通过用户定义的剪枝条件提供给 Aleph。但在这些情况下，用户是将约束作为输入提供给系统的。相比之下，我们的方法无需用户干预即可自动发现此类约束 。

预处理

我们方法的一个关键特征是：在将假设空间交给 ILP 系统进行搜索之前，我们就对其进行缩减。因此，我们的方法可以被视为一个预处理步骤 ，这在人工智能领域已被广泛研究，尤其是在缩小 SAT 实例规模方面 [20]。

ILP 中也有其他预处理工作的研究，特别是从 BK 中推导类型 [49, 54]。例如，McCreath 和 Sharma [49] 自动从 BK 中推导模式声明（mode declarations），比如参数的类型以及哪些参数应为 ground。我们不推导类型，而是从假设空间中移除不可满足、蕴含可约、召回可约和单例可约的规则。

此外，由于我们使用的是约束，我们能推理一些模式无法表达的性质，如反传递性、互斥性和蕴含关系。Bridewell 和 Todorovski [5] 在多任务设置下学习假设空间上的结构约束。相比之下，我们在解决任何任务之前就发现了偏置。

其他 ILP 中的预处理方法侧重于减小 BK 的规模 [18, 19] 或谓词发明 [8, 35]。相比之下，我们是在 BK 中发现约束，以缩减假设空间。

作为一种预处理步骤，Struyf 和 Blockeel [66] 计算了给定背景关系的召回率，以对规则中的文字进行排序，从而减少检查规则与样例和 BK 是否匹配所需的时间。我们使用了类似的算法，但不是对规则中的文字排序，而是利用召回率定义召回可约规则（Definition 11），并据此构建约束，从而缩减假设空间。

人工智能中的冗余

Plotkin [55] 使用蕴含 （subsumption）来判断一个文字在一阶子句 中是否是冗余的。
Joyner [41] 研究了同样的问题，他称之为子句压缩 （clause condensation），其中子句 C的一个压缩是指其最小基数的子集 C′⊆C，使得 C′⊨C。
Gottlob 和 Gottlob 与 Fermüller [31] 改进了 Joyner 的算法，并证明了判断一个子句是否已压缩的问题是 coNP-完全 的。

检测和消除冗余在计算机科学的许多领域都非常有用，并受到了定理证明社区的广泛关注 [38, 43, 67]。
在 SAT 求解器社区中，诸如阻塞子句消去 （blocked clause elimination）[45] 等冗余消除技术在现代求解器中起着关键作用。
这些冗余消除方法的目标与我们论文的目标类似：安全地识别出推导无关的输入 ，即 SAT 输入中包含的文字总是归结为重言式的子句。

3 问题设定

在本节中，我们将定义本文中使用的符号，简要介绍 ILP，然后定义假设空间缩减问题，并定义四种类型的“无意义规则”——我们可以在不移除最优假设的前提下将它们从假设空间中删除。

3.1 预备知识

3.2 归纳逻辑编程（Inductive Logic Programming）

我们将我们的方法建立在 ILP 的“从蕴含中学习”（learning from entailment）设定 [17] 上。我们定义一个 ILP 输入如下:

我们将背景知识限制为 Datalog 程序。在本文其余部分中，我们假设假设中的规则的头部文字不会出现在背景知识中规则的头部。

我们定义一个代价函数如下：

3.3 假设空间缩减

我们的目标是在不移除最优假设 的前提下缩减假设空间：

定义 7（假设空间缩减问题）

给定一个 ILP 输入 (E,B,H)，假设空间缩减问题的目标是找到一个子集 H′⊂H，使得如果 h∈H是一个最优假设，则 h∈H′。

在本文中，我们通过使用背景知识（BK）来识别那些不可能出现在最优假设中的规则，从而缩减假设空间。我们考虑四种类型的规则：

• 不可满足规则

  （unsatisfiable）

• 蕴含可约规则

  （implication reducible）

• 召回可约规则

  （recall reducible）

• 单例可约规则

  （singleton reducible）

下面我们将依次描述这四种规则。

3.4 不可满足规则

一个不可满足规则 是指其体部（body）在给定背景知识（BK）的情况下永远无法为真 的规则。例如，考虑以下规则：

假设 odd 和 even 这两个关系是互斥的 ，那么这条规则是不可满足的 ，因为它的体部（body）是不可满足的。

作为第二个例子，考虑以下规则：

假设我们采用 succ/2 关系的标准定义，那么这条规则是不可满足的，因为 succ/2 是反传递的（antitransitive）。

我们定义不可满足规则如下：

定义 8（不可满足规则）

设 B为背景知识（BK），r是一条体部为 b的规则，并且 B∪{←b}没有模型 （即不一致）。那么称规则 r是不可满足的 。

我们证明：一个不可满足规则的特化规则 也是不可满足的：

命题 1（特化的不可满足性）

3.5 蕴含可约规则

一个蕴含可约规则 是指其体部中存在某个文字被其他体部文字所蕴含。例如，考虑以下规则：

一个蕴含可约规则的某些特化形式也是蕴含可约的：

3.6 召回可约规则

一个召回可约规则 （recall reducible rule）包含一个由背景知识（BK）中可推导出的某个文字的实例数量 所决定的冗余文字 [9]。例如，考虑以下规则：

这条规则包含了一个冗余的文字（succ(A,B) 或 succ(A,C)），因为 succ/2 的第二个参数在函数上依赖于第一个参数。换句话说，如果 succ(A,B) 和 succ(A,C) 都为真，则必有 B = C。

作为第二个例子，考虑以下规则：

这条规则包含了一个冗余的文字（add(A,B,C) 或 add(A,B,D)），因为 add/3 的第三个参数在函数上依赖于前两个参数。换句话说，如果 add(A,B,C) 和 add(A,B,D) 都为真，则必有 C = D。

作为第三个例子，考虑以下规则：

下面我们展示召回可约性如何应用于一条规则：

3.7 单例可约规则

一个单例可约规则 是指其体部中包含一个始终为真 的文字。例如，考虑以下规则：

4 shrinker

前一节概述了我们可以从背景知识（BK）中推导出的四种类型的无意义规则。现在我们介绍 shrinker ，它是一个能够自动识别这些无意义规则并将其从假设空间中移除的系统。

算法1 展示了该方法的高层算法。该算法将 BK 作为 Datalog 程序的形式输入。为简化起见，在本节其余部分中，我们假设 BK 已被实例化为一组事实（facts）[39]。

shrinker 包含三个组件：

1. 第一个组件用于找出 不可满足规则 和 蕴含可约规则 （第3行）；

2. 第二个组件用于找出 召回可约规则 （第4行）；

3. 第三个组件用于找出 单例可约规则 （第5行）。

我们将依次描述这三个组件。然后，我们将说明 shrinker 如何利用这些无意义规则来缩减基于约束的 ILP 系统的假设空间。

4.1 寻找不可满足规则与蕴含可约规则

为了识别不可满足规则 和蕴含可约规则 ，shrinker 构建一些小型的规则模板 （rule templates），并利用背景知识（BK）来检查这些模板的实例是否是不可满足的或蕴含可约的。

一个模板 是一组二阶文字 （second-order literals）。
例如，集合 {P(A,B), Q(B,A)} 就是一个模板，其中 P 和 Q 是二阶变量，A 和 B 是一阶变量。
一个模板的实例 是对这些二阶变量进行具体化（grounding）后的结果，例如：{succ(A,B), succ(B,A)}。

shrinker 按批次处理这些模板。由于可能的模板数量非常庞大，shrinker 使用一个超时机制 （timeout）来在限定时间内尽可能多地发现不可满足或蕴含可约的规则。

算法2 展示了寻找不可满足规则和蕴含可约规则的具体流程。该算法的输入包括：

• 背景知识（BK）

• 规则中允许的最大文字数（max_size）

• 规则中允许的最大不同变量数（max_vars）

• 每次迭代中检查的模板数量（batch_size）

• 时间限制（timeout）

该算法输出一组无意义规则（pointless rules）。

算法2 的工作流程如下。函数 build_templates（第2行）构建所有可能的模板，这些模板最多包含 max_size 个文字和 max_vars 个变量，并按模板大小 （即文字数量）升序返回这些模板。

第5至8行展示了在 BK 上测试模板 以找出不可满足规则和蕴含可约规则的循环过程。

• 函数 select_templates （第6行）从尚未测试的模板中选择 batch_size 个模板进行测试。

• 函数 find_pointless_rules （第8行）是关键函数。它接收 BK 和模板作为输入，并返回发现的无意义规则。

我们使用自底向上 的方式并通过 ASP（Answer Set Programming，回答集编程） 来实现 find_pointless_rules 函数。具体来说，我们为每条规则寻找一个反例，以证明它不是 不可满足的或不是 蕴含可约的。

例如：

• 要证明体部包含 p(A,B), p(B,C), p(A,C) 的所有规则都是不可满足的，我们需要检查是否存在这样一个反例：在 BK 中，文字 p(A,B) 、 p(B,C) 和 p(A,C) 同时为真。

• 要证明体部包含 p(A), q(A) 的规则是蕴含可约的，我们需要检查是否存在这样一个反例： p(A) 为真但 q(A) 为假，或者反过来。

我们使用 ASP 来执行这些检查。首先，我们构建一个 ASP 编码 P，其中包含了所有的 BK。在下文中，我们使用等宽字体表示 ASP 代码。

对于 BK 中每个元数为 a的关系 p，我们在 P中添加如下规则：

4.1.3 推导不可满足规则与蕴含可约规则

我们使用 ASP 求解器 clingo [28] 来寻找 P的一个模型，从而识别出不可满足规则 和蕴含可约规则 。具体来说，我们利用 clingo 的多轮求解 （multi-shot solving）功能 [29]，在不重新接地（regrounding）BK 的前提下，逐步测试一批批模板。

shrinker 使用一个事实来表示一个无意义规则。例如，如果模板 {succ(A,B), succ(B,A)} 是不可满足的，那么 shrinker 将其表示为事实 unsat_ab_ba(succ,succ)。

算法2最终返回一组这样的事实，用以表示发现的无意义规则。

4.2 寻找回召可约规则

为了识别召回可约规则 ，我们采用了一种受 Struyf 和 Blockeel [66] 启发的方法，他们提出通过对规则中的文字进行排序以提高查询效率（详见第2节对该工作的介绍）。从高层次来看，对于任何一个背景关系，我们会确定其任意一组参数子集所能产生的最大答案替换 （ground instantiations，即实例化为具体常量的情况）数量。

我们使用标准的召回记号 [52] 来表示输入/接地参数（用 + 表示）和输出/非接地参数（用 - 表示）。为了说明这种记号，考虑以下事实：

对于 p(-,-) 的召回数 （recall）是 3，因为在 BK 中只有 3 个 p/2 的事实。
对于 p(+,-) 的召回数是 1，因为对于任意一个已知的第一个参数，最多只有一个接地的第二个参数。
对于 q(+,-,-) 的召回数也是 1，因为对于任意一个已知的第一个参数，最多只有一对由第二和第三个参数组成的实例。
而对于 q(-,+,+) 的召回数是 2，因为对于任意一对由第二和第三个参数组成的已知值，在第一个位置上最多存在两个非接地的参数。

算法3 展示了我们用于寻找召回可约规则 的算法。该算法以背景知识（BK）作为输入，并返回一组表示关系在特定参数子集下的召回值的事实。

算法工作流程如下：

• 它遍历 BK 中的每一个原子（第4行），并遍历该原子的所有参数子集（第9行），这对应于所有可能的召回组合。

• 例如，对于原子 succ(A,B) ，使用召回记号表示，其参数子集包括： succ(-,-) 、 succ(+,-) 和 succ(-,+） 。

• 我们忽略所有参数都为输入/已知的情况（如 succ(+,+) ），因为此时召回数恒为1。

• 对于每一个参数子集，我们创建一个由输入/已知参数构成的键（key），以及一个由输出/未知参数构成的值（value）。

• 然后我们将这些键值对添加到一个哈希表中，这个哈希表是针对每个谓词及其参数子集单独维护的。

• 最后，对于每一个关系及其参数子集，我们利用这个哈希表来计算其最大答案替换数量（即召回值）。

该算法返回一组形式为 recall(pred_input_output_count) 的事实，其中：

• pred

  是一个谓词符号，

• input

  是输入变量的序列，

• output

  是输出变量的序列，

• count

  是对应的召回值。

例如：

• 对于召回值为 1 的 p(+,-) ，对应的事实是 recall_p_a_b_1 ；

• 对于召回值为 1 的 p(-,+) ，对应的事实是 recall_p_b_a_1 ；

• 对于召回值为 2 的 q(-,+,+) ，对应的事实是 recall_q_bc_a_2 。

我们使用 ASP 来识别单例可约规则 。需要提醒的是，单例可约规则 是指包含一个始终为真 的文字的规则。例如，考虑以下规则：

假设 length/2 具有合理的语义，那么文字 length(A,B) 始终为真，因为每个列表都有一个长度。换句话说，由于变量 B在这条规则中只出现一次，并且对于所有列表来说变量 A都为真，因此文字 length(A,B) 是冗余的，因为它没有任何区分能力。

我们假设背景关系具有简单的类型系统 （关于类型的详细说明请参见附录6）。我们使用 ASP 来判断某个关系是部分的 （partial）还是全函数性的 （total），并利用这些信息来推导出单例可约规则。

我们描述一下我们的 ASP 编码 P：

• 我们将背景知识（BK）加入到 P 中。

• 对于 BK 中每个元数为 a 的关系 p ，我们在 P 中添加如下规则：

最后，我们通过判断参数是否不是部分的 （partial），来推导出它们是否是全函数性的 （total）。我们使用 ASP 求解器来寻找 P的一个模型，从而识别出具有全函数性的文字。

然后，算法2返回一组事实，表示背景文字中哪些参数是全函数性的。例如：

• 对于 length/2 关系，如果其第一个参数是全函数性的，那么 shrinker 返回事实 total_length_b ；

• 对于 add/3 关系，如果任意两个变量组合都是全函数性的，那么 shrinker 返回三个事实：
  total_add_ab 、 total_add_ac 和 total_add_bc 。

我们证明 shrinker 是正确的 ，即它能够解决假设空间缩减问题 （定义 7）：

4.5 Popper

shrinker 的输出（算法1）是一组无意义规则 ，具体来说是一组表示这些规则的事实。任何 ILP 系统都可以利用这些规则来剪枝假设空间，例如 Aleph 的规则剪枝机制 [64]。我们使用这些规则来缩减基于约束的 ILP 系统 Popper [13] 的假设空间，它可以学习最优且可递归的假设。

Popper 有许多变体，包括可以从噪声数据中学习的版本 [36]、可以学习高阶程序的版本 [56]，以及可以从概率数据中学习的版本 [33]。虽然 shrinker 可以缩减所有这些变体的假设空间，但我们在此描述最简单的版本，因为它足以说明我们是如何将其与 shrinker 结合使用的。

Popper 接收以下输入：

• 背景知识（BK）

• 训练样例

• 假设的最大尺寸

它将假设学习为确定性程序（definite programs）。Popper 会搜索一个最优假设，该假设能够蕴含所有正例、不蕴含任何负例，并且具有最小的规模。

Popper 使用一个“生成—测试—合并—约束”循环（generate, test, combine, constrain loop）来寻找最优假设。

Popper 从一个初始的 ASP 编码 P开始。这个编码可以被视为一个生成器 （generator），因为 P的每一个模型（即回答集）都代表一个假设。

编码 P使用 head（head_literal/3）和 body（body_literal/3）文字来表示假设。每个文字的第一个参数是规则的 ID，第二个参数是谓词符号，第三个参数是文字中的变量，其中 0 表示 A，1 表示 B，依此类推。

例如，考虑以下规则：

在生成阶段 （generate stage），Popper 使用 ASP 求解器为一个固定的假设大小寻找 P的模型（通过限制 head 和 body 中文字数量的基数约束来实现）。如果找不到模型，Popper 会增加假设大小并重新循环。如果存在模型，Popper 将其转换为一个假设 h。

在测试阶段 （test stage），Popper 使用 Prolog 来测试 h在训练样例和背景知识上的表现。如果 h能够蕴含至少一个正例且不蕴含任何负例，则 Popper 将其保存为一个有希望的假设。

在合并阶段 （combine stage），Popper 寻找一个能涵盖所有正例且具有最小规模的有希望假设的组合（即它们的并集）。Popper 将搜索建模为一个组合优化问题，具体来说是一个 ASP 优化问题 [11]。如果找到了这样的组合，Popper 将其作为目前为止的最佳假设，并更新最大假设大小。

在约束阶段 （constrain stage），Popper 利用 h构建约束，并将这些约束添加到 P中以剪枝模型，从而缩减假设空间。例如，如果 h没有 蕴含任何正例，那么 Popper 会添加一条约束来排除它的特化规则（specialisations），因为它们也一定不会蕴含任何正例。

例如，以下约束会剪枝所有比规则 last(A,B) ← tail(A,C), head(C,B) 更具体的规则（即其超集）：

4.6 shrinker + Popper

我们在 Popper 开始搜索假设之前（即开始其循环之前），使用 shrinker 来缩减其假设空间。为此，我们允许 Popper 利用 shrinker 找到的以下四类无意义规则来进行剪枝：

• 不可满足规则

• 蕴含可约规则

4.6.3 召回可约规则

我们使用 ASP 聚合约束 （aggregate constraints）来简洁地表达召回约束。例如，如果 shrinker 发现 succ/2 是函数性的（即对于任意一个已知的第一个参数，最多只有一个已知的第二个参数），它会将这一信息表示为事实 recall_succ_a_b_1。

基于这个事实，我们在 Popper 中添加如下约束：

这条约束会剪枝所有包含以下两个文字的模型（从而也剪枝了对应的假设）：

• body_literal(Rule, succ, (A, B))
• body_literal(Rule, succ, (A, C))

  ，其中 B != C

换句话说，这条约束会剪枝所有体部包含 succ(A,B) 和 succ(A,C) 且 B ≠ C 的规则。该约束适用于所有变量 A 和 B 的替换情况，以及所有规则 Rule。

例如，该约束会剪枝如下规则：

如果 shrinker 发现 succ/2 是单射的 （即对于任意一个已知的第二个参数，恰好存在一个已知的第一个参数），它会将这一信息表示为事实 recall_succ_b_a_1。

基于这个事实，我们在 Popper 中添加如下约束：

4.6.4 单例可约规则

为了剪枝单例可约规则 ，我们向 Popper 的生成编码（generate encoding）中添加如下 ASP 规则：

5 实验

我们声称，shrinker 能够在不剪枝最优假设的前提下缩减假设空间 。命题10支持了这一说法，并表明 shrinker 不会剪枝最优假设。然而，尚不清楚 shrinker 对学习时间会产生怎样的影响。因此，我们的实验旨在回答以下问题：

Q1：shrinker 是否能够减少学习时间？

为了回答 Q1，我们将使用与不使用 shrinker 的 Popper 进行学习时间的对比。

shrinker 从假设空间中移除了不可满足规则、蕴含可约规则、召回可约规则和单例可约规则。为了理解每种类型规则的影响，我们的实验还旨在回答以下问题：

Q2：移除每种类型的无意义规则是否都能减少学习时间？

为了回答 Q2，我们在使用 shrinker 时仅移除一种类型的无意义规则，并比较 Popper 的学习时间。

shrinker 接收一个超时参数 （timeout）。为了理解这个参数的影响，我们的实验旨在回答以下问题：

Q3：更多的预处理时间是否能进一步减少学习时间？

为了回答 Q3，我们比较使用 10 秒和 100 秒超时设置的 shrinker 所带来的影响。

5.1 实验设置 5.1.1 泛化误差（Generalisation Error）

每个数据集中的每个任务都包含训练样例和测试样例。我们使用训练样例来训练 ILP 系统以学习一个假设，并使用测试样例来评估这些假设在未见数据上的泛化能力。

给定一个假设 h、背景知识 B和一组样例 E，我们定义如下指标：

• 真阳性

  （True Positive）：被 h∪B 蕴含的正例；

• 真阴性

  （True Negative）：未被 h∪B 蕴含的负例；

我们将真阳性和真阴性的数量分别记作 tpE(h)和 tnE(h)。

我们使用平衡预测准确率 （balanced predictive accuracy）来衡量泛化误差。该指标通过对正类和负类的平均表现进行评估，从而适用于类别不平衡的数据：

平衡准确率

当假设在两个类别上的表现相同，或者数据是平衡的时，平衡准确率 等价于标准准确率。

5.1.2 设置

我们使用 shrinker 的设置为：max_size=3、max_vars=6、batch_size=1000 和 timeout=10 秒，除非我们在回答 Q3 时使用 timeout=100 秒。我们允许 Popper 学习最多包含 6 个变量和最多 10 个体部文字的规则。我们使用 AWS m6a.16xlarge 实例运行实验，每个学习任务使用一个 CPU 核心。

5.1.3 方法

我们对每项任务设置了 60 分钟的超时限制。Popper 是一种“随时可用”的方法（anytime approach），我们使用 Popper 在最多 60 分钟的学习时间内找到的最佳假设。我们测量平均平衡准确率和平均学习时间。我们将超过一秒的时间四舍五入到最接近的整秒。所有实验重复 10 次，并绘制并报告 95% 置信区间。我们使用配对 t 检验或 Wilcoxon 符号秩检验（取决于差异是否符合正态分布）来确定结果差异的统计显著性。换句话说，任何后续提到的显著性检验都指的是这两种测试之一。

5.1.4 数据集

我们使用了多个数据集：

• 1D-ARC

  ：该数据集 [68] 包含受抽象推理语料库 [6] 启发的视觉推理任务。

• Alzheimer

  ：这些真实世界任务 [44] 涉及学习描述阿尔茨海默病药物设计中四个理想性质的规则。

• IGGP

  ：在归纳通用博弈（Inductive General Game Playing, IGGP）[10] 中，任务是从通用博弈竞赛 [30] 的游戏轨迹中归纳出规则。

• IMDB

  ：我们使用了一个包含电影、演员和导演之间关系的真实世界数据集 [50]。

• List functions

  ：列表函数数据集 [61] 用于评估人类与机器的概念学习能力。每个任务的目标是识别将输入列表映射到输出列表的函数，其中列表元素是自然数。我们使用了一个关系编码 [34]。

• Trains

  ：目标是找到一个能够区分东向列车和西向列车的假设 [46]。

• Zendo

  ：Zendo 是一个多玩家游戏，玩家必须通过构建结构来发现一个秘密规则 [12]。

图1展示了使用 shrinker 后学习时间的改进情况。显著性检验确认（ < 0.05），在 419 个任务中的 170 个（40%）任务上，shrinker 减少了学习时间；而在 3 个（0%）任务上增加了学习时间。其余任务上没有显著差异。平均而言，学习时间减少了 17 ± 3 分钟；学习时间增加的平均值仅为 2 ± 0 秒。

这些只是最小幅度的改进，因为不使用 shrinker 的 Popper 经常在 60 分钟后超时。如果使用更长的超时时间，我们可能会看到更大的改进。

shrinker 可以大幅减少学习时间 。例如，在 list-function-043 任务中（目标是学习如何将一个数字序列前置到列表中），shrinker 将学习时间从 60 ± 0 分钟减少到 6 ± 0 分钟，减少了 90%。在 iggp-duikoshi-next_control 任务中，shrinker 将学习时间从 60 ± 0 分钟减少到 3 ± 0 秒，减少了 99%。

为了进一步探索 shrinker 在减少学习时间方面的潜力，我们进行了一组额外实验，将部分任务的最大学习时间延长至 24 小时。在这一更长的超时设置下，对于 iggp-duikoshi-next_control 任务，shrinker 将学习时间从 6.5 ± 1 小时减少到 1 ± 0 秒；对于 iggp-horseshoe-terminal 任务，shrinker 将学习时间从 10 ± 0 小时减少到 33 ± 3 秒。

为了说明 shrinker 为何有效，我们考虑了 iggp-scissors_paper_stone-next_score 任务。该任务的目标是从游戏观察中学习“石头剪刀布”游戏的规则。在这个任务中，shrinker 发现背景关系 succ/2 是非自反的（irreflexive）、反传递的 （antitransitive）、反三角的 （antitriangular）和非对称的 （asymmetric），这些性质被表示为不可满足规则。shrinker 还发现了蕴含可约规则，例如文字 succ(A,B), int_0(A), int_1(B) 是蕴含可约的。此外，shrinker 还发现 succ/2 关系是单射的和函数性的，这些都被表示为召回冗余规则。尽管 shrinker 仅用了 10 秒的预处理时间，但由此产生的约束却将 Popper 的学习时间从 382 ± 19 秒减少到了 52 ± 1 秒，提升了 86%。

在 3 个任务中学习时间增加的原因是处理 shrinker 所发现约束的开销，即 Clingo 处理这些约束所带来的计算开销。在这几个任务中，平均学习时间仅增加了 2 ± 0 秒。

显著性检验还确认（ < 0.05），在 419 个任务中，shrinker 在 11 个（2%）任务上提高了预测准确率，在 8 个（1%）任务上降低了准确率。其他任务上没有显著差异。提高准确率的主要原因是：在没有 shrinker 的情况下，Popper 有时无法在时间限制内找到一个好的假设。相比之下，由于 shrinker 缩减了假设空间，Popper 需要考虑的假设更少，因此有时能更快地找到更好的假设。此外，根据命题 10，shrinker 是最优安全的（optimally sound），它保证得到一个原假设空间的子集，但仍包含最优假设。根据 Blumer 界限 [4]，给定两个大小不同的假设空间，搜索较小的空间相比搜索较大的空间会带来更高的预测准确率，前提是好的假设同时存在于两者之中。

准确率下降的主要原因是 Popper 的实现问题。例如在 iggp-tiger_vs_dogs-goal 任务中，未使用 shrinker 的 Popper 学到了如下规则：

相比之下，使用 shrinker 的 Popper 无法学习到任何规则，因此其准确率默认为 50%。Popper 之所以无法学习到这条规则，是因为 shrinker 发现 pos_3(A) 的最大召回率为 1 ，也就是说，它只对一个特定值（即 3）有效。

因此，shrinker 判断该更准确的规则是召回可约的 ，并将其从假设空间中剪枝了。

相比之下，在这个理想规则中，谓词符号 pos_3 只在规则中出现一次，但变量 V4在文字 true_cell(V0,V4,V4,V3) 中出现了两次。Popper 无法学习这条规则 ，因为出于历史原因，它禁止一个变量在一个文字中重复出现。因此，未使用 shrinker 的 Popper 使用多个变量来学习一条逻辑上等价的规则。

总体而言，本节的结果表明 Q1 的答案是肯定的：shrinker 能够大幅减少学习时间 。

5.2.2 Q2：移除每种类型的无意义规则是否都能减少学习时间？

图2展示了仅移除不可满足规则 时的学习时间变化情况。这样做在 419 个任务中的 40 个（9%）任务上减少了学习时间，平均减少了 2 ± 0 分钟；在 5 个（1%）任务上增加了学习时间，平均增加了 20 ± 13 秒。

图3展示了仅移除蕴含可约规则 时的学习时间变化情况。这样做在 419 个任务中的 139 个（33%）任务上减少了学习时间，平均减少了 17 ± 3 分钟；在 5 个（1%）任务上增加了学习时间，平均增加了 8 ± 5 秒。

图4展示了仅移除召回可约规则 时的学习时间变化情况。这样做在 419 个任务中的 64 个（15%）任务上减少了学习时间，平均减少了 3 ± 1 分钟；在 4 个（0%）任务上增加了学习时间，平均增加了 1 ± 1 分钟。学习时间增加的原因是，由于前面提到的“变量在一个文字中重复出现”的问题，使用 shrinker 的 Popper 有时需要学习更长的规则，因此耗时更多。

图5展示了仅移除单例可约规则 时的学习时间变化情况。这样做在 419 个任务中的 57 个（11%）任务上减少了学习时间，平均减少了 2 ± 0 分钟；在 4 个（0%）任务上增加了学习时间，平均增加了 47 ± 29 秒。

再次强调，这些改进只是最小幅度的，因为未使用 shrinker 的 Popper 经常在 60 分钟后超时。

总体而言，本节的结果表明 Q2 的答案是肯定的：移除每种类型的无意义规则都可以减少学习时间 ，但其中移除蕴含可约规则带来的影响最大 。

5.2.3 Q3：更多的 shrinker 时间是否能进一步减少学习时间？

图6展示了在使用 10 秒和 100 秒超时设置 的 shrinker 时的学习时间变化情况。显著性检验确认（ < 0.05），使用 100 秒超时设置在 419 个任务中的 28 个（7%）任务上减少了学习时间，在 14 个（3%）任务上增加了学习时间。平均减少时间为 46 ± 17 秒，平均增加时间为 28 ± 15 秒。

总体来看，本节结果表明 Q3 的答案是肯定的：更多的 shrinker 预处理时间可以提升性能 ，但提升幅度并不成比例，并且通常 10 秒的预处理时间已经足够 。

6 结论与局限性

我们提出了 shrinker ，这是一种通过预处理背景知识 来自动缩减 ILP 系统假设空间的方法。shrinker 能够识别出四种类型的无意义规则 （pointless rules）：不可满足规则 （unsatisfiable）、蕴含可约规则 （implication reducible）、召回可约规则 （recall reducible）和单例可约规则 （singleton reducible）。

我们证明了：任何包含无意义规则的假设都不是最优的 ，因此可以从假设空间中安全地移除这些规则（见命题 2、4、6 和 9）。

我们在多个领域进行了实验，结果表明 shrinker 能持续有效地减少 ILP 系统的学习时间 。例如，在仅给予 10 秒预处理时间的情况下，shrinker 可以将学习时间从超过 10 小时减少到仅需 2 秒。

局限性 有限的背景知识（Finite BK）

我们的假设空间缩减思想具有足够的通用性，可以处理以确定性程序 （definite programs）形式表示的背景知识（BK）。然而，由于我们采用的是自底向上 （bottom-up）的实现方式并使用了 ASP，因此我们需要对 BK 进行有限的实例化（grounding）。

这一限制意味着我们的实现无法处理具有无限实例化的背景知识，例如涉及连续值推理的情况。未来的工作应解决这一局限性，例如通过使用自顶向下 （top-down）的方法来发现无意义规则。

封闭世界假设（Closed-world Assumption）

我们采用了封闭世界假设 （CWA），以便从给定的背景知识中识别出无意义规则。例如，如果没有将 odd(2)作为背景知识提供，我们就假设它不成立。

由于几乎所有的 ILP 系统都基于 CWA，因此这一限制仅在将我们的方法用于那些不采用 CWA 的系统 时才适用，例如一些近期的规则挖掘算法 [69]。

含噪声的背景知识（Noisy BK）

我们假设背景知识是无噪声的 ，即如果某个事实（fact）在 BK 中为真，则它确实是应该为真的。处理含噪声的 BK 是一个尚未解决的挑战 [9]，超出了本文的研究范围。

效率问题（Efficiency）

shrinker 使用暴力枚举的方式构建模板，以识别不可满足和蕴含可约规则。然而，我们认为某些规则在缩减假设空间方面具有更大的影响。因此，未来的工作应探索如何对模板进行排序，从而优先找到最具影响力的规则 ，提升预处理效率。

附录 B

我们对命题5 的证明需要一个召回可约性 （recall reducible）的替代定义（定义22），然后证明该替代定义与原始定义（定义11）是等价的。这个替代定义使我们能够将 θ-蕴含中隐含的替换转化为等式文字 （equality literals）。这些等式文字随后用于测试逻辑等价性。

上述构造需要比较一组文字中的参数元组（argument tuples）：

正如我们将在定理1 中展示的那样，召回可约性 （recall reducible，定义11）捕捉了我们对鸽巢原理 （pigeonhole principle）的一种改编形式。

考虑两条规则 r1和 r2。根据定义，如果且这两条规则在逻辑上是等价的，则 r1是召回可约的 。请注意，这通过 θ-蕴含中隐含的替换关系实现了定义22中引入的不等式。

如上所述，召回可约性 （recall reducible）与鸽巢化 （pigeonholed）是两个等价的概念。虽然“鸽巢化”通过引入不等式来形式化我们对鸽巢原理的改编，但“召回可约性”则利用了 θ-蕴含中的隐式替换。

定理1 的证明 提供了相应的构造方法，使得我们可以在两种概念之间进行转换。

https://arxiv.org/abs/2506.06739