點擊參加51CTO網站內容調查問卷
編譯 | 王瑞平、言征
AlphaGo又有“小弟”加入了!
谷歌DeepMind把Alpha系列“卷”到了排序算法上，重磅推出AlphaDev。
它好比一種“開發秘法”，通過使用強化學習AI發現排序算法和散列算法，強行把人類程序員設計的算法分別提速約70%和30%。
研究成果一經推出，瞬間點燃軟件圈！一下子，全球數以百萬計的軟件運行速度飆升，直接超越了科學家和工程師幾十年來的成果，十年未更新的LLVM標準C++庫都更新了。
（來源：Nature）
這也是繼谷歌兩AI部門合體后推出的顛覆性技術。論文以《使用深度強化學習模型發現更快排序算法》（Faster sorting algorithms discovered using deep reinforcement learning）為題發表于Nature。DeepMind計算機科學家Daniel Mankowitz為論文的第一作者。
1、演進：排序算法的由來
排序是一種將許多項目按特定順序組織起來的方法，例如，按照字母順序排列三個字母，從最大到最小的順序排列五個數字或對包含數百萬條記錄的數據庫進行排序。
排序法最早可追溯至二到三世紀，仍在不斷演進。最初，學者們徒手將亞歷山大圖書館書架上的數千本書按字母順序進行排序。
工業革命之后，人們發明了可自行分類的機器，即，將信息存儲在穿孔卡片上的制表機器中，用于收集1890年美國人口普查的結果。
20世紀50年代，商用計算機開始興起，也隨即產生了排序算法。將一系列未排序的數字輸入到排序算法中，它就能輸出排好順序的數字。
如今，在世界各地的代碼庫中，仍有許多不同的排序技術和算法被用于在線整理大量數據。
這些排序算法經過計算機科學家和程序員幾十年的研究開發，變得越來越高效。但是，對其進一步改進仍具有重大挑戰。
2、重頭戲：如何用AlphaDev生成新排序算法？
研究人員最初用AlphaDev生成新算法的目的是高效率完成給定任務。
在這個實驗中，AlphaDev是從零開始構建新算法的，并不是根據以往算法構建，屬于原創。在此過程中，它應用了匯編代碼的中間語言。該語言更接近計算機二進制指令，也更容易讓AlphaDev創造出高效算法。
具體來講，AlphaDev每次生成一個指令，然后測試其輸出正確與否，同時還在模型中設定要求生成最短算法。
當被要求重新設計排序算法時，AlphaDev隨機生成比現有算法快70%的新排序算法，可同時將五個數據排序。在對25萬個數據進行排序時，它也比最好的算法快1.7%。
由于排序算法被廣泛用于各種常用軟件中，這項創新會對全球算法產生重大影響。DeepMind已將它們進行開源，并加入Libc++常用代碼庫。
據DeepMind的研究者描述：“由于指令組合數量龐大，看似簡單的研究過程難度極大?！?/p>
3、緣起：在玩游戲中找到最佳算法
進一步來講，AlphaDev是基于AlphaZero產生的更先進模型。而AlphaZero此前是DeepMind的強化學習模型，曾在圍棋、國際象棋和其它棋類游戲中擊敗了世界冠軍。
通過此項實驗，新模型AlphaDev發揮出從玩游戲轉移到解決科學問題以及從實驗模擬轉移到現實世界應用的獨特優勢。
為訓練AlphaDev發現新算法，研究者將排序模擬為單人“組裝游戲”。在每個游戲回合中，AlphaDev都能觀察到生成的算法和包含在CPU中的信息，然后選擇一條指令添加到算法中走出每一步棋。
論文中提到，匯編游戲非常困難，因為AlphaDev必須能夠有效地搜索到大量可能的指令組合以獲取可以排序的算法。
指令組合數量類似于宇宙中粒子數量或國際象棋(10120局)和圍棋(10700局)中可能走法的組合數量，每個錯誤的舉動將會使整個算法失效。
然后，該模型輸出一個算法并將其與預期輸出比較，根據算法的正確性和延遲時間獎勵代理。
在構建算法時，每次輸入一個指令，AlphaDev通過比較輸出算法與預期結果檢查正確性（對于排序算法，這意味著輸入無序的數字后能夠輸出正確排序的數字）。
模型會獎勵AlphaDev對數字的正確排序以及它的高效。最終AlphaDev通過發現更準確的、更快的程序贏得了比賽。
4、算法創新：交換移動和復制移動指令序列
AlphaDev不僅生成了更快算法，還創新出兩種指令序列。
具體來講，它生成的排序算法包括交換移動和復制移動兩種新的指令序列，每次使用時都會保存一條指令。研究者稱之為“AlphaDev的交換移動和復制移動”。
這種新穎的方法讓人想起AlphaGo的“第37步”——“反直覺”下棋法，震驚了旁觀者并造成一位傳奇棋手的失敗。
通過交換移動和復制移動指令序列，AlphaDev跳過了一個步驟，以一種看起來像錯誤但實際上是捷徑的方式完成目標。這表明，AlphaDev有能力發現原始解決方案，并挑戰如何改進計算機科學算法。
5、測試：推廣和改進散列算法
在發現更快的排序算法后，研究者測試了AlphaDev是否可以推廣和改進另一種計算機科學算法：散列算法。
散列算法是計算中的一種基本算法，用于檢索、存儲和壓縮數據。就像圖書管理員使用分類系統定位某本書一樣，散列算法幫助用戶知道他們要找的是什么以及在哪里可以找到它。
這些算法能夠獲取特定密鑰(例如，用戶名“Jane Doe”)的數據并對其進行散列排序——將原始數據轉換為唯一字符串(例如，1234ghty)。
計算機使用該散列快速檢索與密鑰相關的數據，而不是搜索所有數據。
研究人員將AlphaDev應用于數據結構中最常用的散列算法之一以嘗試發現更快的算法。當將其應用于散列函數的9-16字節范圍時，AlphaDev生成的算法速度快了30%。
今年早些時候，AlphaDev生成的新散列算法曾被發布到開源的Abseil庫中，全世界數以百萬計的開發人員都可以使用，估計它現在每天被使用數萬億次。
6、蓄勢：邁出開發AGI的第一步
通過優化“排序和散列算法”，AlphaDev展示出生成不同實用新算法的能力。
這也是AlphaDev朝著開發通用人工智能（AGI）工具邁出的第一步，通過類似的AI工具還可以幫助優化整個計算生態系統并解決其它有益于社會的問題。
雖然在低級匯編指令空間中優化算法的功能非常強大，但它也存在局限性。目前，團隊也正在探索AlphaDev直接在高級語言(如，C++)中優化算法的能力，這對開發人員更有用。
總之，希望這些新發現能夠激勵開發人員創造新技術和方法、進一步優化基本算法，創造更強大、更可持續的計算生態系統。
7、開源：AI優化代碼的里程碑突破
此前，排序算法每天都會被使用數萬億次。隨著計算需求的增長，人們對算法的性能要求越來越高。雖然人類工程師已發現不同的排序算法，但經過幾十年的優化，很難再有突破，也滿足不了日益增長的需求。
如今，AlphaDev發現了一種更快的排序算法，可對數據進行排序。
新排序算法無所不能，既可應用于對在線搜索結果和社交帖子進行排名，也可在電腦和手機上處理數據。
值得慶賀的是，新排序算法已在主C++庫中開源。世界各地數以百萬的開發人員和公司目前可將其用于云計算、在線購物、供應鏈管理等。
總之，使用人工智能工具優化算法將徹底改變傳統編程方式。這是十幾年來第一次對排序庫進行更改，第一次將強化學習模型設計出的算法添加到排序庫中，因此成為了使用人工智能優化代碼的里程碑式突破。
8、用戶：可能只是噱頭
對于該項研究成果用戶褒貶不一，Twitter上贊美的聲音居多：
“這太棒了！在程序員早期就學會的基本排序任務基礎上，速度提高了70%。看到利用AI在我們都依賴的算法和庫中進行重大加速，真是令人興奮”。
“很快，普通人就可以成為高級程序員”。
“有趣的方法，從裝配級別開始優化”！
但是，也有的程序員認為這只是個噱頭，DeepMind夸大了該算法的功能。
首先就是從效率的角度，它只統計了算法的延遲，而非真正改變了時間復雜度。
而且，它并沒有真正改變排序，這種操作常見于各種其它代碼庫。
參考資料：
1.https://www.nature.com/articles/s41586-023-06004-9
2.https://www.deepmind.com/blog/alphadev-discovers-faster-sorting-algorithms
3.https://www.deepmind.com/blog/optimising-computer-systems-with-more-generalised-ai-tools
4.https://twitter.com/demishassabis
