MADIL: An MDL-based Framework for EfficientProgram Synthesis in the ARC Benchmark

MADIL：一種基于MDL的ARC基準(zhǔn)高效程序合成框架

https://arxiv.org/pdf/2505.01081

摘要

人工智能（AI）在專門任務(wù)中取得了顯著成功，但在技能的高效獲取和泛化能力方面仍面臨挑戰(zhàn)。“抽象與推理語料庫”（ARC）基準(zhǔn)測(cè)試通過要求極少的訓(xùn)練數(shù)據(jù)來評(píng)估智能水平。盡管近年來大語言模型（LLMs）在ARC任務(wù)上的表現(xiàn)有所提升，但它們依賴于大量的預(yù)訓(xùn)練和高昂的計(jì)算成本。我們提出了MADIL（基于MDL的人工智能），這是一種新穎的方法，利用最小描述長(zhǎng)度（MDL）原理實(shí)現(xiàn)高效的歸納學(xué)習(xí)。MADIL執(zhí)行基于模式的分解，從而實(shí)現(xiàn)結(jié)構(gòu)化泛化。雖然其在ArcPrize 2024中的表現(xiàn)（7%）仍低于基于LLM的方法，但它具有更高的效率和可解釋性。本文詳細(xì)介紹了MADIL的方法論、其在ARC任務(wù)中的應(yīng)用以及實(shí)驗(yàn)評(píng)估結(jié)果。

關(guān)鍵詞：人工智能，歸納學(xué)習(xí)，程序合成，最小描述長(zhǎng)度，抽象與推理語料庫，基于模式的分解

1. 引言

在過去十年中，人工智能（AI）在專門任務(wù)中取得了顯著成功，在圖像識(shí)別[1]和棋盤游戲[2]等領(lǐng)域常常超越人類表現(xiàn)。然而，盡管取得了這些進(jìn)展，AI 在泛化能力和適應(yīng)新任務(wù)方面仍存在局限，尤其是在僅需少量訓(xùn)練的情況下——這是人類智能的顯著特征。為了推動(dòng) AI 超越狹義任務(wù)特定泛化的發(fā)展 [3]，F(xiàn). Chollet 提出了一種新的智能衡量標(biāo)準(zhǔn)，該標(biāo)準(zhǔn)優(yōu)先考慮技能獲取效率而非技能執(zhí)行表現(xiàn) [4]。在這個(gè)框架下，智能被定義為一個(gè)智能體在多種任務(wù)中達(dá)到勝任所需的先驗(yàn)知識(shí)和經(jīng)驗(yàn)量，而不是其在任何單一領(lǐng)域中的峰值表現(xiàn)。

為了實(shí)證評(píng)估這一智能概念，Chollet 提出了“抽象與推理語料庫”（ARC，也稱為 ARC-AGI），這是一個(gè)設(shè)計(jì)為心理測(cè)量測(cè)試的基準(zhǔn)，用于評(píng)估和比較人類與機(jī)器智能。ARC 包含一系列任務(wù)，要求基于非常有限的輸入-輸出示例（平均約 3.3 個(gè)）學(xué)習(xí)彩色網(wǎng)格的變換規(guī)則。圖 1 和圖 2 展示了兩個(gè) ARC 任務(wù)樣例，其中第二個(gè)例子將在本文中作為貫穿全文的運(yùn)行案例。

“抽象與推理語料庫”（ARC）對(duì) AI 系統(tǒng)提出了重大挑戰(zhàn)。雖然人類可以解決超過 80% 的任務(wù) [5]，但 AI 表現(xiàn)遠(yuǎn)遠(yuǎn)落后。Kaggle 2020 比賽的獲勝者1 僅能解決 20% 的任務(wù)，并嚴(yán)重依賴硬編碼的基本操作和暴力搜索方法。隨著大型語言模型（LLMs）用于預(yù)測(cè)缺失網(wǎng)格的應(yīng)用，由 J. Cole 在 MindsAI 開創(chuàng)的方法帶來了重大突破。這項(xiàng)創(chuàng)新使 ARC 表現(xiàn)迅速提升：在 ARCathon 20232 上達(dá)到 30%，在 ArcPrize 20243 上達(dá)到 55%。到 2024 年底，OpenAI 的 o3 推理 LLM 實(shí)現(xiàn)了類人水平的表現(xiàn)，盡管計(jì)算成本極高——運(yùn)行高計(jì)算版本時(shí)每個(gè)任務(wù)的推理成本高達(dá)數(shù)千美元。

盡管取得了這些進(jìn)展，基于 LLM 的方法仍然依賴于數(shù)百萬合成任務(wù)的大量預(yù)訓(xùn)練，并且在推理過程中需要大量的計(jì)算資源進(jìn)行微調(diào)和推理。因此，高效技能獲取的挑戰(zhàn)仍未得到根本解決。2025 年 3 月，一個(gè)新的基準(zhǔn)版本 ARC-AGI-24 被推出，以進(jìn)一步推動(dòng) AI 研究。雖然大多數(shù)人類解題者仍能輕松應(yīng)對(duì)，但 ARC-AGI-2 對(duì) LLM 來說難度顯著增加——o3 的成功率下降至僅幾個(gè)百分點(diǎn)。

在本文中，我們介紹了 MADIL，一種針對(duì) ARC 基準(zhǔn)的替代方法。MADIL 是一個(gè)從少量輸入-輸出示例中進(jìn)行歸納學(xué)習(xí)的通用框架。雖然我們主要關(guān)注其在 ARC 中的應(yīng)用，但該方法也已成功應(yīng)用于字符串到字符串轉(zhuǎn)換任務(wù)，如 FlashFill [6] 中的任務(wù)。MADIL（MDL-based AI，即基于最小描述長(zhǎng)度的人工智能）建立在信息論中的最小描述長(zhǎng)度（MDL）原理之上——該原理指出：“能夠最好地描述數(shù)據(jù)的模型就是壓縮效果最好的模型” [7, 8]。本質(zhì)上，MADIL 尋找既能簡(jiǎn)潔解釋給定示例又能良好泛化的任務(wù)模型。在推理階段，MADIL 通過基于模式的分解，自上而下地將輸入拆解為有意義的子組件，然后自下而上構(gòu)建對(duì)應(yīng)的輸出。在學(xué)習(xí)過程中，它識(shí)別輸入和輸出的最佳分解方式，并確定各對(duì)應(yīng)部分之間的變換關(guān)系。這種方法的關(guān)鍵優(yōu)勢(shì)在于 MDL 原則引導(dǎo)分解過程——傾向于實(shí)現(xiàn)更高壓縮率的表示——同時(shí)也簡(jiǎn)化了殘差部分之間的變換，使其更容易學(xué)習(xí)。

盡管 MADIL 的整體表現(xiàn)仍低于當(dāng)前最先進(jìn)的方法——從 ARCathon 2022 的 2% 提升到 ArcPrize 2024 的 7% ——但其基于 MDL 的搜索非常高效，能夠在一分鐘內(nèi)（單 CPU 上）發(fā)現(xiàn)復(fù)雜模型。與進(jìn)行廣泛但淺層探索的暴力搜索方法不同，MADIL 進(jìn)行的是窄而深的搜索，大多數(shù)解決方案在首次探索路徑早期就能找到。與基于 LLM 的方法相比，MADIL 不需要生成合成任務(wù)或數(shù)據(jù)增強(qiáng)。相反，它利用核心知識(shí)先驗(yàn)，將其編碼為一組基本操作、模式和函數(shù)。雖然這些基本操作是面向特定領(lǐng)域的——設(shè)計(jì)用于處理彩色網(wǎng)格推理——但其中許多具有廣泛的適用性，超出了 ARC 任務(wù)本身。例如包括算術(shù)運(yùn)算、位運(yùn)算、幾何變換以及集合操作等，使得 MADIL 成為一種比數(shù)據(jù)密集型深度學(xué)習(xí)方法更結(jié)構(gòu)化、更具可解釋性的替代方案。

本文大幅擴(kuò)展了我們之前關(guān)于 MADIL 的研究 [9, 10]，提供了更深入的解釋，展示了一個(gè)更先進(jìn)的 ARC 解決方案，并引入了多項(xiàng)新貢獻(xiàn)。第 2 節(jié)快速概述 ARC 基準(zhǔn)；第 3 節(jié)討論相關(guān)工作，涵蓋現(xiàn)有 ARC 方法及程序合成領(lǐng)域的更廣泛研究；第 4 節(jié)通過一個(gè)具體任務(wù)示例介紹我們的方法；第 5 節(jié)形式化 MADIL 的一般理論框架并展示其在 ARC 中的應(yīng)用；第 6 節(jié)描述關(guān)鍵算法及其他實(shí)踐細(xì)節(jié)；第 7 節(jié)介紹 MADIL 的三項(xiàng)最新改進(jìn)：(1) 集合管理的整合，(2) 依賴模式的使用，(3) 使用蒙特卡洛樹搜索（MCTS）來改進(jìn)貪心搜索；第 8 節(jié)報(bào)告實(shí)驗(yàn)結(jié)果，評(píng)估 MADIL 的性能、效率和局限性；最后，第 9 節(jié)總結(jié)我們的研究成果，并展望未來的研究方向。

2. 抽象與推理語料庫（ARC）

ARC 是一組任務(wù)集合?，其中每個(gè)任務(wù)都包含訓(xùn)練樣例（平均約 3.3 個(gè)）和測(cè)試樣例（通常為 1 個(gè)）。每個(gè)樣例由一個(gè)輸入網(wǎng)格和一個(gè)輸出網(wǎng)格組成。每個(gè)網(wǎng)格是一個(gè)二維數(shù)組（最大尺寸為 30x30），其中填充的整數(shù)代表顏色編碼（共有 10 種不同的顏色）。對(duì)于給定的任務(wù)，網(wǎng)格的大小在不同樣例之間可能不同，輸入和輸出之間的尺寸也可能不同。

每個(gè)任務(wù)都是一個(gè)機(jī)器學(xué)習(xí)問題，其目標(biāo)是學(xué)習(xí)一個(gè)模型，能夠根據(jù)輸入網(wǎng)格生成輸出網(wǎng)格，而且只能基于少量的訓(xùn)練樣例進(jìn)行學(xué)習(xí)。只有當(dāng)預(yù)測(cè)的輸出網(wǎng)格在所有測(cè)試樣例中都與預(yù)期網(wǎng)格完全相同時(shí)，預(yù)測(cè)才算成功，不存在部分正確的情況。然而，為了補(bǔ)償訓(xùn)練樣例中可能存在的歧義，每個(gè)測(cè)試樣例允許最多三次嘗試?來獲得正確結(jié)果。

圖 2 展示了一個(gè) ARC 任務(wù)，該任務(wù)將在下文中作為貫穿全文的示例使用。需要預(yù)測(cè)的網(wǎng)格位于右下角的位置。

ARC 總共包含 1000 個(gè)任務(wù)：其中 400 個(gè)是“訓(xùn)練任務(wù)”?，400 個(gè)是評(píng)估任務(wù)（也稱為公開任務(wù)），還有 200 個(gè)是用于獨(dú)立評(píng)估的隱藏任務(wù)。在這些隱藏任務(wù)中，有 100 個(gè)組成了所謂的“私有集”（private set），該集合曾用于 2020 至 2024 年的各項(xiàng)挑戰(zhàn)賽（如 Kaggle、ARCathon 和 ArcPrize）；其余的則被稱為“半私有集”（semi-private set），用于評(píng)估專有的 LLMs（見 ArcPrize）。

開發(fā)者應(yīng)僅查看訓(xùn)練任務(wù)，而不應(yīng)查看評(píng)估任務(wù)。后者僅用于評(píng)估所開發(fā)系統(tǒng)的廣泛泛化能力。

3. 相關(guān)工作

早期對(duì) ARC 的研究方法定義了一種程序的 DSL（領(lǐng)域特定語言）——基于函數(shù)組合——該語言能夠?qū)⑤斎刖W(wǎng)格轉(zhuǎn)換為輸出網(wǎng)格，并在訓(xùn)練樣例中搜索正確的程序。這些方法的主要區(qū)別在于原始函數(shù)（先驗(yàn)知識(shí)）和搜索策略的不同。

暴力搜索取得了一定成功——這是 Kaggle 2020 冠軍（Icecuber）和 ARCathon’22 冠軍（Michael Hodel）所采用的方法——但這不能成為解決 ARC 和通用人工智能（AGI）問題的最終方案。為了在龐大的程序空間中進(jìn)行有效搜索，其他方法使用了語法進(jìn)化 [11]、神經(jīng)網(wǎng)絡(luò) [12, 13]、哈希與禁忌列表進(jìn)行搜索樹剪枝 [14]，或通過已解決任務(wù)訓(xùn)練的隨機(jī)搜索 [15]。

一個(gè)難點(diǎn)在于，輸出網(wǎng)格通常僅用于對(duì)候選程序打分，因此搜索過程是“盲目的”。Ouellette [13] 和 Alford [12] 通過神經(jīng)引導(dǎo)搜索改進(jìn)了這一點(diǎn)，在選擇搜索步驟時(shí)考慮輸出網(wǎng)格；Xu [14] 則將生成中的網(wǎng)格與預(yù)期網(wǎng)格進(jìn)行比較。然而，這種方法假設(shè)輸出網(wǎng)格可以與輸入網(wǎng)格進(jìn)行比較，而并非所有任務(wù)都滿足這一前提。

基于函數(shù)的 DSL 方法存在擴(kuò)展性問題，因?yàn)樗阉骺臻g隨著原始函數(shù)數(shù)量呈指數(shù)增長(zhǎng)。因此，搜索深度通常被限制在 3 或 4 層以內(nèi)。Ainooson [15] 通過定義體現(xiàn)專門搜索策略的高層函數(shù)緩解了這一問題。

大多數(shù)基于 DSL 設(shè)計(jì)與搜索的方法在公開集和私有集上的得分均低于 10%，唯一的顯著例外是 Icecuber 在 Kaggle 2020 上取得了 20.6% 的成績(jī)。其成功的關(guān)鍵因素之一是對(duì)輸出網(wǎng)格進(jìn)行分解，通過堆疊從輸入網(wǎng)格計(jì)算出的大規(guī)模組件庫中提取的圖層來實(shí)現(xiàn)。

后來的方法開始使用大型語言模型（LLM）生成輸出網(wǎng)格或變換程序，取得了重大進(jìn)展：在 ARCathon’23 上達(dá)到 30%，在 ArcPrize’24 上達(dá)到 55%。實(shí)際上，像 GPT-4o 這樣的通用 LLM 在 ARC 任務(wù)上表現(xiàn)不佳。由 MindsAI 開創(chuàng)的方法是合成大量類似 ARC 的任務(wù)，并在這些任務(wù)上訓(xùn)練專用的 LLM。

另一個(gè)關(guān)鍵要素是測(cè)試時(shí)微調(diào)（Test-Time Fine-Tuning, TTFT）。它包括將少量 ARC 示例擴(kuò)充成數(shù)千個(gè)示例，然后對(duì)該任務(wù)微調(diào) LLM，再生成多個(gè)候選輸出網(wǎng)格，并對(duì)最有可能的結(jié)果進(jìn)行投票。

Greenblatt [16] 和 Berman [17] 采用了歸納而非轉(zhuǎn)導(dǎo)的方法。他們不直接讓 LLM 為測(cè)試輸入網(wǎng)格生成輸出網(wǎng)格，而是要求 LLM 對(duì)任務(wù)示例進(jìn)行推理，以生成數(shù)千個(gè)候選變換程序（例如 Python 代碼），并通過評(píng)估這些程序在示例上的表現(xiàn)進(jìn)行篩選。他們還采用了一種進(jìn)化方法，要求 LLM 對(duì)更有希望的程序進(jìn)行迭代修改，形成多代演化。

盡管基于 LLM 的方法在 ARC 上取得了客觀的成功，但在 AGI 方面是否真正實(shí)現(xiàn)了進(jìn)步仍存疑問：

1. 訓(xùn)練數(shù)據(jù)的泛化性問題：LLM 被大量訓(xùn)練在數(shù)百萬個(gè)類 ARC 任務(wù)上。對(duì)于某些私有任務(wù)來說，可能存在非常相似的合成任務(wù)，使得 LLM 只需“檢索”解決方案，而不是“推理”新任務(wù)。需要指出的是，ARC 的設(shè)計(jì)初衷是為了測(cè)試分布外推理能力。

2. 人類能力對(duì)比：人類可以在從未接觸過 ARC 任務(wù)的情況下僅憑核心知識(shí)先驗(yàn)解決問題。這說明當(dāng)前 LLM 方法并未真正模擬人類認(rèn)知機(jī)制。

3. 計(jì)算效率問題：由于需要進(jìn)行示例擴(kuò)充、微調(diào)以及生成數(shù)千個(gè)候選結(jié)果，測(cè)試階段的計(jì)算量巨大。效率被認(rèn)為是智能的重要因素 [18]，而與之相對(duì)的暴力搜索方式顯然不是理想路徑，大規(guī)模 LLM 生成也可視為一種暴力搜索形式。

Johnson 等人 [5] 報(bào)告了一項(xiàng)關(guān)于 ARC 的心理學(xué)研究。研究表明，人類使用以對(duì)象為中心的心理表示來解決 ARC 任務(wù)，這與現(xiàn)有基于網(wǎng)格變換的方法形成鮮明對(duì)比。有趣的是，人類認(rèn)為最難的任務(wù)恰恰是那些基于邏輯（如異或操作）和對(duì)稱性（如旋轉(zhuǎn)）的任務(wù)——而這些任務(wù)恰好最容易被基于變換的方法解決。

該研究揭示了兩個(gè)挑戰(zhàn)：

1. 需要一個(gè)包含大量基本操作的集合，尤其是幾何相關(guān)的基本操作；

2. 難以識(shí)別物體，因?yàn)樗鼈兛赡芤蛑丿B或遮擋而部分可見。

一個(gè)寶貴的資源是 LARC（Language-annotated ARC）[19]，它是通過眾包收集的語料庫。它為大多數(shù)訓(xùn)練任務(wù)提供了一個(gè)或多個(gè)自然語言編寫的程序。這些程序之所以被稱為“自然”，是因?yàn)樗鼈兪怯扇祟悋L試解決 ARC 任務(wù)后撰寫的簡(jiǎn)短文本；稱為“程序”，是因?yàn)樗鼈兘?jīng)過驗(yàn)證有效：由兩個(gè)獨(dú)立參與者參與：描述者根據(jù)訓(xùn)練示例生成文本，構(gòu)建者則根據(jù)該文本和測(cè)試輸入網(wǎng)格生成輸出網(wǎng)格。這些自然程序證實(shí)了人類表征的以對(duì)象為中心和聲明式的本質(zhì)。

除了 ARC 基準(zhǔn)之外，程序合成（也稱為程序歸納或示例編程 PbE）領(lǐng)域也有大量研究。早期方法包括歸納邏輯編程（Inductive Logic Programming, ILP）[21]，其中目標(biāo)謂詞是從符號(hào)表示中學(xué)習(xí)得到的。

程序合成的一個(gè)較新成功案例是 FlashFill [6]，它可以根據(jù)少量示例生成字符串到字符串的程序，并已被部署在 Microsoft Excel 中，用于在用戶填寫幾行數(shù)據(jù)后自動(dòng)填充列內(nèi)容。它依賴于 DSL 的定義和高效的數(shù)據(jù)結(jié)構(gòu)，用于計(jì)算與示例兼容的所有程序集合。

FlashMeta [22] 是一個(gè)推廣 FlashFill 的框架，支持將其應(yīng)用于其他 DSL。FlashMeta 的一個(gè)關(guān)鍵組成部分是“見證函數(shù)”（witness functions），它捕捉 DSL 原始操作的逆語義，從而在一定程度上使程序搜索能夠考慮到輸出示例。

Scrybe [23] 也具備某種形式的逆語義，其中示例從函數(shù)結(jié)果反向傳播到參數(shù)。然而，它似乎僅限于結(jié)構(gòu)化數(shù)據(jù)（整數(shù)列表）和組合程序（主要是列表過濾和排列）。

Rule 等人 [24] 同樣關(guān)注列表到列表的程序，但搜索的是元程序（metaprogram）空間，而非直接搜索程序空間。元程序通過幾個(gè)步驟將一組示例轉(zhuǎn)換為程序。這種方法使用的搜索量級(jí)顯著減少，且性能接近人類水平。

Dreamcoder [25] 則交替進(jìn)行“清醒”階段（使用神經(jīng)引導(dǎo)搜索解決問題）和“睡眠”階段（擴(kuò)展抽象庫以壓縮“清醒”階段找到的程序）。

在某些任務(wù)中，貝葉斯程序?qū)W習(xí)被證明優(yōu)于深度學(xué)習(xí)，例如解析和生成手寫世界字母表 [26]。

4. 提出方法的概述

在本節(jié)中，我們將在深入探討技術(shù)細(xì)節(jié)之前，非正式地介紹我們的方法。該介紹基于從訓(xùn)練集中選取的一個(gè)任務(wù)：task 47c1f68c。圖 2 顯示了左側(cè)的三個(gè)演示樣例和右側(cè)的測(cè)試樣例；頂部為輸入網(wǎng)格，底部為輸出網(wǎng)格。我們選擇了這個(gè)相對(duì)復(fù)雜的任務(wù)作為示例，它無法通過在 DSL 搜索空間中的暴力搜索輕易解決，并且其輸入和輸出都展現(xiàn)出一定的結(jié)構(gòu)特征。

現(xiàn)有的基于程序合成的方法通常將程序定義為從輸入到輸出的一系列變換。圖 3 展示了這樣一個(gè)解決當(dāng)前任務(wù)的變換序列，以及它在第一個(gè)演示樣例上的應(yīng)用。該序列為四個(gè)步驟：裁剪左上角的象限，然后將非黑色單元格重新著色為輸入網(wǎng)格中的主要顏色，最后將結(jié)果向右和向下各鏡像一次。

對(duì)于這種變換序列的搜索，可以得出以下幾點(diǎn)觀察：

• 在所有適用于某個(gè)網(wǎng)格（輸入或中間結(jié)果）的變換中，若不考慮目標(biāo)輸出，則沒有理由優(yōu)先選擇某一個(gè)變換。一個(gè)好的變換是指對(duì)生成輸出有幫助的變換。

• 一般來說，很難評(píng)估某個(gè)中間網(wǎng)格相對(duì)于目標(biāo)輸出的有用性。一個(gè)好的中間網(wǎng)格可能具有不同的尺寸、顏色，或包含不同的形狀。

• 大多數(shù)變換是不可逆的，因此大多數(shù)方法只能從輸入到輸出方向生成并評(píng)估變換序列。

正因如此，完整序列通常是在生成之后才通過比較預(yù)測(cè)輸出與期望輸出進(jìn)行評(píng)估。這使得枚舉式搜索呈指數(shù)級(jí)增長(zhǎng)，因此僅限于較短的序列。

更高級(jí)的方法使用訓(xùn)練好的模型，在給定輸入、輸出和之前步驟的情況下，預(yù)測(cè)下一步可能有希望的變換。

在 MADIL 方法中，一個(gè)程序首先將輸入網(wǎng)格分解為多個(gè)部分，然后從這些部分組合出輸出網(wǎng)格。圖 4 展示了當(dāng)前任務(wù)的“分解—組合”過程，并以第一個(gè)樣例進(jìn)行說明。

輸入網(wǎng)格被分解為背景顏色（此處為黑色）和網(wǎng)格內(nèi)容。網(wǎng)格內(nèi)容又被進(jìn)一步分解為一個(gè)由 4 個(gè)子網(wǎng)格組成的“元網(wǎng)格”（metagrid）以及一個(gè)分隔色（此處為紅色）。其中，左上角的子網(wǎng)格又被分解為其單一顏色（此處為藍(lán)色）和內(nèi)容掩碼（contents mask）。

隨后，輸出網(wǎng)格由與輸入相同的背景色（此處為黑色）和一個(gè)新的網(wǎng)格內(nèi)容組成。這個(gè)新的網(wǎng)格內(nèi)容是由輸入掩碼用輸入的分隔色（此處為紅色）著色后得到的一個(gè)較小的網(wǎng)格，再經(jīng)過對(duì)稱展開而生成。

請(qǐng)注意，盡管沒有任何樣例要求，該程序也能正確泛化到其他背景顏色，而不僅僅是“黑色”。

每一個(gè)分解/組合過程被稱為一個(gè)模式（pattern），它可以雙向運(yùn)行：

• 從整體到部分（即分解），

• 或者從部分到整體（即組合）。

組合必須是確定性的，但分解可以是非確定性的：沿著某個(gè)模式，可能存在多種不同的分解方式。例如，當(dāng)一個(gè)網(wǎng)格符合多種對(duì)稱性時(shí)，就可能產(chǎn)生不同的分解結(jié)果。

圖 5 展示了 MADIL 程序，它是當(dāng)前任務(wù)的一個(gè)解決方案。我們實(shí)際上稱之為一個(gè)任務(wù)模型（task model），因?yàn)樗蓛蓚€(gè)網(wǎng)格模型（grid models）組成，而每個(gè)網(wǎng)格模型又是多個(gè)模式的組合。

此外，輸出模型可以引用輸入中的某些部分（例如sepcolor），并對(duì)其應(yīng)用函數(shù)，從而根據(jù)輸入的部分來指定輸出的部分。

關(guān)于“分解—組合”程序的搜索，我們可以做出以下幾點(diǎn)觀察：

• 在所有適用于輸入網(wǎng)格的模式中，優(yōu)先選擇那些能夠更有效壓縮網(wǎng)格的模式，這與輸出網(wǎng)格本身無關(guān)。

• 壓縮率

  可以通過信息論來定義，并通過使用兩段式 MDL（Two-part Minimum Description Length）原則來避免過擬合。

• 模式是可逆的，因此程序可以從兩個(gè)方向構(gòu)建：同時(shí)搜索輸入網(wǎng)格和輸出網(wǎng)格的良好分解方式。

  因此，MADIL 程序的搜索可以分為三個(gè)組成部分：

• 對(duì)輸入網(wǎng)格進(jìn)行壓縮性分解，

• 對(duì)輸出網(wǎng)格進(jìn)行壓縮性分解，

• 將輸入部分映射到輸出部分。

最后一部分可以采用傳統(tǒng)方式進(jìn)行，即搜索從輸入部分到輸出部分的變換序列。然而，在這里我們預(yù)期可以得到更短的變換序列，因?yàn)榉纸膺^程已經(jīng)對(duì)整體變換起到了推動(dòng)作用。

在當(dāng)前的任務(wù)示例中可以觀察到，空變換序列就已足夠，因?yàn)槊恳粋€(gè)輸出部分都可以在輸入部分中找到。

5. 理論

在本節(jié)中，我們將為我們的方法奠定理論基礎(chǔ)。我們首先定義所有關(guān)鍵概念，從值（values）到任務(wù)模型（task models），中間還包括模式（patterns）和函數(shù)（functions），它們是模型的基本構(gòu)建模塊（見第 5.1 節(jié)）。接著，我們定義模型和描述的描述長(zhǎng)度（description lengths），以便應(yīng)用MDL（最小描述長(zhǎng)度）原則。

最后，我們定義學(xué)習(xí)目標(biāo)以及任務(wù)模型的搜索空間，并在該搜索空間上建立一些有用的性質(zhì)。

這些定義具有完全通用性，原則上可以應(yīng)用于任何類型的輸入和輸出。對(duì)于特定領(lǐng)域而言，需要具體實(shí)例化的概念包括：值、模式和函數(shù)。我們提供了它們?cè)?ARC 中的具體定義，作為示例說明，也是我們實(shí)驗(yàn)的基礎(chǔ)。

5.1 定義：從值到任務(wù)模型 5.1.1 值（Values）

“值”是 MADIL 模型的基本構(gòu)成要素。它們用于表示任務(wù)的輸入和輸出，也用于從輸入到輸出的轉(zhuǎn)換過程中的中間表示。

為了衡量值的描述長(zhǎng)度（description length），我們還需要定義值所遵循的分布（distributions）。這些分布不僅用于計(jì)算描述長(zhǎng)度，還用于限制某個(gè)值必須屬于某一特定的值集合。

例如，一個(gè)分布可以是非黑色顏色上的均勻分布（uniform distribution over non-black colors）。這樣的分布限定了可選的顏色范圍，并為每個(gè)顏色分配了一個(gè)概率，從而可以計(jì)算該選擇所需的編碼位數(shù)（即描述長(zhǎng)度）。

簡(jiǎn)而言之，值及其分布共同構(gòu)成了在MDL（最小描述長(zhǎng)度）框架下對(duì)模型進(jìn)行評(píng)估的基礎(chǔ)。

在本研究中，我們更傾向于使用描述長(zhǎng)度（description lengths）而非概率（probabilities）。香農(nóng)的最優(yōu)編碼定理（optimal encoding theorem）為兩者之間建立了直接的聯(lián)系。

5.1.2 函數(shù)與模式（Functions and Patterns）

MADIL 模型中的計(jì)算是通過函數(shù)（functions）和模式（patterns）來完成的。
我們假設(shè)模型中使用的函數(shù)和模式集合是有限的。

5.1.3 表達(dá)式（Expressions）

設(shè) X 是一個(gè)變量集合。變量用于在下文定義的描述和模型中標(biāo)識(shí)各個(gè)部分。

表達(dá)式（Expressions）以經(jīng)典方式定義，即為值、變量和函數(shù)應(yīng)用的組合。

5.1.6 任務(wù)與任務(wù)模型（Tasks and Task Models）

現(xiàn)在我們可以將任務(wù)（tasks）定義為輸入-輸出對(duì)的集合，并將任務(wù)模型（task models）定義為解決該任務(wù)的方案。

我們假設(shè)來自某個(gè)領(lǐng)域的輸入值服從一個(gè)分布 ，輸出值服從一個(gè)分布 。
在 ARC 中，這些分布定義在最多 30x30 大小的 10 色網(wǎng)格上。

5.2 描述長(zhǎng)度（Description Lengths）

如前所述，MDL（最小描述長(zhǎng)度）原則指出：最好的模型是能夠最大程度壓縮數(shù)據(jù)的模型。
在這里，“數(shù)據(jù)”指的是訓(xùn)練樣例集合。

對(duì)于一個(gè)任務(wù) T=?E,F?，其訓(xùn)練樣例集合 E 的先驗(yàn)描述長(zhǎng)度（a priori description length）可以定義如下。

每個(gè)值都根據(jù)該領(lǐng)域中的值分布進(jìn)行編碼。
由于假設(shè)各個(gè)樣例之間是相互獨(dú)立的，并且輸入值與輸出值之間的關(guān)系是未知的（這正是我們想要學(xué)習(xí)的內(nèi)容），因此這些值的編碼只是簡(jiǎn)單拼接在一起。

5.2.1 編碼樣例（Encoding Examples）

對(duì)一組樣例進(jìn)行編碼，相當(dāng)于對(duì)每一個(gè)樣例分別進(jìn)行編碼。
根據(jù)模型 M 對(duì)一個(gè)樣例 (vi,vo) 進(jìn)行編碼，相當(dāng)于對(duì)該樣例中這些值的描述（description）進(jìn)行編碼。

一個(gè)難點(diǎn)在于：同一個(gè)樣例可能對(duì)應(yīng)多個(gè)不同的描述。
根據(jù)MDL（最小描述長(zhǎng)度）原則，我們選擇其中壓縮效果最好的（即描述長(zhǎng)度最短）那個(gè)描述。

5.2.2 編碼模型（Encoding Models）

對(duì)一個(gè)任務(wù)模型（task model）進(jìn)行編碼可以分為兩個(gè)部分：

• 輸入模型（input model）
• 輸出模型（output model）

“5.3. 學(xué)習(xí)目標(biāo)與搜索空間

給定一個(gè)任務(wù) T = ?E, F?，任務(wù)模型可以在兩種推理模式下使用：”

其中：

這是由任務(wù)模型生成的、與輸入值相容的最壓縮描述所對(duì)應(yīng)的輸出值。
如果沒有相容的描述，則返回 ⊥ 作為未定義的結(jié)果。
如果有多個(gè)描述具有相同的最小描述長(zhǎng)度，則不指定具體選擇哪一個(gè)。在實(shí)際中，可以通過對(duì)值的全序關(guān)系來明確指定。
如果一個(gè)任務(wù)模型能夠正確預(yù)測(cè)所有訓(xùn)練樣例的輸出，那么它就是該任務(wù)的一個(gè)解。
如果該模型在所有測(cè)試樣例上也都能正確預(yù)測(cè)，則稱其具有泛化能力。

我們通過定義一個(gè)初始任務(wù)模型以及模型之間的轉(zhuǎn)換，來在所有任務(wù)模型上定義一個(gè)搜索空間，使得所有的模型都可以被到達(dá)（可達(dá)）。
我們用 M.x 表示模型 M 中變量 x 處的子模型。
我們用 M[x ← m′] 表示將 M 中 x 位置的子模型 M.x 替換為 m′，其中滿足 var(m′) = x（以避免變量重命名），并且 Xm′ ∩ XM = {x}（以避免變量捕獲）。

我們首先證明，在給定一組最小轉(zhuǎn)換操作的前提下，這個(gè)搜索空間是完備的——也就是說，所有的任務(wù)模型都是可達(dá)的。這確保了我們可以通過遍歷有限數(shù)量的轉(zhuǎn)換操作來找到解決方案。

需要注意的是，表達(dá)式轉(zhuǎn)換不能被分解為逐個(gè)引入值、變量和函數(shù)的轉(zhuǎn)換，因?yàn)楹瘮?shù)只有在其所有參數(shù)都已定義的情況下才能被求值。這是與“模式”（patterns）之間的關(guān)鍵區(qū)別，也是模式的關(guān)鍵優(yōu)勢(shì)：它們可以分段地引入到模型中。

從初始模型 M0 到任一任務(wù)模型 M 的最小轉(zhuǎn)換集合是唯一定義的，具體方式如下：逐步引入 M 中的每一個(gè)模式和每一個(gè)表達(dá)式。

我們可以將其分解為 ?(M) = ??(M) ? ??(M)，其中第一項(xiàng)是作用于輸入模型的轉(zhuǎn)換子集（x ∈ X??），第二項(xiàng)是作用于輸出模型的轉(zhuǎn)換子集（x ∈ X??）。

轉(zhuǎn)換的應(yīng)用順序是受限制的。一個(gè)轉(zhuǎn)換 x ← m′ 只有在變量 x 被引入之后才能被觸發(fā)。此外，一個(gè)表達(dá)式轉(zhuǎn)換 x ← e 只能在該表達(dá)式所使用的所有變量都被引入之后才能被觸發(fā)。這導(dǎo)致了在 ?(M) 上的一個(gè)偏序關(guān)系。

特別地，輸入模型的轉(zhuǎn)換不依賴于輸出模型的轉(zhuǎn)換；輸出模式的轉(zhuǎn)換也不依賴于輸入的轉(zhuǎn)換。此外，一個(gè)輸出表達(dá)式的轉(zhuǎn)換依賴于輸入和輸出模式的轉(zhuǎn)換，但不依賴于其他表達(dá)式的轉(zhuǎn)換。任何與這一偏序關(guān)系相容的全序排列，都是到達(dá)目標(biāo)任務(wù)模型 M 的有效路徑。

存在兩種簡(jiǎn)單的策略：先全部應(yīng)用輸入轉(zhuǎn)換再應(yīng)用輸出轉(zhuǎn)換，或先全部應(yīng)用模式轉(zhuǎn)換再應(yīng)用表達(dá)式轉(zhuǎn)換。但最有效的搜索策略可能是更混合的形式。

為了引導(dǎo)搜索朝向一個(gè)解決方案，識(shí)別出一種在從初始狀態(tài)到解決方案的路徑中始終保持有效的任務(wù)模型性質(zhì)是非常有益的。事實(shí)上，這可能允許我們剪枝掉大量無效的搜索空間。實(shí)現(xiàn)這一點(diǎn)的方式是將“預(yù)測(cè)期望輸出”的約束放松為“找到一個(gè)輸入-輸出對(duì)的描述”的約束。

可選地，一致性可以擴(kuò)展到測(cè)試輸入，即要求它們必須能夠被輸入模型所描述。我們?cè)谙挛闹凶C明，在通過最小轉(zhuǎn)換進(jìn)行搜索時(shí)，一致性可以用作一種剪枝性質(zhì)。我們首先從證明一個(gè)關(guān)于模型（而非任務(wù)模型）的引理開始。

盡管一致性可以用來剪枝——排除那些與訓(xùn)練樣例不符的模式和表達(dá)式——但在每一步仍可能存在多個(gè)一致的轉(zhuǎn)移，導(dǎo)致可達(dá)狀態(tài)呈指數(shù)級(jí)增長(zhǎng)。因此，引入啟發(fā)式方法來引導(dǎo)搜索朝向更有希望的區(qū)域是非常必要的。

我們采用上一節(jié)中基于最小描述長(zhǎng)度（MDL）原則定義的描述長(zhǎng)度 L ( M , D ) L(M,D)作為啟發(fā)式指標(biāo)：最優(yōu)的模型是那些能更好壓縮數(shù)據(jù)的模型。需要注意的是，雖然更具體的模型通常會(huì)帶來更小的描述長(zhǎng)度，但若插入的模式并不能很好地?cái)M合訓(xùn)練樣例，那么這個(gè)更具體的模型的描述長(zhǎng)度可能反而更大。

6. 算法與實(shí)用方面

在本節(jié)中，我們?cè)敿?xì)介紹了 MADIL 方法中的關(guān)鍵算法，從基于模型的解析（parsing）到搜索能夠解決任務(wù)的任務(wù)模型。這些算法是通用的，我們會(huì)指出那些依賴于具體任務(wù)領(lǐng)域的部分。我們還將討論少量有助于控制“解析搜索”和“任務(wù)模型搜索”的參數(shù)。此外，我們也會(huì)探討一些實(shí)用方面的考慮，即為了提升性能而對(duì)理論或算法所做的小幅度調(diào)整。

6.1 解析與生成：尋找良好的描述

算法1定義了parse 函數(shù)，它輸出一個(gè)惰性序列（lazy sequence），包含屬于模型 m 的所有描述——連同它們的描述長(zhǎng)度——這些描述在某個(gè)環(huán)境 σ 下具有固定值 v。該函數(shù)根據(jù)模型語法樹遞歸定義，遵循定義 12 和第 5.2.1 節(jié)的內(nèi)容。由于序列是惰性計(jì)算的，因此可以高效地計(jì)算有限數(shù)量的描述。

該算法中與具體領(lǐng)域相關(guān)的部分包括：

• L(v | V )

  ：一個(gè)值的描述長(zhǎng)度；

• P?1(v)

  ：基于模式的值的分解方式；

• VP,i(V, v?, ..., vi?1)

  ：模式各部分的值分布。

通常情況下，無法按描述長(zhǎng)度（DL）升序生成所有描述。不過，可以通過兩種方式改進(jìn)生成順序：

1. 可以設(shè)計(jì)P?1，使其優(yōu)先生成更有希望的分解方式。例如，在使用 Motif 模式時(shí)，較小的周期性模式比更大的模式更有希望，因?yàn)樗鼘⒕W(wǎng)格簡(jiǎn)化為更小的子網(wǎng)格。

2. 對(duì)于第 9–11 行中執(zhí)行各部分子描述序列笛卡爾積的 k 層嵌套循環(huán)，可以采用按排名排序的笛卡爾積，優(yōu)先生成低排名（即更優(yōu)）的描述。

算法2基于 parse 函數(shù)，定義了describe 函數(shù)，它輸出屬于某個(gè)任務(wù)模型 M 的示例描述 D 列表，用于固定的輸入-輸出值對(duì)，并按描述長(zhǎng)度（DL）升序排列。對(duì)于每一個(gè)輸入的描述，它會(huì)計(jì)算對(duì)應(yīng)的輸出描述，并將它們的描述長(zhǎng)度相加。

出于可計(jì)算性的考慮，我們通過采樣 Np 個(gè)描述并從中選擇前 Kp 個(gè)描述（即 DL 更小的）來近似結(jié)果，輸入和輸出都這樣做。因此，返回的示例描述的最大數(shù)量為 Kp2。

典型的參數(shù)取值為 Np = 100 和 Kp = 3。我們將在評(píng)估部分（第8節(jié)）研究這些參數(shù)的影響。

算法3定義了generate 函數(shù)，它輸出一個(gè)惰性序列（lazy sequence），包含在某個(gè)環(huán)境 σ 下屬于模型 m 的所有描述。它的定義與 parse 函數(shù)類似，不同之處在于：這里的值是從分布中抽取或通過表達(dá)式求值得到的，并通過模式進(jìn)行組合。

需要注意的是，對(duì)于某些參數(shù)來說，表達(dá)式求值（第6行）和模式組合（第12行）可能是未定義的，在這種情況下不會(huì)產(chǎn)生任何輸出（no yield）。

該算法中與具體領(lǐng)域相關(guān)的部分包括：

• v ～ V

  ：從分布中抽取值；

• P(v?, ..., v?)

  ：基于模式的組合方式；

• VP,i(V, v?, ..., vi?1)

  ：模式各部分的值分布。

通常情況下，無法按描述長(zhǎng)度（DL）升序生成所有描述。不過，可以通過與 parse 函數(shù)類似的方式改進(jìn)生成順序：即對(duì)第9–11行中的 k 層嵌套循環(huán)使用按排名排序的笛卡爾積，優(yōu)先生成低排名的描述。

算法4基于 parse 和 generate 函數(shù)，定義了predict 函數(shù)，它輸出給定任務(wù)模型 M 和固定輸入 v? 后的預(yù)測(cè)輸出列表 v?，并按描述長(zhǎng)度（DL）升序排列。對(duì)于每一個(gè)輸入的描述，它會(huì)生成對(duì)應(yīng)的輸出描述，從而得到一個(gè)輸出值，并將它們的描述長(zhǎng)度相加。

出于可計(jì)算性的考慮，我們通過以下方式近似結(jié)果：采樣 Np 個(gè)輸入描述，從中選擇前 Kp 個(gè)輸入描述；然后對(duì)每個(gè)選中的輸入描述，再采樣 Ng 個(gè)輸出描述，并從中選擇前 Kg 個(gè)輸出描述。

因此，最多可能的預(yù)測(cè)輸出數(shù)量是 Kp × Kg，盡管在實(shí)際基準(zhǔn)測(cè)試中只使用其中的前幾個(gè)輸出（例如 ARCathon 中使用3個(gè)，ArcPrize 中使用2個(gè)）。

典型的參數(shù)取值為：Np = 100，Kp = 3，Ng = Kg = 3。我們將在評(píng)估部分（第8節(jié)）研究這些參數(shù)的影響。

6.2 轉(zhuǎn)換：尋找有希望的模型細(xì)化

算法5定義了transitions 函數(shù)，它返回一個(gè)從任務(wù)模型 M 出發(fā)、一致的轉(zhuǎn)換列表。該函數(shù)接受一個(gè)由示例描述組成的列表的列表作為輸入，其中每個(gè)子列表是通過對(duì)每個(gè)訓(xùn)練樣例調(diào)用 describe 函數(shù)生成的。

返回的轉(zhuǎn)換包括上面定義的最小轉(zhuǎn)換，但也考慮通過更具體的模式或表達(dá)式來細(xì)化一個(gè)模式。這就是為什么對(duì)每一個(gè)不是表達(dá)式的子模型（即未知值或模式）都要計(jì)算轉(zhuǎn)換的原因（第3行）。這使得搜索對(duì)轉(zhuǎn)換順序的依賴性降低。

對(duì)于給定的子模型 M.x，候選轉(zhuǎn)換子模型 m′ 是通過對(duì)每個(gè)示例描述 Dij 調(diào)用 submodels 函數(shù)得到的（第4行），然后對(duì)同一個(gè)示例的不同描述 D ∈ {Dij} 進(jìn)行并集聚合，最后對(duì)所有示例進(jìn)行交集聚合（第6行）。其原理是：一個(gè)一致的子模型必須在某個(gè)每個(gè)示例的描述中保持一致。

submodels 函數(shù)的輸入還包括與描述 Dij 及子模型位置（在輸入或輸出中）相關(guān)的環(huán)境；以及該描述相對(duì)于當(dāng)前模型 M 的描述長(zhǎng)度 DL（第5行）。

每個(gè)子模型 m′ 都附帶一個(gè)估計(jì)的 DL 值：L = L(M, D) ? L(D.x | M.x) + L(D.x | m′)，該值考慮了將 M.x 替換為 m′ 后對(duì)描述編碼的影響。因此，使用最小值來合并一個(gè)示例中不同描述的 DL，使用加法來合并不同示例之間的 DL。

第7–9行計(jì)算了轉(zhuǎn)換的目標(biāo)模型 M′，以及結(jié)合模型變化和描述變化的估計(jì) DL。

submodels 函數(shù)對(duì)于給定的子模型 m 和其對(duì)應(yīng)子描述 d 的值 v，返回三種類型的候選子模型 m′：

• 常量值 v，

• 表達(dá)式 e，

• 基于模式的子模型 P(...)。

表達(dá)式及其值來自于從環(huán)境 σ 中提取的一個(gè)有限集合 E。例如，這個(gè)集合可以包含最多由6個(gè) σ-變量、常量和函數(shù)調(diào)用組成的所有類型正確的表達(dá)式。為了提高效率，這些表達(dá)式根據(jù)它們的值被索引到一個(gè) DAG 數(shù)據(jù)結(jié)構(gòu) [6] 中。這樣可以緊湊地表示大量表達(dá)式，并快速檢索出所有求值結(jié)果為某個(gè)特定值（這里是 v）的表達(dá)式。

基于模式的模型則來自于從值 v 的類型中提取的有限集合 MP。該集合至少應(yīng)包含所有相關(guān)模式對(duì)應(yīng)的模型如 P(?, ..., ?)，也可以包含由多個(gè)模式和常量組成的模型，作為常見轉(zhuǎn)換序列的簡(jiǎn)寫形式。這可能也有助于找到更具壓縮性的轉(zhuǎn)換。

只有那些能夠解析 v 的基于模式的模型才會(huì)被保留為候選轉(zhuǎn)換。估計(jì)的 DL 為：L ? l + l′，其中 L 是當(dāng)前的整體描述長(zhǎng)度，l 是當(dāng)前局部描述的長(zhǎng)度，l′ 是在候選子模型 m′ 下的新局部描述長(zhǎng)度。對(duì)于表達(dá)式來說，l′ 為0，因?yàn)闊o需再進(jìn)行任何編碼（包括常量值）。

返回的轉(zhuǎn)換集合可能是不完整的，原因有兩個(gè)：

1. 每個(gè)示例最多只使用 Kp2 個(gè)描述來生成候選子模型。增加 Kp 會(huì)對(duì)示例描述和轉(zhuǎn)換的計(jì)算成本產(chǎn)生重要影響。

2. 只考慮了一個(gè)有限的表達(dá)式子集。在實(shí)踐中，這受限于表達(dá)式的最大大小（max. Se）和數(shù)量（max. Ne）。

最后需要注意的是，返回的 DL 只是一個(gè)估計(jì)值，因?yàn)樗鼉H重新解析了子描述的值。使用整個(gè)新模型對(duì)完整值進(jìn)行重新解析，可能會(huì)發(fā)現(xiàn)更具壓縮性的描述。

6.3 貪心搜索：尋找最具壓縮性的模型

算法6定義了GreedySearch 函數(shù)，它在給定任務(wù) T 的情況下，在任務(wù)模型空間中執(zhí)行貪心搜索。

該函數(shù)從初始任務(wù)模型開始（第2行），并在當(dāng)前模型 M 無法正確預(yù)測(cè)所有訓(xùn)練樣例時(shí)繼續(xù)循環(huán)（第3行）。
在每次迭代中，它會(huì)計(jì)算這些樣例的描述（第4行），并據(jù)此生成一組候選轉(zhuǎn)換，對(duì)應(yīng)更精細(xì)的模型 M′（第5行）。
從中選出最具壓縮性的那個(gè)模型（第6行），如果它比當(dāng)前模型更具壓縮性（第7行），則將其作為新的當(dāng)前模型（第8行），然后重復(fù)整個(gè)過程，直到無法進(jìn)一步壓縮為止（第10行）。

該搜索過程涉及兩個(gè)參數(shù)：

• K：允許進(jìn)行預(yù)測(cè)的最大嘗試次數(shù)，例如在 ArcPrize 中為 2。
• Kt：最多考慮的候選轉(zhuǎn)換數(shù)量，默認(rèn)為 100。這個(gè)參數(shù)有助于控制效率，因?yàn)橛?jì)算新模型 M′ 在訓(xùn)練集 E 上的描述長(zhǎng)度 L(M′, E) 意味著要對(duì)每個(gè)樣例都進(jìn)行代價(jià)較高的描述計(jì)算。

為了簡(jiǎn)化表述，上述形式化定義中忽略了一些在實(shí)現(xiàn)和實(shí)驗(yàn)結(jié)果中起重要作用的實(shí)用因素（pragmatic aspects）。我們?cè)诖撕?jiǎn)要描述它們。

描述長(zhǎng)度（Description Lengths）

兩部分最小描述長(zhǎng)度（MDL）定義為：L(M, D) = L(M) + L(D | M)，它假設(shè) D 是所有需要建模的數(shù)據(jù)。然而，在像 ARC 這樣的程序綜合任務(wù)中，D 只是任務(wù)所允許的大量輸入-輸出對(duì)中的一小部分。因此，我們?cè)谏鲜龆x中引入了一個(gè)“復(fù)習(xí)因子”α：L(M, D) = L(M) + α·L(D | M)，以增加數(shù)據(jù)部分的權(quán)重，從而允許使用更復(fù)雜的模型。如果 α 的值太小，搜索可能會(huì)過早停止，錯(cuò)過解決任務(wù)所需的關(guān)鍵分解方式；如果 α 的值太大，則可能導(dǎo)致搜索偏向于對(duì)示例過于復(fù)雜的模型，帶來過擬合的風(fēng)險(xiǎn)。在 ARC 中常用的 α 值為 100，我們將在評(píng)估部分與其他值進(jìn)行對(duì)比分析。

輸入與輸出壓縮的不平衡

在 ARC 中遇到的另一個(gè)困難是：對(duì)于某些任務(wù)，輸出網(wǎng)格遠(yuǎn)小于輸入網(wǎng)格。其后果是搜索過程會(huì)完全集中在壓縮輸入上，而忽略了對(duì)輸出的壓縮。然而，為了找到一個(gè)具有預(yù)測(cè)能力的模型，壓縮輸出才是必要的，而在很多情況下，并不需要對(duì)輸入進(jìn)行最大程度的壓縮。因此，我們采用了一種歸一化的描述長(zhǎng)度（normalized DL），使輸入和輸出具有相同的權(quán)重，其基礎(chǔ)是初始模型M? = (m??, m??) ,

其中 分別表示訓(xùn)練輸入和訓(xùn)練輸出。由于貪心搜索只朝著越來越具壓縮性的模型方向前進(jìn)，因此歸一化的描述長(zhǎng)度（DL）取值在區(qū)間 [0, 2] 內(nèi)。

轉(zhuǎn)換（Transitions）

大多數(shù)模式都包含兩個(gè)功能：一是驗(yàn)證一個(gè)值是否符合該模式，二是將該值分解為若干部分。例如，Monocolor模式會(huì)驗(yàn)證一個(gè)網(wǎng)格是否只使用了一種顏色，然后將其分解為“顏色”和“掩碼”兩個(gè)部分。有些模式如IsFull只具有驗(yàn)證功能；而另一些模式如Vec只具有分解功能（一個(gè)二維向量總是可以被分解為兩個(gè)整數(shù)）。

問題是，純分解類的模式通常不具備壓縮性，因?yàn)樗鼈冎皇墙沂玖艘粋€(gè)值的內(nèi)部結(jié)構(gòu)，比如 Vec 揭示了二維向量的兩個(gè)分量。因此，這類模式在搜索過程中往往不會(huì)被選中，盡管它們可能有助于揭示某個(gè)可以進(jìn)一步通過模式或表達(dá)式進(jìn)行壓縮的部分。

為此，我們通過用純分解模式 P 對(duì)最小轉(zhuǎn)換 m′ 進(jìn)行“包裝”來擴(kuò)展這些轉(zhuǎn)換，形式為P(..., m′, ...)。例如：Vec(add(x, 1), ?)表示一個(gè)向量的第一個(gè)分量由表達(dá)式定義，第二個(gè)分量仍待確定。這個(gè)“包裝”過程可以通過嵌套多個(gè)分解操作重復(fù)最多 Sd 次。

搜索（Search）

由于一致性保證（定理2），搜索所考慮的每一個(gè)模型都能解析所有訓(xùn)練輸入。然而，返回的模型可能會(huì)無法解析測(cè)試輸入。為了避免這一點(diǎn)，可以改進(jìn)搜索算法，剪枝掉那些無法解析測(cè)試輸入的模型。這在 ARC 競(jìng)賽中是合理的，因?yàn)樵谶@些比賽中，學(xué)習(xí)系統(tǒng)是可以訪問測(cè)試輸入的。這類似于人類參加 IQ 測(cè)試時(shí)，同時(shí)能看到示例和測(cè)試輸入。不過，至少對(duì)于大多數(shù) ARC 任務(wù)來說，并不需要考慮測(cè)試輸入，就可以找到一個(gè)能夠正確泛化到未見測(cè)試樣例的模型。

所找到的模型可能會(huì)通過包含訓(xùn)練樣例之間的非本質(zhì)規(guī)律而出現(xiàn)過擬合并非任務(wù)核心的情況。例如，在任務(wù)47c1f68c（見圖2）中，所有的訓(xùn)練輸入和輸出都有黑色背景，但實(shí)際上背景可以是任意顏色，只要輸入和輸出使用相同的顏色即可。

在搜索過程中加入對(duì)測(cè)試輸入的解析檢查（見上一段）是一種確保模型能泛化到測(cè)試樣例的方法，但模型仍可能過擬合，無法泛化到未見過的樣例。在這個(gè)示例任務(wù)中，測(cè)試樣例也使用了黑色作為背景色。

因此，我們?cè)谒阉麟A段之后增加了一個(gè)剪枝階段。其做法是：每當(dāng)將輸入模型中的某些模式或值替換為“未知”（unknown）后，并不會(huì)降低模型的預(yù)測(cè)準(zhǔn)確性時(shí)，就執(zhí)行這種替換。在該示例任務(wù)中，常量“黑色”就被替換為一個(gè)未知值。

通過使輸入模型更加通用，我們擴(kuò)大了任務(wù)模型的應(yīng)用范圍，從而增強(qiáng)了其對(duì)未見樣例的泛化能力。

剪枝不適用于輸出模型，因?yàn)檫@會(huì)導(dǎo)致預(yù)測(cè)輸出的數(shù)量增加，從而降低模型的準(zhǔn)確性。

參數(shù). 表3總結(jié)了上述算法中使用的所有參數(shù)，包括每個(gè)參數(shù)的簡(jiǎn)要描述以及它們?cè)趯?shí)驗(yàn)中的默認(rèn)值。

7. 進(jìn)階貢獻(xiàn)

本節(jié)介紹了一些顯著提升在 ARC 上性能的進(jìn)階性貢獻(xiàn)：部分的集合、依賴于值的模式，以及基于MCTS（蒙特卡洛樹搜索）的改進(jìn)搜索方法。

7.1 部分的集合

到目前為止所定義的模式都具有固定數(shù)量的部分（見第5.1.2節(jié)）。
然而，我們還可以設(shè)想一些會(huì)導(dǎo)致可變數(shù)量部分的模式，例如：

• 將一個(gè)精靈圖像（sprite）分割為一組對(duì)象；

• 將一個(gè)網(wǎng)格拆分為多個(gè)子網(wǎng)格；

• 將一維網(wǎng)格分解為顏色序列。

為了避免在模式中使用可變數(shù)量的參數(shù)（這在存在不同類型部分時(shí)會(huì)帶來混淆），我們通過擴(kuò)展值的域，引入了值的序列、序列的序列等等。

對(duì)于某一類值 X：

• [X]

  表示一個(gè) X 類型值的序列；

• [[X]]

  表示一個(gè)由 X 類型序列組成的序列（即“序列的序列”）； 更一般地，X?表示圍繞 X 類型值的 n 層序列結(jié)構(gòu)，我們稱之為 n 維序列（nD sequence）。
  因此，[X] 是一維序列，[[X]] 是二維序列（如果規(guī)則的話，也可稱為矩陣）。

這種結(jié)構(gòu)類似于張量（tensor），即 n 維數(shù)組，但不強(qiáng)制要求規(guī)則性約束，也就是說，子序列的長(zhǎng)度可以不同。

ARC 定義 6。表4列出了涉及序列（sequences）的 ARC 模式，這些模式是對(duì)表2中所列模式的補(bǔ)充。

• Objects：根據(jù)某種分割方式（類型為 Seg，例如 4-連通性且顏色相同）和某種排序準(zhǔn)則（類型為 Order，例如按面積降序），將一個(gè)精靈圖像（sprite）分解為一組對(duì)象。此外還有一個(gè)部分表示精靈圖像的大小，因?yàn)樵撔畔o法從對(duì)象中推導(dǎo)出來。為了便于分別推理長(zhǎng)度與內(nèi)容，序列的長(zhǎng)度（即對(duì)象數(shù)量 n）是單獨(dú)表示的。

• Obj：這是一個(gè)純粹用于對(duì)象分解的模式，用于分離對(duì)象的位置與其圖像內(nèi)容。

• Metagrid：根據(jù)某些邊界劃分，將一個(gè)精靈圖像（或網(wǎng)格或掩碼）分解為一個(gè)由子網(wǎng)格組成的矩陣。圖6展示了一個(gè)輸入符合此模式的任務(wù)示例。此處所有子網(wǎng)格具有相同的尺寸，但這不是必須的。其他組成部分包括：分隔符的顏色（如第一個(gè)例子中的紅色）、是否存在邊框（用一個(gè) 2x2 掩碼表示四個(gè)方向，這里無邊框）、子網(wǎng)格矩陣的維度 (k, l)（如第一個(gè)例子中的 4x4）、每個(gè)子網(wǎng)格的高度和寬度（同一“元行”中的子網(wǎng)格高度一致，同一“元列”中的子網(wǎng)格寬度一致）。

• ColorRow、ColorCol 和 ColorMat：將精靈圖像（或網(wǎng)格或掩碼）分解為一維或二維的顏色序列。前兩者僅適用于一維網(wǎng)格。反過來，AsGrid將規(guī)則的二維顏色序列轉(zhuǎn)換為網(wǎng)格。這類類型轉(zhuǎn)換被定義的原因是：不同類型的值可以支持不同的模式。

• DomainMapC：給定一個(gè)固定的顏色集合 C 作為定義域，將顏色映射縮減為其值域中的顏色。

• Range：將遵循等差數(shù)列的整數(shù)序列分解為起始值和步長(zhǎng)值。注意這里沒有關(guān)于終止值或序列長(zhǎng)度的部分，因?yàn)樾蛄虚L(zhǎng)度是由引入該序列的模式編碼的。

• Consd 和 Repeatd：這兩個(gè)是多態(tài)模式，只作用于 n 維序列，與其內(nèi)容類型無關(guān)。它們通過參數(shù)深度 d ∈ [0, n[ 來指定作用的軸：

• • Consd：在深度 d 處，對(duì)每一個(gè)非空子序列區(qū)分頭部和尾部。例如，Cons1將二維序列 [[0, 1, 2], [3, 4, 5]] 分解為頭部 [0, 3] 和尾部 [[1, 2], [4, 5]]；而Cons?則將其分解為頭部 [0, 1, 2] 和尾部 。

  • Repeatd：驗(yàn)證在深度 d 處的所有子序列是否都是同一個(gè)值的重復(fù)，并可壓縮為該值。例如，Repeat1可將二維序列 [[1, 1], [2, 2, 2]] 壓縮為一維序列 [1, 2]。

觀察圖6所示任務(wù)：每個(gè)輸入網(wǎng)格都匹配 Metagrid 模式，因此被分解為一個(gè)子網(wǎng)格矩陣。每個(gè)子網(wǎng)格又匹配 Monocolor 模式，但 Monocolor 模式期望的是“網(wǎng)格”，而不是“網(wǎng)格的矩陣”。

我們可以通過允許逐項(xiàng)應(yīng)用（item-wise application）預(yù)期類型的 n 維序列上的模式來解決這種類型不匹配的問題。這意味著，Monocolor 的一般定義應(yīng)為：
Grid? = Monocolor(color: Color?, mask: Mask?)。

這種泛化適用于所有模式，包括那些引入或消費(fèi)序列層級(jí)的模式，也適用于函數(shù)。

在子網(wǎng)格矩陣上應(yīng)用 Monocolor 模式后，會(huì)得到一個(gè)顏色矩陣和一個(gè)掩碼矩陣作為組成部分。接著，顏色矩陣可以通過 AsGrid 模式轉(zhuǎn)換為一個(gè)網(wǎng)格，最終輸出網(wǎng)格可以被識(shí)別為該網(wǎng)格的鏡像。

ARC 定義 7。與模式并行地，我們引入了新的函數(shù)來處理任意類型序列：

• 序列的長(zhǎng)度；

• 一維序列的尾部、反轉(zhuǎn)和旋轉(zhuǎn)；

• 二維序列的轉(zhuǎn)置和平鋪（flattening）；

• 聚合操作（如求和、最小值、最大值、最小索引、最大索引、最常見值、最不常見值）；

• 按幾個(gè)關(guān)鍵索引查找項(xiàng)和子結(jié)構(gòu)（例如：第一個(gè) x[0]、最后一個(gè) x[-1]、左上角 x[0, 0]）。

還有一些特定類型的函數(shù)涉及序列：

• 對(duì)掩碼序列進(jìn)行按位邏輯運(yùn)算；

• 獲取一個(gè)網(wǎng)格中顏色的頻率降序排列；

• 獲取網(wǎng)格的一半（halves）或四分之一（quadrants）；

• 將顏色的序列或矩陣轉(zhuǎn)換為網(wǎng)格；

• 一組對(duì)象之間的相對(duì)位置矩陣（用于“在某處平移”和“向某處平移”）。

一個(gè) n 維序列的描述長(zhǎng)度簡(jiǎn)單定義為其所有項(xiàng)的描述長(zhǎng)度之和，前提是這些項(xiàng)是相互獨(dú)立的。發(fā)現(xiàn)這些項(xiàng)之間的依賴關(guān)系是序列模式的任務(wù)，它們可以利用這些依賴性更好地壓縮序列（例如模式 Range）。不需要對(duì)序列長(zhǎng)度進(jìn)行編碼，因?yàn)樗鼈兌急蛔鳛橐朐撔蛄械哪Ｊ降囊徊糠侄鞔_指定。

7.2 依賴型模式（Dependent Patterns）

有一些常見的“模式”雖然很有吸引力，但既不能很好地歸類為模式，也不能滿意地歸類為表達(dá)式。例如，在許多 ARC 任務(wù)中，輸出網(wǎng)格（或其一部分）可以通過對(duì)輸入網(wǎng)格（或其一部分）進(jìn)行裁剪得到。

一方面，這提示我們可以定義一個(gè)函數(shù)：subgrid = crop(grid, position, size)，但這需要為許多不同的 grid、position 和 size 的組合生成表達(dá)式。出于可計(jì)算性的考慮，只能考慮少量固定的 position 和 size 值，可能會(huì)遺漏正確的參數(shù)值。

另一方面，也可以定義一個(gè)模式：subgrid = Crop(grid, position, size)，但這種分解方式面臨更大的挑戰(zhàn)，因?yàn)樗仨毶砂撟泳W(wǎng)格的更大網(wǎng)格。

換個(gè)角度看這個(gè)問題，我們應(yīng)從可計(jì)算的角度出發(fā)來思考。這里存在兩種可行的計(jì)算方式：

第一種計(jì)算是裁剪函數(shù)（cropping function），它是確定性的。
第二種計(jì)算是非確定性的，因?yàn)樽泳W(wǎng)格可能在原網(wǎng)格中出現(xiàn)多次。

此外，對(duì)于任意固定的網(wǎng)格來說，第二種計(jì)算可以看作是第一種計(jì)算的逆過程。
這提示我們可以定義一個(gè)由網(wǎng)格參數(shù)化的模式：在這個(gè)模式中，子網(wǎng)格是整體，而位置和大小是它的組成部分。

我們之所以稱其為依賴型模式（dependent patterns），是類比于依賴類型（dependent types）——即其定義依賴于某個(gè)值的類型。
對(duì)于這種模式來說，在進(jìn)行組合（composition）和分解（decomposition）時(shí)都必須已知“網(wǎng)格”這一參數(shù)，但該參數(shù)可以是一個(gè)計(jì)算結(jié)果。因此，任何在當(dāng)前環(huán)境下定義的表達(dá)式——包括常量值——都可以作為該參數(shù)。

與使用函數(shù)相比，這種模式的優(yōu)勢(shì)在于：在解析時(shí)可以高效地計(jì)算出位置和大小，方法只是在網(wǎng)格中查找子網(wǎng)格的出現(xiàn)位置即可。

在實(shí)際應(yīng)用中，Crop 模式僅被引入到輸出模型中，其 grid 參數(shù)來自輸入模型中的任意一個(gè)網(wǎng)格變量。出于可計(jì)算性的考慮，不考慮更復(fù)雜的表達(dá)式作為參數(shù)。

ARC 定義 8

表5列出了幾個(gè)用于 ARC 的依賴型模式。除了上面描述的 Crop 模式外，還包括：

• Recoloring（重著色）：當(dāng)存在某種對(duì)精靈圖像（sprite）的重著色操作時(shí)，將該圖像壓縮為對(duì)該 sprite 參數(shù)的重著色表示。

• Index（索引）：將整個(gè)值（一個(gè) n 維序列）作為某個(gè)參數(shù)（一個(gè) (n + k) 維序列）中的子結(jié)構(gòu)進(jìn)行定位，并將其壓縮為它的索引（一個(gè)長(zhǎng)度為 k 的一維序列）。

與只能使用少量固定索引的索引函數(shù)不同，Index 模式使得我們可以對(duì)索引位置進(jìn)行推理。

7.3 蒙特卡洛樹搜索（Monte Carlo Tree Search）

隨著模式和函數(shù)數(shù)量的增長(zhǎng)，貪心搜索陷入局部最小值的風(fēng)險(xiǎn)也隨之增加。除了利用 MDL（最小描述長(zhǎng)度）原則外，我們還希望引入更多的探索能力，以便從搜索路徑上的錯(cuò)誤步驟中恢復(fù)過來。

一種在“利用”與“探索”之間取得平衡的經(jīng)典方法是蒙特卡洛樹搜索（MCTS, Monte Carlo Tree Search）[27]。

在該方法中：

• 狀態(tài)（states）是任務(wù)模型 M；
• 根狀態(tài)（root state）是初始空任務(wù)模型 M?；
• 動(dòng)作（actions）是模型之間的轉(zhuǎn)換（transitions）；

一個(gè)狀態(tài)的價(jià)值（value）定義為：1 ? ? L?(M, E) ∈ [0, 1]，其中 L?(M, E) 是歸一化的描述長(zhǎng)度。這個(gè)定義使得更具壓縮性的模型具有更高的價(jià)值，而根狀態(tài)的價(jià)值為 0。

我們將 MCTS 的四個(gè)核心步驟定義如下：

? 選擇（Selection）：根據(jù)UCB1 策略選擇要擴(kuò)展的節(jié)點(diǎn)，探索常數(shù)設(shè)為 c = √2。當(dāng)兩個(gè)子節(jié)點(diǎn)得分相同時(shí)，優(yōu)先選擇描述長(zhǎng)度（DL）更小的那個(gè)節(jié)點(diǎn)，即優(yōu)先探索更有希望的子節(jié)點(diǎn)。? 擴(kuò)展（Expansion）：通過評(píng)估 Kt 個(gè)轉(zhuǎn)換后，選取其中歸一化 DL 最小的前 Kc 個(gè)轉(zhuǎn)換（Kc 表示“子節(jié)點(diǎn)數(shù)量”）來擴(kuò)展選定節(jié)點(diǎn)。因此，Kc 是搜索樹的最大分支因子。 ? 模擬（Rollout）：

使用貪心搜索（算法6.3）進(jìn)行模擬，由于該過程是確定性的，因此每個(gè)節(jié)點(diǎn)只進(jìn)行一次模擬。
不限制模擬的深度，模擬會(huì)在描述長(zhǎng)度無法進(jìn)一步減小時(shí)停止。

? 回傳（Backpropagation）：

回傳的價(jià)值基于模擬過程中最終任務(wù)模型的描述長(zhǎng)度。

8. 評(píng)估

我們從以下幾個(gè)方面對(duì) MADIL 方法在 ARC 上的表現(xiàn)進(jìn)行了評(píng)估：

• 在 ARC 任務(wù)的公開集和私有集上的性能表現(xiàn)；

• 搜索效率

• 對(duì)不同參數(shù)的敏感性。

此外，我們還分析了該方法的失敗情況和局限性。

我們的實(shí)驗(yàn)是在一臺(tái)配備16GB 內(nèi)存的 Intel Core i7x12 處理器、運(yùn)行Fedora 32 系統(tǒng)的機(jī)器上，通過單線程實(shí)現(xiàn)完成的。
相關(guān)的學(xué)習(xí)與預(yù)測(cè)日志可在 GitHub 倉庫中獲取。

8.1 性能與已解決任務(wù)

表6展示了我們的MADIL 方法在三個(gè)數(shù)據(jù)集上的性能表現(xiàn)（第一行）：

• 400 個(gè)公開訓(xùn)練任務(wù)，

• 400 個(gè)公開評(píng)估任務(wù)，

• 以及在不同競(jìng)賽中使用的 100 個(gè)私有任務(wù)。

我們?cè)谠O(shè)計(jì) MADIL 時(shí)只參考了訓(xùn)練任務(wù)，從未查看過評(píng)估任務(wù)，因此對(duì)評(píng)估任務(wù)的測(cè)試構(gòu)成了一個(gè)穩(wěn)健的評(píng)估。
性能指標(biāo)采用的是微平均準(zhǔn)確率（micro-accuracy），它根據(jù)每個(gè)成功預(yù)測(cè)的測(cè)試樣例按比例計(jì)算任務(wù)得分。例如，當(dāng)兩個(gè)測(cè)試樣例中有一個(gè)被正確預(yù)測(cè)時(shí)，該任務(wù)得分為 0.5。

本次報(bào)告的 MADIL 版本為 v3.5，是提交至ArcPrize’24的最終版本。我們將 MADIL 的性能與其他連續(xù)競(jìng)賽中的優(yōu)勝方法進(jìn)行了比較，也與多種基于大語言模型（LLM）的方法進(jìn)行了對(duì)比。其中依賴專有 LLM（從 o3 到 GPT-4o）的方法無法在私有數(shù)據(jù)集上運(yùn)行，因?yàn)樗鼈冃枰ヂ?lián)網(wǎng)連接。

在 400 個(gè)公開評(píng)估任務(wù)中，MADIL 找到了 69 個(gè)任務(wù)的解決方案，即找到了能夠正確預(yù)測(cè)所有訓(xùn)練樣例的任務(wù)模型。其中，有 57 個(gè)模型在所有測(cè)試樣例上也表現(xiàn)正確，泛化率達(dá)到82%。此外還有兩個(gè)任務(wù)雖然模型沒有完全理解訓(xùn)練樣例（僅理解了兩個(gè)訓(xùn)練樣例中的一個(gè)），但仍然做出了正確的預(yù)測(cè)。這表明 MADIL 有時(shí)可以對(duì)未被理解的訓(xùn)練樣例保持魯棒性。

在 ArcPrize’24 中，允許進(jìn)行兩次預(yù)測(cè)嘗試。但實(shí)際上，大多數(shù)任務(wù)在第一次嘗試中就得到了正確結(jié)果。具體來說，在 57 個(gè)已解決的任務(wù)中，有 53 個(gè)任務(wù)的所有預(yù)測(cè)在第一次嘗試中就全部正確。

圖7 展示了在所有評(píng)估任務(wù)（左側(cè)）和僅 57 個(gè)正確解（右側(cè)）中找到模型的大小分布情況。模型的“大小”是指它所包含的值、變量引用、函數(shù)、模式和未知量的總數(shù)。對(duì)于正確解來說，模型大小范圍在 3 到 46 之間，平均為 15.2。這意味著，如果使用暴力搜索來探索 MADIL 的 DSL（領(lǐng)域特定語言），必須搜索到深度高達(dá) 46 才能找到這些模型。這是不可行的——現(xiàn)有的暴力搜索方法最多只能處理深度為 3–4 的模型。只有 4 個(gè)任務(wù)的正確解模型大小小于等于 4。這證明了使用描述長(zhǎng)度來引導(dǎo)搜索的相關(guān)性和必要性。

更詳細(xì)地看，表7 展示了在 400 個(gè)找到的模型中，各種模式和函數(shù)的使用頻率。最常用的網(wǎng)格模式包括：

• BgColor（背景顏色）
• Objects（對(duì)象集合）
• Monocolor（單色）

這些模式共同可以將網(wǎng)格分解為某種背景色下的單色對(duì)象集合； 此外還有識(shí)別網(wǎng)格中各種幾何規(guī)律性的Motif 模式； 以及用于序列處理的模式如Cons（頭部/尾部）和Repeat（重復(fù)結(jié)構(gòu)）。

常見的函數(shù)包括：

• 減法（-）和加法（+），用于通過小常量增減數(shù)值；

• 向量的兩個(gè)分量 i 和 j 的訪問；

• 網(wǎng)格面積及半分對(duì)；

• 對(duì)序列的訪問操作（如索引、尾部）和聚合操作（如最大值 max）；

• 此外，顏色常量（COLOR）也非常常見。

我們還可以將 MADIL 的正確預(yù)測(cè)與 Icecuber 方法進(jìn)行對(duì)比，因?yàn)槲覀兡軌蛑匦逻\(yùn)行 Icecuber。我們只將那些所有測(cè)試輸出網(wǎng)格都被正確預(yù)測(cè)的任務(wù)視為“正確”。

在這個(gè)標(biāo)準(zhǔn)下，MADIL 在 59 個(gè)評(píng)估任務(wù)中表現(xiàn)正確，而 Icecuber 在 117 個(gè)任務(wù)中正確，幾乎是前者的兩倍。除了數(shù)量之外，我們還想知道這兩個(gè)方法在正確任務(wù)上的重疊程度。結(jié)果顯示，兩者確實(shí)存在大量重疊（共 43 個(gè)任務(wù)），但也仍有 16 個(gè)任務(wù)是 MADIL 獨(dú)立解決的，顯示出兩種方法之間的互補(bǔ)性。

8.2 搜索效率

搜索效率是擴(kuò)展表達(dá)能力（expressive power）的關(guān)鍵。事實(shí)上，隨著 DSL 原語數(shù)量的增加，搜索空間呈指數(shù)級(jí)增長(zhǎng)。根據(jù) Chollet [18] 的觀點(diǎn)，智能等價(jià)于“對(duì)新技能的高效獲取”。

表8 通過統(tǒng)計(jì)在搜索過程中所考慮的模型數(shù)量來衡量搜索效率。我們區(qū)分了：

• “所有模型”

  ：包括從初始模型到最終模型路徑上的所有中間模型；

• “最終模型”

  ：即 MCTS 模擬過程中的終點(diǎn)模型，它們代表任務(wù)的候選解。

我們還測(cè)量了對(duì)于找到的最佳模型，其搜索深度和它在最終模型中的排名。我們將這些指標(biāo)在兩個(gè)不同的任務(wù)集合上進(jìn)行了平均：

• 400 個(gè)評(píng)估任務(wù)（第一行）；

• 69 個(gè)實(shí)際找到了解決方案的任務(wù)（第二行）。

第一行數(shù)據(jù)顯示，盡管在所有任務(wù)中平均考慮了超過 28 個(gè)候選模型，但最佳模型通常很快被找到，平均排名為1.6。
總的訪問模型數(shù)平均為177，這在 180 秒的時(shí)間預(yù)算下看起來是較低的。
這一現(xiàn)象可以通過以下事實(shí)解釋：對(duì)于每個(gè)模型，計(jì)算其候選轉(zhuǎn)換、以及為每個(gè)精化的模型計(jì)算其最佳描述和描述長(zhǎng)度（以選擇 top-k 轉(zhuǎn)換）是非常耗時(shí)的。
平均搜索深度為17，對(duì)于一個(gè)隨深度指數(shù)增長(zhǎng)的搜索空間來說，這是一個(gè)很高的值；最大搜索深度甚至達(dá)到了43，并且在這個(gè)深度上確實(shí)找到了一個(gè)解（盡管它未能泛化到測(cè)試樣例）。

第二行顯示的搜索代價(jià)更低（45 vs 177），因?yàn)榇蠖鄶?shù)解決方案是在非常早期就被找到，平均排名為1.3。
實(shí)際上，在 69 個(gè)已解決任務(wù)中，有54 個(gè)任務(wù)是在第一次 MCTS 模擬中就找到了解，也就是通過貪心搜索就能找到。這表明了描述長(zhǎng)度的準(zhǔn)確性以及 MDL 原則的強(qiáng)大能力。

由于在某些任務(wù)中尚未找到解，系統(tǒng)會(huì)嘗試構(gòu)建更復(fù)雜的模型，因此平均搜索深度略低（為 11）。

圖8 展示了在不同最大運(yùn)行時(shí)間下，69 個(gè)任務(wù)中有多少比例的任務(wù)被成功解決。結(jié)果顯示：令人驚訝地，80% 的任務(wù)在前 20 秒內(nèi)就被解決，也就是大約在總時(shí)間預(yù)算的10%內(nèi)完成。

通過對(duì)各函數(shù)運(yùn)行時(shí)間占比的分析，我們發(fā)現(xiàn)：

• 一半的計(jì)算時(shí)間用于為某個(gè)模型計(jì)算示例描述（即describe 函數(shù)，見算法2）；

• 另一半時(shí)間用于為某個(gè)模型計(jì)算轉(zhuǎn)換（即transitions 函數(shù)，見算法5）； 其中，后者中約有三分之二的時(shí)間與表達(dá)式轉(zhuǎn)換有關(guān)。

8.3 參數(shù)與消融研究

在本節(jié)中，我們進(jìn)行了一項(xiàng)參數(shù)研究，目的是觀察表3中列出的各個(gè)參數(shù)變化對(duì)性能的影響。

更具體地說，我們關(guān)注的是那些在 MADIL 的任意版本（從 v3.2 到 v3.6）中都能被滿意解決的 71 個(gè)評(píng)估任務(wù)，并探索降低每個(gè)參數(shù)值（即減少搜索努力）所帶來的影響。我們將影響分為三類：

• “無影響”：任務(wù)數(shù)量沒有減少；
• “小幅影響”：只有少量任務(wù)失敗；
• “顯著影響”：大量任務(wù)失敗。

當(dāng)出現(xiàn)以下情況時(shí)，我們觀察到了顯著影響：

• 當(dāng)只采樣一個(gè)網(wǎng)格描述（Np = 1），或僅保留排名最高的示例描述（Kp = 1）時(shí)，分別失去了 19 個(gè)和 6 個(gè)任務(wù)。
  這說明：采樣多個(gè)描述對(duì)于找到好的描述至關(guān)重要；而多個(gè)示例描述對(duì)于找到好的轉(zhuǎn)換也很重要。
  然而，將 Np 設(shè)為 10（而非 100），或?qū)?Kp 設(shè)為 2（而非 3）僅造成小幅影響（僅失去 1 個(gè)任務(wù)）。

• 當(dāng)限制表達(dá)式大小為 Se = 1時(shí)，失去了 27 個(gè)任務(wù)。
  這表明復(fù)雜的表達(dá)式在解決問題中起到了重要作用。
  然而，在我們的任務(wù)樣本中，將 Se 設(shè)為 5（而非 9）并未導(dǎo)致任務(wù)丟失，反而節(jié)省了時(shí)間，使得在給定的時(shí)間預(yù)算下可以進(jìn)行更多搜索。

• 當(dāng)只使用最有希望的轉(zhuǎn)換（Kt = 1）或使用貪心搜索時(shí)，分別失去了 3 個(gè)和 4 個(gè)任務(wù)。
  這表明，盡管貪心搜索在大多數(shù)情況下有效，但為了跳出局部最小值，仍有必要引入更廣泛的搜索策略。

• 當(dāng)不使用復(fù)習(xí)因子 α 來計(jì)算描述長(zhǎng)度（即設(shè)為 α = 1）時(shí)，失去了 6 個(gè)任務(wù)。
  然而，將 α 設(shè)為 10（而非 100）則沒有影響。

• 當(dāng)既不使用測(cè)試輸入檢查也不進(jìn)行剪枝時(shí)，失去了 6 個(gè)任務(wù)。

總體來看，整個(gè)方法表現(xiàn)出非常強(qiáng)的魯棒性，因?yàn)橹挥性?strong>Np = 1和Se = 1的情況下才會(huì)出現(xiàn)顯著影響，而在所有其他情況下影響都是中等或可以忽略的。

唯一觀察到的積極影響出現(xiàn)在將Ne（候選表達(dá)式數(shù)量）設(shè)為 [30, 100] 范圍內(nèi)（而非 1000）時(shí)，這使得多解決了一個(gè)任務(wù)。
這是因?yàn)槊杜e候選表達(dá)式的開銷在此被轉(zhuǎn)化為更多的搜索機(jī)會(huì)所抵消，從而提升了整體性能。

8.4. 失敗任務(wù)與局限性

我們通過分析失敗的任務(wù)來研究我們方法的局限性。失敗有三種類型：
(a) 找到了一個(gè)解，但它不具備泛化能力；
(b) 看起來存在一個(gè)解，但沒有找到；
(c) 在當(dāng)前實(shí)現(xiàn)中確實(shí)不存在解。

泛化失敗（Generalization failures）

我們?cè)诖丝疾炝?1個(gè)訓(xùn)練任務(wù)，這些任務(wù)找到了一個(gè)解，但在某些或所有測(cè)試實(shí)例上是錯(cuò)誤的。主要原因是出現(xiàn)了虛假表達(dá)式（spurious expressions），它們能夠“補(bǔ)償”對(duì)網(wǎng)格的錯(cuò)誤分解方式。當(dāng)訓(xùn)練樣本較少、或者允許使用更大的表達(dá)式（參數(shù) Se）時(shí)，出現(xiàn)虛假表達(dá)式的風(fēng)險(xiǎn)會(huì)增加。經(jīng)過檢查，這些表達(dá)式看起來非常人為和牽強(qiáng)，根據(jù)MDL（最小描述長(zhǎng)度）原則，它們應(yīng)該受到強(qiáng)烈的懲罰。

這表明我們需要改進(jìn)表達(dá)式的描述長(zhǎng)度設(shè)計(jì)，并調(diào)整模型與數(shù)據(jù)之間的權(quán)衡（參數(shù) α）。

搜索失敗（Search failures）

我們?cè)诖丝疾炝?2個(gè)訓(xùn)練任務(wù)，這些任務(wù)在當(dāng)前實(shí)現(xiàn)下看似可解，但未能找到解。最常見的原因（21個(gè)任務(wù)）是有時(shí)需要非壓縮性轉(zhuǎn)換（non-compressive transitions）才能最終得到更壓縮的解。這表明我們可以進(jìn)行如下兩方面的改進(jìn)：

1. 允許一定程度上的非壓縮性轉(zhuǎn)換，例如采用類似“延遲接受爬山法”（late acceptance hill-climbing）這樣的啟發(fā)式方法；

2. 某些描述長(zhǎng)度的設(shè)計(jì)可能存在問題，高估了某些描述的信息量。尤其是在對(duì)象分割方面，未充分考慮連通性因素。

另一個(gè)常見原因（15個(gè)任務(wù)）是前 Kp 個(gè)描述不夠多樣化，導(dǎo)致遺漏了關(guān)鍵的轉(zhuǎn)換步驟。請(qǐng)記住，候選轉(zhuǎn)換是基于這些描述生成的。在計(jì)算描述時(shí)存在組合爆炸問題。假設(shè)一個(gè)模型將網(wǎng)格描述為某種背景顏色上的對(duì)象集合，而沒有額外限制條件，那么對(duì)于每種背景顏色、每種分割模式、每個(gè)對(duì)象排列順序等，都可能存在不同的描述。雖然描述長(zhǎng)度可以幫助選擇更相關(guān)的描述，但這種選擇可能在不同示例之間不一致。

這建議我們做出如下改進(jìn)：

1. 可以增加 Kp 的值，但這會(huì)帶來計(jì)算成本，而且面對(duì)組合復(fù)雜度時(shí)這種方法效果有限；

2. 可以接受僅基于部分訓(xùn)練樣例推導(dǎo)出的候選轉(zhuǎn)換，盡管這可能會(huì)顯著增加轉(zhuǎn)換計(jì)算的開銷；

3. 可以修改解析過程，改為為模型中的每個(gè)變量計(jì)算取值集合，而不是計(jì)算描述集合（描述是變量到取值的映射），從而打破組合復(fù)雜度。

其他搜索失敗的原因（13個(gè)任務(wù)）包括：候選轉(zhuǎn)換排序不佳導(dǎo)致解決方案遠(yuǎn)離當(dāng)前路徑、虛假表達(dá)式誤導(dǎo)搜索方向、以及計(jì)算密集型步驟拖慢搜索速度。

缺失的原始操作（Missing primitives）

為了覆蓋ARC任務(wù)所依賴的核心知識(shí)先驗(yàn)，我們?nèi)匀鄙僭S多基本操作：

• 非中心化的圖案（motifs）、旋轉(zhuǎn)后核心圖案的可比性、以及不同基本圖案的復(fù)雜組合；

• 更適合用繪圖算法理解的形狀，如螺旋形或樓梯形；

• 更魯棒的對(duì)象分割機(jī)制，特別是針對(duì)重疊、不連通對(duì)象的情況，以及利用不同示例間對(duì)象的相似性和差異性，例如盡可能優(yōu)先選擇相同形狀；

• 超越當(dāng)前基于向量相對(duì)位置的對(duì)象間拓?fù)潢P(guān)系，如“相鄰于”、“位于其上方”、“相對(duì)”等；

• 對(duì)網(wǎng)格方向不變性的支持；

• 將輸出（子）網(wǎng)格分段分解為多個(gè)部分的堆疊結(jié)構(gòu)——這是 Icecuber 方法的關(guān)鍵組成部分之一。

當(dāng)前DSL在處理序列方面也存在局限性。經(jīng)常需要根據(jù)某種模式將一個(gè)序列劃分為兩個(gè)子序列，但這里存在一個(gè)“先有雞還是先有蛋”的問題：既要找到劃分方式，又要找到對(duì)應(yīng)的模式。另一個(gè)限制是，輸出序列不僅僅是輸入序列的映射，有時(shí)還需要添加或刪除某些元素。最后，我們幾乎完全避免使用n元表達(dá)式（即使用多個(gè)變量的表達(dá)式），以防止在枚舉表達(dá)式時(shí)出現(xiàn)組合爆炸。這一點(diǎn)部分通過序列上的關(guān)系矩陣得到了補(bǔ)償。定義像 Px 這樣更具依賴性的模式，而不是使用像 f(x, y) 這樣的二元函數(shù)，可能有助于解決這個(gè)問題。

當(dāng)前方法的局限性

還有一些限制似乎不容易、甚至不可能通過向DSL中添加原始操作來彌補(bǔ)。第一個(gè)限制是，模式是在單個(gè)網(wǎng)格上分別解析的，因此無法獲得全局視角。如果能夠同時(shí)解析所有輸入網(wǎng)格或所有輸出網(wǎng)格，將會(huì)更有益，有時(shí)甚至是必要的。例如，這將有助于在不同示例之間一致地選擇分割模式或圖案。此外，將輸入和輸出網(wǎng)格一起建模也會(huì)更有幫助，而不是分別處理。例如，這可以幫助識(shí)別哪些部分保持不變、哪些部分發(fā)生了變化，從而指導(dǎo)分割過程。

另一個(gè)限制是缺乏關(guān)鍵結(jié)構(gòu)，如條件語句和遞歸。雖然這類任務(wù)不是大多數(shù)，但確實(shí)有一些任務(wù)依賴于這些結(jié)構(gòu)。已有早期關(guān)于程序合成的研究可以作為基礎(chǔ) [6, 23, 24]。

我們?cè)诖酥赋龅淖詈笠粋€(gè)限制——當(dāng)然還有其他限制——是候選表達(dá)式轉(zhuǎn)換是通過值在表達(dá)式DAG（有向無環(huán)圖）中檢索的，因此依賴于表達(dá)式結(jié)果與期望值之間的簡(jiǎn)單相等性。如果能有一個(gè)類似基于內(nèi)容的信息檢索（CBIR）系統(tǒng)，將會(huì)強(qiáng)大得多。例如，一個(gè)網(wǎng)格查詢可以返回包含該網(wǎng)格的更大網(wǎng)格，或者該網(wǎng)格的對(duì)稱形式；一個(gè)序列查詢可以返回包含該序列的更長(zhǎng)序列，或者該序列的簡(jiǎn)單變換形式（例如去重、反轉(zhuǎn)）。

9. 結(jié)論與展望

我們?cè)敿?xì)介紹了一種新的程序合成方法——MADIL，它基于描述性模型和最小描述長(zhǎng)度（MDL）原則。在這一框架下，一個(gè)程序通過使用輸入模型對(duì)輸入進(jìn)行分解，并使用輸出模型將該分解作為輸入來構(gòu)造輸出，從而實(shí)現(xiàn)從輸入到輸出的映射。從輸入-輸出示例中學(xué)習(xí)一個(gè)程序的過程遵循MDL原則，尋找能夠最好地壓縮這些示例的一對(duì)模型。

將MADIL應(yīng)用于某個(gè)領(lǐng)域（即某類任務(wù)），主要在于定義一組模式（patterns），其中每個(gè)模式支持某些值的分解與組合。在本文中，我們將重點(diǎn)放在Abstraction and Reasoning Corpus