DeepMind又雙叒叕帶著重磅成果登Nature了！

這一次，他們又一強化學(xué)習(xí)AI，在計算機領(lǐng)域最最最基礎(chǔ)的兩個算法上做了新突破：

一個是排序算法，發(fā)現(xiàn)了速度最高可提升70%的新實現(xiàn)；

另一個是哈希算法，也找到了速度提高30%的新方法。

不僅如此，該AI所用方法被稱為“重現(xiàn)當(dāng)年AlphaGo的神來之筆”，也就是看似違法直覺，實則一舉擊敗人類高手李世石的那次。

消息一出，立刻引爆學(xué)術(shù)圈，有網(wǎng)友就直呼：

沒想到這么古老又基礎(chǔ)的算法還能被進(jìn)一步改進(jìn)。

而正是因為這一最新成果，十年都沒有更新的LLVM標(biāo)準(zhǔn)C++庫都更新了，并且數(shù)十億人將會受益。

因為，無論是排序還是哈希，它們的應(yīng)用場景從在線購物、云計算到供應(yīng)鏈管理等各個場景都能用到，每天會被調(diào)用上億次！

不過，如DeepMind所說：

大家千萬不要太興奮了，AI的力量用于代碼效率提升才剛剛開始。

Alpha家族“新貴”發(fā)現(xiàn)更快排序算法

這個AI名叫AlphaDev，屬于Alpha家族“新貴”，并且基于AlphaZero打造（就是2017年擊敗世界冠軍的那個棋類AI）。

它的發(fā)現(xiàn)并非基于現(xiàn)有算法，而是從最底層的匯編指令開始摸索的。

DeepMind的研究員給它設(shè)計了一種單人“組裝”游戲：

只要能夠搜索并選擇出合適的指令（下圖A流程），正確且快速地排好數(shù)據(jù)（下圖B流程），就能獲得獎勵。

但這個游戲的挑戰(zhàn)不僅在于搜索空間的大?。山M合指令數(shù)相當(dāng)于宇宙中的粒子數(shù)），也在于獎勵函數(shù)的性質(zhì)，因為一條錯誤指令就可能會使整個算法失效。

AlphaDev擁有兩個核心組件：學(xué)習(xí)算法和表示函數(shù)。

其中，學(xué)習(xí)算法主要是在強大的AlphaZero上擴展的，它可以結(jié)合DRL和隨機搜索優(yōu)化算法來進(jìn)行巨量的指令搜索；主要的表示函數(shù)則基于Transformer，它能夠抓住匯編程序的底層結(jié)構(gòu)，并表示成特殊的序列。

隨著AlphaDev不斷地打怪升級，研究員還會限制它能執(zhí)行的步數(shù)，以及待排序列的長度。

最終，AlphaDev發(fā)現(xiàn)了一種全新排序算法：

如果序列較短，相比人類基準(zhǔn)排序算法，它能將速度提高70%；如果序列長度超過25000個元素，則提高1.7%。

（3-5個元素的短序列排序其實使用非常廣泛，因為它能夠作為較大排序函數(shù)的一部分被多次調(diào)用。因此，只要改進(jìn)了短序列，任意數(shù)量序列的整體排序速度都能得到提高。）

具體而言，該算法的創(chuàng)新主要在于兩種指令序列：

（1）AlphaDev Swap Move（交換移動）
（2）AlphaDev Copy Move（復(fù)制移動）

如下圖所示，左邊是利用了min(A,B,C)的原始sort3實現(xiàn)，右邊是通過“AlphaDev Swap Move”，只需要min(A,B)的實現(xiàn)。能夠發(fā)現(xiàn)可以省掉一步指令，還只需要算出A和B的最小值即可。

作者表示，這種新穎的方法讓人想起當(dāng)年AlphaGo的“第 37 步”——一種違反直覺的下法卻直接擊敗傳奇圍棋選手李世石，讓觀眾全都震驚不已。

同樣，AlphaDev則是通過交換和復(fù)制移動，跳過了一個步驟，以一種看似錯誤但實際上是捷徑的方式達(dá)成目標(biāo)。

如下圖所示，在對8個元素進(jìn)行排序的算法中，AlphaDev也同樣利用“AlphaDev Copy Move”，用max (B, min (A, C))替換了原始實現(xiàn)中更為復(fù)雜的max (B, min (A, C, D))指令，并且使整個算法的指令總數(shù)也減少了一步。

而在發(fā)現(xiàn)更快的排序算法后，作者也用AlphaDev試了試哈希算法，以此證明其通用性。

結(jié)果也沒有讓人失望，AlphaDev在9-16字節(jié)的長度范圍內(nèi)也實現(xiàn)了30%的速度提升。

和排序算法一樣，他們已將新方法集成到了Abseil庫中，全球數(shù)百萬開發(fā)人員現(xiàn)在都可以使用。

最后，作者表示，兩種新算法的實現(xiàn)顯示AlphaDev具有強大的發(fā)現(xiàn)原始解決方案的能力，并且將使我們進(jìn)一步思考計算機領(lǐng)域基礎(chǔ)算法的改進(jìn)方式。

不過，由于本次研究中使用的匯編語言具有局限性，他們接下來還是打算嘗試AlphaDev在高級語言（如 C++）中優(yōu)化算法的能力。

網(wǎng)友：不算發(fā)現(xiàn)新的排序算法

對于這一成果，不少人表示非常興奮。

如這位網(wǎng)友所說：

AlphaGo驚艷全世界后，強化學(xué)習(xí)還能做什么？還能做任何有實際意義的事情嗎？這就是答案。

不過這次，有不少人指出，DeepMind似乎有夸大標(biāo)題的嫌疑。

它計算的是算法延遲，而非傳統(tǒng)意義上的時間復(fù)雜度。如果真算時間復(fù)雜度，數(shù)據(jù)可能不好看。

它改進(jìn)的并不是排序本身，而是在現(xiàn)代CPU上做新的排序（特別是短序列）。這種操作其實不算罕見，比如FFTW、ATLAS這些庫就是這么做的。

同意，他們只是為特定CPU找到了更快的機器優(yōu)化，并不算發(fā)現(xiàn)新的排序算法，方法本身很酷，但還不算開創(chuàng)性研究。

大家怎么看？

論文地址：https://www.nature.com/articles/s41586-023-06004-9
官方博客：https://www.deepmind.com/blog/alphadev-discovers-faster-sorting-algorithms?utm_source=twitter&utm_medium=social&utm_campaign=OCS

參考鏈接：
[1]https://twitter.com/demishassabis/status/1666545516941803520
[2]https://news.ycombinator.com/item?id=36228125
[3]https://twitter.com/DeepMind/status/1666462540367372291