【導讀】「Alpha」家族再添新成員AlphaDev！谷歌大腦DeepMind合體后首發力作，全新AI系統將排序算法提速70％，C++排序庫十年來首次更改。AI創造AI的時代要來了？

今天，「Alpha」家族再添一名新成員：AlphaDev。

整個計算生態系統的基礎，或將被AI創造的新算法顛覆！

谷歌大腦和DeepMind合體沒多久，就帶來這樣一個驚世之作。

AlphaDev不僅可以將排序算法提速70％，甚至在有的算法上，能比人類快3倍之多。 十多年來，C++排序庫首次更改。AI優化世界代碼，又達新里程碑。 目前，最新研究已登上Nature。

論文地址：https://www.nature.com/articles/s41586-023-06004-9 通過強化學習，AlphaDev發現了更加有效的算法，直接超越了科學家和工程師們幾十年來的精心打磨。 現在，新的算法已經成為兩個標準C++編碼庫的一部分，每天都會被全球的程序員使用數萬億次。 有網友表示，終于來了，我們現在正在踏入未知領域：人工智能正在構建人工智能！

強化學習打破十年算法瓶頸

如同AlphaZero、AlphaFold等前輩一樣，AlphaDev也直接掀起了一個領域的變革。 DeepMind計算機科學家、論文一作Daniel Mankowitz表示，「我們起初根本不相信。」 「說實話，我們沒有想到會取得更好的成績：這是一個非常短的程序，而這些類型的程序，此前已經被研究幾十年了。」 當前，GPT-4、Bard等大模型的參數指數級增長，對算力等資源的需求不斷增長。而過去50年里，人類不斷依靠芯片的改進以跟上步伐。 但隨著微芯片接近物理極限，改進代碼讓計算更強大、更持續變得至關重要。尤其是，對每天運行數萬億次代碼的算法愈重要。 今天，Google DeepMind在Nature發表的論文中，首次介紹了阿爾法家族的「新貴」AlphaDev。

AlphaDev發現了一種更快的排序算法，數十億人每天都在不知不覺中使用這些算法。 它們是一切的基礎，從在線搜索結果，社交帖子，到計算機和手機數據處理方式。這些算法每天都要執行數萬億次。 利用AI生成更好的算法，將改變我們對計算機編程的方式，并影響我們數字化社會的方方面面。 根據Nature論文中的數據，AlphaZero所創造的算法能比人類的數據排序速度快三倍。

今天，Google DeepMind還開源了在主C++庫中的最新排序算法，所有人皆可用。 開源地址：https://reviews.llvm.org/D118029

什么是排序？

排序是一種以特定順序組織多個項目的方法。 比如按字母順序排列三個字母，從大到小排列五個數字，或者將包含數百萬條記錄的數據庫排序。 在人類歷史中，排序方法一直在演變。最早的例子可以追溯到二、三世紀，那時的學者們在亞歷山大圖書館的書架上，靠純手工的方式，以字母順序排列擺放了數千本書。 工業革命后，我們發明了可以幫助分類的機器——制表機將信息存儲在穿孔卡上，用于收集1890年美國的人口普查結果。 而隨著20世紀50年代商業計算機的興起，出現了最早的計算機科學排序算法。 在今天，世界各地的代碼庫中都使用了許多不同的排序技術和算法，在線組織大量數據。

排序算法，也就是輸入一系列未排序的數字，然后輸出排序后的數字 這些算法，都已成為計算機科學的基石。 如今我們的算法，都需要計算機科學家和程序員投入幾十年的研究去開發。 這是因為，現有的算法效率如此之高，再往前的每一步改進，都是重大的挑戰。 這個艱難程度就好比找到一種節省電力能源的新方法，或者找到更高效的數學方法。

尋找新算法

AlphaDev的創新意義在于，它并不是通過改進現有算法，而是完全從頭開始發現了更快的算法。 而且，它竟然著手于大多數人類并沒有想到的地方——計算機匯編指令。 匯編指令用于創建二進制代碼。雖然開發者寫代碼時用的是C++等高級語言，但為了讓計算機理解，這些高級語言必須翻譯成「低級」的匯編指令。

我們一般用C++之類的高級編程語言寫代碼，然后使用編譯器將其轉換為低級CPU指令，即匯編指令。匯編器再將匯編指令轉換為可執行的機器代碼 谷歌DeepMind的研究者相信，在這個較低的層級中存在許多可改進的空間，而這些改進在更高級的編程語言中可能很難發現。 在這個更低的級別上，計算機的存儲和操作都更靈活，因此如果再多做一些潛在的改進，就會對速度和能源產生巨大的影響。

圖A：一個最多排序兩個元素的C++算法

圖B：代碼相應的程序集

AlphaDev：匯編版AlphaZero

眾所周知，DeepMind的強化學習模型，在圍棋、國際象棋和將棋等游戲中，屢次擊敗世界冠軍。 而我們這次的主角——AlphaDev，基于的正是AlphaZero。 AlphaDev的工作方式與之前的AlphaZero相似，后者結合了計算機推理和直覺，在棋盤游戲中選擇每一步的走法。 只不過，AlphaDev并不會選擇下一步怎么走棋，而是選擇添加哪些指令。 為了訓練AlphaDev來發現新的算法， DeepMind將排序問題轉化成了一個「匯編游戲」（Assembly Game）。 在每一輪中，AlphaDev都需要觀察它生成的算法以及中央處理器（CPU）中包含的信息，并通過在算法中添加一條指令來進行移動。 而這個匯編游戲非常困難，因為AlphaDev必須有效地搜索大量可能的指令組合，從而找到一個可以排序且比當前最佳算法更快的算法。 其中「可能的指令組合」，甚至可以直接類比于宇宙中的粒子數量，或者國際象棋（10^120局）和圍棋（10^700局）中可能的走法組合。 更進一步的是，任何一個錯誤的移動，都可能會使整個算法無效。 最后，DeepMind會根據AlphaDev正確排序數字的能力以及完成排序的速度和效率給予獎勵，而AlphaDev則需要通過發現一個正確且更快的程序來贏得游戲。

圖A：匯編游戲。玩家AlphaDev以系統狀態st為輸入，并通過選擇一條匯編指令將其添加到已經生成的算法中來進行一次移動。

圖B：獎勵計算。在每次移動后，生成的算法會接受測試，智能體將根據算法的正確性和響應時間獲得獎勵。 具體來說，在進行深入思考（deliberation）時，AlphaZero會在每一個決策點琢磨下一步可能的行動，以及下一步的下一步的可能性。就像樹狀圖一樣，一步步往后推，算出哪些行動最有可能成功。 但問題在于，如果把每一個可能的情況分支都考慮到，所需的時間可能要比宇宙的年齡還長。因此，研究人員使用類似直覺（intuition）的東西來縮小范圍。 在每一步中，程序將當前狀態輸入神經網絡（一個復雜的、可調的數學函數），以找到最合適的行為。同時，在訓練過程中，神經網絡還會根據結果不斷進行更新。有時還會故意不選評分最高的行為來進行主動探索。 AlphaDev可以采取的行動一共有四種，包括比較不同值、移動數值到另一個位置、或者跳轉到程序的不同部分。 在執行完每一步之后，再試圖對一組列表進行排序，并根據正確排序的列表中的數值數量獲得獎勵。 如此這般，這般如此，一直到排完整個列表，或者達到程序長度限制，從頭開始一個新的程序。

C++運行速度提升70%

AlphaDev發現新的排序算法，為LLVM libc++排序庫帶來了明顯的改進。 對于較短的序列，速度提高了70%，而對于超過250,000個元素的序列，速度只提高了約1.7%。 研究人員專注于改進3-5個元素較短的序列排序算法。 這些算法是使用最廣泛的算法之一，因為它們經常作為更大排序函數的一部分被多次調用。 改進這些算法可以為任何數量的項目的排序提升整體的速度。

為了使新的排序算法為所有人可用，研究人員還將其進行了逆向工程，并將其翻譯成「程序猿」最常用的一種編碼語言C++。 目前，這些算法現在可以在LLVM libc++標準排序庫中找到。

散列函數效率提升30%

在發現更快的排序算法之后，DeepMind測試了AlphaDev是否能夠推廣并改進不同的計算機科學算法——散列（Hash）。 散列是計算中的一種基本算法，用于檢索、存儲和壓縮數據。就像圖書管理員使用分類系統來找到特定的書籍一樣，散列算法幫助用戶知道他們正在尋找的內容以及確切的位置。 這些算法將特定的key（例如用戶姓名「Jane Doe」）進行散列處理，也就是，將原始數據轉換為唯一的字符串（例如1234ghfty）。然后，計算機會使用這個散列值來快速檢索與鍵相關的數據，而不是搜索所有數據。 結果顯示，當應用于散列函數的9到16字節范圍時，AlphaDev發現的算法比傳統算法快30%。 現在，DeepMind也將新的散列算法發布到了開源的Abseil庫中。據了解，這個算法預計每天都會被使用數萬億次。

兩種新策略：「swap move」和「copy move」

AlphaDev不僅發現了更快的算法，還發現了新的方法。 它的排序算法包含新的指令序列，每次應用時都會保存一條指令。這可能會產生巨大的影響，因為這些算法每天被使用數萬億次。 研究人員將其稱之為「AlphaDev swap move」和「AlphaDev copy move」。 最新方法讓人想起AlphaGo讓人震驚的「第37步」。 2016年那場人機大戰中，AlphaGo下了一顆違反人類直覺的棋，一個簡單的肩沖，擊敗了傳奇圍棋選手李世石。 通過這兩種策略，AlphaDev跳過了一個步驟，以一種看起來錯誤，但實際上是快捷方式連接項目。 這表明，AlphaDev有能力發現原創性解決方案，并挑戰了我們對如何改進計算機科學算法的思考方式。 如下圖示例原始sort3實現，有min(A, B, C)，使用AlphaDev Swap Move，AlphaDev發現，你只需要min(A, B)。

再比如，原始實現用max(B, min(A ,C, D))中較大的排序算法對8個元素進行排序。 AlphaDev發現使用其「swap and copy moves」時只需要max(B, min(A, C))。

優化全世界的代碼，一次一個算法

通過優化和推出全球開發者使用的改進排序和散列算法，AlphaDev證明了，它有能力概括和發現世界級的新算法。 Google DeepMind認為，AlphaDev是朝著開發AGI工具邁出的一步，這些工具有助于優化整個計算生態系統，還能解決其他有益于社會的問題。 不過，研究人員也承認，目前AlphaDev在低級匯編指令優化能力非常強，但是隨著算法的發展也存在局限性。 為了讓開發者更可用，AlphaDev用高級語言（如C++）優化算法的能力正在探索中。 AlphaDev的新發現，如「AlphaDev swap move」和「AlphaDev copy move」，不僅表明它可以改進算法，還可以找到新的解決方案。 研究人員希望，這些發現能激勵研究人員和開發人員創造技術和方法，進一步優化基礎算法，以創建一個更強大、更可持續的計算生態系統。

網友熱評

英偉達科學家Jim Fan對AlphaDev做了一個深度總結： 排序算法是所有關鍵軟件的基礎。DeepMind的AlphaDev將小序列（3-5項）的排序速度提高了70%。要點： - 主要的RL算法是基于最初下圍棋Go、Chess & Shogi的AlphaZero。同樣的想法也適用于搜索程序！ - 研究人員沒有對C代碼進行優化，而是對匯編代碼進行優化。這是一個刻意的選擇，去低級別的擠壓每一條指令的保存。 - 匯編代碼然后被逆向工程為C++，并在LLVM中開源。 - 即使表征網絡使用了Transformer，它也不是一個基礎模型。整個流程只適用于排序，對于其他任務如散列，必須重新訓練。

在使用ML的算法發現方面取得了另一個重要的里程碑!

AlphaDev是DeepMind的一個改變游戲規則的人工智能，它創新了核心計算機科學算法。它正在重新構想排序方法，短序列的速度可提高70%。甚至散列算法的發現速度提高了30%。強化學習正在重塑算法的格局！

還有網友稱，在我們對語言模型感到興奮之余，也不要忘記其他深度學習算法的成功故事：AlphaZero、AlphaFold，以及現在的AlphaDev。

參考資料： https://www.deepmind.com/blog/alphadev-discovers-faster-sorting-algorithms