抽象和推理语料库的图形、约束和搜索

Graphs, Constraints, and Search for the Abstraction and Reasoning Corpus

抽象和推理语料库的图形、约束和搜索 github.com/khalil-research/ARGA-AAAI23

https://ar5iv.labs.arxiv.org/html/2210.09880?_immersive_translate_auto_translate=1

摘要 抽象和推理语料库（ARC）旨在评估通用人工智能算法的性能。ARC关注广泛的泛化和少样本学习，这使得使用纯机器学习很难解决。一种更有前景的方法是在适当设计的领域特定语言（DSL）中进行程序合成。然而，这些方法的成功也有限。我们提出了基于图抽象的抽象推理（ARGA），这是一个新的以对象为中心的框架，首先使用图表示图像，然后在基于抽象图空间的DSL中搜索正确的程序。通过使用约束获取、状态哈希和禁忌搜索，降低了这种组合搜索的复杂性。一系列广泛的实验证明了ARGA在高效解决ARC的一些复杂以对象为中心的任务方面的潜力，产生了正确且易于理解的程序。

为了更好地衡量机器学习和人类学习之间的差距，Chollet在2019年创建了抽象和推理语料库（ARC）。该数据集包含1000个基于图像的推理任务，每个任务要求在给定输入的情况下输出一个图像。为了“学习”产生所述输出的过程，每个任务都有2-5个输入-输出图像对作为训练实例；这些训练输入与实际测试输入不同，但可以由相同的（未知）过程解决。图1中显示了一些示例。Kaggle举办了一场有超过900支队伍参加的竞赛来解决ARC（Kaggle 2020）。尽管付出了巨大的努力，但这些解决方案在隐藏测试集上的准确率最高仅为20%。事实上，尽管对人类来说很简单，但第一名的解决方案无法解决图1中显示的三个示例中的两个。

识别物体，对它们执行的动作以及它们之间的关系构成了人类认知核心系统的很大一部分（Spelke和Kinzler 2007）。ARC在其任务中体现了这一概念。事实上，Acquaviva 等人（2021 年）发现，当人类试图通过语言解决 ARC 任务时，他们使用的短语中有一半与对象检测有关。因此，以对象为中心的方法来求解ARC是非常有前途的。令人惊讶的是，这一关键见解尚未得到利用。

ARGA:用图形抽象进行抽象推理

为了实现这一目标，我们提出了带有图抽象的抽象推理（ARGA），这是一个以对象为中心的框架，用于解决ARC任务。我们的设计理念是通过仔细集成以下内容来构建一个计算高效、可扩展、对象感知的 ARC 求解器：

• – 表示：启用对象感知需要从将输入视为像素转向具有空间或其他关系的对象图形。我们设计了各种这样的图形抽象，以迎合ARC的多样性及其对对象的不同定义。
• – 结构：基于一阶逻辑，我们基于图形的 DSL 可以为 ARC 的任务定义复杂但可解释的解决方案程序。这与纯神经网络类型的方法形成鲜明对比，后者试图以通常的黑盒方式将输入映射到输出。
• – – 搜索：有了表示和 DSL，我们选择了完整的树搜索算法。给定一个任务，搜索会在 DSL 中查找一个程序，该程序为每个任务的训练示例生成正确的输出。 每当我们的 DSL 中存在一个正确的任务程序时，只要有足够的时间，搜索就可以找到它。
• – 约束：利用（已解决的）训练示例不仅告诉我们正确的程序做什么，而且告诉我们它不应该做什么（例如，在图 1（左）中，对象不应该移动），我们使用约束获取来简化我们的组合搜索空间。约束在同一个图形 DSL 中表示，并且可以通过任意算法获取。
• 图 2 说明了 ARGA 的 DSL、Search 和 Constraints 组件;图 4 说明了表示。通过ARGA，我们希望为对ARC和类似的小样本推理情况感兴趣的AI研究人员提供第一个这样的系统，他们可以在此基础上构建和探索基于图形和搜索的推理功能。

我们的实现可在 GitHub 上找到 1 。

由于面向对象的抽象和推理是最先进的ARC求解器的主要故障模式，因此我们定义了标准，以选择面向对象的ARC任务的子集作为测试平台，以评估我们的方法与其他顶级求解器的比较。 所讨论的 160 个任务涵盖了广泛的具有挑战性的问题，可归类为对象重新着色、对象移动和对象增强。我们通过以下方式展示了ARGA的设计和性能如何有利：

• – 可扩展性和模块化：ARGA 的每个组件都可以几乎独立地扩展，以针对额外的 ARC 任务或优化性能：可以添加新的图形抽象，可以将额外的对象过滤器和转换附加到 DSL，可以测试新的搜索策略，更快的约束获取算法可以无缝地取代我们的算法。
• – – 计算效率：我们的 DSL 包含许多基于对象的选择过滤器以及转换（例如，重新着色、移动等）。由于这些程序可以组合在一起以形成 ARC 任务的候选程序，因此生成的搜索空间在组合上很大。 尽管如此，通过对 160 个基于对象的 ARC 任务的实验，我们表明，当 ARGA 找到解决方案时，它通过探索极少量的可能解决方案来实现，这实际上比 Kaggle 竞赛的获胜者少了三个数量级。
• – 有效性：我们当前的 DSL 仅包括 4 个基本滤波器和 11 个转换。然而，我们解决了 160 个任务中的 57 个，仅略微落后于 Kaggle 获胜者的 64 个任务（共 160 个）。后者包括通过检查更多 ARC 任务获得的更大的转换体。

‍系统概述 我们提出了一个两阶段框架，它采用以对象为中心的方法来求解ARC任务。首先，受 Go 工作启发的图抽象阶段（Graepel et al. 2001），其中 2D 网格图像被映射到（多个）无向图表示，这些图表示在更高的抽象级别上捕获有关图像中对象的信息。其次，解综合阶段，其中使用约束引导搜索来制定要应用于抽象图的一系列操作，这些操作将导致解决方案。可能的操作空间由特定于 ARGA 的关系域特定语言 （DSL） 定义。

由于 DSL 定义了对抽象图的操作，我们将首先描述图抽象阶段并正式定义抽象图的结构。然后，将详细定义 DSL。最后，将讨论溶液合成阶段。

图抽象

图抽象允许我们在宏观层面上搜索解决方案。换句话说，我们一次修改像素组，而不是单独修改每个单独的像素。因此，这种方法的搜索空间比非抽象的原始图像对应物更小。

现在，我们正式引入一些术语，这些术语有助于定义我们的抽象图（如图 3 所示），下一节的 DSL 将利用这些术语。我们使用的语言建立在一阶逻辑之上，它提供了一种灵活且富有表现力的语言来描述类型化对象和关系。DSL 中的对象类型如表 1 所示，可以用作一元谓词，例如，

𝑁𝑜𝑑𝑒(𝑛) is true 𝑛∈𝑁𝑜𝑑𝑒 iff 。对象之间的一些示例关系如表 2 所示，完整的关系集可在附录表 6 中找到。

设 𝑖 为 ARC 任务的任何输入或输出 2D 网格图像。 𝑖 可以完全由其像素集指定 𝑝 。假设 𝑔 是一个具有抽象节点集的抽象图 𝑛 。表 2 显示了这些类型之间的关系。每个节点 𝑛 表示根据抽象规则在原始图像 𝑖 中检测到的一个对象（例如，一个图形抽象是“相同颜色的非黑色相邻像素形成一个节点”），节点之间的关系表示这些对象之间的关系。

因此，图抽象过程执行映射， 𝐺 为图像 𝐼 生成一些抽象图。我们注意到，可以通过多种方式定义此映射。可以使用不同的图形抽象来识别图像中的对象，使用对象的不同定义。

由于来自不同图抽象定义的抽象图共享相同的底层结构，因此我们能够在不修改 DSL 的情况下显着扩展解空间。

在图 1（中）所示的示例中可以看出对一个对象具有多个定义的有用性。在第一次检查时，人们可能会认为对象被定义为具有相同颜色的连接像素。

然而，经过进一步检查，我们意识到不同列中连接的红色像素实际上是不同的对象，因为它们在输出图像中有不同的修改。

因此，定义多个抽象过程可以提高 ARGA 从输入图像中正确捕获对象信息的能力。下面将进一步讨论示例中提到的两种不同的抽象：

非背景单色连接像素：在此抽象中，对象（或节点）被定义为一组共享相同颜色的连接像素。抽象算法的伪代码如附录算法 1 所示，图 4 中显示了此抽象的图示。

非背景单色垂直连接像素：在此图形抽象中，对象被定义为一组不是背景颜色的垂直连接像素。图 4 中是这种抽象的图示。

重叠对象

请注意，我们的表示允许在修改对象时将像素与图形中的多个节点相关联。

这可以通过观察对象在网格上可能相互重叠来直观地理解，因为人们应用一系列变换来解决给定的任务。

我们的图形抽象确保了尽管某些对象可能被部分遮挡，但它们仍然被跟踪并被视为一个完整的对象。这允许系统事先了解对象持久性知识。

ARC 的图形 DSL

现在，我们介绍一个基于上一节中定义的对象和关系构建的 ARGA 提升关系 DSL。

DSL 用于正式描述用于匹配节点模式、确定图转换参数和对抽象图执行转换的过滤器语言，如下所述。图 3 显示了使用 DSL 表示的示例解决方案。

过滤 器

筛选器用于从图形中选择节点。基本语法是一阶逻辑的一个子集：

转换

转换用于修改筛选器选择的节点。它们通过修改对象关系的值来做到这一点。表 3 描述了一些转换;完整列表见附录表8。

动态参数转换

在图 1（左）所示的示例中，我们可以“静态”标识节点应更新到的颜色。但是，这不适用于图 5，因为转换后的灰色对象的目标颜色是其相邻的 size-1 对象的目标颜色。因此，我们定义了参数绑定函数，它允许我们动态生成用于转换的参数。 下面提供了参数绑定的语法及其解释和示例：

Full Operation

随着过滤器、转换和参数绑定的正式定义，我们现在可以将它们组合起来，对抽象图进行完全修改。给定一个过滤器、一个转换和变换所采用的每个参数的 𝑘 参数绑定 𝑃𝑎𝑟𝑎𝑚𝑖(𝑥,𝑣) （ 𝑖∈{1…𝑘} ）（如果 𝑘=0 IF 可能没有）：

Solution Synthesis

DSL明确定义了解决方案空间并成功提取了输入图像，将进行搜索以合成解决方案。

许多 ARC 任务具有非常复杂的逻辑，具有多个可检测对象，这意味着即使使用我们的高级图形抽象，搜索空间也太大，无法详尽探索。

因此，开发算法的关键目标是减少搜索空间。为了实现这一点，我们引入了一个约束获取模块，该模块获取约束，这些约束用于修剪搜索树中没有希望的分支，即不可能导致训练任务正确解决方案的转换序列。

其他技巧，如散列和禁忌列表，也用于加快搜索速度。搜索树的图示如图 2 所示。

检索策略

启发式函数

约束引导搜索

我们用一个例子来说明这个概念。图 1（左）中的所有对象的位置都不应改变。因此，我们可以定义约束 positionUnchanged，当节点和该节点的更新版本共享同一组像素时，该约束值得到满足，从而确保节点在图像上的位置在变换过程中保持不变。

因此，所有修改节点像素的转换都可以通过搜索树中的此约束进行修剪。可视化效果如图 2 所示。

可以使用我们之前介绍的相同语言来定义约束。例如，positionUnchanged 定义为：

约束获取

散列法

不同的变换或变换序列极有可能产生相同的抽象图。为了避免重复的搜索工作，我们对搜索树中的每个节点进行哈希处理，以便只探索一次等效节点。 因此，搜索树具有有向无环图的结构。图 2 显示了一个示例。

禁忌清单

在我们当前的实现中，来自不同抽象的抽象图共享同一个搜索树。因此，贪婪的最佳优先搜索可能会陷入没有希望的本地解决方案中。

为了避免这种情况，我们实现了一个简单的禁忌列表，它跟踪每个抽象的性能。如果一个抽象产生的结果越来越差，我们暂时把它放在禁忌列表上，这样就不会探索具有这种抽象的节点。

实验

Chollet （ 2019） 指出，ARC 旨在评估“开发人员感知泛化”，所有 ARC 任务都是唯一的，除了核心先验之外，不假设任何知识。因此，在ARC任务的子集上实现和评估ARGA应该为我们的方法的有效性提供有用的见解，而无需广泛开发转换函数，这不是我们贡献的重点。

我们专注于 ARC 中 160 个以对象为中心的任务的子集，并将它们分为三组：（1） 对象重新着色任务，它改变输入图像中某些对象的颜色;（2）物体移动任务，改变输入图像中某些物体的位置;（3） 对象增强任务，从输入图像中扩展或添加某些图案到对象。图 1 显示了三个子类别中每个子类别的示例任务。

为了进行比较，我们在同一任务子集上评估了 Kaggle 挑战赛的第一名模型（顶夸克 2020）。该模型的执行没有比赛强制执行的时间限制，并且该模型产生的得分最高的候选者用于生成最终预测。

结果

ARGA 和 Kaggle 竞赛第一名解决方案的性能如表 4 所示。除了物体移动任务外，我们的模型在准确性方面的表现略差于 Kaggle 获胜者。这可能是由于我们的 DSL 所跨越的解决方案空间不够富有表现力，因为它仅使用 160 个任务中的一个子集进行开发。另一方面，Kaggle 解决方案中使用的 DSL 是通过首先手动解决 ARC 中的 200 个任务（top quarks 2020）开发的。

尽管精度较低，但 ARGA 在搜索方面实现了更好的效率，因为我们能够以更少的 3 个数量级探索节点来获得解决方案。这表明，通过更具表现力的DSL和更高效的实现，ARGA应该能够以更少的搜索工作解决更多的任务（ARGA目前是用Python实现的，而Kaggle解决方案是用C++实现的）。

此外，对于 ARGA，求解所有训练实例的任务数（# 训练正确）与求解单个测试实例的任务数（# 测试正确）之间的差距要小得多。这表明 ARGA 更擅长找到正确泛化的解决方案，而 Kaggle 解决方案经常过度拟合训练实例。

消融研究

表5显示了ARGA不同变体的性能;所有 160 个任务都报告了准确性。我们看到，使用约束获取在减少搜索空间方面非常有效，导致在到达解决方案之前探索的平均节点减少了 38%。此外，结果表明，禁忌列表、哈希以及正确的搜索策略对于最佳性能都很重要。我们注意到，如附录表 11 所示，ARGA 变体解决的任务集没有显着差异。

相关工作

当前 ARC 求解器

解决ARC已经有很多尝试。大多数已经取得一些成功的人都在程序合成范式中利用了 DSL（Kaggle 2020）。已经表明，人类能够编写一组具有足够表现力的自然语言指令来解决大多数 ARC 任务，这表明 ARC 可以通过足够强大的 DSL 和高效的程序合成算法来解决（Johnson 等人，2021 年）。事实上，这是 Chollet （ 2019） 在介绍数据集时建议的方法：“假设的 ARC 求解器可以采用程序合成引擎的形式”，该引擎“生成将输入网格转换为输出网格的候选者”。

使用这种方法的解决方案包括 Kaggle 挑战赛的获胜者，其中 DSL 是通过手动求解 ARC 任务创建的，程序合成算法是利用有向无环图 （DAG） 的搜索。DAG 中的每个节点都是一个图像，节点之间的边是变换（Top Quarks 2020）。第二名的解决方案在遵循类似方法之前引入了预处理阶段（de Miquel Bleier 2020）。许多其他 Kaggle 表现最好的人也采用这种方法（Golubev 2020;柳基斯 2020;彭罗斯 2020 年）。Fischer等人（2020）提出了一种语法进化算法，用于在其DSL中生成解决方案。Alford et al. （ 2021） 利用一个名为 DreamCoder 的现有程序合成系统 （Ellis et al. 2020） 通过压缩过程从简单的 DSL 创建抽象。然后，该程序使用神经引导的合成为新任务编写解决方案。

解决 ARC 的其他方法包括神经抽象推理器，这是一种深度学习方法，可以成功解决 ARC 问题的一个子集（Kolev、Georgiev 和 Penkov 2020）。Assouel et al. （ 2022） 开发了一种组合想象方法，该方法可以生成看不见的任务以更好地概括。Ferré （ 2021） 开发了一种基于描述性网格的方法。然而，这些方法并没有取得最先进的结果。

约束获取

（CA） 是一个旨在从示例生成约束规划 （CP） 模型的领域（De Raedt、Passerini 和 Teso 2018）。最先进的 CA 算法可能是活跃的，需要用户的交互（Bessiere 等人，2013 年;Arcangioli、Bessiere 和 Lazaar 2016），或被动的，只需要初始示例（Bessiere 等人，2005 年）。

用于 ARGA 的被动 CA 算法受到 ModelSeeker （Beldiceanu and Simonis 2012） 的影响，该算法从全局约束目录 （Beldiceanu， Carlsson， and Rampon 2005） 以及 Lallouet et al. （ 2010） 开发的系统中找到相关约束，该系统使用归纳逻辑编程 （ILP） 并从逻辑解释中制定约束。

结论

我们提出了使用图抽象的抽象推理（ARGA），这是一个以对象为中心的框架，它通过首先生成图抽象，然后执行约束引导搜索来解决ARC任务。我们在ARC数据集的以对象为中心的子集上评估了我们的框架，并获得了有希望的结果。值得注意的是，在搜索空间内找到解决方案的效率表明，随着DSL的进一步发展，我们的方法有可能解决比最先进的方法复杂得多的问题。