點擊參加51CTO網(wǎng)站內(nèi)容調(diào)查問卷

編譯 | 王瑞平、言征

AlphaGo又有“小弟”加入了!

谷歌DeepMind把Alpha系列“卷”到了排序算法上，重磅推出AlphaDev。

它好比一種“開發(fā)秘法”，通過使用強(qiáng)化學(xué)習(xí)AI發(fā)現(xiàn)排序算法和散列算法，強(qiáng)行把人類程序員設(shè)計的算法分別提速約70%和30%。

研究成果一經(jīng)推出，瞬間點燃軟件圈！一下子，全球數(shù)以百萬計的軟件運行速度飆升，直接超越了科學(xué)家和工程師幾十年來的成果，十年未更新的LLVM標(biāo)準(zhǔn)C++庫都更新了。

（來源：Nature）

這也是繼谷歌兩AI部門合體后推出的顛覆性技術(shù)。論文以《使用深度強(qiáng)化學(xué)習(xí)模型發(fā)現(xiàn)更快排序算法》（Faster sorting algorithms discovered using deep reinforcement learning）為題發(fā)表于Nature。DeepMind計算機(jī)科學(xué)家Daniel Mankowitz為論文的第一作者。

1、演進(jìn)：排序算法的由來

排序是一種將許多項目按特定順序組織起來的方法，例如，按照字母順序排列三個字母，從最大到最小的順序排列五個數(shù)字或?qū)Π瑪?shù)百萬條記錄的數(shù)據(jù)庫進(jìn)行排序。

排序法最早可追溯至二到三世紀(jì)，仍在不斷演進(jìn)。最初，學(xué)者們徒手將亞歷山大圖書館書架上的數(shù)千本書按字母順序進(jìn)行排序。

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

20世紀(jì)50年代，商用計算機(jī)開始興起，也隨即產(chǎn)生了排序算法。將一系列未排序的數(shù)字輸入到排序算法中，它就能輸出排好順序的數(shù)字。

如今，在世界各地的代碼庫中，仍有許多不同的排序技術(shù)和算法被用于在線整理大量數(shù)據(jù)。      

這些排序算法經(jīng)過計算機(jī)科學(xué)家和程序員幾十年的研究開發(fā)，變得越來越高效。但是，對其進(jìn)一步改進(jìn)仍具有重大挑戰(zhàn)。

2、重頭戲：如何用AlphaDev生成新排序算法？

研究人員最初用AlphaDev生成新算法的目的是高效率完成給定任務(wù)。

在這個實驗中，AlphaDev是從零開始構(gòu)建新算法的，并不是根據(jù)以往算法構(gòu)建，屬于原創(chuàng)。在此過程中，它應(yīng)用了匯編代碼的中間語言。該語言更接近計算機(jī)二進(jìn)制指令，也更容易讓AlphaDev創(chuàng)造出高效算法。

具體來講，AlphaDev每次生成一個指令，然后測試其輸出正確與否，同時還在模型中設(shè)定要求生成最短算法。

當(dāng)被要求重新設(shè)計排序算法時，AlphaDev隨機(jī)生成比現(xiàn)有算法快70%的新排序算法，可同時將五個數(shù)據(jù)排序。在對25萬個數(shù)據(jù)進(jìn)行排序時，它也比最好的算法快1.7%。

由于排序算法被廣泛用于各種常用軟件中，這項創(chuàng)新會對全球算法產(chǎn)生重大影響。DeepMind已將它們進(jìn)行開源，并加入Libc++常用代碼庫。

據(jù)DeepMind的研究者描述：“由于指令組合數(shù)量龐大，看似簡單的研究過程難度極大。”

3、緣起：在玩游戲中找到最佳算法  

進(jìn)一步來講，AlphaDev是基于AlphaZero產(chǎn)生的更先進(jìn)模型。而AlphaZero此前是DeepMind的強(qiáng)化學(xué)習(xí)模型，曾在圍棋、國際象棋和其它棋類游戲中擊敗了世界冠軍。

通過此項實驗，新模型AlphaDev發(fā)揮出從玩游戲轉(zhuǎn)移到解決科學(xué)問題以及從實驗?zāi)M轉(zhuǎn)移到現(xiàn)實世界應(yīng)用的獨特優(yōu)勢。

為訓(xùn)練AlphaDev發(fā)現(xiàn)新算法，研究者將排序模擬為單人“組裝游戲”。在每個游戲回合中，AlphaDev都能觀察到生成的算法和包含在CPU中的信息，然后選擇一條指令添加到算法中走出每一步棋。

論文中提到，匯編游戲非常困難，因為AlphaDev必須能夠有效地搜索到大量可能的指令組合以獲取可以排序的算法。

指令組合數(shù)量類似于宇宙中粒子數(shù)量或國際象棋(10120局)和圍棋(10700局)中可能走法的組合數(shù)量，每個錯誤的舉動將會使整個算法失效。

然后，該模型輸出一個算法并將其與預(yù)期輸出比較，根據(jù)算法的正確性和延遲時間獎勵代理。

在構(gòu)建算法時，每次輸入一個指令，AlphaDev通過比較輸出算法與預(yù)期結(jié)果檢查正確性（對于排序算法，這意味著輸入無序的數(shù)字后能夠輸出正確排序的數(shù)字）。

模型會獎勵A(yù)lphaDev對數(shù)字的正確排序以及它的高效。最終AlphaDev通過發(fā)現(xiàn)更準(zhǔn)確的、更快的程序贏得了比賽。

4、算法創(chuàng)新：交換移動和復(fù)制移動指令序列

AlphaDev不僅生成了更快算法，還創(chuàng)新出兩種指令序列。

具體來講，它生成的排序算法包括交換移動和復(fù)制移動兩種新的指令序列，每次使用時都會保存一條指令。研究者稱之為“AlphaDev的交換移動和復(fù)制移動”。

這種新穎的方法讓人想起AlphaGo的“第37步”——“反直覺”下棋法，震驚了旁觀者并造成一位傳奇棋手的失敗。

通過交換移動和復(fù)制移動指令序列，AlphaDev跳過了一個步驟，以一種看起來像錯誤但實際上是捷徑的方式完成目標(biāo)。這表明，AlphaDev有能力發(fā)現(xiàn)原始解決方案，并挑戰(zhàn)如何改進(jìn)計算機(jī)科學(xué)算法。

5、測試：推廣和改進(jìn)散列算法

在發(fā)現(xiàn)更快的排序算法后，研究者測試了AlphaDev是否可以推廣和改進(jìn)另一種計算機(jī)科學(xué)算法：散列算法。

散列算法是計算中的一種基本算法，用于檢索、存儲和壓縮數(shù)據(jù)。就像圖書管理員使用分類系統(tǒng)定位某本書一樣，散列算法幫助用戶知道他們要找的是什么以及在哪里可以找到它。

這些算法能夠獲取特定密鑰(例如，用戶名“Jane Doe”)的數(shù)據(jù)并對其進(jìn)行散列排序——將原始數(shù)據(jù)轉(zhuǎn)換為唯一字符串(例如，1234ghty)。

計算機(jī)使用該散列快速檢索與密鑰相關(guān)的數(shù)據(jù)，而不是搜索所有數(shù)據(jù)。

研究人員將AlphaDev應(yīng)用于數(shù)據(jù)結(jié)構(gòu)中最常用的散列算法之一以嘗試發(fā)現(xiàn)更快的算法。當(dāng)將其應(yīng)用于散列函數(shù)的9-16字節(jié)范圍時，AlphaDev生成的算法速度快了30%。

今年早些時候，AlphaDev生成的新散列算法曾被發(fā)布到開源的Abseil庫中，全世界數(shù)以百萬計的開發(fā)人員都可以使用，估計它現(xiàn)在每天被使用數(shù)萬億次。

6、蓄勢：邁出開發(fā)AGI的第一步  

通過優(yōu)化“排序和散列算法”，AlphaDev展示出生成不同實用新算法的能力。

這也是AlphaDev朝著開發(fā)通用人工智能（AGI）工具邁出的第一步，通過類似的AI工具還可以幫助優(yōu)化整個計算生態(tài)系統(tǒng)并解決其它有益于社會的問題。

雖然在低級匯編指令空間中優(yōu)化算法的功能非常強(qiáng)大，但它也存在局限性。目前，團(tuán)隊也正在探索AlphaDev直接在高級語言(如，C++)中優(yōu)化算法的能力，這對開發(fā)人員更有用。

總之，希望這些新發(fā)現(xiàn)能夠激勵開發(fā)人員創(chuàng)造新技術(shù)和方法、進(jìn)一步優(yōu)化基本算法，創(chuàng)造更強(qiáng)大、更可持續(xù)的計算生態(tài)系統(tǒng)。

7、開源：AI優(yōu)化代碼的里程碑突破

此前，排序算法每天都會被使用數(shù)萬億次。隨著計算需求的增長，人們對算法的性能要求越來越高。雖然人類工程師已發(fā)現(xiàn)不同的排序算法，但經(jīng)過幾十年的優(yōu)化，很難再有突破，也滿足不了日益增長的需求。

如今，AlphaDev發(fā)現(xiàn)了一種更快的排序算法，可對數(shù)據(jù)進(jìn)行排序。

新排序算法無所不能，既可應(yīng)用于對在線搜索結(jié)果和社交帖子進(jìn)行排名，也可在電腦和手機(jī)上處理數(shù)據(jù)。

值得慶賀的是，新排序算法已在主C++庫中開源。世界各地數(shù)以百萬的開發(fā)人員和公司目前可將其用于云計算、在線購物、供應(yīng)鏈管理等。

總之，使用人工智能工具優(yōu)化算法將徹底改變傳統(tǒng)編程方式。這是十幾年來第一次對排序庫進(jìn)行更改，第一次將強(qiáng)化學(xué)習(xí)模型設(shè)計出的算法添加到排序庫中，因此成為了使用人工智能優(yōu)化代碼的里程碑式突破。

8、用戶：可能只是噱頭 

對于該項研究成果用戶褒貶不一，Twitter上贊美的聲音居多：

“這太棒了！在程序員早期就學(xué)會的基本排序任務(wù)基礎(chǔ)上，速度提高了70%。看到利用AI在我們都依賴的算法和庫中進(jìn)行重大加速，真是令人興奮”。

“很快，普通人就可以成為高級程序員”。

“有趣的方法，從裝配級別開始優(yōu)化”！

但是，也有的程序員認(rèn)為這只是個噱頭，DeepMind夸大了該算法的功能。

首先就是從效率的角度，它只統(tǒng)計了算法的延遲，而非真正改變了時間復(fù)雜度。

而且，它并沒有真正改變排序，這種操作常見于各種其它代碼庫。

參考資料：

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