專家的問題求解依賴於強大的思維方式語言——即用於思考問題及其解決方案的語言系統。獲得專業知識意味著學習這些語言——包括概念體系以及使用它們的技能。我們提出了 DreamCoder ，一個透過編寫程式來解決問題的學習系統。它透過創建用於表達領域概念的程式語言，並結合神經網路引導在這些語言中搜索程式的過程，從而逐步建構專業知識。一種「覺醒-睡眠」（wake-sleep）學習演算法交替地擴展語言，加入新的符號抽象，並在想像和回放的問題上訓練神經網路。DreamCoder 能夠解決經典的歸納程式設計任務，也能完成創造性任務，例如繪製圖像和建構場景。它重新發現了現代函數式程式設計、向量代數以及經典物理學的基本原理，包括牛頓定律和庫侖定律。概念是以組合方式從先前學到的內容中建構出來的，形成多層的、可解釋的符號表示，這些表示可以遷移到新任務中，同時仍能隨著經驗的增長而靈活、高效地擴展。
人工智慧（AI）長期以來的一個夢想是建構出像兒童一樣學習的機器（1）——即從極少的知識出發，逐漸成長到人類成年所擁有的全部知識。然而這一目標仍然遙遠，因為人類智慧依賴於許多尚未被人工系統掌握的學習能力。雖然目前的機器通常為單一類別的任務設計，但人類卻能學會解決各種各樣的問題，從烹飪到微積分再到平面設計。此外，雖然機器學習通常需要大量數據且泛化能力較弱，而人類往往只需少量經驗就能實現強泛化。也許最顯著的區別在於：人類會建構專業知識——我們獲得可以交流和拓展的知識，在已有概念的基礎上不斷生成新概念，從而在掌握某一領域後變得越來越擅長學習、學得更快。
本文介紹了 DreamCoder，這是一種旨在更接近人類能力的機器學習系統——能夠在廣泛領域中高效地發現可解釋、可複用且可泛化的知識。DreamCoder 體現了一種我們稱之為「覺醒-睡眠貝葉斯程式歸納」（wake-sleep Bayesian program induction）的方法。本節其餘部分將解釋其背後的核心思想：將學習視為程式歸納意味著什麼；為什麼將程式歸納視為貝葉斯模型中的推理是有價值的；以及「覺醒-睡眠」演算法如何使模型隨著經驗累積而不斷成長，從而以更高效的方式學習，使得這種方法具有實用性和可擴展性。
我們將學習表述為程式歸納的方法可以追溯到人工智慧發展的早期階段（2）：我們將學習一個新任務視為在程式空間中搜索能夠解決該任務、或具有預期行為的程式。圖1展示了DreamCoder所應用的八個不同領域中的程式歸納任務範例（圖1A），以及經典列表處理領域中一個任務的深入說明：在僅給出少量輸入-輸出範例的情況下，學習一個對數字列表進行排序的程式（圖1B）。與純統計方法相比，將學習視為程式歸納帶來了某些優勢。
符號化程式展現出強大的泛化能力——直觀上，它們傾向於外推而不是僅僅內插。這也使得學習過程非常樣本高效：通常只需幾個範例就足以指定要學習的某個函數。從設計上來看，程式是高度人類可解釋的：它們涵蓋了我們科學和工程中的標準建模語言，並揭示了可用於重用和組合的知識，以解決日益複雜的任務。最後，程式是通用的：原則上，任何圖靈完備的語言都可以表示智慧所能解決的所有計算問題。
然而，儘管具備這些優勢，並且在多個領域取得了成功應用（3–9），程式歸納在AI領域的影響力仍然有限。貝葉斯框架有助於闡明其中的挑戰，同時也指出了應對這些挑戰的路徑。我們用於搜索的程式語言定義了學習的假設空間和先驗概率；在該語言中越短的程式，其先驗概率越高。雖然任何通用程式語言都支援程式歸納，但以往的系統通常發現必須從精心設計的領域特定語言（DSL）開始，這種DSL提供了強有力的、人工調整的歸納偏置或先驗知識。沒有 DSL 的話，要發現的程式會過長（先驗概率低），從而在合理的時間內難以被搜索到。即使有了精心設計的先驗，由於搜索空間的組合性質，尋找最優程式的搜索對於通用演算法來說幾乎總是難以處理的。因此，大多數實際的程式歸納應用不僅需要手工設計的DSL，還需要專門設計的搜索演算法來利用該DSL實現快速推理。這兩個要求限制了程式歸納的可擴展性和廣泛適用性。
DreamCoder透過在一個給定領域中學習緊湊地表示並高效地歸納程式，解決了這兩個瓶頸問題。該系統實現了「學會學習」——寫出更好的程式，並更高效地搜索這些程式——它透過共同建構兩種不同類型的領域專業知識來實現這一點：（1）明確的陳述性知識，表現為一種學習到的領域特定語言，捕捉跨任務常見的概念抽象；（2）隱式的程式性知識，表現為一個神經網路，指導如何使用學習到的語言來解決新任務，體現為一種學習到的領域特定搜索策略。從貝葉斯的角度來看，該系統同時學習了程式的先驗分布，以及一個由神經網路參數化的推理演算法，用於高效近似在觀察任務數據條件下的程式後驗分布。
DreamCoder以一種自監督、自我引導的方式學習這兩方面的內容，在多次面對一組訓練任務的過程中逐步建構兩者。這使得學習可以在新領域中擴展，並且只要接收到足夠多樣化的訓練任務，也可以在某一領域內部擴展。通常只需要中等數量的任務就足以在新領域中啟動學習過程。例如，圖1B中展示的列表排序函數代表了系統循環處理的109個任務之一，系統在學習過程中逐步建構了一個包含約20個基本操作的庫，用於處理數字列表，而這些操作又成為解決未來遇到的新任務的基礎組件。
DreamCoder學習的語言形式是多層次的抽象層級結構（圖1B 和 圖7A、B）。這些層級結構類似於深度神經網路中的內部表示，但在這裡，每一層都是基於之前程式碼層定義的符號程式碼建構而成，使這些表示自然地具有人類可解釋性和可解釋性。抽象網路隨著時間推移逐漸增長，每一層概念都建立在先前獲得的概念之上，這靈感來源於人類建構概念體系的方式：我們在學習微積分之前先學代數，而在代數之前先學算術；我們在學習繪製複雜圖案之前先學習簡單形狀的繪製。例如，在列表處理的例子中（圖1B），我們的模型透過調用一個四層深的庫組件——「取第n大的元素」——來實現對數字序列的排序，而該組件又調用了更低層次的學習概念：最大值（maximum）和過濾（filter）。理論上，等效的程式也可以用起始語言編寫，但最終學習到的語言生成的程式更加易於理解且更簡短。如果僅用初始原語表達，這些程式將過於複雜，以至於學習者無法在合理的時間內找到它們。只有在獲得了領域特定的專業知識之後，大多數問題才變得在實踐中可解。
DreamCoder這個名字來源於它以「醒-睡」循環的方式迭代式地增長領域知識，這種機制粗略地受到睡眠不同階段中發生的記憶鞏固過程的啟發（10, 11）。總體而言，「醒-睡」貝葉斯學習（12）在訓練一個定義學習者先驗的概覽生成模型和一個神經網路識別模型之間進行交替，後者學會在給定新數據的情況下反轉這個生成模型。在「清醒」階段，使用生成模型來解釋新數據，並由識別模型進行引導；而在「睡眠」階段，識別模型則透過從生成模型採樣的虛構數據集（稱為「夢境」或「幻想」）進行離線學習。
DreamCoder發展了用於程式學習的「醒-睡」方法：其學習到的語言定義了一個覆蓋程式和任務的生成模型，其中每個程式解決一個特定的假設性任務；其神經網路則學習識別任務之間的模式，以最好地預測可能解決任何給定新任務的程式組件。在「清醒」階段，系統會接收到多個任務的數據，並嘗試合成能夠解決這些任務的程式，同時利用神經識別模型提出候選程式。學習發生在兩個不同但交錯的「睡眠」階段中：一個是透過整合「清醒」階段找到的程式中的新抽象來擴展所學語言（即生成模型）；另一個則是透過對從生成模型中採樣的「幻想」程式進行訓練來優化神經網路（即識別模型）。
這種「醒-睡」架構建立在兩個已有思想的基礎上並進一步將它們融合：貝葉斯多任務程式學習（5, 13, 14）和神經引導的程式綜合（15, 16），這兩個方向在最近的文獻中各自具有重要影響，但在我們的工作中才首次被結合在一起，最早始於EC2演算法（17），而如今在DreamCoder中實現了更大規模的擴展（詳見S3部分對前期工作的進一步討論）。
由此產生的系統具有廣泛的應用潛力。我們描述了其在八個領域中的應用（圖1A）：經典的程式合成挑戰、更具創造性的視覺繪圖與建構問題，以及最終捕捉遞歸程式設計、向量代數和物理基本語言的庫學習。我們所有的任務都涉及從極少量的數據中歸納程式，例如一個新概念或函數的五到十個範例，或者一張描繪新對象的圖像或場景。所學到的語言涵蓋了確定性和概率性程式，以及既可以生成式地運行（如生成圖像或計畫）也可以條件式地運行（如將輸入映射到輸出）的程式。
綜上所述，我們希望這些應用能夠說明程式歸納在人工智慧系統中成為一種實用、通用且數據高效的建構可解釋、可重用知識的方法的潛力。
醒/睡程式學習
我們現在描述DreamCoder中學習的具體細節，首先概述演算法及其數學形式化表達，然後深入講解其三個階段的細節。學習過程是疊代進行的，每一次疊代（公式1，圖2）都會經歷一個「清醒」階段和兩個「睡眠」階段的循環：在「清醒」階段嘗試解決任務，隨後透過兩個「睡眠」階段來學習如何解決新任務。
在清醒階段（圖2頂部），系統在訓練集中抽取任務，並嘗試搜索能夠解決這些任務的程式。神經識別模型會根據每個任務所觀察到的數據對候選程式進行排序，從而引導整個搜索過程。候選程式會根據兩個標準進行打分：一是它們對當前任務的解決程度，二是根據已學習的程式生成模型，該程式在先驗上是否合理。
第一個「睡眠」階段被稱為抽象階段（圖2左側），它透過重放「清醒」階段的經驗，從任務解決方案中提取常見的程式片段，並將這些片段抽象為新的程式碼基本單元，從而擴展程式設計原語庫（即生成模型）。這一機制增加了學習者陳述性知識的廣度與深度——當我們將學習到的庫看作一個網路時，就如圖1B或圖7所示。
第二個「睡眠」階段我們稱之為夢境階段（圖2右側），它透過訓練用於輔助程式搜索的神經網路，來提升學習者編寫程式碼的程式性技能（即操作技能）。
神經識別模型不僅在重放的經驗上進行訓練，還在「幻想」（fantasies）數據上進行訓練。「幻想」是指從已學習的庫中隨機採樣的程式——作為生成模型。這些隨機程式定義了系統在夢境階段需要解決的任務，並且神經網路被訓練為：根據每個想像任務的可觀測數據，預測所找到的解決方案。
從概率推理的角度來看，DreamCoder觀察一組任務組成的訓練集，記作 X，並推斷出兩個內容：一是每一個任務 x ∈ X 的求解程式 ρx；二是該領域中可能解決任務的程式的先驗分布（如圖2中間所示）。這個先驗由一個庫（記作 L）來編碼，它定義了一個關於程式的生成模型，記作 P[ρ|L]（詳見S4.3節）。神經網路透過以任務的觀察範例為條件，預測一個關於可能解決該任務的程式的近似後驗分布，從而幫助尋找解決問題的程式。因此，該網路作為一個識別模型（recognition model），與生成模型聯合訓練，這種做法借鑒自Helmholtz機器（12）。我們用 Q(ρ|x) 表示識別模型預測的近似後驗分布。
從高層次來看，「醒-睡」循環對應於如圖2所示的一系列更新操作；這些更新旨在最大化給定任務集合 X 下關於庫 L 的後驗的一個下界（詳見附錄 S4.1）。
其中，P[L] 是對庫（library）的一個描述長度先驗（見附錄 S4.5），而 P[x|ρ] 是在給定程式 ρ 的情況下任務 x ∈ X 的似然。例如，當任務 x 是由輸入/輸出指定時，這個似然值為 0 或 1；而在學習一個概率性程式時，該似然是該程式生成所觀察到任務的概率。
這個三階段推理過程透過兩種不同形式的「自我引導」（bootstrapping）機制來實現。在每一次睡眠循環中，下一個版本的庫都基於前幾個循環中學到的概念建構，從而使得學習到的庫變得越來越深、越來越豐富。同時，生成模型和識別模型也在相互引導：一個更專業的庫可以為識別模型提供更豐富的「夢境」進行學習；而一個更準確的識別模型則可以在清醒階段解決更多任務，這些任務又會反饋給下一個版本的庫。
這兩個「睡眠」階段還共同緩解了程式合成過程中伴隨而來的組合爆炸問題。更高層次的庫例程允許用更少的函數調用來解決問題，從而有效地減少了搜索的深度；而神經識別模型則會降低那些在程式空間中不太可能路徑的權重，從而有效減少搜索的廣度。
清醒階段
清醒階段的任務是尋找具有高後驗概率的特定任務程式，即那些兼具高似然（因為它們能解決任務）和高先驗概率（因為它們在當前語言中的描述長度較短）的程式。在每一次清醒循環中，我們從訓練集的一個隨機小批量（minibatch）中採樣任務（或者根據領域大小和複雜度，也可能使用整個訓練集）。然後，我們透過按照識別模型 Q(ρ|x) 下的概率降序枚舉程式，來搜索能夠解決每個任務的程式，並檢查某個程式 ρ 是否對該任務的求解分配了正概率（即 P[x|ρ] > 0）。
由於模型可能會找到許多能夠解決某一特定任務的程式，我們只保留一小部分（beam search 中的 k = 5）具有最高後驗概率 P[ρ|x, L] 的程式，並在 Eq. 1 的睡眠更新中對這組候選程式進行邊緣化處理。
我們將程式表示為多態類型化的 λ 演算表達式（polymorphically typed λ-calculus expressions），這是一種表達能力很強的形式系統，包含條件語句、變數、高階函數，以及定義新函數的能力。
抽象階段
在抽象睡眠階段，模型透過擴展其概念庫來增長自身的知識體系，目標是發現一些專門化的抽象結構，從而使其能夠更容易地表達當前任務的解決方案。所謂「表達的簡便性」轉化為一種對庫的偏好：那些最能壓縮清醒階段所找到程式的庫將被優先選擇。抽象睡眠的目標（公式1）等價於最小化庫的描述長度（−log P[D]），加上對清醒階段所找到程式進行重構後的描述長度之和。
直觀上，我們透過「壓縮重複使用的程式碼」來最大化一個貝葉斯準則；但與壓縮重複的語法結構不同，我們透過對程式進行重構來揭示其中重複出現的語義模式。
程式碼可以以無限多種方式進行重構，因此我們限制了程式與其重構之間的 λ 演算求值步驟數，從而得到一個有限但通常極其龐大的重構集合。圖3展示了一個例子：模型從一組通用原語（包括透過Y組合子實現的遞歸）出發，逐步發現了現代函數式程式設計中最基本的構建塊之一——高階函數map。在這個例子中，可能的重構方式大約有 10¹⁴ 種——這個數量隨著程式大小和允許的最大求值步數呈指數級增長。
為了解決這一指數爆炸問題，我們引入了一種新的數據結構用於表示和操作這些重構集合，它結合了版本空間代數（version space algebras）和等價圖（equivalence graphs）的思想，並推導出了用於其構造的動態規劃演算法（見附錄 S4.5）。這種數據結構的增長速度與程式大小成多項式關係，這得益於對共享子樹的因子化表示；但它與最大求值步數的界限之間仍是指數關係。我們可以透過設置較小的界限（例如設為3）來控制這個指數項的規模，而不會影響性能。結果帶來了顯著的效率提升：一個包含 10⁶ 個節點的版本空間可以在幾分鐘內計算出來，它可以代表圖3中原本需要幾個世紀才能顯式枚舉和搜索的 10¹⁴ 種重構方式。
夢境階段
在夢境睡眠階段，系統訓練其識別模型，以便在後續的清醒階段加速問題求解過程中的程式搜索。我們將識別模型實現為神經網路，並透過網路結構注入領域知識：例如，在從圖像中歸納圖形程式時，我們使用卷積網路，使其偏向於學習有用的圖像特徵。
我們在兩類自我監督的數據來源上訓練識別網路：一是清醒階段發現程式的重放數據，二是「幻想」數據，即從庫 L 中採樣的程式。重放數據確保識別模型能夠在實際需要解決的任務上進行訓練，並且不會遺忘如何解決它們；而「幻想」則提供了大量且高度多樣化的訓練數據，對於數據效率至關重要：成為某個領域的專家既不是一個少樣本學習問題，也不是一個大數據問題。我們通常在 100–200 個任務上訓練 DreamCoder，這對於一個高容量的神經網路來說樣本量太小。然而，一旦模型學會了定制化的領域庫，我們就可以從中無限地採樣或生成「夢境」，用來訓練識別網路。
我們的夢境階段與傳統的「醒-睡」（wake-sleep）方法中的夢境階段有所不同。經典的「醒-睡」方法會從生成模型中採樣一個隨機程式，執行該程式以生成一個任務，並訓練識別網路從該任務中預測出所採樣的程式。而我們則將「做夢」視為生成一連串隨機問題的過程，並在睡眠期間透過一種主動的方式，使用與清醒階段相同的程式搜索過程來解決這些問題。然後我們訓練識別網路，使其能夠根據這些問題來預測所發現的解決方案。
具體來說，我們透過最大化以下期望值來訓練識別模型 Q，使其執行最大後驗（MAP）推理：
其中期望是對所有任務取的。如果這個期望是相對於任務的經驗分布計算的，則訓練數據就是重放數據；如果它是相對於生成模型的採樣計算的，則訓練數據就是幻想數據。我們在重放數據和幻想數據之間採用 50/50 的混合比例進行訓練；對於那些從輸入映射到輸出的幻想任務，我們從訓練任務中採樣輸入。雖然理論上可以訓練 Q 執行完整的後驗推理，但我們的 MAP 目標具有一項優勢：它教會識別網路為每個問題找到最簡單、標準的解決方案。更技術性地說，我們的 MAP 目標透過迫使網路將所有的概率質量集中在一個語義等價但語法不同的表達式集合中的唯一一個成員上，從而打破了程式空間中的語法對稱性。手工編寫的對稱性打破機制已被證明對許多程式合成器至關重要（22, 23）；關於 DreamCoder 所學習到的對稱性打破機制的回溯與實證分析，請參見附錄 S4.6。
結果
我們首先在兩個經典的基準領域中對 DreamCoder 進行了實驗性研究：列表處理（list processing）和文本編輯（text editing）。在這兩種情況下，任務都透過條件映射（即輸入/輸出範例）來定義，並從一個通用的函數式程式設計基礎開始訓練，包括如map、fold、cons、car、cdr等基本例程。
我們的列表處理任務共包含來自（17）的 218 個問題，按 50/50 的比例劃分為測試集和訓練集，每個任務提供 15 個輸入/輸出範例。在解決這些問題的過程中，DreamCoder 合成了大約 20 個新的庫例程（見附錄 S1.1），並重新發現了諸如filter等高階函數。每一次抽象循環都在前幾次睡眠週期中發現的概念基礎上建構——例如模型首先學會了filter，然後用它學會提取列表中的最大元素，接著用這個例程學會一個新的庫例程來提取列表中第 n 大的元素，最終使用這個新例程實現了數字列表的排序（見圖1B）。
合成能夠編輯文本的程式是程式語言與人工智慧文獻中的一個經典問題（18），並且用於合成文本編輯程式的演算法已經應用於 Microsoft Excel（7）。例如，這類系統可以觀察到「Alan Turing」 → 「A.T.」這樣的映射關係，並推斷出一個將「Grace Hopper」轉換為「G.H.」的程式。以往的文本編輯程式合成器依賴於人工設計的基本操作庫和人工設計的搜索策略。而在這裡，我們聯合學習這兩個要素，並取得了與當前最先進的通用領域程式合成器相當的表現。
我們在 128 個自動生成的文本編輯任務上訓練系統，並在 2017 年 SyGuS（24）程式合成競賽中的 108 個文本編輯問題上進行測試。在學習之前，DreamCoder 在 10 分鐘內解決了 3.7% 的問題，平均搜索時間為 235 秒；而在學習之後，它解決了 79.6% 的問題，並且速度快得多，平均求解時間僅為 40 秒。本次競賽中表現最好的合成器 CVC4 解決了 82.4% 的問題——但比賽條件是每道題分配 1 小時時間和 8 個 CPU 核心，在這種更寬鬆的計算資源條件下，我們解決了 84.3% 的問題。
此外，SyGuS 每個文本編輯問題都配有各自不同的手工設計的基本操作庫。而我們僅學習了一個適用於所有編輯任務的統一文本編輯概念庫，這是實際應用中的一項必要前提。
接下來我們考慮更具創造性的任務：生成圖像、計畫和文本。程式化或生成式的視覺概念——從 Bongard 問題（25）、手寫字符（5, 26）到 Raven 推理矩陣（27）——在人工智慧與認知科學中被廣泛研究，因為它們連接了低層次感知與高層次推理之間的橋樑。
在此我們受到 LOGO 海龜繪圖（Turtle graphics）（28）的啟發，讓模型控制一支「畫筆」，並具備命令式流程控制能力以及角度和距離上的算術運算能力，任務是繪製一個由 160 張圖像組成的語料庫（按 50/50 劃分測試集和訓練集；見圖4A）。在訓練 DreamCoder 經歷了 20 輪「醒-睡」循環後，我們檢查了所學到的庫（見附錄 S1.1），發現了可解釋的參數化繪圖例程，這些例程對應其訓練數據中視覺對象的類別，如多邊形、圓形和螺旋線（圖4B）——系統在無監督的情況下學會了其視覺世界中的基本對象類型。
此外，它還學會了更抽象的視覺關係，如徑向對稱性（radial symmetry），並透過將其抽象為一個新的高階函數加入到庫中（圖4C）。
可視化系統在其學習過程中所做的「夢境」，可以揭示生成模型是如何引導識別模型訓練的：隨著庫的增長並越來越適應當前領域，神經網路接收到的訓練數據也變得更加豐富和多樣化。在學習初期，使用庫所編寫的隨機程式是簡單且結構鬆散的（圖4D），對識別模型的訓練價值有限；而在學習之後，系統的「夢境」變得結構豐富（圖4E），以創造性的方式組合從訓練數據中獲得的潛在建構模塊和模式，這些方式在其清醒經驗中從未出現過，但卻非常適合用於訓練一個具有廣泛泛化能力的識別模型（29）。
受經典人工智慧「複製演示」任務（copy demo）啟發——在這個任務中，智能體觀察一個由積木搭建的塔，然後嘗試重新建構它（30）——我們接下來給 DreamCoder 提供了 107 個「複製塔」的任務（按 50/50 劃分測試集與訓練集，見圖5A），其中系統需要同時觀察一個塔的圖像及其每個積木的位置，並編寫一個程式來規劃一個模擬機械手如何建造這座塔。系統使用的控制流原語與 LOGO 圖形相同。在其學習到的庫中，我們發現了用於建構積木塔的參數化「選項」（options）（31），包括拱門、樓梯和橋梁等概念，這些概念也在模型的夢境中出現（圖5C-D）。
接下來我們考慮少樣本學習概率性生成概念的能力，這是人類自然具備的一項能力，例如學習自然語言中的新規則（32）、學習符號和標誌的常規模式（5），或學習產生詞語的新運動程式（33）。我們首先讓 DreamCoder 從少量字符串中推斷出一個概率性正則表達式（Regex，參見圖1A中的範例），這些字符串來自從網頁爬取的 256 個 CSV 列（數據來源：(34)，任務按 50/50 劃分測試集與訓練集，每個概念提供 5 個字符串範例）。系統學會了學習描述典型文本概念結構的正則表達式，如電話號碼、日期、時間或金額（見圖S5）。它可以解釋許多現實世界中的文本模式，並將其解釋作為概率性生成模型，用來想像這些概念的新實例。
例如，儘管 DreamCoder 並不了解美元金額的概念，但它可以從 $5.70、$2.80、$7.60 等範例中推斷出背後的一個抽象模式，並生成 $2.40 和 $3.30 這樣的其他範例。對於帶有例外的情況，如 -4.26、-1.69、-1.622、…、-1，它會推斷出一個概率模型，通常生成像 -9.9 這樣的字符串，偶爾也會生成像 -2 這樣的異常情況。它還可以學習一些更冷門的概念——這些概念可能人類也不熟悉，但只需幾個例子就能快速學會並進行推廣：例如給出 -00:16:05.9、-00:19:52.9、-00:33:24.7 等範例後，它推斷出一個生成概念，能夠生成 -00:93:53.2，以及諸如 -00:23=43.3 這樣的合理近似結果。
最後我們考慮推斷生成平滑軌跡的實值參數方程（見附錄 S2.1.6 和圖1A，「符號迴歸」）。每個任務的目標是對特定曲線生成的數據進行擬合——該曲線要麼是有理函數，要麼是最高四次的多項式。我們為 DreamCoder 初始化了加法、乘法、除法操作，以及關鍵的任意實值參數，並透過內循環梯度下降優化這些參數。我們將每個參數化程式建模為概率性地生成一組曲線，並透過貝葉斯信息準則（BIC）（35）懲罰這些連續參數的使用。我們的貝葉斯機制學會了聚焦於那些既能解釋數據又能盡量避免使用多餘連續參數的程式。例如，當給定 1.7x² − 2.1x + 1.8 的實值數據時，它推斷出一個包含三個連續參數的程式；而當給定 x−2.2/3.8 的數據時，它推斷出一個僅包含兩個連續參數的程式。
跨領域對 DreamCoder 的定量分析
為了更好地理解 DreamCoder 是如何學習的，我們將完整的系統與幾種缺失關鍵組件的變體進行了對比實驗，這些變體分別缺少神經識別模型（即「夢境」睡眠階段）或形成新庫例程的能力（即「抽象」睡眠階段）。我們還與以下幾種基準方法進行了對比：
- 探索-壓縮（Exploration-Compression）（13）：交替搜索程式並壓縮出重複使用的組件，形成一個學習到的庫，但沒有使用我們的重構演算法；
- 神經程式合成（Neural Program Synthesis）：在初始庫的樣本上訓練一個 RobustFill（16）模型；
- 枚舉法（Enumeration）：為每個任務執行 24 小時的類型導向枚舉（23），生成並測試多達 4 億個程式。
為了隔離壓縮機制在學習良好庫中的作用，我們還建構了兩種「記憶」（Memorize）基準線。這些變體透過將任務解決方案整體納入庫中作為新的基本操作來擴展庫；它們不嘗試進行壓縮，而是簡單地記住清醒階段找到的解決方案，以便在新問題上重用（參見 (36)）。我們評估了有和沒有神經識別模型的「記憶」變體。
在多個領域中，我們的模型始終解決了最多的保留測試任務（圖6A；關於記憶基準線請參見圖S13），並且通常以最短時間完成（平均 54.1 秒；中位數 15.0 秒；圖 S11）。這些結果表明，DreamCoder 的核心組件——在「睡眠-抽象」階段透過重構和壓縮進行庫學習，在「睡眠-夢境」階段進行識別模型學習——都對其整體性能做出了實質性貢獻。
這些組件之間的協同效應在更具創造性和生成性的結構建構領域（如 LOGO 圖形和塔樓建造）中尤為明顯：在這些領域中，任何替代模型都無法解決超過 60% 的保留任務，而 DreamCoder 學會了解決幾乎 100% 的任務。圖6A 所示 DreamCoder 訓練至收斂所需的時間因領域而異，但在適度計算資源下（20–100 個 CPU），通常只需大約一天即可完成。
透過觀察所學庫隨時間的增長情況（無論是否包含學習到的識別模型），我們發現了其深度和規模上的功能顯著差異。在各個領域中，更深的庫與更高的任務解決率密切相關（相關係數 r = 0.79），而具備學習到的識別模型的系統在所有深度上表現更優。此外，識別模型也促使最終學到的庫具有更深的層次，從而達到更高的漸近性能水平（圖6B，圖S1）。學習庫的大小與性能之間也存在類似但較弱的關係。因此，識別模型似乎引導出了「更好」的庫，其中「更好」與所學符號表示的深度和廣度都相關。
從 DreamCoder 的識別模型如何引導庫學習的角度來看，我們分析了這些表示是如何共同嵌入待解決問題的相似性結構的。DreamCoder 首先在識別網路的啟動中編碼一個任務，然後用一個能解決該任務的符號程式重新表示這個任務。隨著學習過程的推進，這些隱式的初始表示逐漸與最終程式解決方案的顯式結構趨於一致，表現為識別網路啟動空間中問題相似性與用於解決問題的程式碼組件相似性之間的相關性不斷增強（參見圖S4；使用 χ² 檢驗，學習前後 p < 10⁻⁴）。透過 t-SNE 嵌入可視化這些學到的任務相似性後發現，隨著模型獲得更豐富的概念詞彙，其表示逐漸將具有更高抽象共性的任務歸類在一起（圖S3）——這可能類似於人類領域專家學會根據問題背後的原理而非表面相似性進行分類的方式（37, 38）。
從學習庫到學習語言
我們到目前為止的實驗研究了 DreamCoder 如何從一個「初學者」狀態開始成長，初始時給定了一些基本的領域特定過程，使得只有最簡單的問題具有簡短、直接的解決方案；而隨著系統逐漸成長為「專家」狀態，它掌握了各種概念，使即使最難的問題也能透過簡短、有意義的程式來解決。現在我們提出一個問題：是否可以從一個更精簡的起點出發進行學習，甚至在一開始就不具備任何基礎的領域知識？DreamCoder 是否可以僅從高度通用的程式設計和算術原語出發，逐步發展出一種既包含基礎又包含高級領域概念的領域專用語言，從而能夠解決某個領域中的所有問題？
受經典物理學中從實驗數據推斷物理定律的研究啟發（39–41），我們首先讓 DreamCoder 學習描述 60 條不同的物理定律和數學恆等式，這些定律和恆等式來自 AP 和 MCAT 物理考試的「速查表」，並基於每個公式所對應的數值範例數據進行學習。完整數據集包括許多力學與電磁學中廣為人知的定律，這些定律自然地用諸如向量、力和比值等概念表達。但與直接提供這些數學抽象不同，我們只給 DreamCoder 初始化了一個更加通用的基礎——少量遞歸序列操作原語（如map和fold）以及基本算術操作，並測試它是否能自行學習出適用於物理學的數學語言。
事實上，在經歷了 8 次「醒-睡」循環後，DreamCoder 成功學習了數據集中 93% 的定律和恆等式。它首先學會了向量代數的基本建構模塊，例如內積、向量和與範數（圖7A）。然後，它利用這個數學詞彙表建構多個物理定律背後的核心概念，例如「平方反比律」的模式，使它能夠學會牛頓的萬有引力定律和庫侖的靜電力定律，從而有效地完成了從最初的遞歸序列處理語言到類似物理學語言的「基變換」。
那麼，DreamCoder 是否也能夠學習這個遞歸序列處理語言本身呢？我們將系統初始化為僅包含 1959 年 Lisp 的最小原語集合（car,cdr,cons, ...），並要求它解決 20 個基礎程式設計任務——這些任務類似於電腦科學入門課程中常見的練習題。關鍵在於，初始語言包含了原始的遞歸機制（Y 組合子），理論上允許學習者表達任意遞歸函數，但除此之外並沒有提供任何現成的遞歸函數；在此前的設置中，我們將遞歸封裝在更高階函數（如map,fold等）中作為原語提供給學習者。借助足夠的計算時間（大約 64 個 CPU 上運行五天），DreamCoder 學會了解決全部 20 個問題，並在此過程中建構了一個相當於現代函數式程式設計慣用法的庫，包括map,fold,zip,length，以及像在區間內生成自然數列表這樣的算術操作（見圖7B）。
所有這些庫函數都可以用高階函數fold及其對偶unfold來表達，這兩種操作在形式上是遞歸數據類型上的兩個最基本操作，這一發現被稱為「折紙式程式設計」（origami programming）（42）。DreamCoder 重現了這一發現的過程：它首先重新發明了fold，然後是unfold，接著定義了所有其他遞歸函數為fold和unfold的組合。
討論
我們的研究表明，建構一個通用的程式歸納系統是可能且可行的：它能夠學習所需的專業知識，以表示和解決許多在性質上截然不同的領域中的新學習任務，並且隨著經驗的累積不斷提升其專業能力。DreamCoder 中的最佳專業知識依賴於顯式的陳述性知識與隱式的程式性技能的共同學習。
更廣泛地來看，DreamCoder 能夠學習某個領域概念結構的深層顯式表示，這展示了將符號主義、概率方法與神經網路學習結合的強大能力：層級表示學習演算法可以創造出人類可理解的知識，這與傳統的深度神經網路不同；它所產生的符號化專業知識表示具有靈活性，能夠隨著經驗不斷適應與擴展，這又不同於傳統的 AI 專家系統。
我們在此關注的問題中，解決方案空間可以透過清晰的符號形式來準確捕捉，即使在一些包含其他複雜性的領域也是如此，例如圖像像素輸入、生成文本模式中的例外和不規則情況，或我們在符號迴歸範例中使用的連續參數。然而，現實世界中的大量數據遠比這些更加混亂。未來程式歸納面臨的一個關鍵挑戰就是如何更好地處理普遍存在的噪音和不確定性，這需要更多地依賴概率性和神經網路的人工智慧方法（5, 43, 44）。
最近的研究探索了各種混合神經-符號表示的程式歸納方法（45–49），而將這些方法與 DreamCoder 的庫學習和自我引導能力相結合，可能是未來發展的重要方向。
要將程式歸納擴展到整個 AI 領域——比如常識推理、自然語言理解或因果推斷——還需要大量的創新，但這也蘊含著巨大的潛力。作為一種學習載體，程式的獨特優勢在於：它們結合了普遍表達力、數據高效的泛化能力，以及可解釋、可組合的重用潛力。
如今，我們不僅可以學習單個程式，還可以學習整個領域的特定語言，這使得程式的另一個特性變得尤為重要：程式是以一種人和機器都能理解的方式表達知識。
認識到每一個 AI 系統本質上都是人類智慧與機器智慧的聯合產物，我們認為這裡所展示的工具為建構一條真正由人機共同參與的 AI 發展路徑奠定了基礎。
在接下來的討論中，我們將進一步探討我們的工作對於建構更好的人類學習模型，以及更具人類特徵的機器學習形式所帶來的更廣泛意義。
與生物學習的介面
DreamCoder 的「醒-睡」機制靈感來源於 Helmholtz 機器，而 Helmholtz 機器本身又粗略地借鑒了人類在睡眠期間的學習過程。DreamCoder 引入了一對交錯進行的「睡眠」循環概念，有趣的是，生物意義上的睡眠同樣也分為多個階段。快速眼動（REM）睡眠，即「夢境」睡眠，與產生隱式程式性技能的學習過程有關（11），它涉及情節重放和夢境，這類似於我們模型中的「夢境」睡眠階段。
慢波睡眠則與新陳述性抽象的形成與鞏固相關（10），大致對應於我們模型中的「抽象」睡眠階段。雖然 DreamCoder 和 Helmholtz 機器都不是為了建模生物學過程而設計的，但我們推測我們的方法可能使「醒-睡」學習演算法更接近人類睡眠中實際發生的學習過程。
DreamCoder 的知識是逐步增長的，其動態機制與早期關於「課程學習」（curriculum learning）（50）和「從小開始」（starting small）（51）的發展性理論有關但又有所不同。不同於由人類教師安排任務難度順序並讓系統逐步解決（即「課程」），DreamCoder 的學習方式更類似於自然界的無監督探索：它嘗試解決隨機抽取的任務，在清醒階段探索自身能力的邊界，並在隨後的睡眠循環中擴展這一邊界，透過從簡單任務中學到的概念來引導更複雜任務的求解。
然而，人類的學習方式更加主動：他們可以選擇要解決哪些任務，甚至可以自行生成任務——要麼作為通向更難問題的中間步驟，要麼出於好奇心或審美等動機。建構能夠以類似人類方式自動生成問題的智能體，是未來的重要一步。
我們將領域專業知識劃分為顯式的陳述性知識和隱式的程式性技能的做法，粗略地受到認知科學中「雙過程模型」（dual-process models）（52, 53）以及人類專家研究（37, 38）的啟發。人類專家不僅學會可以用語言表達的陳述性領域概念——例如藝術家學習弧線、對稱性和透視原理；物理學家學習內積、向量場和平方反比定律——還掌握了迅速運用這些概念解決新問題的程式性（且通常是隱式）技能。
這兩種知識共同使專家能夠基於問題解決方案的「深層結構」對其做出更準確的分類（37, 38），並在尚未開始尋找解決方案之前就能憑直覺判斷哪些概念可能有用。我們認為，這兩類專業知識對於生物和人工的學習系統來說都是必不可少的組成部分，而神經網路與符號方法在這裡扮演著互補的角色。
什麼應該預先內置，什麼應該透過學習獲得
像人類一樣學習——尤其是像兒童那樣學習——的目標，常常被研究人員等同於「從零開始」學習的目標。他們假設，正如同圖靈所提出的那樣，兒童一開始幾乎是「白板」狀態：「就像你從文具店買來的筆記本：機制很少，空白頁很多。」（1）
程式歸納作為通用人工智慧的一種方法，其根源也在於這一願景，受早期研究成果的推動，這些研究表明，原則上，只要有一個最小化的圖靈完備語言，就有可能歸納出能解決任何可計算問題的程式（2, 54–56）。DreamCoder 能夠從最基礎出發，發現函數式程式設計、向量代數和物理學的基本詞彙表，這可以被視為朝向這一目標邁出的又一步。
那麼這種方法是否可以進一步擴展，不只是一次學習一個領域，而是從一個極小的基礎出發，同時發展出多個不同類型問題的專業知識？這種進步可能依賴於跨領域的元學習（metalearning）——即建構一個跨領域的庫，或稱為「思維語言」（language of thought）（57, 58），就像人類透過生物和文化演化集體建構起來的那樣，然後它可以分化成無限多種新問題領域的表示。
儘管這些方向令人著迷，但從如此微小的基礎出發去學習如此之多的內容，未必是我們通往人工智慧的最佳路徑——尤其是在我們可以站在眾多巨人肩膀上的今天。即使從理論上講，「從零開始」是可能的，這類方法通常會面臨眾所周知的數據匱乏問題（如神經網路），或者如果不依賴數據，則需要巨大的計算資源：僅為了建構「折紙式」的函數式程式設計能力，DreamCoder 就消耗了大約一年的 CPU 時間。
相反，我們從「程式草圖」（sketching）的程式綜合方法中汲取靈感（22）。sketching 方法通常獨立處理單個合成問題，並期望由人類工程師勾勒出解決方案的骨架。與此類似，我們在系統中預置了我們認為對於在多個不同領域中解決問題至關重要的基本要素——一套相對簡潔但通用強大的控制流操作符、高階函數和類型系統。然後我們利用學習機制在這些基礎上建構專門化的語言。
程式綜合中學習的未來可能在於那些初始化時具有更豐富但仍廣泛適用資源的系統，比如模擬引擎或現代程式設計語言標準庫所體現的那些資源。
這一願景也塑造了我們如何看待程式歸納對建構更像人類的人工智慧的最佳貢獻方式：不是追求「白板」式學習，而是在已有豐富內置知識的基礎上進行學習。在學習我們這裡所討論的各個領域之前，人類兒童天生就具備「核心知識」（core knowledge）：用於表示和推理物體、代理、空間和其他常識概念的概念系統（59–61）。
我們強烈支持這樣的人工智慧方法：從人類已有的概念資源出發，建構人類可理解的知識體系。這可能是我們通往一種存在於人類世界之中、並與人類智慧共生共進的人工智慧系統的最佳路徑。
原文連結：https://arxiv.org/pdf/2006.08381