Domain-Specific Language for theAbstraction and Reasoning Corpus
https://github.com/michaelhodel/arc-dsl/blob/main/arc_dsl_writeup.pdf
答案见第二部分
一
1 引言
1.1 抽象与推理语料库
抽象与推理语料库（ARC）[1] 是一个数据集，旨在作为通用人工智能基准，与论文《论智能的衡量》[2] 一同发布。ARC 包含 1000 个任务，其中 800 个是公开的（400 个作为训练集，400 个作为评估集），200 个是私有的，用作隐藏测试集。每个任务由大约几个示例组成，每个示例由一个输入网格和一个输出网格组成。对于每个示例，输出网格是通过对输入网格应用特定任务的转换而得到的结果。测试者的目标是根据少数示例推断出转换，并在测试示例上成功应用该转换，其中输出是缺失的。尽管这个领域受到限制（即每个像素仅允许使用 10 种不同颜色中的一种，且分辨率最多为 30 x 30），但允许的任务非常广泛。ARC 任务涵盖了从对象性、算术、几何等广泛的概念[2]，从简单的转换（如网格的镜像和旋转）到更复杂的转换（涉及对象检测和条件性应用操作，如对象移动、修改或移除）。
大多数 ARC 任务成年人可以轻松解决，但到目前为止，没有当前的计算机程序显示出太多希望：在 2020 年的 Kaggle 竞赛[3]中，近 1000 个参赛队伍中，只有十几个队伍在排行榜上的任务准确率超过了 10%。只有获胜者超过了 20% 的标记。特别是当前的标准机器学习技术表现不佳。许多当前的顶级尝试遵循 François Chollet 建议的程序合成方法，即创建一个能够表达任何 ARC 任务解决方案程序的领域特定语言（DSL），然后通过搜索 DSL 组件的组合来构建候选程序。这种性能差异主要是因为 ARC 侧重于广泛的泛化（即 ARC 表现出极大的任务多样性）和少样本学习（即每个任务只有非常少的示例），因此 ARC 本身并不适合机器学习技术。
1.2 动机与概述
主要目标是构建一个简洁的领域特定语言（DSL），为未来在 ARC 上的工作打下坚实的基础，该 DSL 能够编写简短的程序来解决 ARC 任务。希望实现这一目标的动机是相信这样的 DSL 可以为后续工作奠定重要的基础。在我看来，ARC 可以被视为一个搜索问题，通过在正确的领域（如一个好的 DSL）内工作，可以将其映射到一个显著更容易的搜索问题。
1.2.1 创建 DSL
要创建的领域特定语言应满足两个主要的高层次目标：
- 它应当在表达能力上足够强大，即对于大多数可想象的 ARC 任务，存在且仅存在 DSL 中可表达的程序。
- 它应当是抽象和通用的，即它定义的原语数量较少，并且每个原语对许多 ARC 任务都有用。
第一个目标的原因是，对于一个应该有潜力全面解决 ARC 的语言来说，这是一个必要条件。第二个目标的原因是为了限制对训练任务的过拟合，并允许简洁的任务解决方案程序，这也是任何程序合成方法的必要条件。
DSL 将遵循完全函数式的方法，依赖于简单的类型，而不是定义自定义类。DSL 的组件（也称为原语或函数）大致可以分为属性函数、转换函数和辅助函数。
1.2.2 构建求解器
创建任务求解程序的原因有很多，最重要的包括：它极大地促进了 DSL 的开发，在一定程度上可以作为 DSL 的测试，即概念验证，有助于更好地理解 ARC，从而间接有助于设计程序合成方法，提供统计数据，这些数据可以直接用于约束或指导搜索，并可能作为未来工作的基础，例如数据增强或生成新的 ARC 任务。
目标是仅使用 DSL 函数和每个函数仅使用少量调用来创建 ARC 训练任务的求解器（即任务求解程序）。因此，不允许使用 DSL 之外的其他构造（如 for 循环或 if 语句），并且每个求解器中 DSL 函数的出现次数应较少，即大约十几个或理想情况下甚至只有几个。
1.2.3 改进 DSL 和求解器
由于为固定的 DSL（尚未使用过）创建求解器或使用固定的求解器集重构 DSL 是不可行的，因此对 DSL 的工作以及实现求解器将不可避免地是一个迭代的手把手过程。目标是首先实现一组被认为合理且普遍有用的 DSL 组件，而不考虑具体任务。接下来，在不修改 DSL 的第一个版本的情况下，为训练任务的一个小子集构建求解器。随后，通过使用启发式方法交替改进 DSL 和求解器，例如：
- 当 DSL 组件的使用频率太低甚至不存在，其功能被认为过于特定，其签名过于复杂，或者其功能可以很容易地表示为其他 DSL 组件的简短组合时，移除这些 DSL 组件。
- 当它们对应于求解器中非常频繁使用的现有函数的组合，需要消除使用非 DSL 构造，或者允许编写（显著）更短的求解器时，添加 DSL 组件。
2 领域特定语言
2.1 工作流程
在充分理解 ARC 任务的精神后，我构建了 DSL 的初稿，主要通过查看任务并思考如何编写代码来解决它们。首先进行了一些浅显的现有 DSL 调查——首先是为了大致了解其他人如何进行，并且只进行了浅显的调查，以避免在某个可能次优的方向上受到太强烈的引导。这个 DSL 的第一次迭代是在不查看单个任务的情况下创建的，目的是避免引入可能过于特定于单个任务的 DSL 原语。几乎任何被认为对 ARC 有潜在用处的函数都被实现了。
在下一步中，解决了前几十个 ARC 训练任务：对于一些相对直接的任务，实现了求解器，同时尽量主要使用现有的 DSL 原语，并尽可能少地使用本机构造（如循环或分支）。求解器表示一个特定于任务的程序，可以正确地将给定任务的每个示例的输入网格转换为输出网格。由于 DSL 的初期状态，许多任务被跳过，只有少数任务仅使用 DSL 函数实现。偶尔，如果它们在多个任务中的有用性变得足够明显（因此其功能足够通用），则会添加新的 DSL 原语。记录了关于缺少或冗余功能的观察结果。
在第三步中，对 DSL 进行了彻底修订。许多原语要么被简化，要么变得更通用，或者在过于冗余或使用频率太低时被移除。例如，对于许多谓词，存在表示相反条件的冗余原语，如“按条件过滤容器中的每个元素”和“按条件的否定过滤容器中的每个元素”，这与保持 DSL 简单不符。因此，这些对应的原语被移除，而是添加了一个简单的辅助原语，它只是否定，因此允许通过函数组合实现相同的功能。添加了许多原语，因为它们被认为通用且有用，即允许解决以前具有挑战性的任务，或减少甚至避免在求解器中使用非 DSL 构造。随着进展的继续，添加 DSL 原语的需求变得显著减少，并且——除了拥有更好的 DSL 外，还由于对 DSL 和 ARC 任务风格的熟悉——完全在 DSL 内编写求解器变得容易得多。
最终，我为整个 400 个训练任务编写了完全在 DSL 内的求解器。与许多其他工作一样，少数任务导致了大部分工作。对于许多任务，编写求解器程序非常直接，只需几分钟，但对于一些任务，这是一个非常具有挑战性和漫长的过程，主要不是由于缺乏如何首先编写解决任务的程序的良好概念，而是由于必须编写仅使用 DSL 原语的程序，因此灵活性有限。在构建此类求解器的原因中提到的那些原因中，这样做（即解决所有训练任务）是为了更有力地证明 DSL 的充分性和一个相对小且通用的 DSL 能够编写大部分简洁的求解器程序的能力。
2.2 设计原则
在这里，我打算概述在构建 DSL 时遵循的设计原则。我尝试遵循的主要设计原则是：
- 坚持函数式和基于类型的设计，即没有自定义类，例如存储对象的一堆附加属性的“对象”类，或考虑对象周围上下文信息的类：网格只是一个整数向量的向量，对象只是一个属于对象的单元格（像素）的集合，其中每个单元格再次表示为一个元组，其中第一个条目对应于颜色，第二个条目对应于单元格的位置；
- 编写抽象函数，即抽象掉细节：例如，“形状”或“出现的颜色集合”的概念对网格和网格上的对象都有效，因此这些原语应该能够接受其中任何一种类型作为参数；
- 编写通用函数，即尽量减少仅用于编写求解器的 DSL 原语。（请注意，在某些情况下，即使函数被认为足够通用，但由于偶然或后期引入，尽管如此，它们的使用频率仍然很低，因此有些例外情况）；
- 强制简单的函数签名，即函数接受的参数数量应较少，并且它们应始终只返回一个实体。
- 约束到简单类型，即只有少量不同的类型，如“网格”或“对象”或“整数”；
- 避免冗余，即具有可以非常简洁地表示为其他 DSL 原语组合的 DSL 原语。（请注意，在某些情况下，某些 DSL 原语的特定组合使用频率非常高，因此有些例外情况）。
DSL 的开发在某种程度上是测试驱动的，即每个原语都有一些相应的单元测试，这些测试作为健全性检查，并使开发更加健壮。事实上，拥有测试对于重构非常有用。
2.3 结果
2.3.1 概述
DSL [4] 可以分为三个大致相等大小的原语类别：
- 转换：转换网格或对象的函数，例如调整大小、镜像、旋转、重新着色、移动、删除等；
- 属性：提取实体某些特征的函数，例如最左侧被占用的单元格、质心、形状、大小、对象是否为线、正方形等；
- 工具：实现集合操作（例如差集、并集、交集、插入、移除）、算术操作（例如加法、减法、乘法、整数除法）或提供各种辅助功能的函数（例如过滤、函数组合、参数绑定、分支、容器合并）。
请注意，这种分类既不是有意的（这只是为了提供概览，而不是按设计进行的细分），也不清晰（少数原语可能不适合任何类别，并且许多原语可以被认为属于多个类别）。
2.3.2 类型
原语主要在简单且通常是自定义的类型上工作。固定允许的类型并保持它们受约束的目标是多方面的，例如允许注释 DSL 原语（在搜索求解器的 DSL 原语组合的上下文中非常有用，几乎是必要的），限制可能出现的值的空间，更好地结构化和概览代码，更好地理解有用的抽象层次等。类型是使用 Python 的 typing 模块构建的。仅使用可哈希类型的动机（例如使用 FrozenSet 而不是 Set 或 Tuple 而不是 List）是这允许在无序容器中嵌套容器（例如一组对象），这提供了更大的灵活性，以及例如在搜索过程中在字典中进行更快的查找。请注意，有些是不可约的基本类型，如整数或布尔值，有些只是更简单类型的容器（例如对象作为类型对象的项目的容器）。因此，有许多自然的父子对应关系（即“容器中元素的类型”-“容器的类型”），例如整数-整数集、对象-对象集等。拥有这些对应关系对于程序合成也很有用，因为它例如允许根据提供的输入值的类型推断函数的特定返回类型（注释为返回通用容器）（例如考虑 argmax）。选择避免字典类型的原因主要是简单性和事实，即不需要它，即有简单的解决方法，加上可哈希字典不容易支持。类似地，浮点数也不支持，主要是由于简单性，而且由于它们在极少数情况下（考虑到 ARC 的离散性质）才有用，即使在那些情况下也可以找到解决方法。
同时拥有元组和集合的原因是顺序有时很重要（例如 (x, y) 坐标），并且集合操作是方便的内置操作，这是一个早期设计选择。然而，事后看来，选择仅有序容器（元组）带来的更少且更一致的类型的优势可能值得偶尔更简洁或更快的代码的权衡。当选择为 Cell（IntegerTuple）、Object（Indices）和 Objects（IndicesSet）使用相关类型时，也做出了类似的权衡：当颜色不重要或颜色的概念无意义时（例如表示移动方向或网格或对象形状的 (x, y) 向量），不需要它，因此可以通过不处理它们来简化原语。然而，这引入了一些冗余；如果我要（或一旦我将）重构 DSL，很可能会去掉 Indices 和 IndicesSet 作为类型（但保留 IntegerTuple 类型）。
总共有 56 种不同的输入签名（即形式为（“第一个参数的类型”，“第二个参数的类型”等的元组）。最常见的输入签名只接受一个补丁、网格、片段或数值，或两个补丁，或一个容器和一个可调用对象等。总共有 160 个原语（见表 2、3、4、5、6），其中 79 个接受一个参数，67 个接受两个参数，13 个接受三个参数，只有一个（即对象检测函数）接受四个参数，没有原语接受超过四个参数。在 20 种定义的类型中，18 种至少出现一次作为返回值类型；最常见的是网格、整数、索引和布尔值。
2.3.3 对象性
虽然并非每个 ARC 任务都依赖于在对象级别上工作（例如，有些任务在像素级别上处理更好，有些在网格级别上处理更好），但对象的概念是核心。我的 DSL 有一个主要原语用于从网格中提取一组对象，对象原语的参数如下：
- 网格：从中提取对象的网格。
- 单值：属于同一对象的单元格是否只允许一种颜色（或者它们是否可以是不同颜色）。
- 对角线：单元格是否需要与对象中的至少一个单元格直接相邻才能属于该对象（或者是否允许它仅对角相邻）。
- 背景：背景颜色（定义为最常见的颜色）的单元格是否也属于对象（或者它们是否被忽略）。
还有两个进一步的原语提取对象，并将每对颜色相同的单元格视为同一对象的一部分（一个考虑背景颜色，一个忽略背景颜色）。这允许种不同的对象概念。对象原语是最常用的原语之一，使用了 248 次，并在超过 50% 的任务中使用。尽管它们相当原始和有限，即有些受限，但它们在大多数情况下被证明是足够的，对于少数不够的情况，有解决方法（例如，有些情况下，区分对角相邻和直接相邻的单元格的概念不够充分，因为最好指定同一对象的两个单元格之间的最大允许距离）。可以想象一个在许多方面更优雅的通用对象检测函数，例如一个原语，它接受一个网格和一个布尔函数，该函数接受两个单元格（即两个颜色和位置的元组），返回一个布尔值，指示两个单元格是否应属于同一对象。但当然，即使这样的原语也不能检测任意对象，因为有些更高级的情况，对象之间的边界非常难以自动检测，并且不一定仅取决于单元格之间的颜色或距离。
提取对象的代码工作如下：它遍历网格中的所有像素。每当一个像素已经被另一个对象占用或该像素的颜色是背景值（并且背景颜色不是允许的对象颜色）时，该像素被忽略。否则，初始化一个对象，首先只包含当前像素。然后，对象通过反复插入所有满足条件的相邻像素（并且尚未标记为属于当前或之前的对象）来增长，直到没有更多的相邻像素。
2.3.4 示例
以下是一个求解器的示例，旨在展示简单 DSL 原语的简单组合如何表达几乎任意的程序。
2.3.5 概念验证
作为一个概念验证，DSL 被用于解决 400 个训练任务 [5]。我为创建求解器设定的规则如下：每个任务都有一个求解器，求解器是特定于任务的函数，它将该任务的任何示例的输入网格作为单个参数，并返回正确的相应输出网格。唯一允许的操作是将函数调用的结果存储在变量中，其中所有参数必须是输入网格、一些常量（如整数或表示方向的常见向量）或同一求解器中先前计算的变量，并且每个被调用的函数必须是 DSL 原语或同一求解器中先前构造的变量。这也意味着每行代码都必须是一个函数调用。这种编程风格相当不寻常，但允许更容易的分析（例如，对于严格格式的代码，构造控制流图或分析原语的使用频率要容易得多）。
目标是尽量减少求解器的长度，即函数中的代码行数（但不是全局性的，因为这与 DSL 的复杂性有折衷，即可以通过简单地构造相应的 DSL 原语来欺骗每个任务的最小程序长度，从而完全违背目的）。这是通过迭代实现的，如前所述，在实现和改进现有求解器以及修改 DSL 之间进行迭代。一些用于编写更简洁求解器的技术例如是将求解器中非常频繁的代码段提升到 DSL 中，或半自动地尝试检测重构的潜力。
在这方面，遵循了“更短更好”的原则，并相应地设计了 DSL，在知道找到更短的程序更有可能，以及更短的程序不太可能过拟合任务的情况下：想象一个任务，其中每个输入网格都有一个对象，该对象总是向右移动一个常数 k，碰巧对于所有示例，k 也与对象的宽度相同。在这种情况下，按常数移动和按宽度移动都会给出有效的程序，但如果测试示例的输入网格的对象宽度不同，则可能会失败。当然，也可能是相反的情况，即任务的意图是“按对象的宽度移动”，但前者可以说更容易，因此更有可能是“正确的”。这触及了“过度确定”任务的重要主题，即找到一个成功解决所有训练示例但未能解决（部分）测试示例的程序。鉴于 ARC 的性质（即规则由自然语言描述，这是模糊的），不可能证明一个在训练示例上工作的程序是“正确的”，因为这种正确性的概念不存在。然而，如果 ARC 创建者提供了一个有能力的 DSL 以及一个程序复杂度的度量标准，并声称“解释所有训练示例的最不复杂的程序在定义上是正确的”，那么这种正确性的概念就会存在。幸运的是，尽管这是我担心在搜索程序时可能成为问题的事情，但事实证明这几乎不是一个问题，因为在绝大多数情况下，找到的解决训练示例的程序也能解决测试示例——这要么证明了 François 的工作质量（或者，也是我的 DSL 的质量）。
我为自己设定的一个目标是尽可能多的任务使用最多十个原语（即代码行）。最终，这实现了 400 个任务中的 235 个（其中 79 个在最多 5 个函数调用中解决）。此外，78 个程序超过 20 行，只有三个超过 50 行。
2.4 局限性
肯定有一些原语，人们可以想到它们相当通用且有用，但目前不属于 DSL。例如，人们认为像操作符累加或递归（其中递归深度无法提前识别）这样很少发生的事情目前无法在 DSL 中简洁地表达，而是只能通过例如大量分支来区分情况来实现。此外，有许多操作理想情况下应该被泛化：目前，为网格实现的旋转、修剪或分割等操作与补丁不兼容，尽管从概念上讲它们同样适用于补丁，并且也可能有用。此外，依赖于整数元组（例如表示偏移、方向或轴）的操作的设计原则并不统一：对于一些操作，如镜像、移动、绘制线条等，轴或方向通过提供一个整数元组作为参数来指示，而在其他情况下，可以通过类似的函数签名覆盖，有多个原语，每个方向或轴一个，例如检索对象的角。这种差异主要是由于两种情况中哪一种被认为允许更短的求解器程序。然而，可以想象一个更通用的设计，其中这些功能总是一个原语，接受一个额外的参数。这不仅会使 DSL 更简洁、更少冗余，而且允许一些程序控制流更自然的情况，例如可以直接推断方向向量并将其传递给原语，而不是必须使用分支来选择相应的方向或轴特定的原语。还有许多这样的权衡，更好的设计选择并不简单。
此外，类型中存在一些冗余：无序容器（如集合）实际上并不需要，它们只是一个早期设计选择，因为集合操作在编程语言中已经存在。像交集和只允许唯一元素这样的概念显然也可以很容易地通过有序容器（如元组）来支持。
此外，求解器中使用了两个设计原则：一个是在大多数计算中对有序容器应用函数，另一个是主要构造函数，然后只应用一次构造的函数。这也可以统一。远离构造函数将具有更简单的程序控制流的优点，远离向量化操作将具有允许对求解器使用的子程序进行更大直接洞察的优点，例如可以更容易地调查诸如“求解器中构造的函数的分布是什么？”这样的问题。
还应注意的是，预定义的类型并未严格遵循，即一些子类型在求解器中使用，但未在类型集中指定：例如，有时使用了一组函数，代码允许这样做，因为一些原语接受通用容器作为参数，但是“函数容器”并未在定义的类型中明确列出。理想情况下，人们会更严格地约束允许的类型，即强制每个原语的参数为预定义类型。
参考文献
1. Chollet, F. The Abstraction and Reasoning Corpus (2019).
2. Chollet, F. On the Measure of Intelligence (2019).
3. Kaggle. Abstraction and Reasoning Challenge (2020).
4. Hodel, M. DSL for ARC (2023).
5. Hodel, M. Solver Programs for the ARC Training Tasks (2023).
二
答案 demo:
热门跟贴