6月8日，DeepMind 在著名學(xué)術(shù)刊物 Nature 上，發(fā)表了其最新研究成果：一個名為 AlphaDev 的 AI 系統(tǒng)。AlphaDev不僅可以將排序算法提速70％，甚至在有的算法上，能比人類快3倍之多。十多年來，C++排序庫首次更改。AI優(yōu)化世界代碼，又達新里程碑。
從名字上便可以看出，AlphaDev 與 AlphaGo、AlphaFold 一樣，同屬 DeepMind 旗下的 Alpha 系列，而 AlphaDev 的發(fā)布也同樣在業(yè)界引起了廣泛關(guān)注。
具體來說，AlphaDev 是一種通過強化學(xué)習(xí)來發(fā)現(xiàn)增強的計算機科學(xué)算法的 AI 系統(tǒng)，它發(fā)現(xiàn)了一種更快的排序算法，直接超越了科學(xué)家和工程師們幾十年來的研究，將排序算法的速度提高了 70%！
DeepMind 計算機科學(xué)家 Daniel Mankowitz 更是表示：“我們估計，AlphaDev 發(fā)現(xiàn)的排序算法和哈希算法每天都會被調(diào)用數(shù)萬億次。”
強化學(xué)習(xí)，打破計算瓶頸
既然 AlphaDev 發(fā)現(xiàn)的是一種全新的排序算法，那我們便先從“排序”說起。
不論是將 3 個字母按字母順序排列、將 5 個數(shù)字從大到小排列，亦或是將一個有上百萬條記錄的數(shù)據(jù)庫進行排列，這都是排序，是一種幾乎所有關(guān)鍵軟件的基礎(chǔ)算法。在 20 世紀 50 年代之前，排序工作多數(shù)都依賴人工，直至后來商業(yè)計算機興起，最早用于排序的計算機科學(xué)算法才開始出現(xiàn)并發(fā)展。
如今，開發(fā)者們所用的排序技術(shù)和算法，都是過去幾十年計算機科學(xué)家和程序員們積累下來的研究成果。相較于幾十年前的手動排序，現(xiàn)在的算法確實已經(jīng)很高效，但也正因如此，想要將其進一步改進無疑是一項重大挑戰(zhàn)，難度不亞于“找到一種新的節(jié)電方式”或“發(fā)現(xiàn)一種更有效的數(shù)學(xué)方法”。當前，GPT-4、Bard等大模型的參數(shù)指數(shù)級增長，對算力等資源的需求不斷增長。而過去50年里，人類不斷依靠芯片的改進以跟上步伐。但隨著微芯片接近物理極限，改進代碼讓計算更強大、更持續(xù)變得至關(guān)重要。尤其是，對每天運行數(shù)萬億次代碼的算法愈重要。
因此，DeepMind 在論文中提到：“人類的直覺和專業(yè)知識對于改進算法至關(guān)重要。然而，許多算法已經(jīng)到了人類專家無法進一步優(yōu)化它們的階段，導(dǎo)致計算瓶頸不斷擴大。”
AlphaDev發(fā)現(xiàn)了一種更快的排序算法，數(shù)十億人每天都在不知不覺中使用這些算法。它們是一切的基礎(chǔ)，從在線搜索結(jié)果，社交帖子，到計算機和手機數(shù)據(jù)處理方式。這些算法每天都要執(zhí)行數(shù)萬億次。利用AI生成更好的算法，將改變我們對計算機編程的方式，并影響我們數(shù)字化社會的方方面面。根據(jù)Nature論文中的數(shù)據(jù)，AlphaZero所創(chuàng)造的算法能比人類的數(shù)據(jù)排序速度快三倍。
今天，Google DeepMind還開源了在主C++庫中的最新排序算法，所有人皆可用。
開源地址：https://reviews.llvm.org/D118029
打破傳統(tǒng)，從匯編指令入手
為了幫助打破這一計算瓶頸，DeepMind 引入了 AlphaDev， AlphaDev的創(chuàng)新意義在于，它并不是通過改進現(xiàn)有算法，而是完全從頭開始發(fā)現(xiàn)了更快的算法。而且，它竟然著手于大多數(shù)人類并沒有想到的地方——計算機匯編指令。匯編指令用于創(chuàng)建二進制代碼。雖然開發(fā)者寫代碼時用的是C++等高級語言，但為了讓計算機理解，這些高級語言必須翻譯成「低級」的匯編指令。
以此作為靈感，DeepMind 認為相較于在高層次的編碼語言中，在匯編指令這個較低的層次上，應(yīng)該還存在許多改進空間，而這些改進在更高級的編程語言中可能很難發(fā)現(xiàn)。因為計算機的存儲和操作會更靈活，如果再多做一些潛在的改進，對速度和能源使用也將產(chǎn)生更大影響。
通過玩“游戲”來發(fā)現(xiàn)新算法
眾所周知，DeepMind的強化學(xué)習(xí)模型，在圍棋、國際象棋和將棋等游戲中，屢次擊敗世界冠軍。而我們這次的主角——AlphaDev，基于的正是AlphaZero。AlphaDev的工作方式與之前的AlphaZero相似，后者結(jié)合了計算機推理和直覺，在棋盤游戲中選擇每一步的走法。只不過，AlphaDev并不會選擇下一步怎么走棋，而是選擇添加哪些指令。
為了訓(xùn)練AlphaDev來發(fā)現(xiàn)新的算法，DeepMind 讓 AlphaDev 開始了一個單人“匯編游戲（Assembly Game）”。
根據(jù)論文介紹，在這個游戲中，玩家需要選擇一系列低級匯編指令，以此產(chǎn)生一種新的高效排序算法：“這個游戲很有挑戰(zhàn)性，因為玩家需要考慮匯編指令的組合空間，以產(chǎn)生一種既可證明正確又快速的算法。難度不僅來自搜索空間的大小，可能的組合數(shù)量類似于國際象棋和圍棋，而且其中一條不正確的指令都可能會使整個算法無效。”
在游戲過程中，AlphaDev 每玩一次 AssemblyGame，都會從頭開始構(gòu)建一個匯編程序，從一組初始無序的指令開始構(gòu)建，從而定義一種新的高效算法。
隨著游戲的進行，算法不斷建立，而 AlphaDev 會通過比較算法的輸出和預(yù)期的結(jié)果來檢查它是否正確。對于排序算法，AlphaDev 的檢驗方式是：輸入無序的數(shù)字后，可否輸出正確排序的數(shù)字。
DeepMind 將游戲的輸贏作為 AlphaDev 的激勵方式，而該游戲的輸贏也很好判定：
? 使用匯編指令，生成正確的低延遲算法，AlphaDev 即贏得游戲。
? 生成不正確的算法或正確但低效的算法，AlphaDev 即輸?shù)粲螒颉?/p>
新排序算法，速度提升 70%！
于是，在這樣的“游戲”過程中，AlphaDev 發(fā)現(xiàn)了更快的排序算法，主要是圍繞 3-5 個元素的較短序列的排序算法。
DeepMind 解釋道：“因為這些算法是使用最廣泛的算法之一，它們經(jīng)常作為較大排序函數(shù)的一部分被多次調(diào)用，改進這些算法可以加快對任意數(shù)量項目進行排序的整體速度。”
因而，AlphaDev 發(fā)現(xiàn)的這個新排序算法，對于較短的序列來說，速度可提升 70%，對于超過 25 萬個元素的序列來說，速度也能提高約 1.7%。
為了讓更多人用到這個新排序算法，DeepMind 對算法進行了逆向工程，并以此改進了 LLVM libc++ 標準排序庫，可供全球數(shù)百萬開發(fā)者和公司使用。DeepMind 計算機科學(xué)家 Daniel Mankowitz 激動表示：“這些算法目前位于 C++ 標準排序庫中，這是十多年來對這些子例程的首次更改！”
新哈希函數(shù)，速度提升 30%！
除了新排序算法，通過研究 AlphaDev 的發(fā)現(xiàn)過程，它實際上還創(chuàng)造了一種新方法：其排序算法包含新的指令序列，每次應(yīng)用時都會跳過一條指令——對于每天都會被使用上萬億次的排序算法來說，這無疑將產(chǎn)生巨大影響。
DeepMind 研究人員將此稱作 “AlphaDev 交換和復(fù)制動作（AlphaDev swap and copy moves）：通過交換和復(fù)制移動，AlphaDev 跳過了一個步驟，以一種看似錯誤實際上很快捷的方式連接項目。“這顯示了 AlphaDev 發(fā)現(xiàn)原始解決方案的能力，并挑戰(zhàn)了人類改進計算機科學(xué)算法的思考方式。”
如下圖示例原始sort3實現(xiàn)，有min(A, B, C)，使用AlphaDev Swap Move，AlphaDev發(fā)現(xiàn)，你只需要min(A, B)。
再比如，原始實現(xiàn)用max(B, min(A ,C, D))中較大的排序算法對8個元素進行排序。AlphaDev發(fā)現(xiàn)使用其「swap and copy moves」時只需要max(B, min(A, C))。
不僅如此，在發(fā)現(xiàn)了新排序算法后，DeepMind 還測試了 AlphaDev 是否可以改進數(shù)據(jù)結(jié)構(gòu)中常用的哈希算法，結(jié)果 AlphaDev 不負眾望，確實也發(fā)現(xiàn)了一種新的哈希算法，將其應(yīng)用于 9-16 字節(jié)范圍內(nèi)的哈希函數(shù)時，速度可提高 30%。而這個新哈希算法，也會在今年被發(fā)布到開源的 Abseil 庫中，供全球數(shù)百萬開發(fā)者使用。
用 AI 來優(yōu)化代碼的未來
通過以上新發(fā)現(xiàn)的排序算法和哈希算法，AlphaDev 已展示出了其概括和發(fā)現(xiàn)新算法的能力，即用 AI 來優(yōu)化世界上的代碼，并朝著開發(fā)通用 AI 工具邁出了重要一步。Google DeepMind認為，AlphaDev是朝著開發(fā)AGI工具邁出的一步，這些工具有助于優(yōu)化整個計算生態(tài)系統(tǒng)，還能解決其他有益于社會的問題。
不過，研究人員也承認，目前AlphaDev在低級匯編指令優(yōu)化能力非常強，但是隨著算法的發(fā)展也存在局限性。為了讓開發(fā)者更可用，AlphaDev用高級語言（如C++）優(yōu)化算法的能力正在探索中。AlphaDev的新發(fā)現(xiàn)，如「AlphaDev swap move」和「AlphaDev copy move」，不僅表明它可以改進算法，還可以找到新的解決方案。研究人員希望，這些發(fā)現(xiàn)能激勵研究人員和開發(fā)人員創(chuàng)造技術(shù)和方法，進一步優(yōu)化基礎(chǔ)算法，以創(chuàng)建一個更強大、更可持續(xù)的計算生態(tài)系統(tǒng)。
參考鏈接：
https://www.deepmind.com/blog/alphadev-discovers-faster-sorting-algorithms
評論 0