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

這一次，他們又一強化學習AI，在計算機領域最最最基礎的兩個算法上做了新突破：

一個是排序算法，發現了速度最高可提升70%的新實現；

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

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

消息一出，立刻引爆學術圈，有網友就直呼：

沒想到這么古老又基礎的算法還能被進一步改進。

而正是因為這一最新成果，十年都沒有更新的LLVM標準C++庫都更新了，并且數十億人將會受益。

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

不過，如DeepMind所說：

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

Alpha家族“新貴”發現更快排序算法

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

它的發現并非基于現有算法，而是從最底層的匯編指令開始摸索的。

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

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

但這個游戲的挑戰不僅在于搜索空間的大小（可組合指令數相當于宇宙中的粒子數），也在于獎勵函數的性質，因為一條錯誤指令就可能會使整個算法失效。

AlphaDev擁有兩個核心組件：學習算法和表示函數。

其中，學習算法主要是在強大的AlphaZero上擴展的，它可以結合DRL和隨機搜索優化算法來進行巨量的指令搜索；主要的表示函數則基于Transformer，它能夠抓住匯編程序的底層結構，并表示成特殊的序列。

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

最終，AlphaDev發現了一種全新排序算法：

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

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

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

（1）AlphaDev Swap Move（交換移動）
（2）AlphaDev Copy Move（復制移動）

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

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

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

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

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

結果也沒有讓人失望，AlphaDev在9-16字節的長度范圍內也實現了30%的速度提升。

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

最后，作者表示，兩種新算法的實現顯示AlphaDev具有強大的發現原始解決方案的能力，并且將使我們進一步思考計算機領域基礎算法的改進方式。

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

網友：不算發現新的排序算法

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

如這位網友所說：

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

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

它計算的是算法延遲，而非傳統意義上的時間復雜度。如果真算時間復雜度，數據可能不好看。

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

同意，他們只是為特定CPU找到了更快的機器優化，并不算發現新的排序算法，方法本身很酷，但還不算開創性研究。

大家怎么看？

論文地址：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