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

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

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

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

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

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

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

而正是因?yàn)檫@一最新成果，十年都沒(méi)有更新的LLVM標(biāo)準(zhǔn)C++庫(kù)都更新了，并且數(shù)十億人將會(huì)受益。

因?yàn)椋瑹o(wú)論是排序還是哈希，它們的應(yīng)用場(chǎng)景從在線購(gòu)物、云計(jì)算到供應(yīng)鏈管理等各個(gè)場(chǎng)景都能用到，每天會(huì)被調(diào)用上億次！

不過(guò)，如DeepMind所說(shuō)：

大家千萬(wàn)不要太興奮了，AI的力量用于代碼效率提升才剛剛開(kāi)始。

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

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

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

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

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

但這個(gè)游戲的挑戰(zhàn)不僅在于搜索空間的大小（可組合指令數(shù)相當(dāng)于宇宙中的粒子數(shù)），也在于獎(jiǎng)勵(lì)函數(shù)的性質(zhì)，因?yàn)橐粭l錯(cuò)誤指令就可能會(huì)使整個(gè)算法失效。

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

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

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

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

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

（3-5個(gè)元素的短序列排序其實(shí)使用非常廣泛，因?yàn)樗軌蜃鳛檩^大排序函數(shù)的一部分被多次調(diào)用。因此，只要改進(jìn)了短序列，任意數(shù)量序列的整體排序速度都能得到提高。）

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

同意，他們只是為特定CPU找到了更快的機(jī)器優(yōu)化，并不算發(fā)現(xiàn)新的排序算法，方法本身很酷，但還不算開(kāi)創(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