ARC 400題的DSL答案

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: