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

本文來自微信公眾號：量子位 （ID：QbitAI），作者：豐色

總結

以上是生活随笔為你收集整理的重现当年 AlphaGo 神来之笔，DeepMind 新 AI 发现提速 70% 排序算法，十年都没更的 C++ 库更新了的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。