使用归纳逻辑编程解决抽象和推理测试，ARC

Program Synthesis using Inductive Logic Programming for the Abstraction and Reasoning Corpus使用归纳逻辑编程的抽象和推理语料库的程序综合

https://arxiv.org/abs/2405.06399

背景：

千万级别的kaggle比赛，刚启动

定义智能，测量智能

摘要。

抽象和推理语料库（ARC）是一个通用的人工智能基准，目前还没有任何机器学习方法能够解决，包括大型语言模型（LLM）。它要求强大的泛化和推理能力，而这正是基于神经网络的系统的弱点。在这项工作中，我们提出了一个程序合成系统，该系统使用归纳逻辑编程（ILP），一个符号人工智能的分支，来解决ARC。我们手动定义了一个简单的特定领域语言（DSL），对应于与ARC相关的一小组以对象为中心的抽象。这是ILP使用的背景知识，用于创建为我们系统提供推理能力的逻辑程序。整个系统能够泛化到看不见的任务，因为ILP可以从少数例子中创建逻辑程序，在ARC的情况下：每项任务的输入-输出网格示例对。这些逻辑程序能够生成输出网格中存在的对象，这些对象的组合可以形成一个完整的程序，将输入网格转换为输出网格。我们随机选择一些不需要我们实现的少量对象原语的ARC任务，并表明仅给定这些，我们的系统可以解决需要每个任务的不同推理的任务。

1 引言

机器学习[5]，更具体地说，深度学习[14]，已经在几个领域取得了巨大的成功，并超过了人类的性能。然而，这些成功是在所谓的基于技能或狭隘的人工智能领域，因为每个DL模型都被准备好很好地解决一个特定的任务，但在解决不同类型的任务时却失败了[18][13]。众所周知，人工神经网络（ANN）和深度学习（DL）缺乏泛化能力。当它们应用于分布外数据时，它们的性能会下降[12][8][27]。最近，大型语言模型（LLM）显示出了惊人的能力，缩短了机器和人类智能之间的差距。但它们仍然显示出缺乏推理能力，需要大量的数据和计算。ARC挑战是由Francois Chollet设计的，目的是评估我们的人工智能系统是否在模仿人类形式的通用智能方面取得了进展。ARC可以被视为一个通用人工智能基准，一个程序合成基准，或一个心理测量智力测试[6]。它在2019年提出，但仍然是一个未解决的挑战，甚至最好的DL模型，如LLM也无法解决它[15][4][3]。GPT-4V，即GPT4增强的视觉任务[1]，也无法解决它[26][19][23]。

它的目标是人类和人工智能系统，旨在模仿人类形式的通用流体智能。它在格式上与经典的智商测试格式Raven's Progressive Matrices [22]有些相似。它需要Chollet所描述的开发人员意识到的泛化，这是一种比Out-of-Distribution泛化更强的泛化形式[6]。在ARC中，包含400个示例的评估集只包含在训练集中没有出现过的任务，也有400个示例，所有这些任务都需要非常不同的逻辑模式来解决，开发人员无法预见。还有一个包含200个示例的测试集，它是完全私有的。对于一个开始着手解决ARC的研究人员来说，也许最好将其理解为程序合成基准[6]。程序合成[9][10]是人工智能的一个子领域，目的是生成满足高级规范的程序，通常以程序的输入和输出示例对的形式提供，这正是ARC的格式。Chollet建议首先开发一个能够表达任何ARC任务的所有可能解决方案程序的特定领域语言（DSL）[6]。由于ARC任务的确切集合是有意不正式定义的，并且可以是只涉及核心知识先验的任何东西，因此这是一个挑战。对象性被认为是人类的核心知识先验之一，对于解决ARC[6]是必要的。以对象为中心的抽象使得对象意识成为可能，这对于人类解决ARC任务[2][11]似乎至关重要，并且是人类一般视觉理解的核心[24]。之前有使用以对象为中心的方法来处理ARC的工作，显示了它的有用性[16][2]。归纳逻辑编程（ILP）[20]也被认为是一种机器学习方法，但据我们所知，它从未应用于ARC挑战。它可以执行程序合成[7]，并且已知能够从少数训练示例中学习和泛化[17][21]。我们开发了一个使用ILP的程序合成系统，基于我们手动定义的以对象为中心的抽象。它通过搜索训练示例中存在的对象之间的逻辑关系组合来进行程序合成。这些逻辑关系是由使用ILP获得的逻辑程序定义的。我们的系统构建的完整程序由能够在输出网格中生成对象的逻辑程序组成。我们选择了五个只包含简单几何对象的随机示例，并将我们的系统应用到这些示例上。

2以对象为中心的抽象和表示

以对象为中心的抽象通过关注对象之间的关系而不是单个像素，大大减少了搜索空间。然而，就对象而言，可能存在多种方式来解释同一幅图像，因此，我们为同一幅图像保留了多个重叠的对象表示。

2.1 对象和对象之间的关系

我们手动定义了一个简单的DSL，它由对象：点、线和矩形以及对象之间的关系组成：线从点、平移、复制、点直线路径到。

2.2 多种表示

在我们以对象为中心的方法中，图像表示是由一组对象（可能重叠）和背景颜色定义的。这种表示可以通过首先用背景颜色填充网格，然后在上面绘制每个对象来从空网格构建目标图像。一个图像网格可以由多个对象表示定义。例如，一个空网格中的单个矩形也可以定义为形成相同矩形的几个线或点对象。由于我们从一开始就不清楚输入网格到输出网格转换背后的逻辑，所以我们不知道对象矩形是否是这个逻辑的关键（矩形之间的关系），或者相反，这个逻辑是否需要使用线表示，因为它可能涉及到依赖于线的关系，比如线从点的关系。

同样，相同的图像变换可以用不同的关系来解释。因此，我们使用对象和关系的多种混合表示，直到我们得到最终的程序或程序，可以将每个训练输入网格转换为输出网格，并为测试示例生成有效的输出网格，这将是我们的系统给出的输出解决方案。如果单独应用多个程序可以成功地产生相同的输入-输出训练图像转换，我们可以使用其中的任何一个，或者选择一个，例如：最短的程序，根据奥卡姆原则，它更有可能是正确的。

3ILP

归纳逻辑编程（ILP）是一种基于逻辑的机器学习形式。其目标是诱导出一个假设，一个逻辑程序或一组逻辑规则，在给定的训练示例和背景知识（BK）上进行泛化。我们的DSL由对象和关系组成，是给定的BK。与其他形式的ML一样，目标是在训练示例上诱导出一个假设。然而，大多数形式的ML使用向量/张量来表示数据，而ILP使用逻辑程序。而且，大多数形式的ML学习函数，而ILP学习关系。基本的ILP问题是有效地搜索一个大的假设空间。有一些ILP方法以自上而下或自下而上的方式进行搜索，还有一些结合了两者。在我们的系统中，我们使用自上而下的方法。使用ILP学习一个大型程序是非常具有挑战性的，因为搜索空间可能会变得非常大。有一些方法试图克服这个问题。

3.1 分治法

分治法[25]将示例划分为子集，并为每个子集搜索一个程序。我们使用分治法，但不是将其应用于示例，而是将其应用于示例中的对象。

4 使用ILP进行程序合成

ILP通常被视为一种概念学习方法，但它能够构建一个Prolog中的逻辑程序，这是图灵完备的，因此，它进行了程序合成。我们通过组合逻辑程序来扩展这一点，构建一个更大的程序，按顺序生成对象，以填充一个空网格，这在程序上对应于应用网格转换以达到解决方案。一个关系可以用来生成对象。除了PointStraightPathTo之外，我们所有的关系都能够根据关系中的第一个对象生成对象。为了生成一个明确的输出，关系应该由一个逻辑程序定义。这个逻辑程序是通过在我们的系统中使用ILP构建的。Prolog中的一个逻辑程序示例：

这个逻辑程序可以明确地生成输出中的两条线。变量Direction对此不是必需的，因为点在网格的边缘，所以每个点只能在一个方向上生长成线。

如果程序更短，它将从每个输入点生成多条线。例如，同一个逻辑程序的主体中没有最后一个术语：

因此，通过ILP获得逻辑程序，我们实际上正在构建一个生成对象的程序，这些对象可以填充空的测试输出网格，以达到解决方案。

5 系统概述 5.1 对象和关系检索

我们的系统首先检索在每个任务的示例的输入和输出网格中定义在我们DSL中的所有对象。正如我们之前报道的，我们保留多个对象表示，它们可能在占用图像中的相同像素方面重叠。然后我们在找到的对象之间搜索在我们的DSL中定义的关系。我们搜索仅在输入网格中出现的对象之间的关系：输入-输入关系，仅在输出网格中出现的对象之间的关系：输出-输出关系，以及在输入网格和输出网格中的对象之间的关系：输入-输出关系。之前找到的对象类型可以限制对关系的搜索，因为某些关系特定于某些类型的对象。

5.2 ILP调用

然后我们调用ILP创建逻辑程序来定义仅在上一步中找到的关系。这也减少了搜索空间。我们从输入-输出关系开始，因为我们需要用输入的信息构建输出对象。在我们在输出网格中生成了一些对象之后，我们可以开始使用输出-输出关系从其他输出对象生成输出对象。输入-输入关系可以出现在规则体中，但不会成为ILP定义的目标关系，因为它们不会在输出中生成任何对象。

每次ILP调用后，被视为输入信息的内容会增加。ILP调用返回的关系和对象会产生一个更新的网格，现在被视为存在于输入中，而这个更新的网格被作为初始输出网格，在后续的ILP调用中继续构建。

5.2.1 候选生成

要添加到规则体（Horn子句）中的候选术语是在检索步骤（5.1）中找到的对象和关系，加上Equal(X,…)、GreaterThan(X,…)、LowerThan(X,…)、Member(X,…)谓词。GreaterThan和LowerThan只与数字变量相关。我们还考虑aX+b，其中X是一个数字变量，a和b是我们预定义的某个区间内的常数。由于我们使用的是类型化的对象和关系，我们只需要生成那些与每个目标关系变量相关的候选者。例如，在构建一个定义关系的逻辑程序：LineFromPoint(point,line,len,orientation,direction)时，我们将生成与点或点的属性相关的候选者，以便实例化关系中的第一个变量Point。然后我们继续处理其他变量（除了line变量）：len、orientation和direction。Len是Int类型，所以它只与其他Int变量或常数相关。变量Line保持自由，因为它是我们希望关系生成的对象。

5.2.2 正例和反例

正如我们在第3节中看到的，FOIL需要正例和反例来诱导一个程序。ARC数据集只包含正例。因此，我们创建了一种表示负例的方法。

对于每个逻辑程序，我们的系统的正例是该程序生成的存在于训练数据中的对象，而反例是该程序生成的但不存在于训练数据中的对象。

例如，假设图3中的输出是正确的，但程序生成了图4中的所有线条，就像我们展示的较短的Prolog程序一样。对于这个程序，它涵盖的正例将是图3中的两条线，而它涵盖的负例将是图4中的所有线，除了垂直线。

在这里，与考虑整个网格相比，我们的以对象为中心的方法也降低了搜索的复杂性，以定义什么是正例或非正例。

5.2.3 训练示例之间的统一

为每个关系和所有任务训练示例进行ILP调用。我们的ILP系统被限制为生成可以在示例之间统一的程序，也就是说，它们是抽象的，并且可以泛化到两个或更多的训练示例。

为什么是两个而不是所有的训练示例？我们选择的五个示例之一帮助我们开发了我们的系统，它向我们展示了解决所有训练示例的程序可能过于复杂，而且没有必要解决测试示例。

在图5中，我们可以看到一项任务示例并推导出其解决方案的逻辑：从点开始画线，直到网格的对边，然后沿着与线垂直的方向重复平移这些线，直到网格的尽头。

为了统一这项任务中的四个训练示例，并按照我们为这个解决方案描述的逻辑，需要一个比只统一前两个示例的解决方案更复杂的程序。让我们看一系列逻辑程序，它们解决了前两个训练示例，并且也会成功解决测试示例：

测试示例在输出网格中只需要两次平移，所以一个具有更多平移的程序可以工作，因为它会填满整个网格，额外的平移只是不会应用。我们的系统认为这是一个有效的程序。但如果测试网格更长，需要的平移次数多于训练示例中的次数，我们的程序就无法工作，因为平移次数不会产生精确的解决方案，而是不完整的解决方案。对于这种类型的任务，我们需要使用更高阶的构造，如：Do Until、Repeat While或带有条件的递归，以多次应用相同的关系，或者直到某个条件失败或被触发。这是未来工作的范围。

5.3 规则、网格状态和搜索

第一次ILP调用在空网格状态下进行。每次ILP调用都会产生一个定义关系的规则，该关系生成对象，并为每个示例和测试示例返回添加了这些对象的新输出网格状态。后续每次ILP调用都在更新后的输出网格状态下进行。搜索将寻找正确的逻辑程序序列，可以从空网格开始构建输出网格。当我们有一个程序至少构建了一个完整的训练示例输出网格，该程序在两个或更多示例之间是统一的，并且也可以在测试输出网格中产生一个有效的解决方案（不一定是正确的解决方案），我们认为它是最终程序。一个有效的程序是构建一致理论的程序。例如，一个生成不同颜色的相交线的程序是不一致的，因为这两条线不能同时存在于输出网格中（一条线与另一条线重叠）。我们认为这样的程序是无效的，并在搜索完整程序时丢弃它们。

5.4 演绎搜索

在图7中，我们可以看到一项任务示例，为了解决它，反向操作会更简单，即从输出信息生成输入网格，但由于我们不能通过这种方式解决测试输出网格，我们使用一种演绎搜索来克服这个问题。

当我们应用由ILP构建的逻辑程序时，根据对象生成的顺序，我们可能会有不同的结果。当一个对象在输出网格中生成时，之后生成的任何其他对象都不能与之相交。因此，同一逻辑程序的网格空间覆盖率可能会因程序应用的顺序而有所不同。这是我们系统的程序方面。当依次应用多个逻辑程序时，这个问题会变得更加严重。因此，在应用完整程序生成测试输出网格时，我们使用演绎搜索以覆盖最大面积的方式应用整个程序。由于最终程序是可以覆盖训练输出网格整个表面的程序，我们应该有一个可以覆盖所有测试输出网格的解决方案。

6 实验我们的系统已成功应用于五项任务，如图1中的三项任务：08ed6ac7、a48eeaf7、7e0986d6，图5中的任务：0a938d79和图7中的任务：150deff5。在附录中，我们展示了每个任务的Prolog输出解决方案。

7 结论

我们展示了我们的系统能够解决选定的5个样本任务。当我们完成软件实现时，我们将把我们的系统应用于完整的训练和评估数据集。ILP是我们系统的核心，我们展示了只有通过提供一个小DSL或背景知识，ILP才能构建和表示ARC任务解决方案背后的逻辑。ILP为我们的系统提供了抽象学习和泛化能力，这是ARC挑战的核心。由于其他ARC任务可能依赖于许多不同的DSL原语，我们计划开发一种自动化DSL创建的方法。如前所述，我们可能需要高阶构造来解决其他任务，并计划将其纳入我们的系统。