神經演算法推理

在這篇文章中，我們將探討「經典計算」（classical computation）：這類計算通常出現在大學電腦科學的演算法與資料結構課程中 [1]。想想最短路徑尋找、排序、將問題分解為更簡單問題的聰明方法，以及為了高效檢索和更新而組織資料的精妙方式。當然，鑑於 The Gradient 對人工智慧的關注，我們不會止步於此；我們還將研究如何利用深度神經網路來「捕捉」（capture）這類計算。

為什麼要捕捉經典計算？

或許值得先澄清我對經典計算的濃厚興趣從何而來。競爭性程式設計（Competitive programming）——即透過快速編寫程式，在給定的時間和記憶體限制內解決問題的藝術——在我中學時期是一項非常受歡迎的活動。對我而言，它確實是進入電腦科學領域的門戶，我相信今天許多機器學習從業者和研究人員也有類似的經歷。我曾在國際程式設計競賽中獲得多枚獎牌，例如 ACM-ICPC 西北歐區域賽，這是大學生頂級的電腦科學競賽。希望我在競爭性程式設計方面的成功，也能為我撰寫這一主題提供一些資歷證明。

雖然這說明了為什麼「我」在意經典計算，但為什麼「我們所有人」都應該在意呢？為了得到答案，讓我們思考一下經典演算法所具備的一些關鍵特性：

• 它們是可證明正確的，而且我們通常能對計算終止所需的「資源」（時間或記憶體）提供強有力的保證。
• 它們提供強大的泛化能力：雖然演算法通常是透過觀察幾個小規模的範例輸入而設計的，但一旦實作，它們就能在規模顯著更大、或分佈與範例不同的輸入上毫無差錯地運行。
• 就設計而言，它們是可解釋的且具組合性的：它們的（虛擬）程式碼表示使得推論計算的實際行為變得容易得多，而且人們可以輕易地透過子程式將各種計算重新組合在一起，以實現不同的功能。

綜合看來，這些特性似乎正是困擾現代深度神經網路的最主要問題：你很難保證它們的準確性，它們在分佈外（out-of-distribution）輸入上經常崩潰，而且它們作為「黑盒子」臭名昭著，複合錯誤會阻礙組合性。

然而，正是這些技能對於使 AI 對人類具有「啟發性」和「實用性」至關重要！例如，要讓一個 AI 系統可靠且具啟發性地向人類教授某個概念，其輸出的品質不應取決於輸入的微小細節，且它應該能夠將該概念泛化到新的情境中。可以說，這些技能也是通往構建通用智慧體（generally-intelligent agents）道路上缺失的關鍵一步。因此，如果我們能在深度神經網路中捕捉經典計算的特質方面取得任何進展，這很可能是一項非常有成果的追求。

第一印象：演算法對齊

我進入這個領域的旅程始於一個有趣但看似無關緊要的問題：

神經網路能否「學習執行」經典演算法？

這可以被視為一種評估特定神經網路在多大程度上具備演算法行為能力的良好「基準」（benchmark）；可以說，如果一個系統能產生某種計算的輸出，它就已經「捕捉」到了它。此外，學習執行為評估機器學習模型提供了一個獨特且完善的環境：

• 無限的資料來源——因為我們可以生成任意數量的輸入；
• 需要複雜的資料操作——這對深度學習來說是一項具挑戰性的任務；
• 具有明確指定的目標函數——簡化了可解釋性分析。

當我們在 2019 年開始研究這個領域時，我們真的只把它當作一個非常巧妙的基準測試——但它確實正成為一個非常活躍的領域。在我們努力的同時，麻省理工學院（MIT）的一個團隊嘗試解決一個更具野心但密切相關的問題：

是什麼讓神經網路在擬合某些（演算法）任務時表現「更好」（或「更差」）？

這篇里程碑式的論文《神經網路能推論什麼？》（What Can Neural Networks Reason About?）[2] 為為什麼某種架構可能更適合某項任務建立了數學基礎（就「樣本複雜度」而言：將驗證損失降低到 epsilon 以下所需的訓練範例數量）。作者的主要定理指出：更好的「演算法對齊」（algorithmic alignment）會帶來更好的「泛化能力」。嚴格定義演算法對齊超出了本文範圍，但可以非常直觀地視覺化：

在這裡，我們可以看到「圖神經網路」（GNN）[3] 如何與用於尋找最短路徑的經典「Bellman-Ford」演算法 [4] 對齊的視覺化分解。具體來說，Bellman-Ford 維持其對圖中每個節點 $u$ 距離源節點多遠的當前估計值：一個「距離變數」（$d_u$）。在每一步中，對於節點 $u$ 的每個鄰居 $v$，都會提出一個對 $d_u$ 的更新建議：結合（最佳地）到達 $v$ 以及穿過連接 $v$ 和 $u$ 的邊（$d_v + w_{vu}$）。然後將距離變數更新為所有建議中的最佳值。圖神經網路的操作可以自然地分解以遵循 Bellman-Ford 的資料流：

• 距離變數對應於 GNN 維護的節點特徵；
• 將邊距離加到距離變數對應於計算 GNN 的訊息函數（message function）；
• 根據此度量選擇最佳鄰居對應於 GNN 的置換不變聚合函數（permutation-invariant aggregation function），$\bigoplus$。

一般來說，可以證明，我們越能緊密地「分解」神經網路以遵循演算法的「結構」，在學習執行此類演算法時，我們就能期待越有利的「樣本複雜度」。Bellman-Ford 是「動態規劃」（DP）演算法 [5] 的典型例子，這是一種通用的問題解決策略，它將問題分解為子問題，然後重新組合其解以找到最終解。

MIT 團隊做出了一個重要的觀察：GNN 似乎在演算法上與 DP 對齊，而由於 DP 本身可以用來表達許多有用的經典計算形式，因此 GNN 應該是學習執行的非常強大的通用模型。這得到了幾個精心構建的 DP 執行基準測試的驗證，在這些測試中，像 GNN 這樣的關係模型明顯優於歸納偏置（inductive biases）較弱的架構。GNN 一直是我長期關注的興趣 [6]，所以當時正是發布我們自己對該領域貢獻的時機：

圖演算法的神經執行

在與 Xu 等人 [2] 同期發布的這篇論文 [7] 中，我們對使用 GNN 學習執行進行了深入的實證分析。我們發現，雖然演算法對齊確實是模型類別選擇的強大工具，但遺憾的是，它並不允許我們「掉以輕心」。也就是說，我們不能直接將任何具表現力的 GNN 應用於演算法執行任務並期待獲得極佳的結果，尤其是在分佈外的情況下——我們之前已將其確定為「真正」推論系統應該表現良好的關鍵設定。與其他神經網路一樣，GNN 非常容易「過擬合」訓練輸入分佈的特徵，學習「聰明的捷徑」並規避它們試圖執行的實際程序。

因此，我們確定了關於謹慎使用「歸納偏置」的三個關鍵觀察，以進一步提高與某些路徑尋找問題的演算法對齊，並允許在測試時泛化到大 5 倍的輸入：

• 大多數傳統的深度學習設置涉及一疊具有「不共享」參數的層。這從根本上限制了神經網路可以執行的計算量：如果在測試時，出現了比訓練資料大得多的輸入，預計會需要更多的計算步驟——然而，不共享參數的 GNN 無法支持這一點。為了應對這個問題，我們採用了 encode-process-decode 範式 [8]：單個「共享」處理器 GNN 被迭代多次，且這個迭代次數在訓練和推論時都可以是變動的。這種架構也提供了一種與「迭代」計算進行演算法對齊的巧妙方式，因為大多數演算法都涉及重複應用某種計算直到收斂。
• 由於大多數路徑尋找演算法（包括 Bellman-Ford）都需要「局部」最佳化（即在每一步選擇「恰好一個」最佳鄰居），我們選擇使用 max aggregation（最大值聚合）來組合 GNN 中發送的訊息。雖然這看起來是一個非常直觀的想法，但它與當時的民間傳說背道而馳，因為當時已知 max-GNN 在區分非同構圖方面在理論上遜於 sum-GNN [9]。（我們現在有了可靠的理論證據 [10] 說明為什麼這是一個好主意。）
• 最後，雖然大多數深度學習設置只需要根據輸入產生輸出，但我們發現這錯失了大量指導模型與演算法對齊的方法。例如，演算法有許多有趣的「不變量」可以明確地教給 GNN。在 Bellman-Ford 的情況下，執行 $k$ 次迭代後，我們應該能夠恢復所有距離源節點不超過 $k$ 步的最短路徑。因此，我們利用這一見解在每一步為 GNN 提供逐步監督（step-wise supervision）。這個想法似乎在最近幾個月的大型語言模型設計中得到了關注 [11, 12]。

以上所有三項改變都造就了更強大的演算法對齊 GNN。

玩轉對齊遊戲

必須強調的是，演算法對齊的直觀想法——從架構設計中的電腦科學概念汲取靈感——絕非新穎之舉！教科書級的例子是「神經圖靈機」（NTM）和「可微分神經電腦」（DNC）[13, 14]。這些作品具有決定性的影響力；事實上，在嘗試使隨機存取記憶體與基於梯度的最佳化相容的過程中，NTM 在 Transformer [15] 出現的三年前就為我們提供了最早形式的基於內容的注意力機制（content-based attention）！

然而，儘管具有影響力，這些架構在現今的實踐中幾乎「從未」被使用。這有很多可能的原因，但在我看來，是因為它們的設計過於「脆弱」：試圖一次將許多可微分組件引入同一個架構中，卻沒有明確的「如何」組合它們的指導，或者在它們無法在任務上顯示有用訊號時，缺乏一種簡單的除錯方法。我們的研究路線仍然想構建類似 NTM 的東西——但要透過使用演算法對齊來更仔細地孤立原型化每個構建塊，並對哪些塊有利於哪些目標演算法的執行有更細粒度的視圖，從而使其更成功地部署。

我們「玩演算法對齊遊戲」的方法似乎產生了一系列成功的專業化 (G)NN，我們現在擁有用於學習執行線性對數序列演算法 [16]、迭代演算法 [17]、基於指標的資料結構 [18] 以及持久輔助記憶體 [19] 的優秀「細粒度」解決方案。最終，這些見解也轉化為更細粒度的理論。鑑於我們的 NEGA 論文 [7]，演算法對齊的發明者將他們的理論精煉為現在所謂的「線性演算法對齊」[10]，為我們使用最大值聚合等做法提供了正當性。最近的見解顯示，理解演算法對齊可能需要「因果推論」[20, 21]，對其進行適當的形式化可能需要「範疇論」[22]，而對其進行適當的描述可能需要分析「非同步計算」[23]。因此，演算法對齊近年來正成為深度學習數學方法中一個非常令人興奮的領域。

為什麼不直接「運行」目標演算法？……以及反駁

雖然在解決我們最初的「玩具問題」方面似乎取得了許多有用的進展，但學習執行的想法並不容易通過同行評審。我個人最喜歡的一條審稿意見——全文引用如下：「這篇論文肯定會加速構建演算法模型的研究，而且肯定有很多研究人員會從中受益，我只是不確定這項研究是否應該存在」。

作為論文的第一作者，收到這樣的評論顯然不是什麼愉快的事。但儘管如此，讓我們試著放下我的自尊，看看能從這類評論中學到什麼。這類評論在某種意義上提出了一個完全合理的觀點：從「恆真句」的角度來看，目標演算法執行「它自己」的效果肯定比我們在其上學習的任何 GNN 都要好（或至少一樣好）。顯然，如果我們希望這些想法得到廣泛認可，我們需要展示學習執行如何能被有效地應用於「純粹」執行之外的場景。

我們的探索引出了許多可能的想法，在本文的剩餘部分，我將展示其中影響力最大的三個想法。

首先，演算法對齊模型可以加速科學研究。如果你想要明確的證據，看看《自然》（Nature）雜誌的封面就知道了 [24]。在我們的工作中，我們訓練 (G)NN 來擬合數學家感興趣的數學資料集，然後使用簡單的梯度顯著性方法向數學家「發出訊號」，告訴他們應該關注輸入的哪些部分。雖然這類訊號通常雜訊很大，但它們確實能讓數學家在一個原本擁有數百或數千個節點的圖中，只研究最顯著的 20-30 個節點，使模式發現變得容易得多。發現的模式隨後可以成為新定理的基礎，和/或用於推導猜想。

透過這種簡單的方法，我們能夠對兩個截然不同的數學領域做出獨立貢獻：紐結理論 [25] 和表示論 [26]，兩者隨後都發表在各自領域的頂級期刊上，從而為我們贏得了《自然》雜誌的讚譽。但是，雖然我們的方法在原理上很簡單，但在表示論分支中出現了一個問題：該使用哪種 (G)NN？ 標準的具表現力的 GNN 並沒有產生清晰可解釋的結果。

這就是演算法對齊幫助我們的地方：我們的表示論合作者 Geordie Williamson 提供了一種演算法，如果我們能獲得特權資訊（privileged information），該演算法就能計算出我們感興趣的輸出。我們使用一個將其組件明確與此目標演算法對齊的 GNN 模型取得了最佳結果。

更廣泛地說：在這種情況下，目標演算法存在，但執行它是不可行的（由於特權輸入）。演算法對齊允許我們無論如何都能從中嵌入「先驗知識」。

其次，演算法對齊模型是快速的啟發式方法。在最近與蘇黎世聯邦理工學院（ETH Zürich）的電腦網路和機器學習合作者的工作中，我們研究了神經演算法推論在電腦網路中的適用性 [27]。具體來說，我們尋求加快「配置合成」（configuration synthesis）這一具挑戰性的任務：根據給定的電腦網路應滿足的約束條件規範（specification），產生相應的網路配置（一個指定網路中路由器及其連接的圖）。一旦在該配置上執行了網路協定，該配置必須滿足所有規範。

產生這些配置已知是一個非常具挑戰性的 NP-hard 問題——在實踐中，它通常使用緩慢的 SMT 求解器來解決，這往往需要「雙重指數級」的複雜度。相反，我們選擇利用演算法推論的想法，透過「反轉協定」（這可以被視為一種圖演算法）來生成配置。具體來說，我們生成許多隨機網路配置，在它們之上執行協定，並收集關於所得網路的所有真實事實以提取相應的規範。這為我們提供了從規範到配置生成基於圖的資料集所需的一切，並將演算法對齊的 GNN 擬合到該資料集。

自然地，由於只需要機器學習模型的一次前向傳遞，這種方法在推論時比 SMT 求解器快得多：對於某些配置，我們觀察到比之前的最先進技術有超過 490 倍的加速。當然，天下沒有白吃的午餐：我們為這種加速付出的代價是測試時產生的配置偶爾會出現不準確。即便如此，在我們評估的所有相關分佈上，滿足的約束條件平均比例始終保持在 90% 以上，這使得我們的方法已經可以應用於下游的「人機協作」（human-in-the-loop）用途——而且它很可能加速人類設計師的工作，因為通常初始配置是「不可滿足的」，這意味著 SMT 求解器會花費大量精力，最後只會說找不到滿足條件的配置。在此期間，GNN 的快速前向傳遞本可以允許更快速的迭代。

更廣泛地說：在這種情況下，目標演算法只是被近似，但它提供了一種快速且「相當準確」的啟發式方法，實現了快速的人機協作迭代。

應用經典演算法的一個核心問題

為了引出第三個也是最後一個想法，讓我提出一個具啟發性的任務：「幫我找到從 A 到 B 的最佳路徑」。你會如何回應這個提示？

很有可能，特別是如果你像我一樣具有理論電腦科學背景，你會以一種非常「單一」的方式回應這個問題。也就是說，你會微妙地「假設」我為你提供了一個加權圖，並要求你找到該圖中兩個特定頂點之間的最短路徑。然後，我們可以勤奮地應用我們最喜歡的路徑尋找演算法（例如 Dijkstra 演算法 [28]）來解決這個查詢。我應該強調，至少在撰寫本文時，今天大多數最先進的 AI 聊天機器人的情況也大同小異——當被提示上述任務時，雖然它們通常會尋求進一步的資訊，但它們會迅速假設提供了一個輸入加權圖！

然而，我的問題中沒有任何內容要求這兩個假設中的任何一個為真。首先，現實世界通常充滿雜訊且動態變化，很少提供這種抽象化的輸入。例如，該任務可能涉及在現實交通網絡中兩個地點之間旅行的最佳方式，這是一個具挑戰性的路由問題，依賴於處理嘈雜、複雜的資料來估計即時交通速度——這是我個人在 Google 地圖 [29] 中部署 GNN 時學到的教訓。其次，為什麼「最佳」必須等於「最短」？在交通路由的背景下，根據具體的情境和目標，「最佳」很可能意味著成本最高效、污染最少等等。所有這些變化都使得直接應用 Dijkstra 演算法變得困難，並且在實踐中可能需要多個演算法的「組合」。

這兩個問題都凸顯了我們通常需要在複雜的現實世界資料與適合運行目標演算法的輸入之間進行具挑戰性的「映射」。從歷史上看，這種映射是由「人類」完成的，無論是手動還是透過專門的啟發式方法。這自然引出了以下問題：人類是否能指望在一般情況下手動找到必要的映射？ 我會認為，至少自 1950 年代以來，我們就已經知道這個問題的答案是「否定」的。直接引用 Harris 和 Ross [30] 的論文（這是最早關於「最大流」問題的報告之一，透過分析鐵路網絡）：

對鐵路系統和單個軌道容量的評估，在很大程度上是一門藝術。作者不知道有任何經過測試的數學模型或公式能包含所有必須權衡的變化和無法估量的因素。即使個人與他正在評估的特定領土有密切聯繫，最終的答案，無論多麼準確，在很大程度上仍是判斷和經驗的產物。

因此，即使是技能高超的人類，在為每個鐵路鏈接附加單個標量「容量」值時，通常也需要進行有根據的猜測——而且這需要在對輸入網絡執行任何流演算法「之前」完成！此外，正如最近亞馬遜最後一哩路路由研究挑戰賽（Amazon Last Mile Routing Research Challenge）[31] 的以下聲明所證明的：

……理論路徑規劃與現實生活中的路徑執行之間仍存在重要差距，大多數基於最佳化的方法都無法彌合這一差距。這一差距與以下事實有關：在現實運營中，路徑的品質並非僅由其理論長度、持續時間或成本定義，而是由影響駕駛員在現實條件下有效、安全且方便地執行規劃路徑程度的多種因素定義。

因此，即使在今天高風險、大數據的環境中，這些考量仍然具有相關性。這是經典演算法與它們最初旨在解決的現實世界問題之間的根本鴻溝！滿足應用演算法的嚴格前提條件可能會導致來自複雜、自然發生的輸入的大量資訊損失。或者簡單來說：

如果我們在「錯誤」的輸入上執行演算法，演算法是否可證明正確並不重要！

如果資料是「部分可觀測的」、環境中存在「對抗性參與者」等，這個問題會變得更加棘手。我必須強調，這不是理論電腦科學家傾向於關注的問題，這可能是有充分理由的！專注於「抽象化」設置中的演算法已經相當具挑戰性，而且它產生了一些最精妙的計算程序，顯著改變了我們的生活。話雖如此，如果我們想為這些程序賦予「超能力」，並使它們適用於遠遠超出其最初設想的輸入類型，我們需要找到某種方法來彌合這一鴻溝。我們的提議——神經演算法推論（neural algorithmic reasoning）藍圖 [32]，旨在透過將目標演算法「神經化」來彌合這一鴻溝。

神經演算法推論

既然我們確定的關鍵限制是需要「手動」進行輸入特徵工程，那麼一個很好的切入點可能就是簡單地用神經網路編碼器取代特徵工程師。畢竟，取代特徵工程正是深度學習取得重大突破的原因 [33]！編碼器將學習從原始資料中預測演算法的輸入，然後我們可以在這些輸入上執行演算法以獲得我們感興趣的輸出。

這種流水線非常受歡迎 [34]；近期已有開創性的結果，允許在演算法本身不可微分的情況下透過編碼器進行反向傳播 [35]。然而，它面臨著「演算法瓶頸」問題：即它完全致力於演算法的輸出 [36]。也就是說，如果編碼器對演算法輸入的預測很差，我們就會遇到與之前相同的問題——演算法將在錯誤的環境中給出完美的答案。由於所需的輸入通常本質上是標量（例如輸入圖每條邊的單個距離），編碼器通常被賦予將現實世界資料極其豐富的結構僅映射為單個數字的任務。這在低數據或部分可觀測的場景中尤其成為問題。

為了打破演算法瓶頸，我們轉而選擇將編碼器「和」演算法都表示為高維神經網路！現在，我們的演算法模型是一個「處理器」神經網路——將高維嵌入映射到高維嵌入。為了恢復相關輸出，我們可以在處理器的輸出嵌入上附加一個適當的解碼器網路。如果我們能夠保證這個處理器網路「捕捉」到了演算法的計算，那麼我們就能同時解決之前確定的所有問題：

• 我們的流水線將是一個端到端「可微分」的神經網路；
• 它在整個過程中也將是「高維」的，緩解了演算法瓶頸；
• 如果任何計算無法由處理器解釋，我們可以添加直接從編碼器到解碼器的「跳躍連接」（skip connections），以處理此類殘餘資訊。

所以，我們現在需要的只是產生一個捕捉計算的神經網路！但是，等等……這不正是我們在整篇部落格文章中一直在討論的內容嗎？:)

我們得出了「神經演算法推論」（NAR）藍圖 [32]：

這張圖代表了我們到目前為止所涵蓋的所有內容的簡潔總結：首先，我們透過與目標演算法的演算法對齊，或在學習執行目標演算法上進行預訓練，或兩者兼而有之，來獲得合適的處理器網路 $P$！準備就緒後，我們將 $P$ 納入我們感興趣的任何處理原始（自然）資料的神經流水線中。用最初 NAR 論文 [32] 的話來說，這允許我們將目標演算法應用於「以前認為它們無法處理的輸入」。根據情況，我們可能希望在部署後保持 $P$ 的參數凍結，或者 $P$ 甚至可以完全是「非參數化」的 [37, 38]！

雖然最初只是一個提議，但現在已有幾個成功的 NAR 實例發表在頂級會議上 [36, 39, 40, 41]。在最近的一篇論文 [41] 中，我們旨在研究如何對小鼠大腦中的血管進行分類——這是一項非常具挑戰性的圖任務，涉及數百萬個節點和邊 [42]。然而，雖然直接從特徵對血管進行分類並非易事，但可以合理地假設血管的主要目的是進行血液流動——因此，用於「流分析」的演算法可能適合在此部署。相應地，我們首先預訓練了一個 NAR 處理器來執行相關的最大流和最小割演算法 [43]，然後成功地將其部署在大腦血管圖上，超越了之前的最先進 GNN。值得注意的是，大腦血管圖比我們用於學習執行的合成圖大 180,000 倍，且整個過程僅應用了極少的超參數調整！我們有信心這次成功只是眾多成功中的第一步。

我們從哪裡可以獲得「好」的處理器？

雖然前幾小節給出的想法希望能為捕捉經典計算的實用性提供充分的論據，但在實踐中，我們仍然需要知道「要捕捉哪些計算」！上述所有 NAR 論文都使用了與下游任務高度相關的目標演算法，並且處理器是使用基於這些演算法構建的客製化執行資料集進行訓練的。這通常需要同時具備領域專業知識和電腦科學專業知識，因此代表了一個明顯的進入門檻！

自從我開始從事 NAR 研究以來，我一直對降低這個進入門檻非常感興趣，同時也希望提供一系列在各種任務中都應該有用的「基礎處理器」。這促成了一項為期兩年的工程努力，最終以開源 CLRS 演算法推論基準測試 (https://github.com/deepmind/clrs) [44] 告終。

CLRS 基準測試的靈感來自於 Cormen、Leiserson、Rivest 和 Stein 的標誌性教科書《演算法導論》（CLRS）[1]，這是最受歡迎的經典演算法和資料結構大學教科書之一，也是競爭性程式設計師的「聖經」。儘管它有數千頁，但它僅包含約 90 種不同的演算法，而這些演算法往往構成了整個軟體工程職業生涯的基礎！因此，CLRS 中的演算法可以構成我們理想的「基礎處理器」集合，我們致力於讓構建和訓練 NAR 處理器來執行 CLRS 中的演算法變得容易。

在它的第一個版本中，我們發布了 CLRS-30，這是一個針對 CLRS 中三十種演算法的資料集和處理器生成器集合，涵蓋了廣泛的技能：排序、搜尋、動態規劃、圖演算法、字串演算法和幾何演算法。

CLRS-30 的特別之處在於它向使用者展示了多樣化的資料、模型和流水線：給定目標演算法變數的適當規範、目標演算法的實作以及理想的隨機輸入採樣器，CLRS 將「自動」以時空圖結構格式產生該演算法變數的完整執行軌跡、相關的編碼器/解碼器/處理器模型以及損失函數。出於這個原因，我們通常將 CLRS 稱為「資料集和基準生成器」，而不是單個資料集。

例如，這是一個由 CLRS 產生的對列表 [5, 2, 4, 3, 1] 進行「插入排序」的軌跡：

這個軌跡完全暴露了演算法的內部狀態：列表的指標（綠色）如何隨時間變化，當前正在排序哪個元素（紅色），以及它需要被排序到的位置（藍色）。預設情況下，這些可以用於逐步監督，儘管最近提出了更多有趣的軌跡使用方式，例如 Hint-ReLIC [21]。

為什麼只停留在「一個」演算法？我們能學習「全部三十個」嗎？

如前所述，CLRS-30 將三十種不同的演算法轉換為「統一」的圖表示。這為一個顯而易見的問題鋪平了道路：我們能否學習一個處理器（具有單組權重）來執行所有演算法？ 為了明確起見，我們設想的 NAR 處理器如下：

也就是說，單個 (G)NN 能夠執行排序、路徑尋找、凸包尋找以及所有其他 CLRS 演算法。由於不同演算法之間的輸入和輸出維度可能差異巨大，我們仍然建議為每個演算法使用單獨的編碼器和解碼器——映射進出處理器的潛在空間——然而，我們刻意將這些保持為「線性函數」，以便將大部分計算工作放在 $P$ 上。

然而，儘管基本想法在原理上很簡單，但這被證明並非易事。大多數先前學習多種演算法的嘗試，例如 NEGA [7] 或其繼任者 NE++ [45]，都刻意專注於學習執行高度相關的演算法，因為其學習訊號很可能具有良好的相關性。相應地，我們最初在所有 CLRS-30 上進行的單處理器多任務訓練運行導致了 NaN。

我們已經確定「單任務不穩定性」是造成這種情況的主要原因：如果任何單個演算法任務的梯度是有雜訊或不穩定的，這會轉化為所有三十個任務上的不穩定訓練。因此，我們發起了一次為期兩個月的專門「小規模突擊」，以識別並修復單任務學習器中的學習穩定性問題。我們最終得到的模型 Triplet-GMPNN [46]，在 CLRS-30 上的絕對平均性能比之前的最先進技術提高了 20% 以上，並實現了成功的多任務訓練！更重要的是，我們現在擁有一個單一的「通用型」（generalist）Triplet-GMPNN，平均而言，它在分佈外評估中「匹配」了三十個「專家型」（specialist）Triplet-GMPNN：

雖然從這張圖中可以明顯看出，在產生一個完全「演算法化」的 NAR 處理器庫之前，我們還有很長的路要走，但這一結果已被視為一個重要的「壓縮」里程碑，類似於 Gato [47] 論文。我們的 Triplet-GMPNN 模型的發布在 Twitter、Reddit 和 HackerNews 上引發了極其有趣的討論，特別是鑑於其對構建通用智慧系統的意義。總體而言，在過去短短三年內，各個團隊在 NAR 方面取得的進展令人驚嘆。而我們才剛剛開始：既然我們原則上可以構建通用型 NAR 處理器，我對這為未來研究和產品帶來的潛力感到無比興奮。

想了解更多嗎？

不用說，這篇文章還有很多內容沒有涵蓋——特別是本文討論的許多論文的技術和實作細節。如果你在這裡讀到的內容讓你感興趣並想了解更多，甚至想親自嘗試 NAR 模型，我建議你查看 LoG’22 關於 NAR 的教程 (https://algo-reasoning.github.io/)，這是我與 Andreea Deac 和 Andrew Dudzik 共同講授的。在不到三小時的時間裡，我們涵蓋了掌握開發、部署和深化神經演算法推論器基礎所需的所有理論，並提供了豐富的程式碼指標和參考資料。當然，如果你有任何後續問題、有趣的討論點，甚至是有趣的專案想法，非常歡迎直接聯繫！

參考文獻

（參考文獻列表保持原樣，此處略）

作者簡介

Petar Veličković 是 Google DeepMind 的主任研究科學家（Staff Research Scientist）、劍橋大學的附屬講師，以及劍橋大學克萊爾學堂的成員。Petar 擁有劍橋大學（三一學院）的電腦科學博士學位，導師為 Pietro Liò。他的研究涉及幾何深度學習——設計尊重資料中不變性和對稱性的神經網路架構（他曾合著過一本關於此主題的原型書）。

引用

在學術背景或書籍中進行歸屬時，請引用此作品為：

Petar Veličković, "Neural Algorithmic Reasoning", The Gradient, 2023.

BibTeX 引用：

@article{veličković2023nar,
author = {Veličković, Petar},
title = {Neural Algorithmic Reasoning},
journal = {The Gradient},
year = {2023},
howpublished = {\url{https://thegradient.pub/neural-algorithmic-reasoning/},
}