GoogleDeepMind打破十年演算法封印，AlphaDev驚世登場，顛覆人類演算法模式！

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

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

Google大腦和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指令，也就是彙編指令。彙編器再將彙編指令轉換為可執行的機器碼

GoogleDeepMind的研究者相信，在這個較低的層級中存在許多可改進的空間，而這些改進在更高級的程式語言中可能很難發現。

在這個更低的層級上，電腦的儲存和操作都更靈活，因此如果再多做一些潛在的改進，就會對速度和能源產生巨大的影響。

圖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。

#

以上是GoogleDeepMind打破十年演算法封印，AlphaDev驚世登場，顛覆人類演算法模式！的詳細內容。更多資訊請關注PHP中文網其他相關文章！