以对象为中心和MDL原则处理ARC挑战 2023

Tackling the Abstraction and Reasoning Corpus (ARC) with Object-centric Models and the MDL Principle

用以对象为中心的模型和MDL原则处理抽象和推理语料库(ARC)

https://arxiv.org/abs/2311.00545

https://github.com/sebferre/ARC-MDL

每个任务的学习超时仅为30秒。考虑到问题的难度，我们认为这样的结果相当鼓舞人心

some opensource ARC project code

https://github.com/you68681/GPAR Generalized Planning for the Abstraction and Reasoning Corpus https://arxiv.org/abs/2401.07426 update https://github.com/khalil-research/ARGA-AAAI23 https://ar5iv.labs.arxiv.org/html/2210.09880

https://github.com/sebferre/ARC-MDL https://arxiv.org/abs/2311.00545 Tackling the Abstraction and Reasoning Corpus (ARC) with Object-centric Models and the MDL Principle

https://arxiv.org/pdf/2402.03507 Neural networks for abstraction and reasoning:Towards broad generalization in machines https://github.com/mxbi/dreamcoder-arc 未上传, base: 相关两个早期代码：https://github.com/ellisk42/ec https://github.com/neurosymbolicgroup/neurosymbolic-modules

related code: Probabilistic Abduction for Visual Abstract Reasoning via Learning Rules in Vector-symbolic Architectures https://arxiv.org/abs/2401.16024 https://github.com/IBM?q=vector-symbolic&type=all&language=&sort=

摘要‍

抽象和推理语料库（ARC）是一个具有挑战性的基准，旨在推动人工智能研究走向人类水平的智能。它是一个独特的任务集合，关于生成彩色网格，仅由几个例子指定。与现有工作的基于转换的程序相比，我们引入了以对象为中心的模型，这些模型与人类产生的自然程序一致。我们的模型不仅可以进行预测，还可以为输入/输出对提供联合描述。最小描述长度（MDL）原则用于有效地搜索大型模型空间。解决了各种各样的任务，学习到的模型与自然程序相似。我们通过将其应用于不同的领域来证明我们方法的通用性。

1 引言

在过去十年中，人工智能（AI）在特定任务上取得了令人印象深刻的进展，有时甚至达到了超人的性能：例如，图像识别[15]、棋盘游戏[21]、自然语言处理[6]。然而，人工智能仍然缺乏人类智能的通用性和灵活性，无法在很少的训练下适应新任务。为了推动人工智能研究超越狭隘的泛化[11]，F. Chollet[4,5]引入了一种衡量智能的标准，这种标准重视技能获取效率而不是技能表现，即代理需要多少先前的知识和经验才能达到一系列任务（例如，棋盘游戏）的合理良好水平，这比其在任何特定任务（例如，国际象棋）上的绝对表现更重要。Chollet还以心理测量测试的形式引入了抽象和推理语料库（ARC）基准，以衡量和比较人类和机器的智能。ARC是一个任务集合，包括学习如何将一个输入的彩色网格转换为一个输出的彩色网格，仅给出几个例子。这是一个非常具有挑战性的基准。虽然人类可以解决超过80%的任务[14]，但Kaggle比赛1的获胜者只能解决20%的任务（使用大量硬编码的原始数据和暴力搜索），而最近的ARCathon'22比赛2的获胜者只能解决6%的任务。

现有的已发布方法[10,3,23,2]以及Kaggle的获胜者都将ARC挑战视为一个程序合成问题，其中一个程序是由原始转换组成的，学习是通过搜索大型程序空间来完成的。相比之下，心理学研究表明，人类为解决ARC任务而产生的自然程序是以对象为中心的，并且比程序性的更具声明性[14,1]。当被要求口头说明如何解决一个任务时，参与者通常会首先描述在输入网格中期望什么，然后根据在输入网格中找到的元素来生成输出网格。

我们相对于现有工作做出了两项贡献：

1. 以对象为中心的模型，使得可以解析和生成基于对象模式和对这些对象进行计算的网格；2. 基于最小描述长度（MDL）原则[20]的高效搜索以对象为中心的模型。

一个ARC任务的模型结合了两种网格模型，一种是输入网格，另一种是输出网格。这与自然程序的结构非常匹配。与只能从输入网格预测输出网格的基于转换的程序相比，我们的模型还可以为一对网格提供联合描述。它们也可以创建新的网格对，尽管这并没有在本文中评估。原则上，它们也可以适用于基于单个网格或网格序列的任务。所有这些都是可能的，因为网格模型既可以用于解析网格，也可以用于生成网格。

MDL原则来自信息论，它说“最能描述数据的模型是压缩最多的模型”[20,12]。例如，它已经被应用于模式挖掘[22,9]。MDL原则在两个层面上使用：（a）根据网格模型选择最佳网格解析，（b）通过增量构建越来越精确的模型来高效地搜索大型模型空间。MDL在（a）级是必不可少的，因为将网格分割成对象是任务依赖的，并且必须与输出对象作为输入对象的函数的定义一起学习。这两项贡献相互支持，因为现有的搜索策略无法处理我们的网格模型的大量基本组件，而且基于转换的程序不适合基于MDL的搜索所需的增量评估。

我们报告了基于网格模型的有前景的结果，这些模型仍然远未涵盖ARC假设的所有知识先验。在60秒的时间预算内，为96/400个不同的训练任务找到了正确的模型。其中许多与人类产生的自然程序相似。此外，我们通过将其应用于自动填充电子表格列[13]来证明我们方法的通用性，其中输入和输出是字符串行而不是网格。

本文的组织结构如下。第2节介绍了ARC基准和一个运行示例任务。第3节讨论了相关工作。第4节定义了我们的以对象为中心的模型，第5节解释了如何使用MDL原则学习它们。第6节报告了实验结果，并与现有方法进行了比较。

2 抽象和推理语料库（ARC）

ARC是一个任务集合3，其中每个任务由训练示例（平均3.3个）和测试示例（通常1个）组成。每个示例由一个输入网格和一个输出网格组成。每个网格都是一个二维数组（大小可达30x30），填充着代表颜色的整数（10种不同的颜色）。对于给定的任务，网格的大小可以从一个示例到另一个示例变化，也可以在输入和输出之间变化。每个任务都是一个机器学习问题，其目标是学习一个模型，该模型可以从输入网格生成输出网格，因此只需从几个训练示例中学习。预测只有在所有测试示例的预测输出网格严格等于预期网格时才成功，没有部分成功。然而，每个测试示例允许三次尝试，以补偿训练示例中的潜在歧义。图1显示了两个ARC任务（缺少预期的测试输出网格）。第一个在本文中用作运行示例。我们现在更正式地定义网格、示例和任务。

ARC任务平均有3.3个训练示例，1或2个测试示例（通常为1个）。如图1所示，一个任务的不同输入网格不需要具有相同的大小，也不需要使用相同的颜色。测试网格也是如此。

ARC总共包含1000个任务：400个“训练任务”4，400个评估任务，以及200个用于独立评估的秘密任务。图1显示了400个训练任务中的两个。开发人员应该只关注训练任务，而不是评估任务。后者应该仅用于评估开发系统的广泛泛化能力。

3 相关工作

ARC基准是最近才出现的，到目前为止还没有发布很多方法。我们所知道的所有方法都定义了一个DSL（领域特定语言）的程序，将输入网格转换为输出网格，并搜索一个在训练示例上正确的程序[10,3,23,2]。差异主要在于原始转换（先验知识）和搜索策略。定义越来越多像Kaggle获胜者那样的原始数据是很有诱惑力的，因此有更多的先验知识，但根据Chollet的衡量标准，这意味着一个不太智能的系统。为了在庞大的程序空间中引导搜索，这些方法要么使用语法进化[10]，神经网络[3]，使用哈希和Tabu列表修剪搜索树[23]，或者在已解决任务上训练的随机搜索[2]。一个困难是输出网格通常只用于评分候选程序，因此搜索有点盲目。Alford[3]通过神经引导的双向搜索改进了这一点，该搜索从输入和输出两个方向扩展程序。Xu[23]将正在进行的生成网格与预期网格进行比较，但这限制了该方法只能应用于输出网格与输入网格具有相同大小和相同对象的任务。基于DSL的方法存在一个扩展问题，因为搜索空间随着原始数据的数量呈指数增长。Ainooson[2]通过定义体现专门搜索策略的高级原始数据来缓解这一困难。我们在评估部分比较和讨论了它们的性能。

Johnson等人[14]报告了一项关于ARC的心理学研究。它揭示了人类使用以对象为中心的心理表征来解决ARC任务。这与基于网格转换的现有解决方案形成了对比。有趣的是，人类发现最困难的任务是基于逻辑（例如，网格之间的异或）和对称性（例如，旋转）的任务，正是那些最容易被基于DSL的方法解决的任务。该研究提出了两个挑战：（1）需要大量的原始数据，特别是关于几何学的；（2）识别对象的困难，由于重叠或遮挡，对象可能只能部分可见。一个宝贵的资源是LARC，即语言注释的ARC[1]，通过众包收集。它为大多数训练任务提供了一个或几个自然程序，证实了人类表征的以对象为中心和声明性质。自然程序是由参与者产生的简短文本描述，可以被另一个参与者用来生成测试输出网格（无需访问训练示例）。

除了ARC基准之外，在程序合成领域也做了大量工作，这也被称为程序归纳或示例编程（PbE）[17]。早期的方法是归纳逻辑编程（ILP）[19]，其中目标谓词是从符号表示中学习的。PbE在Microsoft Excel 2013的FlashFill功能中使用，从几个示例中学习复杂的字符串处理公式[18]。Dreamcoder[8]交替使用神经引导搜索的唤醒阶段来解决问题，以及扩展抽象库的睡眠阶段来压缩在唤醒期间发现的程序。贝叶斯程序学习在解析和生成手写世界字母表方面被证明优于深度学习[16]。

4 ARC网格的以对象为中心的模型

我们引入了以对象为中心的模型，这是模式和函数的混合，与仅由函数组成的基于DSL的程序形成对比。我们用网格模型来说明这一点，这些网格模型用具有不同形状、颜色、大小和位置的对象来描述ARC网格。这样的网格模型用于解析网格，即根据模型理解其内容，也用于生成网格，使用模型作为模板。一个任务模型包括两个网格模型，可以预测输出网格，描述一对网格，或为给定任务创建一对新网格。

4.1 混合模式和函数

网格模型的目的是区分任务网格中不变和可变的元素。在任务b94a9452（图1顶部）中，所有输入网格都包含一个正方形，但大小、颜色和位置各不相同。这可以用一个模式Square(size:?, color:?, pos:?)来表示，其中Square被称为构造器（这里带有三个参数），问号被称为未知数（类似于Prolog变量）。还有一个用于位置的构造器，如二维向量Vec(i:?, j:?)，以及大小的原始值（例如，3）和颜色（例如，蓝色）。模式可以嵌套，就像在Square(3,?,Vec(?,2))中一样，这意味着“一个大小为3的正方形，其左上角在第二列”，以便让模型尽可能具体。完全基础的模式（没有未知数）被称为描述：例如，Square(3,blue,Vec(2,4))。

然而，仅凭模式，没有办法使输出网格依赖于输入网格，这是解决ARC任务的关键。因此，我们在网格模型中添加了两个成分（通常是输出模型）：对网格描述（通常是输入描述）的组件的引用，以及函数应用，以允许一些输出组件成为计算结果。例如，在任务b94a9452中，输出网格中小正方形的模型可以是Square(!small.size, !large.color, !small.pos - !large.pos)，其中例如!small.size是对输入网格中小正方形大小的引用，'-'是减法函数。这个模型表示“小的输出正方形与小的输入正方形具有相同的大小，与大的输入正方形具有相同的颜色，其位置是两个输入正方形的位置之差。”

表1和表2分别列出了我们在实验中使用的网格模型的模式构造器和函数。每个构造器/函数都有一个结果类型和类型化的参数。参数类型限制了哪些值/构造器/函数可以用作参数。构造器参数的名称用于引用网格模型或网格描述的组件。网格、对象和形状构造器有一个隐含的参数grid，用于表示原始网格。输入模型使用隐含的参数来表达约束，例如，声明不同的对象具有相同的颜色。

一个任务模型M = (Mi, Mo)由一个输入网格模型Mi和一个输出网格模型Mo组成。图2显示了一个正确的任务b94a9452的模型，用文字表述为：“输入网格中有两个堆叠的完整矩形，背景为黑色。输出网格的大小与底部对象（lay[1].object）相同，背景颜色为顶部对象（lay[0].object）的颜色。输出网格有一个顶部对象的副本，重新着色为底部对象的颜色，其位置是顶部对象位置和底部对象位置之间的差值。”

4.2 使用网格模型解析和生成网格

我们为任何网格模型M引入了两个操作：将网格g解析为描述π和生成网格描述π，从而生成网格g。这些操作类似于从语法中解析和生成句子，其中句法树对应于我们的描述π。

在这两种操作中，首先使用描述作为评估上下文（称为环境，记为ε）来解析模型M中的引用。具体来说，每个引用都是ε中的一个路径，并被替换为此路径末尾的子描述。然后对这些引用应用的函数进行评估。结果是只包含模式和值的简化模型M′。

解析。网格g的解析包括用与网格内容相对应的描述替换简化模型M′中的未知数。没有必要描述网格的全部内容，这允许部分模型。网格从上层到下层进行分析，以考虑重叠的对象。对象的分析是上下文的，它取决于在分析上层之后网格中剩余的部分。出于效率原因，每个网格都被预处理以提取单色部分的集合，并且对象被解析为这些部分的并集（见图3）。由于网格的分析可能变得组合，我们限制了由解析产生的描述的数量，并根据第5节中定义的描述长度度量对它们进行排序。例如，使用图2的模型Mi解析运行任务中的第一个输入网格返回以下描述：πi = Layers(Vec(12,13), black, [Layer(Vec(2,4), Colored(Rectangle(Vec(2, 2), Full), yellow), Layer(Vec(1,3), Colored(Rectangle(Vec(4,4), Full), red) ])。

生成。网格的生成包括用正确类型的随机描述替换简化模型M′中的剩余未知数，以获得网格描述，然后可以将其转换为具体的网格。例如，图2的输出模型Mo应用于上述第一个输入网格的描述πI作为环境ε，生成以下描述πo = Layers(Vec(4,4), yellow, [Layer(Vec(1,1), Colored(Rectangle(Vec(2,2), Full), red)])。这个描述符合预期的输出网格。

一个重要的点是，这两个操作是多值的，即可能返回多个描述。事实上，根据一个模型解析一个网格通常有多种方式，例如，如果模型提到一个单一的对象，而网格包含多个对象。当一个模型包含未知数时，也可以生成多个网格。

4.3 使用任务模型进行预测、描述和创建

我们通过展示任务模型可以在三种不同模式下使用来证明其多功能性：从输入网格预测输出网格，共同描述一对网格，或为任务创建一对新网格。我们在下面使用符号ρ, π ∈ parse(M, ε, g)来说明π是根据模型M和环境ε对网格g的第ρ次解析；符号ρ, π, g ∈ generate(M, ε)表示π是由模型M和环境ε生成的第ρ个描述，g是由π描述的具体网格。排名ρ的原因是解析和生成是多值的。

预测模式在模型学习后，在测试案例的评估阶段使用，通过预测给定输入网格的输出网格。它包括首先使用输入模型和空环境解析输入网格以获得输入描述πI，然后使用输出模型和输入网格描述作为环境生成输出网格。

描述模式在模型的学习阶段使用（见第5节）。它允许获得一对网格的联合描述。它包括解析输入网格和输出网格。请注意，输出网格的解析取决于输入网格解析的结果，因此称为“联合描述”。

创建模式可以创建任务的新示例。它包括连续生成输入网格和输出网格，后者以前者为基础。这种模式在ARC挑战中没有使用，但它可以为测量系统的智能做出贡献。事实上，如果一个代理真正理解了任务，它应该能够产生新的示例5。

在所有模式下，nil环境与输入模型一起使用，因为输入网格首先出现，没有任何先验信息。还要注意，所有模式都继承了解析和生成的多值属性。这三种模式突出了我们的以对象为中心的模型和现有方法的基于DSL的程序之间的本质区别。后者是为预测设计的（计算输出作为输入的函数），它们不提供网格的描述，也不提供创建新输入网格的方法。可以通过随机生成输入网格并应用程序来创建新示例，但一般来说，它不会尊重大多数任务的不变量：例如，会生成随机位图而不是实心正方形。

5 基于MDL的模型学习

基于MDL的学习通过搜索压缩数据更多的模型来进行。要压缩的数据在这里是训练示例的集合。我们必须定义两件事：（1）模型和示例的描述长度，（2）模型的搜索空间和策略。

5.1 描述长度

MDL中的一种常见方法是定义整体描述长度（DL）为两部分之和（两部分MDL）：模型M和根据模型编码的数据D[12]。

在我们的案例中，模型是由两个网格模型组成的任务模型，数据是训练示例（网格对）的集合。为了弥补示例数量较少的问题，并允许足够复杂的模型，我们使用了一个排练因子α ≥ 1，就像每个示例被看到α次一样。

形式为L(ρ, π, g | M, ε)的项表示根据网格模型M和环境ε通过解析得到的第ρ个描述π编码的网格g的DL，它作为中间表示。我们可以通过使用π作为网格的中间表示来分解这些项。

项L(ρ) := LN(ρ) − LN(1)编码了不选择第一个解析描述的额外成本，惩罚更高的排名。LN(n)是一个经典的整数通用编码[7]。项L(π | M, ε)测量了必须添加到模型和环境以编码描述的信息量，通常是未知数的值。项L(g | π)测量了原始网格和描述产生的网格之间的差异。当对所有示例ρi = 1且L(ρo, πo, go | Mo, πi) = 0时，即当对每个输入网格使用第一个描述时，输出网格无需再编码，因此输出网格可以从输入网格完美预测。必须定义三个基本的模型相关DL：

我们概述了第4节中定义的网格模型的这些定义。我们回顾一下，描述长度通常是从概率分布中得出的，方程为L(x) = − log P(x)，对应于最优编码[12]。

定义L(M)相当于用构造器、值、未知数、引用和函数作为节点来编码语法树。由于类型的限制，每个节点实际上只可能有一小部分：例如，类型Layer只有一个构造器。我们在可能的节点上使用均匀分布，对非有界整数使用通用编码。根据环境中具有兼容类型的所有组件的均匀分布来编码引用。我们给未知数的概率低于构造器，给引用/函数的概率更高，以鼓励更具体的模型，并使输出依赖于输入。

定义L(π | M, ε)相当于编码模型中未知的描述组件。由于这些描述组件实际上是基础模型组件，所以可以重用上面为L(M)的定义，只需调整概率分布以排除未知数、引用和函数。

定义L(g | π)相当于编码网格g中哪些单元格被描述π错误指定。为了与网格模型和描述具有可比性，我们将每个不同的单元格表示为一个点对象——Layer(Vec(i,j),Colored(Point,c))——并将其编码为描述。我们还必须编码不同单元格的数量。

表3显示了任务b94a9452中图2模型的描述长度L(M, D)的分解，分为输入和输出，以及用模型编码的模型和数据。请记住，L(D | M)是每个示例的α = 10份。它显示输出网格的DL为零比特，这意味着它们完全由网格模型和输入网格决定。因此，所提出的模型是该任务的解决方案。输入网格的平均DL为2355.2/10/3 = 78.5比特，与输入网格模型的DL相当。

5.2 搜索空间和策略

模型的搜索空间由以下特征定义：（1）初始模型，（2）细化操作符，它返回给定模型M的模型细化列表M1 . . . Mn。细化可以插入一个新组件，用模式替换未知数（为构造器参数引入新的未知数），或者用表达式（引用、值和函数的组合）替换模型组件。细化操作符可以访问联合描述，因此可以由它们指导。与之前的基于MDL的方法[22]类似，我们采用基于模型描述长度的贪婪搜索策略。在每一步，从初始模型开始，选择减少更多L(M, D)的细化。当没有模型细化能减少它时，搜索停止。为了弥补输入和输出网格可能具有非常不同大小的事实，我们实际上使用了一个归一化的描述长度ˆL，它给予全局DL的输入和输出组件相对于初始模型相同的权重。

我们的初始模型对输入和输出都使用未知网格？：Minit = (?, ?)。可用的细化如下：

表4显示了任务b94a9452的学习轨迹，显示了在每一步找到的最具压缩性的细化。它揭示了系统是如何学习任务（步骤在括号中给出）：“输入和输出网格由背景上的对象层组成（1-2）。输入中有一个矩形lay[1]（3），输出中有一个矩形lay[0]（4）。输出网格的大小是输入中的lay[1]（5）。输入中还有另一个矩形lay[0]，位于lay[1]之上（6）。我们可以使用它的颜色作为输出的背景（8）。输出矩形与输入矩形lay[0]相同，但颜色为lay[1]（7），其位置等于两个输入矩形的位置之差（9）。所有矩形都是完整的（10-11），输入背景为黑色（12）。”

5.3 剪枝阶段

学习到的模型有时缺乏泛化能力，在测试示例上失败。这是因为上面定义的基于MDL的学习的目标是在网格对上找到最具压缩性的任务模型。这对于描述模式和创建模式是相关的。然而，在预测模式下，输入网格模型被用作匹配输入网格的模式，只要它能捕获生成输出网格的正确信息，就应该尽可能通用。例如，如果训练示例中的所有输入网格高度为10，那么模型将在输入网格高度为12的测试示例上失败，即使该高度对于生成输出完全不重要。

因此，我们添加了一个剪枝阶段作为学习模型的后处理。原理是从这个学习到的模型开始，并在不破坏正确预测的情况下重复应用反向细化。反向细化可以移除一层或将构造器/值替换为未知数。为了有一个统一的学习策略，我们在这里也使用基于MDL的策略，只是将描述长度调整为预测模式。在预测模式下，输入网格是给定的，因此我们用L(go | M, gi)替换L(gI, go | M)。因此，DL L(ρI, πi, gi | Mi, nil)变为L(ρI, πi, gi | Mi, nil, gi)，这等于L(ρI)，因为πI完全由输入网格、输入网格模型和解析等级决定。这个新定义使得在降低DL的同时简化输入模型成为可能。事实上，这种简化通常会减少L(Mi)，但会增加L(πI | Mi, nil)和L(gI | πI)。后两项不再计入面向预测的度量。与ρI相关的成本很重要，因为选择错误的输入网格描述几乎总是会导致错误的预测输出网格。DL L(ρo, πo, go | Mo, πi)变为L(ρo, πo, go | Mo, πi, gi)，这等于前者，因为πI是gI的抽象表示。事实上，与输入网格不同，保持输出网格尽可能压缩是很重要的。

在任务b94a9452中，从图2的模型开始，剪枝阶段执行了三个泛化步骤，将两个输入矩形的Full掩码和输入背景的黑色替换为未知数。这些泛化在ARC任务的测试示例中并不是必需的，但它们使模型能够在打破训练示例不变量的输入网格上工作，例如，一个十字形在一个矩形上方，矩形在一个蓝色背景上方。

6 评估

在本节中，我们首先在ARC上评估我们的方法，将其与现有方法在成功率、效率、模型复杂性和模型自然性方面进行比较。然后，我们通过将其应用于不同的领域（电子表格）来评估我们的方法的泛化能力，其中输入和输出是字符串行。我们的实验在Fedora 32、Intel Core i7x12（16GB内存）上使用单线程实现进行。由于不涉及随机性，我们对每个任务集进行一次运行。

6.1 抽象和推理语料库（ARC）

我们在800个公共ARC任务上评估了我们的方法，并参加了2022年ARCathon挑战赛，作为MADIL团队。少数参数是基于训练任务设置的。为了确保解析和学习之间的计算时间达到良好平衡，我们设置了一些限制，这些限制在我们的实验中保持稳定。由网格解析产生的描述数量限制为64，只有3个最具压缩性的描述被保留用于计算细化。在每一步，最多考虑100,000个表达式，根据DL估计，只有20个最有希望的细化被评估。排练率α设置为10。任务彼此独立处理，不从一个任务学习到另一个任务。结果为每个任务的学习时间限制为60秒，加上10秒的剪枝阶段。

学习和预测日志以及已解决训练任务的截图可作为补充材料提供。任务集和基线。我们考虑了四个任务集，已经报告了结果：400个训练任务和400个评估公共任务，Kaggle'20的100个秘密任务，以及ARCathon'22的100个秘密任务。我们推测这些秘密任务是从200个秘密ARC任务中选取的。作为基线，我们考虑了在所考虑任务集上报告结果的已发布方法[10,3,23,2]。我们还包括了两次挑战的获胜者作为参考。不幸的是，报告的结果很少，论文没有提供他们的代码。我们的方法的代码可在GitHub6上作为开源代码获取。版本2.7用于此处报告的实验。成功率。在训练任务上，我们有更多的结果可以比较，我们的方法解决了96个（24%）训练任务，几乎与最好的方法（Ainooson等人的26%）相当。这两种方法还解决了相似数量的评估任务（23 vs 26任务），并且在ARCathon'22中都解决了2/100任务，并列第四。比较不同的任务集，似乎评估任务比训练任务明显更难，ARCathon的秘密任务似乎更难，因为获胜者只能解决6个任务。Icecuber设法在Kaggle'20中正确预测了惊人的20.6%的测试输出网格，但代价是手工编写了142个原始数据，10k行代码，以及暴力搜索（每个任务计算数百万个网格）。

ARC评估协议允许每个测试示例进行三次预测。然而，我们的方法在96个已解决训练任务中的90个中的第一次预测实际上是正确的。这表明我们的学习模型在对任务的理解上是准确的。为了更好地评估学习模型的泛化能力，我们还测量了泛化率，即在训练示例上正确的模型在测试示例上也正确的比例：在训练任务上为92%（94/102），在评估任务上为72%（23/32）。这再次表明评估任务具有更高的泛化难度。如果没有剪枝阶段，这个比率在训练任务上下降到89%（91/102）。这表明剪枝阶段是有用的，尽管面向描述的模型学习已经擅长泛化。泛化失败的原因有：例如，测试示例有多个对象，而所有训练示例只有一个对象；训练示例有一个误导性的不变量。

效率和模型复杂性。根据Chollet的说法，智能是获取新技能的能力。虽然ARC通过每个任务只有几个训练示例和独特的任务来强制数据效率，但它并没有强制先验的数量或计算资源的效率。因此，评估后者是有用的。我们已经提到了Icecuber的方法，它依赖于大量的原始数据和密集的计算。Ainooson等人的方法，其性能与我们的相当，使用了52个原始数据，每个已解决任务平均耗时约700秒。相比之下，我们的方法使用了30个原始数据，每个已解决训练任务耗时4.6秒（所有训练任务耗时21.7秒）。此外，将学习时间加倍至120秒并不会导致解决更多任务，所以60秒似乎足以找到一个解决方案（如果有的话）。还要注意，我们的方法在找到解决方案时不会停止学习，而是在无法实现更多压缩时停止。

另一种评估效率的方法是查看学习模型的复杂性，通常在程序合成方法中，模型由原始数据组成的数量。这种复杂性的一个好代理是在分配时间内达到的搜索深度。在我们的案例中，它等于应用于初始空模型的细化次数。很少有方法提供这些信息：Icecuber将深度限制为4，Ainooson的最佳结果是通过最大深度为3的暴力搜索实现的。基于DreamCoder[3]的方法有类似的限制，但可以通过发现和定义新的操作作为原始数据的常见组合，并在一个任务到另一个任务中重用它们来学习更复杂的程序。由于采用了贪婪策略，我们的方法可以在更少的计算时间内更深入地挖掘。在训练任务上，60秒的超时时间内完成的细化步骤数量从4到57不等，平均为19步。这证明了MDL标准在引导搜索走向正确模型方面的有效性。这一说法得到了这样一个事实的加强，即束搜索（宽度=3）并没有导致解决更多任务。

学习到的模型。尽管我们的模型很简单，但已解决任务的学习模型非常多样化。它们表达了各种转换：例如，移动一个对象，扩展线条，将一个对象放在另一个对象后面，按从大到小的顺序排列对象，去除噪音等。请注意，这些转换都不是我们模型中的原始数据，它们是根据对象、基本算术、简单几何和MDL原则学习的。

我们将我们的学习模型与LARC[1]的自然程序进行了比较。值得注意的是，我们的许多模型涉及与自然程序相同的对象和类似的操作。例如，任务b94a9452的自然程序是：“[输入]有一个正方形形状，里面有一个小正方形，位于大正方形的中心，背景为黑色。两个正方形有不同的颜色。制作一个与大正方形相同大小的输出网格。内部小正方形的大小和位置应与输入网格中的相同。两个正方形的颜色互换。”对于其他任务，我们的模型缺少自然程序使用的一些概念，但设法补偿它们：例如，拓扑关系如“旁边”或“顶部”通过三次尝试得到补偿；大多数颜色通过MDL原则选择最大的对象得到补偿。然而，在大多数情况下，识别出相同的对象。

这些观察结果表明，我们的以对象为中心的模型与人类产生的自然程序非常一致，不同于基于网格转换组合的方法。作为一个例子，[10]在任务23b5c85d上学到的程序是strip black; split colors; sort Area; top; crop，这是一系列网格到网格的转换，没有明确提到对象。

6.2 从网格到字符串（FlashFill）

与ARC相比，一种类似但不同的任务是自动填充电子表格中的一些列，给定已经填充的列，仅从几个输入-输出示例中。在程序合成领域的一项著名工作[13]导致了Microsoft Excel 2013的一个新功能，称为FlashFill。作为一个简单的例子，考虑一个电子表格，其中A列包含姓氏（例如，Smith），B列包含名字（例如，Jones Paul），C列期望包含第一个名字的首字母后跟姓氏（例如，J. Smith）。

与ARC一样，每个任务都有一些输入-输出对，输出应根据输入预测。主要的区别在于输入和输出的类型，这里是字符串行而不是彩色网格。这里的研究假设是，通过仅改变模式、函数和特定于模型的DL的定义，我们的方法能够学习解决上述工作中给出的示例任务的模型。

模型。表6列出了我们的字符串行模型的模式。行模型描述了一行字符串，只是一个单元格模型数组。单元格模型描述了电子表格单元格的内容，即一个字符串。它可以是空字符串（Nil），或者是带有中间标记和两侧子字符串的字符串因式分解。这里的标记扮演着对象的角色。标记模型可以是常量字符串或正则表达式，从预定义的列表中选择：例如，Digits = [0-9]+匹配连续的数字序列。未知数（？）可以用作单元格模型和条件（Cond）。最后，Alt构造器可以在单元格模型和标记模型中使用，以表达替代（Alt(?,M1,M2)）、条件（Alt(expr,M1,M2)）和可选（Alt(?,M,Nil)）。目前可用的函数有限：字符串长度、过滤字符（数字、字母、大写字母、小写字母）、将字符串转换为大写或小写、将整数和布尔值转换为字符串、与某个常量值的相等性和条件的逻辑运算符。表达式和引用目前仅限于标记。为了比较，FlashFill的DSL也使用预定义的正则表达式，但使用它们来定位字符串中的位置，而不是标记。他们的程序是条件表达式（switch），其中每个分支是由位置指定的子字符串和常量字符串的连接。相比之下，我们的模型允许自由嵌套条件（Alt）和连接（Factor）。然而，他们的DSL有循环，这在我们的模型中还没有对应的部分。

任务集。为了初步评估，我们使用了[13]中的14个示例作为任务集。每个任务有一个或两个字符串作为输入，一个字符串作为输出，以及2-6个训练示例（平均3.4个）。我们用3-6个评估示例补充它们，其中一些具有一些泛化难度。这14个任务以与ARC任务相同的JSON格式提供在补充材料中。

效率和成功率。学习需要1秒或更短的时间，除了任务1和任务13，它们的输入字符串较长，分别需要9.9秒和5.2秒。搜索深度从11到76不等，平均为35步。对于11/14个任务（除了任务4、5、9），学习到的模型正确地描述和预测了训练示例。然而，只有5个学习到的模型能泛化到所有测试示例：3个模型在一个测试示例上失败（例如，在任务3中，文件扩展名.mp4包含一个与其他文件扩展名不同的数字）；在任务8中，训练示例是不明确的，因为输入字符串是不同格式的日期，输出字符串可以是天或年份的最后两位数字；在任务11中，训练示例有一个打字错误（故意的），这使得任务未指定。其他任务的（部分）失败是由于我们的模型缺少功能，特别是循环的对应部分，或者是因为错误的细化序列。例如，任务9可以通过延迟插入替代来解决。

学习到的模型。输入模型可以表示为带有标记组和替代项的正则表达式，输出模型可以表示为带有组标识符作为变量的字符串插值。对于任务10，我们得到以下模型。

输入由三个整数组成，第一个是可选的。输出是这三个整数的连接，用破折号分隔，当输入中缺少第一个整数时，它是425。在FlashFill中，通常会产生大量的程序，因为执行的是穷举搜索。对于任务10，[13]中给出的解决方案程序如下（A指的是输入列）：

这说明了我们的基于模式的模型和基于计算的DSL程序之间不同的编程风格。

7 结论和展望

我们提出了一种新颖且通用的方法，用于有效地学习任务技能，这些任务包括生成结构化输出作为结构化输入的函数。根据Chollet的智能度量，有效学习意味着目标任务范围的知识先验有限，每个任务只有几个示例，并且计算资源较低。我们的方法基于描述性任务模型，结合了以对象为中心的模式和计算，以及MDL原则来指导模型搜索。我们已经详细介绍了在彩色网格上ARC任务的应用，并概述了在字符串上FlashFill任务的应用。我们已经展示了有希望的结果，特别是在效率、模型复杂性和模型自然性方面。

在ARC上进一步发展将需要大量的设计工作，因为我们目前的模型到目前为止只覆盖了ARC任务所需知识先验的一小部分（例如，目标导向性）。对于FlashFill任务，添加循环和常见函数的对应部分预计足以达到最先进的水平。

补充材料

我们在这里描述了随论文附带的补充文件的内容。源代码的公共存储库也可在以下网址获得：https://github.com/sebferre/ARC-MDL 用于ARC，以及 https://github.com/sebferre/ARC-MDL-strings 用于FlashFill。有两个主要目录：一个用于ARC任务，另一个用于FlashFill任务。

任务集

ARC的公共任务集可在以下网址在线获取：https://github.com/fchollet/ARC。有两个任务集：训练任务和评估任务，每个任务集包含400个任务。FlashFill的任务集由[13]中的14个示例组成。我们以JSON文件的形式在FlashFill/taskset/中提供它们，使用与ARC任务相同的格式，只是字符串和字符串数组被用来代替彩色网格。为了方便起见，我们还提供了FlashFill/taskset/allexamples.json 文件，以便在一个文件中浏览所有示例。

结果我们为每个任务集提供了学习和预测日志：– ARC/trainingtasks.log – ARC/evaluationtasks.log – FlashFill/tasks.log

每个日志文件以超参数值开始，并以全局统计度量结束。对于每个任务，它提供了以下内容：

– 初始模型的详细DL（描述长度）；– 学习轨迹（包括剪枝阶段）作为细化序列，并显示归一化DL的减少；– 剪枝前后学习到的模型及其详细DL；– 每个训练示例的最佳联合描述（ARC评估任务除外，以免泄露内容给AI开发者，这是F. Chollet的建议）；– 每个训练和测试示例的预测；– 最后是任务的几个度量。

每个任务和最后提供的度量如下：

– runtime-learning：学习时间，以秒为单位（包括剪枝阶段）；– bits-train-error：在输出训练网格上犯下的剩余错误，以比特为单位；– acc-train-micro：预测正确的训练输出网格的比例；– acc-train-macro：如果所有训练输出网格都正确预测，则为1，否则为0；– acc-train-mrr：训练输出网格正确预测的平均逆排名（MRR），如果所有第一次预测都正确，则为1；– acc-test-micro：预测正确的测试输出网格的比例；– acc-test-macro：如果所有测试输出网格都正确预测，则为1，否则为0；– acc-test-mrr：测试输出网格正确预测的平均逆排名（MRR），如果所有第一次预测都正确，则为1。

ARC中的参考度量是acc-test-macro。微度量提供了更细致和乐观的成功度量。

为了方便起见，我们还在ARC/solvedtasks中为我们的方法解决的96个ARC训练任务中的每一个提供了图片。我们诚挚地邀请读者浏览这些图片，以快速了解我们的方法可以解决的任务多样性。这些图片是与ARC任务一起提供的UI的屏幕截图。