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

整個(gè)計(jì)算生態(tài)系統(tǒng)的基礎(chǔ)，或?qū)⒈?AI 創(chuàng)造的新算法顛覆！

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

AlphaDev 不僅可以將排序算法提速 70％，甚至在有的算法上，能比人類快 3 倍之多。

十多年來，C++ 排序庫首次更改。AI 優(yōu)化世界代碼，又達(dá)新里程碑。

目前，最新研究已登上 Nature。

通過強(qiáng)化學(xué)習(xí)，AlphaDev 發(fā)現(xiàn)了更加有效的算法，直接超越了科學(xué)家和工程師們幾十年來的精心打磨。

現(xiàn)在，新的算法已經(jīng)成為兩個(gè)標(biāo)準(zhǔn) C++ 編碼庫的一部分，每天都會(huì)被全球的程序員使用數(shù)萬億次。

有網(wǎng)友表示，終于來了，我們現(xiàn)在正在踏入未知領(lǐng)域：人工智能正在構(gòu)建人工智能！

強(qiáng)化學(xué)習(xí)打破十年算法瓶頸

如同 AlphaZero、AlphaFold 等前輩一樣，AlphaDev 也直接掀起了一個(gè)領(lǐng)域的變革。

DeepMind 計(jì)算機(jī)科學(xué)家、論文一作 Daniel Mankowitz 表示，「我們起初根本不相信。」

「說實(shí)話，我們沒有想到會(huì)取得更好的成績：這是一個(gè)非常短的程序，而這些類型的程序，此前已經(jīng)被研究幾十年了。」

當(dāng)前，GPT-4、Bard 等大模型的參數(shù)指數(shù)級(jí)增長，對(duì)算力等資源的需求不斷增長。而過去 50 年里，人類不斷依靠芯片的改進(jìn)以跟上步伐。

但隨著微芯片接近物理極限，改進(jìn)代碼讓計(jì)算更強(qiáng)大、更持續(xù)變得至關(guān)重要。尤其是，對(duì)每天運(yùn)行數(shù)萬億次代碼的算法愈重要。

今天，Google DeepMind 在 Nature 發(fā)表的論文中，首次介紹了阿爾法家族的「新貴」AlphaDev。

AlphaDev 發(fā)現(xiàn)了一種更快的排序算法，數(shù)十億人每天都在不知不覺中使用這些算法。

它們是一切的基礎(chǔ)，從在線搜索結(jié)果，社交帖子，到計(jì)算機(jī)和手機(jī)數(shù)據(jù)處理方式。這些算法每天都要執(zhí)行數(shù)萬億次。

利用 AI 生成更好的算法，將改變我們對(duì)計(jì)算機(jī)編程的方式，并影響我們數(shù)字化社會(huì)的方方面面。

根據(jù) Nature 論文中的數(shù)據(jù)，AlphaZero 所創(chuàng)造的算法能比人類的數(shù)據(jù)排序速度快三倍。

今天，Google DeepMind 還開源了在主 C++ 庫中的最新排序算法，所有人皆可用。

什么是排序？

排序是一種以特定順序組織多個(gè)項(xiàng)目的方法。

比如按字母順序排列三個(gè)字母，從大到小排列五個(gè)數(shù)字，或者將包含數(shù)百萬條記錄的數(shù)據(jù)庫排序。

在人類歷史中，排序方法一直在演變。最早的例子可以追溯到二、三世紀(jì)，那時(shí)的學(xué)者們?cè)趤啔v山大圖書館的書架上，靠純手工的方式，以字母順序排列擺放了數(shù)千本書。

工業(yè)革命后，我們發(fā)明了可以幫助分類的機(jī)器 —— 制表機(jī)將信息存儲(chǔ)在穿孔卡上，用于收集 1890 年美國的人口普查結(jié)果。

而隨著 20 世紀(jì) 50 年代商業(yè)計(jì)算機(jī)的興起，出現(xiàn)了最早的計(jì)算機(jī)科學(xué)排序算法。

在今天，世界各地的代碼庫中都使用了許多不同的排序技術(shù)和算法，在線組織大量數(shù)據(jù)。

這些算法，都已成為計(jì)算機(jī)科學(xué)的基石。

如今我們的算法，都需要計(jì)算機(jī)科學(xué)家和程序員投入幾十年的研究去開發(fā)。

這是因?yàn)?，現(xiàn)有的算法效率如此之高，再往前的每一步改進(jìn)，都是重大的挑戰(zhàn)。

這個(gè)艱難程度就好比找到一種節(jié)省電力能源的新方法，或者找到更高效的數(shù)學(xué)方法。

尋找新算法

AlphaDev 的創(chuàng)新意義在于，它并不是通過改進(jìn)現(xiàn)有算法，而是完全從頭開始發(fā)現(xiàn)了更快的算法。

而且，它竟然著手于大多數(shù)人類并沒有想到的地方 —— 計(jì)算機(jī)匯編指令。

匯編指令用于創(chuàng)建二進(jìn)制代碼。雖然開發(fā)者寫代碼時(shí)用的是 C++ 等高級(jí)語言，但為了讓計(jì)算機(jī)理解，這些高級(jí)語言必須翻譯成「低級(jí)」的匯編指令。

谷歌 DeepMind 的研究者相信，在這個(gè)較低的層級(jí)中存在許多可改進(jìn)的空間，而這些改進(jìn)在更高級(jí)的編程語言中可能很難發(fā)現(xiàn)。

在這個(gè)更低的級(jí)別上，計(jì)算機(jī)的存儲(chǔ)和操作都更靈活，因此如果再多做一些潛在的改進(jìn)，就會(huì)對(duì)速度和能源產(chǎn)生巨大的影響。

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

圖 B：代碼相應(yīng)的程序集

AlphaDev：匯編版 AlphaZero

眾所周知，DeepMind 的強(qiáng)化學(xué)習(xí)模型，在圍棋、國際象棋和將棋等游戲中，屢次擊敗世界冠軍。

而我們這次的主角 ——AlphaDev，基于的正是 AlphaZero。

AlphaDev 的工作方式與之前的 AlphaZero 相似，后者結(jié)合了計(jì)算機(jī)推理和直覺，在棋盤游戲中選擇每一步的走法。

只不過，AlphaDev 并不會(huì)選擇下一步怎么走棋，而是選擇添加哪些指令。

為了訓(xùn)練 AlphaDev 來發(fā)現(xiàn)新的算法，DeepMind 將排序問題轉(zhuǎn)化成了一個(gè)「匯編游戲」（Assembly Game）。

在每一輪中，AlphaDev 都需要觀察它生成的算法以及中央處理器（CPU）中包含的信息，并通過在算法中添加一條指令來進(jìn)行移動(dòng)。

而這個(gè)匯編游戲非常困難，因?yàn)?AlphaDev 必須有效地搜索大量可能的指令組合，從而找到一個(gè)可以排序且比當(dāng)前最佳算法更快的算法。

其中「可能的指令組合」，甚至可以直接類比于宇宙中的粒子數(shù)量，或者國際象棋（10^120 局）和圍棋（10^700 局）中可能的走法組合。

更進(jìn)一步的是，任何一個(gè)錯(cuò)誤的移動(dòng)，都可能會(huì)使整個(gè)算法無效。

最后，DeepMind 會(huì)根據(jù) AlphaDev 正確排序數(shù)字的能力以及完成排序的速度和效率給予獎(jiǎng)勵(lì)，而 AlphaDev 則需要通過發(fā)現(xiàn)一個(gè)正確且更快的程序來贏得游戲。

圖 A：匯編游戲。玩家 AlphaDev 以系統(tǒng)狀態(tài) st 為輸入，并通過選擇一條匯編指令將其添加到已經(jīng)生成的算法中來進(jìn)行一次移動(dòng)。

圖 B：獎(jiǎng)勵(lì)計(jì)算。在每次移動(dòng)后，生成的算法會(huì)接受測試，智能體將根據(jù)算法的正確性和響應(yīng)時(shí)間獲得獎(jiǎng)勵(lì)。

具體來說，在進(jìn)行深入思考（deliberation）時(shí)，AlphaZero 會(huì)在每一個(gè)決策點(diǎn)琢磨下一步可能的行動(dòng)，以及下一步的下一步的可能性。就像樹狀圖一樣，一步步往后推，算出哪些行動(dòng)最有可能成功。

但問題在于，如果把每一個(gè)可能的情況分支都考慮到，所需的時(shí)間可能要比宇宙的年齡還長。因此，研究人員使用類似直覺（intuition）的東西來縮小范圍。

在每一步中，程序?qū)?dāng)前狀態(tài)輸入神經(jīng)網(wǎng)絡(luò)（一個(gè)復(fù)雜的、可調(diào)的數(shù)學(xué)函數(shù)），以找到最合適的行為。同時(shí)，在訓(xùn)練過程中，神經(jīng)網(wǎng)絡(luò)還會(huì)根據(jù)結(jié)果不斷進(jìn)行更新。有時(shí)還會(huì)故意不選評(píng)分最高的行為來進(jìn)行主動(dòng)探索。

AlphaDev 可以采取的行動(dòng)一共有四種，包括比較不同值、移動(dòng)數(shù)值到另一個(gè)位置、或者跳轉(zhuǎn)到程序的不同部分。

在執(zhí)行完每一步之后，再試圖對(duì)一組列表進(jìn)行排序，并根據(jù)正確排序的列表中的數(shù)值數(shù)量獲得獎(jiǎng)勵(lì)。

如此這般，這般如此，一直到排完整個(gè)列表，或者達(dá)到程序長度限制，從頭開始一個(gè)新的程序。

C++ 運(yùn)行速度提升 70%

AlphaDev 發(fā)現(xiàn)新的排序算法，為 LLVM libc++ 排序庫帶來了明顯的改進(jìn)。

對(duì)于較短的序列，速度提高了 70%，而對(duì)于超過 250,000 個(gè)元素的序列，速度只提高了約 1.7%。

研究人員專注于改進(jìn) 3-5 個(gè)元素較短的序列排序算法。

這些算法是使用最廣泛的算法之一，因?yàn)樗鼈兘?jīng)常作為更大排序函數(shù)的一部分被多次調(diào)用。

改進(jìn)這些算法可以為任何數(shù)量的項(xiàng)目的排序提升整體的速度。

為了使新的排序算法為所有人可用，研究人員還將其進(jìn)行了逆向工程，并將其翻譯成「程序猿」最常用的一種編碼語言 C++。

目前，這些算法現(xiàn)在可以在 LLVM libc++ 標(biāo)準(zhǔn)排序庫中找到。

散列函數(shù)效率提升 30%

在發(fā)現(xiàn)更快的排序算法之后，DeepMind 測試了 AlphaDev 是否能夠推廣并改進(jìn)不同的計(jì)算機(jī)科學(xué)算法 —— 散列（Hash）。

散列是計(jì)算中的一種基本算法，用于檢索、存儲(chǔ)和壓縮數(shù)據(jù)。就像圖書管理員使用分類系統(tǒng)來找到特定的書籍一樣，散列算法幫助用戶知道他們正在尋找的內(nèi)容以及確切的位置。

這些算法將特定的 key（例如用戶姓名「Jane Doe」）進(jìn)行散列處理，也就是，將原始數(shù)據(jù)轉(zhuǎn)換為唯一的字符串（例如 1234ghfty）。然后，計(jì)算機(jī)會(huì)使用這個(gè)散列值來快速檢索與鍵相關(guān)的數(shù)據(jù)，而不是搜索所有數(shù)據(jù)。

結(jié)果顯示，當(dāng)應(yīng)用于散列函數(shù)的 9 到 16 字節(jié)范圍時(shí)，AlphaDev 發(fā)現(xiàn)的算法比傳統(tǒng)算法快 30%。

現(xiàn)在，DeepMind 也將新的散列算法發(fā)布到了開源的 Abseil 庫中。據(jù)了解，這個(gè)算法預(yù)計(jì)每天都會(huì)被使用數(shù)萬億次。

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

AlphaDev 不僅發(fā)現(xiàn)了更快的算法，還發(fā)現(xiàn)了新的方法。

它的排序算法包含新的指令序列，每次應(yīng)用時(shí)都會(huì)保存一條指令。這可能會(huì)產(chǎn)生巨大的影響，因?yàn)檫@些算法每天被使用數(shù)萬億次。

研究人員將其稱之為「AlphaDev swap move」和「AlphaDev copy move」。

最新方法讓人想起 AlphaGo 讓人震驚的「第 37 步」。

2016 年那場人機(jī)大戰(zhàn)中，AlphaGo 下了一顆違反人類直覺的棋，一個(gè)簡單的肩沖，擊敗了傳奇圍棋選手李世石。

通過這兩種策略，AlphaDev 跳過了一個(gè)步驟，以一種看起來錯(cuò)誤，但實(shí)際上是快捷方式連接項(xiàng)目。

這表明，AlphaDev 有能力發(fā)現(xiàn)原創(chuàng)性解決方案，并挑戰(zhàn)了我們對(duì)如何改進(jìn)計(jì)算機(jī)科學(xué)算法的思考方式。

如下圖示例原始 sort3 實(shí)現(xiàn)，有 min (A, B, C)，使用 AlphaDev Swap Move，AlphaDev 發(fā)現(xiàn)，你只需要 min (A, B)。

再比如，原始實(shí)現(xiàn)用 max (B, min (A ,C, D)) 中較大的排序算法對(duì) 8 個(gè)元素進(jìn)行排序。

AlphaDev 發(fā)現(xiàn)使用其「swap and copy moves」時(shí)只需要 max (B, min (A, C))。

優(yōu)化全世界的代碼，一次一個(gè)算法

通過優(yōu)化和推出全球開發(fā)者使用的改進(jìn)排序和散列算法，AlphaDev 證明了，它有能力概括和發(fā)現(xiàn)世界級(jí)的新算法。

Google DeepMind 認(rèn)為，AlphaDev 是朝著開發(fā) AGI 工具邁出的一步，這些工具有助于優(yōu)化整個(gè)計(jì)算生態(tài)系統(tǒng)，還能解決其他有益于社會(huì)的問題。

不過，研究人員也承認(rèn)，目前 AlphaDev 在低級(jí)匯編指令優(yōu)化能力非常強(qiáng)，但是隨著算法的發(fā)展也存在局限性。

為了讓開發(fā)者更可用，AlphaDev 用高級(jí)語言（如 C++）優(yōu)化算法的能力正在探索中。

AlphaDev 的新發(fā)現(xiàn)，如「AlphaDev swap move」和「AlphaDev copy move」，不僅表明它可以改進(jìn)算法，還可以找到新的解決方案。

研究人員希望，這些發(fā)現(xiàn)能激勵(lì)研究人員和開發(fā)人員創(chuàng)造技術(shù)和方法，進(jìn)一步優(yōu)化基礎(chǔ)算法，以創(chuàng)建一個(gè)更強(qiáng)大、更可持續(xù)的計(jì)算生態(tài)系統(tǒng)。

網(wǎng)友熱評(píng)

英偉達(dá)科學(xué)家 Jim Fan 對(duì) AlphaDev 做了一個(gè)深度總結(jié)：

排序算法是所有關(guān)鍵軟件的基礎(chǔ)。DeepMind 的 AlphaDev 將小序列（3-5 項(xiàng)）的排序速度提高了 70%。要點(diǎn)：

-  主要的 RL 算法是基于最初下圍棋 Go、Chess & Shogi 的 AlphaZero。同樣的想法也適用于搜索程序！

- 研究人員沒有對(duì) C 代碼進(jìn)行優(yōu)化，而是對(duì)匯編代碼進(jìn)行優(yōu)化。這是一個(gè)刻意的選擇，去低級(jí)別的擠壓每一條指令的保存。

- 匯編代碼然后被逆向工程為 C++，并在 LLVM 中開源。

- 即使表征網(wǎng)絡(luò)使用了 Transformer，它也不是一個(gè)基礎(chǔ)模型。整個(gè)流程只適用于排序，對(duì)于其他任務(wù)如散列，必須重新訓(xùn)練。

在使用 ML 的算法發(fā)現(xiàn)方面取得了另一個(gè)重要的里程碑!

AlphaDev 是 DeepMind 的一個(gè)改變游戲規(guī)則的人工智能，它創(chuàng)新了核心計(jì)算機(jī)科學(xué)算法。它正在重新構(gòu)想排序方法，短序列的速度可提高 70%。甚至散列算法的發(fā)現(xiàn)速度提高了 30%。強(qiáng)化學(xué)習(xí)正在重塑算法的格局！

還有網(wǎng)友稱，在我們對(duì)語言模型感到興奮之余，也不要忘記其他深度學(xué)習(xí)算法的成功故事：AlphaZero、AlphaFold，以及現(xiàn)在的 AlphaDev。

參考資料：

• https://www.deepmind.com/blog/alphadev-discovers-faster-sorting-algorithms

本文來自微信公眾號(hào)：新智元 （ID：AI_era）

廣告聲明：文內(nèi)含有的對(duì)外跳轉(zhuǎn)鏈接（包括不限于超鏈接、二維碼、口令等形式），用于傳遞更多信息，節(jié)省甄選時(shí)間，結(jié)果僅供參考，IT之家所有文章均包含本聲明。