ARC挑战方法的第一步，基于描述性网格模型和最小描述长度原则2021

First Steps of an Approach to the ARC Challenge based on Descriptive Grid Models and the Minimum Description Length Principle

基于描述性网格模型和最小描述长度原则的ARC挑战方法的第一步

https://arxiv.org/abs/2112.00848

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=

摘要‍

François Chollet最近引入了抽象和推理语料库（ARC）作为衡量人类和机器广泛智能的工具。它非常具有挑战性，Kaggle竞赛中最好的方法只能解决20%的任务，依赖于手工制作的转换链的暴力搜索。在本文中，我们介绍了基于描述性网格模型和最小描述长度（MDL）原理的方法的初步探索。网格模型描述了网格的内容，并支持解析网格和生成网格。MDL原理被用来指导寻找好的模型，即最能压缩网格的模型。我们报告了过去一年的进步，改进了总体方法和模型。在400个训练任务中，我们的表现从解决5个任务增加到29个任务，每个任务只使用30秒的计算时间。我们的方法不仅能预测输出网格，还能输出一个可理解的模型和解释，说明模型是如何逐步构建的。

1 引言

本文档描述了我们对François Chollet引入的ARC（抽象和推理语料库）挑战的方法，作为一种衡量智能的工具，无论是人类还是人工智能[2]。ARC的引入是为了促进人工智能（AGI）的研究[5]，并从以系统为中心的泛化转向开发者意识到的泛化。后者使系统能够“处理系统或系统开发者之前从未遇到过的情况”。例如，一个被训练用来识别猫的系统具有以系统为中心的泛化能力，因为它能识别它从未见过的猫，但在一般情况下，它不具备开发者意识到的泛化能力，因为它不能仅凭几个例子学会识别马（与小孩不同）。

ARC由1000个学习任务组成，400个用于训练，400个用于评估，还有200个由作者保密，以确保无偏见的评估。每个任务都包括学习如何从一个输入彩色网格生成一个输出彩色网格（见图1中的示例）。ARC是人工智能的一个具有挑战性的目标。

正如F. Chollet所写：“据我们所知，ARC似乎无法通过任何现有的机器学习技术（包括深度学习）来解决”[2]。主要困难如下：

– 预期的输出不是一个标签，甚至不是一组标签，而是一个大小可达30x30、最多有10种不同颜色的彩色网格。因此，它属于结构化预测的范畴[3]。

– 预测的输出必须与预期的输出完全匹配。如果有一个单元格出错，任务就被认为是失败的。为了补偿这一点，每个输入网格允许进行三次尝试。

– 在每个任务中，通常有2到4个训练实例（输入网格+输出网格），以及1到2个测试实例，需要对其进行预测。

– 每个任务都依赖于从输入网格到输出网格的独特转换。特别是，任何评估任务都不能通过在训练任务上学到的转换来解决。实际上，每个任务都是一个独特的学习问题，ARC评估的是广泛的泛化能力和少量样本学习。

这些困难的补偿是，输入和输出数据比现实生活中的数据（如照片或文本）简单得多。我们认为这有助于专注于智能的核心特征，而不是可扩展性问题。

2020年春季组织了一场Kaggle竞赛，以挑战ARC作为衡量智能的工具的鲁棒性，并看看使用最先进的技术可以取得什么成就。获胜者的解决方案能够解决100个（秘密）评估任务中的20%，这已经是一个显著的成就。然而，它基于手工制作的网格转换链的暴力搜索，这些转换是从142个基本转换的集合中选择的。这很难扩展到更大的任务集合，正如作者承认的那样：“不幸的是，我觉得我的解决方案本身并没有让我们更接近AGI。”另一位竞争对手使用了基于转换的类似领域特定语言，并使用语法进化来搜索程序空间[4]。他们的方法解决了Kaggle任务的3%，并在400个训练任务上解决了7.68%。

我们的方法基于MDL（最小描述长度）原理[9,6]，该原理认为“最适合某些数据的模型是压缩数据最多的模型”。MDL原理已经被成功应用于各种数据结构的模式挖掘（交易[11]、序列[10]、关系数据库[7]或图形[1]），以及分类[8]。

与这些工作的一个主要区别是，要学习的模型不仅需要解释数据，还需要能够进行结构化预测，即从输入网格生成输出网格。在这个阶段（版本2.2），我们考虑的模型相当简单，几乎没有机会覆盖ARC任务的大部分：单色点和形状，以及位置和大小的基本算术。

我们的首要目标是证明基于MDL的方法对ARC挑战的有效性，以及对AGI的希望。我们的方法在400个训练任务中成功解决了29个（7.25%），在400个评估任务中成功解决了6个（1.5%），每个任务的学习超时仅为30秒。考虑到问题的难度，我们认为这样的结果相当鼓舞人心。此外，解决的任务相当多样，学习到的模型通常接近于任务的最简单模型（在选定的模型类别中）。

本报告的组织如下。第2节给出了ARC网格和任务的正式定义。第3节解释了我们在两部分MDL框架下对ARC任务的建模，特别是我们的模型类别。第4节描述了基于MDL的学习过程，这归结为定义描述长度和模型细化。第5节报告了我们在训练和评估ARC任务上对我们的方法的评估，以及对少数任务学习到的模型。

2定义ARC任务

定义1（颜色）。我们假设有一个有限的符号集合C，我们称之为颜色。

在ARC中，有10种颜色，用JSON文件中的数字（0..9）表示，用Web界面中的颜色（例如，黑色、紫色、红色）表示(see Figure 1).

定义2（网格）。一个网格g ∈ C^h×w 是一个具有h 0行和w 0列的颜色矩阵。网格通常显示为彩色网格。行数h = height(g)称为网格的高度，列数w = width(g)称为网格的宽度。

网格单元格由坐标(i, j)特征化，其中i选择一行，j选择一列。坐标(i, j)处的颜色表示为gij或g[i, j]。坐标范围从(0, 0)到(h − 1, w − 1)。

在ARC中，网格的大小从1 × 1到30 × 30不等。

定义3（示例）。一个示例是一个网格对e = (gI, go)，其中gI称为输入网格，go称为输出网格。

如图1所示，输出网格不必与输入网格具有相同的大小，它可以更小或更大。

定义4（任务）。一个任务是一个对T = (E, F)，其中E是训练示例的集合，F是测试示例的集合。

学习者只能访问训练示例的输入和输出网格。它的目标是，对于每个测试示例，根据输入网格预测输出网格。如图1所示，一个任务的不同输入网格不必具有相同的大小，也不必使用相同的颜色。测试网格也是如此。

ARC总共由1000个任务组成：400个用于训练，400个供开发者评估，200个用于独立评估。图1显示了400个训练任务中的一个，有三个训练示例和一个测试输入网格。

开发者应该只关注训练任务，而不应该关注评估任务，后者应该只用于评估系统的广泛泛化能力。每个任务通常有2到4个训练示例，1到2个测试示例。

在两部分MDL中建模ARC任务 这里的目的是设计一类任务模型，可以用来表示从输入网格到输出网格的转换。我们的关键直觉是，一个任务模型可以分解为两个网格模型，一个用于输入网格，另一个用于输出网格。输入网格模型表达了所有训练输入网格的共同点，而输出网格模型表达了所有训练输出网格的共同点，作为输入网格的函数。从输入网格到输出网格的实际转换涉及两个模型，如下所示。输入网格模型用于解析输入网格，这会产生一些信息，这些信息可以表征输入网格。然后，将解析信息输入输出网格模型，以生成输出网格。在以下段落中，以“版本X”开头的段落是针对该版本特有的，而其他段落则是通用的。

3.1 模型

版本2。我们网格模型的主要组成部分是对象。确实，ARC网格通常可以被视为背景上的各种形状的对象。对象可以是分离的、嵌套的或相互重叠。每个对象都有一个位置和一个形状。

形状有一个颜色，要么是一个点，要么适合某个大小的矩形框。在后一种情况下，精确的形状由一个掩码指定，该掩码可以是一个自定义位图或几种预定义的规则形状之一。对象的位置是相对于形状的左上角单元格的。每个对象属性（例如，位置、大小、颜色）可能是常量（例如，形状总是红色）或在示例中是可变的。

我们定义我们的模型为表示具体网格对的数据结构的模板。图2用代数数据类型定义了这些数据结构，用于网格对、网格、对象、形状、掩码和向量（2D位置和大小）。它们使用自然数（N）、颜色（C）和2D位图（M）的原始类型。粗体的大写名称称为构造器，构造器参数的小写名称称为字段。

一个任务由两个网格组成，一个用于输入网格，另一个用于输出网格。每个网格被描述为背景上的层堆栈，每一层由单个对象组成。背景有一个大小（2D向量）和一个颜色。一个对象是一个形状，位于某个位置。形状要么是一个点，用它的颜色描述；要么是一个矩形，用它的大小、颜色和掩码描述。该掩码允许考虑规则和不规则形状，并指出矩形框中的哪些像素实际上属于形状（其他像素可以看作是透明的）。掩码可以是一个自定义位图或几种常见的规则形状之一：全矩形、矩形边框、棋盘格和居中的十字。描述图1中第一个训练对的数据结构是：

数据结构中的路径是从数据结构的根到某个子结构的字段序列。在上面的例子中，路径in.size.j指的是输入网格的宽度，即13；路径out.layers[0].shape.color指的是输出网格顶部形状的颜色，即红色；路径in.layers[1].pos指的是输入网格底部形状的位置，即Vec(1, 3)。

给定一个数据结构d和一个路径p，d中由p引用的子结构用点表示法d.p表示。为了从具体的网格对泛化到一般的任务模型，我们引入了两种元素，可以用来替换任何子结构：未知数和表达式。一个未知数，我们用一个问号?表示，表示任何预期类型的任何数据结构都可以适合。例如，一个与图1中所有输入网格相匹配的网格模型是：

它匹配具有12行和黑色背景的网格，以及两个堆叠的任意位置、任意大小和任意颜色的矩形。顶部矩形可以有任何掩码，而底部矩形应该是完整的。解析的目的是填补空白，用数据结构替换未知数，使得整个结果数据结构正确地描述了一个网格或一对网格。一个未知路径是模型中的一个路径，它通向一个未知数。上面网格模型中的未知路径是：size, layers[0].pos, layers[0].shape.size, layers[0].shape.color, layers[0].shape.mask, layers[1].pos, layers[1].shape.size, layers[1].shape.color。

模型m的未知路径集合记为U(m)。

可能包含未知数的数据结构称为模式。如果一个数据结构不含未知数，则称为基础数据结构。给定一个基础数据结构d和一个模式p，记号d ∼ p表示d与p一致或p与d匹配。这意味着基础数据结构d可以通过用基础数据结构替换模式中的未知数来获得。例如，我们有Vec(12, 14) ∼ Vec(12, ?)。

一个表达式定义了数据结构的一部分作为对某个输入数据结构的计算结果，我们称之为环境。表达式由原始值、构造器、运算符/函数和变量组成。在版本2中，唯一的运算符是对自然数进行零、加法和减法运算，它们用于计算网格和形状的位置和大小。变量是对环境部分的引用。引用环境数据结构中这些部分的一种方便方式是使用环境数据结构中的路径。如果只由原始值和构造器组成的表达式实际上将是数据结构，因此不被视为表达式。输出网格的环境是输入网格，因此可以根据输入网格的内容计算输出网格的一部分。输入网格没有环境，因此表达式在输入网格模型中没有用处。重新使用上面的输入网格模型，我们现在可以为图1中的任务定义一个正确且完整的模型，使用输入网格的未知数和输出网格的表达式：

用文字来说，这个模型表示：“在输入网格中找到黑色背景上的两个堆叠的完整矩形，然后生成一个输出网格，其大小与底部形状相同，背景颜色为顶部形状的颜色，最后添加一个完整矩形，其大小与顶部形状相同，颜色与底部形状相同，位置为顶部形状位置和底部形状位置（相对位置）之间的差。”

如果一个模型是良型的（构造器参数、运算符操作数类型等），并且所有变量都是环境数据结构中的有效路径，则该模型是良型的。更具体地说，如果输入网格模型不包含变量，并且输出网格模型中的所有变量都是输入网格模型中的有效路径，则任务模型是良型的。

如果任务模型的输出网格模型不包含未知数，那么它就可以用来从描述输入网格的数据结构中确定性地生成输出网格，则该任务模型是确定的。

3.2 模型的数据 Data According to a Model

在基于MDL的方法中，为了公平比较不同的模型，必须有一个无损的数据编码。因此，识别“模型的数据”是很重要的，即需要添加到模型中的数据，以便捕捉原始数据中的所有信息。

我们首先考虑网格模型，其中数据是一个网格。可以将网格与形式语言和文法规则进行类比。在这个类比中，网格是句子，网格模型是文法规则，而根据模型的数据是解析树。解析树解释了文法规则如何生成句子。这里，图2中定义的数据结构在网格模型中扮演解析树的角色，它们是网格解析树，我们用希腊字母π表示。网格解析树，即根据模型的数据，是一个数据结构，它通过用表达式的值替换表达式，用值替换未知数，使得结果数据结构正确地描述了网格。描述长度只会计算实例化未知数的数据结构，因为解析树的其余部分已经从模型中知道了。

对于输入网格gIk（第k个示例），πIk表示根据某个固定的输入网格模型mi的一个可能的网格解析树。同样，对于输出网格gOk，πOk表示根据某个固定的输出网格模型mo和输出环境εo的一个可能的网格解析树。

实际上，一个网格模型可能无法解释网格的所有单元格。这在数据中出现噪声时会发生，也会在学习过程中发生，其中中间模型显然是不完整的。为了在不失信息的情况下处理这些情况，我们定义“根据模型的数据”为网格解析树加上原始网格g与网格解析树π生成的网格之间的差异单元格列表。我们称这种额外信息为网格增量，记为δ。

另一个困难是，当测试输入网格与从训练示例中学到的输入网格模型不匹配时。例如，所有训练示例中的输入网格大小为(10,10)，但测试输入网格的大小为(10,12)。在这种情况下，没有网格解析树既与网格模型一致又与网格一致。在许多情况下，这种差异并不影响模型的有效性，这只不过是过度具体（一种过拟合）。我们解决这一困难的方法是允许近似解析，即允许网格解析树偏离网格模型。由于这些差异出现在网格解析树π中，因此没有信息损失。当然，描述长度会考虑到这些差异以惩罚它们。

为了说明，让我们考虑图1中任务的以下（不完整）输入网格模型：

对于第一个输入网格gI1（上标i表示输入网格，o表示输出网格，下标标识示例），主要有两种“根据模型的数据”：

第一个解决方案看起来更好，因为它有一个小得多的网格增量，而且它的网格解析树的大小与第二个解决方案相同。

3.3 网格、网格模型、网格解析树和网格增量上的基本函数Primitive Functions on Grids, Grid Models, Grid Parse Trees,and Grid Deltas

我们在这里定义了处理 网格、网格模型、网格解析树和网格增量的关键基本函数。

我们首先定义网格增量和它们上的简单算术运算。

然后我们定义两个与网格模型的语义直接相关的函数。第一个函数将网格解析树转换为网格。

定义6（网格绘制）。给定一个网格解析树π，draw(π)是根据网格解析树给出的指令绘制的网格。

版本2。给定图2中指定的网格解析树π，网格draw(π)是通过首先生成具有指定大小和背景颜色的网格，然后在该网格上自底向上绘制层来获得的。每个层，要么是一个点，要么是一个矩形，以明显的方式绘制。对于点PosShape(Vec(i, j), Point(c))，位置(i, j)处的单元格被设置为颜色c。对于矩形PosShape(Vec(i, j), Rectangle(Vec(h, w), c, m))，位置(i + x, j + y)处的每个单元格，对于任何x ∈ [0, h[ 和 y ∈ [0, w[，如果相对位置(x, y)属于掩码m，则被设置为颜色c。第二个函数将网格模型应用于环境，解析对它的引用，并用它们的评估结果替换表达式。

定义7（模型应用）。给定一个网格模型m和一个模型环境ε，apply(m, ε)是通过用环境ε上的评估结果替换m中的表达式而得到的模型。得到的模型没有表达式，但可能仍有未知数。如果m中的某个变量在ε中未定义，则该操作未定义。

版本2。环境是网格解析树，变量是它们的路径。只有三个运算符——零、加、减——它们在整数值上以通常的方式进行评估。

我们还定义了两个非确定性函数，它们从网格模型产生网格解析树，从而产生网格描述。第一个函数对应于网格的解析。

定义8（网格解析）。给定一个网格模型m和一个网格g，parse(m, g)非确定性地返回一个网格解析树π，它大约与模型m一致，并大约绘制为网格g。非确定性允许模型对网格有不同的解释。

版本2。这是迄今为止最复杂的原始函数。解析分为三个阶段。首先，网格被划分为相邻的单色区域。其次，对象被寻找为单个部分或部分的联合，以覆盖一些对象被其他对象重叠的情况。小部分（覆盖的单元格少于5个）也被视为相邻的独立点。当对象的形状不是点或完整矩形时，考虑两种形状：一种形状带有完整掩码，将矩形框上的缺失单元格视为噪声；另一种形状带有掩码，包含属于对象的矩形框内的单元格，并且具有相同的颜色。尽可能使用规则掩码（例如，边框、十字），否则使用位图。第三，根据网格模型查找对象的匹配叠加。

对于每一层，以固定顺序考虑候选对象，包括一些简单的启发式方法。最后考虑黑色对象，因为黑色通常是背景颜色。然后，按照覆盖的单元格数量递减的顺序考虑对象。除了这些启发式方法外，还定义了一个总顺序，因为这使得实验更容易重现，也有助于消除一些情况的歧义。例如，如果模型包含几个点，它们将从左到右、从上到下与网格中的点匹配。层次是自顶向下的解析。

如果以一种天真的递归方式进行，搜索空间就不会被公平地探索。事实上，第一层的第二个候选对象只有在考虑了其他层的所有候选对象，并与第一层的第一个候选对象结合时才会被考虑。定义所有层的解析树的排名为各层选定的候选对象排名之和，我们按递增的排名探索搜索空间，以优先考虑所有层的第一个候选对象。这一改进是在版本2.2中引入的。

作为解析的例子，图1中的测试输入网格有三个相邻的部分：浅蓝色、绿色和黑色。可以从这些部分识别出三个矩形：一个小的浅蓝色正方形、一个被蓝色覆盖的绿色矩形，以及一个覆盖整个网格并被其他矩形覆盖的黑色矩形。根据上面的模型，这个输入网格被解析为坐标(3,4)处的2x2浅蓝色矩形，位于坐标(1,2)处的6x6绿色矩形之上，位于黑色背景之上。

与版本1相比，解析被非确定化，意味着产生了一系列网格解析树。我们使用下面定义的描述长度来从较短的DL到较长的DL对这个序列进行排序。确实，DL越短，网格解析树就越可信。由于解析过程中的组合问题，我们使用了各种界限：模型中给定层的最大候选对象数量、在排序之前产生的网格解析树的最大数量，以及实际返回的网格解析树的最大数量。相对于近似解析，我们还限制了与模型相比的不同之处的数量。

第二个函数对应于生成，其中网格解析树是通过填充网格模型的空白产生的，即猜测缺失的元素。

定义9（网格生成）。给定一个没有任何表达式的网格模型m，generate(m)非确定性地返回一个网格解析树，该树是通过用类型兼容的子树替换模型中的未知数而得到的。

3.4 Reading and Writing a Grid with a Grid Model

我们定义了两个重要的组件，用于读取和写入网格。它们简单地由上述基本函数组成，并用作训练和使用模型的基本块。

定义10（网格读取）。给定一个模型m，函数readm接受一个环境和一个网格作为输入，并返回一个网格解析树和增量作为输出。

图3给出了读取组件的示意性描述。当读取一个网格g时，首先将网格模型应用于输入环境，以便解析模型可能包含的任何表达式。然后使用得到的模型将输入网格解析为网格解析树π。最后，计算由π指定的网格和g之间的网格增量。对（π, δ）提供了输入网格的无损表示，如以下引理所表达。

图4给出了写入组件的示意性描述。当写入一个网格时，首先将网格模型应用于输入环境，以便解析模型可能包含的任何表达式。然后使用得到的模型通过实例化未知数来生成一个网格解析树，从中可以绘制出一个具体的网格。除了网格之外，解析树也被输出，以提供网格是如何生成的解释。

3.5任务模型:预测、训练和创造

图5给出了预测的示意性描述。首先使用输入网格模型mi读取输入网格gI，使用空环境，非确定性地得到输入网格解析树πi和输入增量δI。

然后，使用输入网格解析树作为环境，通过写入输出网格模型mo来生成预测的输出网格。

例如，给定图1中测试输入网格的读取返回的输入网格解析树，输出网格模型生成一个坐标为(2,2)的2x2绿色矩形，位于一个6x6浅蓝色背景之上，这就是预期的网格。

在训练阶段，输入和输出网格都是已知的。然而，计算预测输出网格和预期输出网格之间的网格增量不足以学习更好的模型。拥有每个网格的网格解析树更有用，因为它提供了模型如何“看待”网格的解释。因此，我们定义了train函数，它链接了输入和输出网格的读取。

也可以为任务创建新的示例，即仅从输入和输出网格模型创建输入和输出网格。

图7给出了创建模式的示意性描述。输入网格模型用于给定空环境写入输入网格。然后，输入网格的解析树被用作输出网格模型的环境，以生成与输入网格一致的输出网格。该过程高度非确定性，因为在给定的输入网格模型下，通常可以生成多个网格。确实，它通常包含几个未知数。

4 学习任务模型

基于MDL的学习通过选择压缩数据最好的模型来进行。这涉及两个主要组件：（a）一个压缩度量，以便比较模型，（b）一个探索模型空间的策略。压缩度量称为描述长度。

4.1描述长度

在两部分的最小描述长度（MDL）中，描述长度（DL）L(M, D)衡量了使用模型M传达数据D所需的比特数。它根据以下方程分解为两部分：

因子α默认等于10，以给数据相对于模型更多的权重，从而允许学习更复杂的模型。确实，ARC任务的示例数量非常少（平均3个）。

根据任务模型，每个网格的描述长度基于网格对的链式读取。首先，相对于给定读取的网格的描述长度归结为网格解析树和网格增量的描述长度。

请注意，网格解析树π的描述长度是相对于应用于其环境的网格模型m的。确实，我们只需要编码网格解析树中在网格模型中未知的部分或与网格模型不同的部分。其详细的定义取决于网格模型的定义。

网格增量δ的描述长度是相对于网格解析树π的。这是有效的，因为网格解析树在增量之前被编码，因此在编码网格增量时是可用的。其详细的定义也略微取决于网格模型。

然后，我们通过选择“最佳读取”来定义输入网格和输出网格的绝对描述长度，即最小化两个网格累计DL的链式读取。

由于学习策略只选择给出越来越短描述长度的模型，归一化的描述长度 位于区间 [0, 2] 中，每个部分（输入和输出）的贡献位于区间 [0, 1] 中。

在为网格模型和网格解析树定义描述长度时，我们假设了一些基本类型的基本描述长度：

模板。有三种类型的模板（分布为Pt）：原始值和构造器（Pt = 0.4，1.3比特），表达式（Pt = 0.5，1比特），以及未知数（Pt = 0.1，3.3比特）。构造器的每个字段和函数的每个参数都是模板，因此原则上允许任意混合值、构造器、函数和未知数。在版本2中，我们从不为网格、对象、形状和函数参数使用未知数。表达式被赋予更高的概率，因为它们从环境中解释了网格解析树的一部分。未知数被赋予最低的概率，因为它们对应于未解释的部分。

网格模型（L(m)）是类型为Grid的模板，并以此方式编码。网格解析树（L(π|m)）仅由原始值和构造器组成，理论上可以这样编码。然而，由于网格解析树是根据网格模型解析网格得到的，网格解析树的一部分已经在网格模型中编码了。实际上，网格模型的真正目的是确切地提取所有示例网格共有的部分，并避免重复编码。网格解析树中需要编码的唯一部分是（a）与网格模型中的未知数对应的部分，以及（b）由于近似解析而与网格模型不同的部分。

（a）关于未知数，可以从模型中导出一个固定的顺序。因此，只需将对应于每个未知数的网格解析子树的编码串联起来就足够了。

（b）关于不同的部分，我们没有任何先验信息，无论是它们的数量，还是它们在网格解析树中的位置。我们首先用通用编码来编码它们的数量。然后，我们通过编码它们在网格解析树中的位置来编码每个不同的部分，使用均匀分布，并在该位置编码子树。

对不同部分位置的编码可能可以通过几种方式改进。首先，有些差异比其他差异更有可能：例如，不同的矩形宽度与完全不同的形状。其次，并非所有位置的子集都有意义，因为差异位置不应在另一个差异位置之内，否则将需要两次编码同一部分。

网格增量（L(δ|π)）。为了与网格模型和网格解析树可比，我们将网格增量δ编码为一组点。因此，网格增量的描述长度定义为：

请注意，点的描述长度是相对于从网格解析树绘制的网格进行的。特别是，这使得网格大小可用于点位置的编码。

对于图1中的任务，表1比较了初始模型和上面给出的示例解决方案模型的描述长度，对于α = 10（每个示例计为10）。表格详细说明了输入网格和输出网格之间的划分，以及模型（L(M))和根据模型的数据（L(D|M))之间的划分。我们观察到模型DL的增加在很大程度上被数据DL的减少所抵消。结果压缩增益为16.3%，减少了六倍。特别是，使用解决方案模型，输出网格的描述长度降为零，这意味着输出网格完全由模型和输入网格解析树解释。

4.2学习策略

模型空间通常太大，无法进行系统探索，必须使用启发式方法来指导寻找好模型的搜索。学习策略包括从初始模型开始，迭代细化模型，寻找最佳模型，即最能压缩的模型。给定一个模型类，搜索策略因此完全由以下内容指定：

1. 一个初始模型M0（初始模型），通常是简单的模型；2. 以及一个函数R，它将每个模型M映射到一个有序的细化模型列表M1, M2, ...（细化），通常考虑到根据模型的数据（这里，网格、网格解析树和网格增量）。

我们说一个细化Mi是压缩的，如果它比原始模型M减少了描述长度。细化的排序很重要，因为可能的细化数量可能非常大，通过测量其描述长度来评估每个细化是有成本的。确实，这涉及到每个细化模型对输入和输出网格的解析。因此，这种排序是启发式方法的关键部分。

启发式方法的另一部分包括限制每个模型考虑的压缩细化的数量，以及每次迭代后保留的模型数量。贪婪搜索选择第一个压缩细化，并且在每次迭代中只有一个模型。束搜索通过为每个模型选择Kr个压缩细化，然后从中为下一次迭代选择Km个最佳模型，从而提供更广泛的探索。Km是束宽。当找不到压缩细化时，搜索停止。

版本2。初始模型由两个最小的网格模型组成，简化为背景，具有未知的大小和颜色，没有形状层。

使用了两种细化：（1）向网格模型（输入或输出）添加一个新对象，（2）用另一个模板（通常是值或表达式）替换模板的一部分（通常是某个未知数）。在第一种细化中，新对象可以插入到层列表中的任何位置。插入的对象可以是一个完全未指定的点或矩形：PosShape(?, Point(?)) 或 PosShape(?, Rectangle(?, ?, ?))。在输出网格模型中，插入的对象也可以是输入网格模型中的对象或形状，使用路径作为变量来引用它们：pobject 或 PosShape(?, pshape)。确实，输出网格通常会重用输入网格中的形状，要么在相同的位置，要么在要确定的不同位置。插入对输入网格的这种引用是不必要的，因为它们可以从未指定的对象中学习，但它们加速了学习。

第二种细化允许用模板t替换路径p处的模型的一部分。替换模板要么是模式，即原始值、构造器和未知数的组合；要么是使用环境变量的表达式。对于输入网格模型，它只能是模式，因为环境为空。对于输出网格模型，输入网格解析树中的每个路径都可用作环境变量。在这个版本中，我们只考虑由单个原始值或单个构造器组成的模式，所有字段都是未知数；我们只考虑整数上的表达式，形式为x, x + c, x − c, x + y, x − y，对于任何环境变量x, y，以及任何常数整数c ∈ {1, 2, 3}。当被替换的部分p是未知数时，它可以使模型更具体地适应任务。当被替换的部分是输出网格模型中的模式，并且被表达式替换时，它可以使输出网格更好地定义为输入网格的函数。总之，未知数可以被模式和表达式替换，输出网格模型中的模式可以被表达式替换。

细化的尝试性排序如下：输出形状、输入形状、输出表达式、输入表达式。在表达式中，排序是：x, x − c, x + c, x − y, x + y。

导致上述关于图1中任务的模型的压缩细化序列如下面的表格所示。归一化描述长度是在应用细化后达到的。每个细化都描述为模型路径（左侧）和模板（右侧）之间的等式。实际上，通过形状定义层的细化为该形状插入了一个新层。

在步骤1和5中，输入中引入了两个矩形对象。在步骤3中，输出中引入了一个矩形对象。结合背景网格，这足以覆盖两个网格中的所有单元格。到步骤5，因此没有空的网格增量。在步骤2和6中，输出网格的大小和颜色分别等同于底部输入形状（in.layer[1].shape.size）和顶部输入形状（in.layer[0].shape.color）。在步骤4和7中，输出形状的大小和颜色分别等同于顶部输入形状（in.layer[0].shape.size）和底部输入形状（in.layer[1].shape.color）。在步骤8中，输出形状的掩码等同于顶部输入形状的掩码（示例中始终为 Full）。在这个阶段，只需要指定输出形状的位置。步骤9-11将输出形状的位置展开为向量，并找到定义这些位置的表达式，这里是指顶部输入形状和底部输入形状之间的差异。在这个阶段，模型已经解决了任务，因为它可以为任何输入网格正确生成输出网格。步骤12-13发现所有输入形状都是完全矩形。步骤14发现输入背景颜色是黑色。其他步骤将剩余的位置和大小展开为向量，并发现所有输入网格都有12行。这是一种偶然的规律性，需要近似解析来解析测试实例，因为它有14行。

5 评估

表2报告了我们的方法在训练和评估任务上的表现（每项任务400个），针对不同版本和超时设置。超时为每个任务的学习时间设定了限制。在这两组任务中，我们提供了训练示例的表现，已知输出网格，以及测试示例的表现。在每种情况下，我们都给出了两个度量标准n1/n2：n1是所有示例都正确解决的任务数，n2是任务的部分得分总和。例如，如果一个任务有两个测试示例，只有一个被解决，得分就是0.5。

版本1。这个第一版是通过查看任务ba97ae07和b94a9452设计的。在训练任务上评估它表明，这个简单模型能够解决额外的3.5个任务：6f8cd79b、25ff71a9（2个正确示例）、5582e5ca、bda2d7a6（2个中的1个正确示例）。这个版本甚至能够解释另外3个任务的所有训练示例，因此总共有8个任务，尽管它们在相关的测试示例上失败了：任务a79310a0（3个示例）、bb43febb（2个示例）、694f12f3（2个示例）和a61f2674（2个示例）。

对于任务a79310a0，v1认识到一个形状被移动并改变了颜色，但是，尽管所有训练形状都是矩形，测试形状却不是矩形。对于任务bb43febb和694f12f3，v1找到了一些不合理的表达式来替换一些未知数，例如，用一个位置替换一些高度而不是减去一个常量的高度，或者用一个在训练示例中有效但不适用于测试示例的常数替换一些未知数。对于任务a61f2674，v1不够强大，但鉴于只有两个训练示例，它设法找到了一些特定情况的规律。

尽管在训练任务上取得了这些令人鼓舞的结果，但这个版本无法解决任何评估任务。我们想知道这是一个统计上的偶然性，还是评估任务比训练任务更难的事实。

版本1.1。表3比较了不同策略关于模型细化的结果与版本1.1。例如，第一行考虑在常数之前使用变量表达式，并按此顺序考虑细化：输入形状、输入表达式、输出形状、输出表达式。在测试中的最佳策略是 Ei-Si-Eo-So。首先细化输入模型在细化输出模型时提供了有用的参数。在插入新形状之前插入表达式有助于消除解析过程中的歧义，这通常发生在模型包含几个不特定的形状时。

成功的训练任务是ba97ae07、bda2d7a6、6f8cd79b、e48d4e1a、25ff71a9。与版本1相比，我们在bda2d7a6上通过成功解决两个测试实例改进了，并且获得了e48d4e1a。前者是通过使用掩码来解释的，后者是通过改进从网格中提取矩形来解释的。然而，我们在b94a9452和5582e5ca上失败了。在版本1中，后者是偶然成功的，前者是因为测试输入被用于训练。最后，与上一版本相比，17.3个训练实例成功，之前是9.6个。因此，总的来说，我们认为这个新版本是一个有价值的改进。

这一点通过表2得到了证实，该表显示这个新版本成功完成了4个评估任务，而上一版本一个也没有成功。

版本2。表2报告了版本2在不同超时设置下的结果。它使用贪婪搜索（Km = 1），但在每一步，它会寻找多达20个压缩细化（Kr = 20），在其中选择最佳的那个。网格解析寻找多达512个网格解析树，并只保留最佳的三个。在训练示例上不激活近似解析，并在测试示例上限制为3个差异。表2显示与以前版本相比有了显著改进，特别是在训练任务上。成功任务的数量从5个跃升到训练数据集中的24个，从4个跃升到评估数据集中的8个。这似乎证实了评估任务本质上比训练任务更复杂。由于模型的语言与版本1.1中的相同，改进主要来自于这些模型的使用和修改方式：- 使用网格解析树中的路径而不是变量名， - 在网格解析中引入非确定性， - 对候选网格解析树和细化进行排序， - 能够替换模板的任何部分，不仅仅是未知数， - 更好地定义描述长度。

更高的超时设置是必需的，因为非确定性显著增加了计算复杂性。

在60秒的超时设置下，有22个成功的训练任务，分别是：1bfc4729、1cf80156、1f85a75f、25ff71a9、445eab21、48d8fb45、5521c0d9、5582e5ca、681b3aeb、6f8cd79b、a1570a43、a79310a0、a87f7484、aabf363d、b1948b0a、b94a9452、ba97ae07、bda2d7a6、bdad9b1f、e48d4e1a、e9afcf9a、ea32f347。在120秒的超时设置下，额外成功的任务有：23581191、91714a58。尽管学到的模型并没有正确理解任务48d8fb45，但该任务是成功的。系统发现了一个可能不是任务创建者预期的相关性。在其他任务上学到的模型是恰当的，并且尽管模型语言简单，它们相当多样化。我们非正式地描述一些学到的模型来说明这种多样性。

• a79310a0。找到一个青色的矩形并将其向下移动一行。出乎意料的是，测试实例中有一个不规则形状而不是矩形。得益于近似解析，输入网格解析树包含了不规则形状的掩码，这被用来生成输出网格。

• aabf363d。在左下角找到一个任意形状和一个有颜色的点，输出与原形状相同的形状，除了颜色，颜色要与该点相同。

• b94a9452。找到一个任意形状在粉色背景上，简单地将背景颜色改为红色。

• ba97ae07。找到两个完全填充的矩形，反转层的列表：底部矩形在顶部，顶部矩形在底部。

• bdad9b1f。找到两段线，一个2x1的青色矩形和1x2的红色矩形。将每段线延伸成横跨整个网格的线，然后在两条线的交点处添加一个黄色的点。

• e48d4e1a。在10x10的黑色网格上找到两条彩色线，一个1x10的矩形和一个10x1的矩形。还找到一个右上角的灰色矩形，宽度为1。根据灰色矩形的高度H，在不同位置生成相同的线条。垂直线向左移动H列（减法），水平线向下移动H行（加法）。这涉及到计算新位置的算术表达式。

• ea32f347。找到三个灰色的完全填充的矩形，根据解析排序启发式，从大到小（顶层）到小（底层）隐式排序。用不同的颜色生成相同的矩形：顶部的变成蓝色，中间的变成黄色，底部的变成红色。

• 1cf80156。在黑色网格上裁剪任意颜色的形状。

• 1f85a75f。在黑色网格上裁剪任意颜色的形状，该网格还包含许多其他颜色的点在随机位置（一种噪声）。

• 6f8cd79b。从任意大小的黑色网格开始，生成相同大小的青色网格，并在位置(1,1)添加一个黑色矩形，其大小比网格少两行和两列。效果是在输入网格上添加了青色边框。

• 445eab21。找到两个形状，较大的一个隐式地在顶部。生成一个2x2的网格，其颜色与顶部形状相同。

- 681b3aeb。在黑色背景上找到两个形状。生成一个3x3网格，使用其中一个形状的颜色，并在(0,0)位置添加另一个形状。实际上，这两个形状互补并在3x3网格中铺开。学到的模型有效，因为评估协议允许预测三个输出网格，并且只有两种可能性，因为左上角的单元格必须属于这两个形状中的一个。此外，由于较大的形状会首先尝试，并且它占据左上角单元格的概率更高，所以在第一次尝试时有超过50%的正确机会。

- 5521c0d9。找到三个完全填充的矩形：一个黄色的、一个红色的和一个蓝色的。将它们每个向上移动，移动距离等于它们的高度。

- 5582e5ca。在3x3彩色网格上找到两个形状。生成相同的彩色网格但不包含形状。实际上，任务是识别输入网格中的主要颜色。即使模型中没有计数和多数的概念，MDL原则隐式地识别了最能压缩的主要颜色。

对于11个训练任务，该方法在所有训练实例上都成功了，尽管它在测试实例上失败了。这意味着找到了一个有效的模型，但它不能泛化到测试实例。以下是泛化失败的一些原因：

- 在常数和变量之间做出错误的选择，并发现偶然的算术等式（例如，0962bcdd）；

- 形状的错误分割，例如偏好完全矩形而不是不规则形状（例如，1caeab9d）；

-应该在测试实例中多次执行转换，而在所有训练实例中一次就足够了（例如，29c11459）；

- 通过网格旋转或网格置换保持不变性（例如，4522001f）。

版本2.1, 2.2。这个版本对模型只带来了一些变化，但它显著提高了解析网格的效率，这是学习模型的主要成本。表2显示，我们在30秒内取得了与120秒内相似的结果。由于更好的层次堆栈解析策略，每个网格的解析树数量限制从512降低到64。

为了记录，与版本2相比的主要变化如下：– 区分形状和对象以更好地表示对象移动， – 更丰富的掩码集（边框、棋盘格和十字形）， – 零作为一个无元运算符，以避免表达式如e1 − e1， – 小部分可以被视为相邻点， – 解析层次堆栈时更好的策略， – 归一化描述长度，以平衡输入和输出相对于网格大小， – 将输入形状和对象插入输出模型， – 优化以减少超时。

与版本2相比，在60秒内新增解决的7个训练任务是：08ed6ac7, 23581191, 72ca375d, 7e0986d6, a61ba2ce, be94b721, ddf7fa4f。在两个带星号的任务中，学习到的模型不够精确，但由于系统允许进行三次尝试，并且只有少数阅读选项，它找到了正确的答案（并没有真正理解为什么）。例如，在任务72ca375d中，输入网格有三个对象，而输出网格只有一个，即具有对称性的那个。我们的系统只理解输出选择了输入对象，并为每个对象尝试了一次。

6 讨论与展望

我们已经证明，结合描述性网格模型和MDL原理是应对ARC挑战的一种可行且令人鼓舞的方法。与其他方法不同，它侧重于网格的内容，而不是从输入网格到输出网格的转换。实际上，我们的学习算法甚至不试图从输入网格预测输出网格，只是寻找一对网格的简短联合描述，仅假设输出网格可能依赖于输入网格。输出网格的预测只是副产品。学习到的模型也可以用来创建新的示例。

我们认为，这使我们的方法更加健壮和可扩展，并且在认知上更有说服力。通过不同版本的进步更多地与改进总体方法有关，而不是与模型类别有关。事实上，从第一个版本到现在（彩色背景上的点堆栈和盒装形状，加上非常简单的算术），模型并没有太大变化。改进的关键在于灵活性。灵活性主要体现在解析过程中通过非确定性和近似。为了应对由此带来的复杂性，MDL原理似乎是选择最可信的解析，即描述长度最短的解析，至关重要。因此，MDL原理在两个层面上使用：在底层用于解析网格，在高层用于选择模型细化。

我们惊讶地发现，在评估任务上的结果远远低于训练任务。之前也有过同样的观察[4]。我们没有查看评估任务，正如ARC的设计者建议的那样，以避免在我们的方法中包含ARC特定的先验知识。我们怀疑评估任务的网格更大或更复杂，因为每个任务的运行时间更长。我们也怀疑它们需要更困难的泛化，因为这是F. Chollet提出的智力衡量的关键因素。

我们相信，我们的方法可以解决更多的任务，因为当前的网格模型相当简单。首先，只涵盖了少数核心人类先验。其次，许多任务涉及相对简单的全网格转换（例如，旋转、对称）。这些通常是基于转换的方法可以解决的任务，但我们的模型还无法解决。另一个重要的限制是，当一个网格包含一个大小可变的对象集合，每个对象都需要以相同的方式处理时。这需要模型中某种形式的循环。