【導(dǎo)讀】「Alpha」家族再添新成員AlphaDev!谷歌大腦DeepMind合體后首發(fā)力作,全新AI系統(tǒng)將排序算法提速70%,C++排序庫(kù)十年來(lái)首次更改。AI創(chuàng)造AI的時(shí)代要來(lái)了?
今天,「Alpha」家族再添一名新成員:AlphaDev。
整個(gè)計(jì)算生態(tài)系統(tǒng)的基礎(chǔ),或?qū)⒈籄I創(chuàng)造的新算法顛覆!
谷歌大腦和DeepMind合體沒(méi)多久,就帶來(lái)這樣一個(gè)驚世之作。
AlphaDev不僅可以將排序算法提速70%,甚至在有的算法上,能比人類快3倍之多。 十多年來(lái),C++排序庫(kù)首次更改。AI優(yōu)化世界代碼,又達(dá)新里程碑。 目前,最新研究已登上Nature。
論文地址:https://www.nature.com/articles/s41586-023-06004-9 通過(guò)強(qiáng)化學(xué)習(xí),AlphaDev發(fā)現(xiàn)了更加有效的算法,直接超越了科學(xué)家和工程師們幾十年來(lái)的精心打磨。 現(xiàn)在,新的算法已經(jīng)成為兩個(gè)標(biāo)準(zhǔn)C++編碼庫(kù)的一部分,每天都會(huì)被全球的程序員使用數(shù)萬(wàn)億次。 有網(wǎng)友表示,終于來(lái)了,我們現(xiàn)在正在踏入未知領(lǐng)域:人工智能正在構(gòu)建人工智能!
強(qiáng)化學(xué)習(xí)打破十年算法瓶頸
如同AlphaZero、AlphaFold等前輩一樣,AlphaDev也直接掀起了一個(gè)領(lǐng)域的變革。 DeepMind計(jì)算機(jī)科學(xué)家、論文一作Daniel Mankowitz表示,「我們起初根本不相信?!?「說(shuō)實(shí)話,我們沒(méi)有想到會(huì)取得更好的成績(jī):這是一個(gè)非常短的程序,而這些類型的程序,此前已經(jīng)被研究幾十年了?!?當(dāng)前,GPT-4、Bard等大模型的參數(shù)指數(shù)級(jí)增長(zhǎng),對(duì)算力等資源的需求不斷增長(zhǎng)。而過(guò)去50年里,人類不斷依靠芯片的改進(jìn)以跟上步伐。 但隨著微芯片接近物理極限,改進(jìn)代碼讓計(jì)算更強(qiáng)大、更持續(xù)變得至關(guān)重要。尤其是,對(duì)每天運(yùn)行數(shù)萬(wàn)億次代碼的算法愈重要。 今天,Google DeepMind在Nature發(fā)表的論文中,首次介紹了阿爾法家族的「新貴」AlphaDev。
AlphaDev發(fā)現(xiàn)了一種更快的排序算法,數(shù)十億人每天都在不知不覺(jué)中使用這些算法。 它們是一切的基礎(chǔ),從在線搜索結(jié)果,社交帖子,到計(jì)算機(jī)和手機(jī)數(shù)據(jù)處理方式。這些算法每天都要執(zhí)行數(shù)萬(wàn)億次。 利用AI生成更好的算法,將改變我們對(duì)計(jì)算機(jī)編程的方式,并影響我們數(shù)字化社會(huì)的方方面面。 根據(jù)Nature論文中的數(shù)據(jù),AlphaZero所創(chuàng)造的算法能比人類的數(shù)據(jù)排序速度快三倍。
今天,Google DeepMind還開源了在主C++庫(kù)中的最新排序算法,所有人皆可用。 開源地址:https://reviews.llvm.org/D118029
什么是排序?
排序是一種以特定順序組織多個(gè)項(xiàng)目的方法。 比如按字母順序排列三個(gè)字母,從大到小排列五個(gè)數(shù)字,或者將包含數(shù)百萬(wàn)條記錄的數(shù)據(jù)庫(kù)排序。 在人類歷史中,排序方法一直在演變。最早的例子可以追溯到二、三世紀(jì),那時(shí)的學(xué)者們?cè)趤啔v山大圖書館的書架上,靠純手工的方式,以字母順序排列擺放了數(shù)千本書。 工業(yè)革命后,我們發(fā)明了可以幫助分類的機(jī)器——制表機(jī)將信息存儲(chǔ)在穿孔卡上,用于收集1890年美國(guó)的人口普查結(jié)果。 而隨著20世紀(jì)50年代商業(yè)計(jì)算機(jī)的興起,出現(xiàn)了最早的計(jì)算機(jī)科學(xué)排序算法。 在今天,世界各地的代碼庫(kù)中都使用了許多不同的排序技術(shù)和算法,在線組織大量數(shù)據(jù)。
排序算法,也就是輸入一系列未排序的數(shù)字,然后輸出排序后的數(shù)字 這些算法,都已成為計(jì)算機(jī)科學(xué)的基石。 如今我們的算法,都需要計(jì)算機(jī)科學(xué)家和程序員投入幾十年的研究去開發(fā)。 這是因?yàn)?,現(xiàn)有的算法效率如此之高,再往前的每一步改進(jìn),都是重大的挑戰(zhàn)。 這個(gè)艱難程度就好比找到一種節(jié)省電力能源的新方法,或者找到更高效的數(shù)學(xué)方法。
尋找新算法
AlphaDev的創(chuàng)新意義在于,它并不是通過(guò)改進(jìn)現(xiàn)有算法,而是完全從頭開始發(fā)現(xiàn)了更快的算法。 而且,它竟然著手于大多數(shù)人類并沒(méi)有想到的地方——計(jì)算機(jī)匯編指令。 匯編指令用于創(chuàng)建二進(jìn)制代碼。雖然開發(fā)者寫代碼時(shí)用的是C++等高級(jí)語(yǔ)言,但為了讓計(jì)算機(jī)理解,這些高級(jí)語(yǔ)言必須翻譯成「低級(jí)」的匯編指令。
我們一般用C++之類的高級(jí)編程語(yǔ)言寫代碼,然后使用編譯器將其轉(zhuǎn)換為低級(jí)CPU指令,即匯編指令。匯編器再將匯編指令轉(zhuǎn)換為可執(zhí)行的機(jī)器代碼 谷歌DeepMind的研究者相信,在這個(gè)較低的層級(jí)中存在許多可改進(jìn)的空間,而這些改進(jìn)在更高級(jí)的編程語(yǔ)言中可能很難發(fā)現(xiàn)。 在這個(gè)更低的級(jí)別上,計(jì)算機(jī)的存儲(chǔ)和操作都更靈活,因此如果再多做一些潛在的改進(jìn),就會(huì)對(duì)速度和能源產(chǎn)生巨大的影響。
圖A:一個(gè)最多排序兩個(gè)元素的C++算法
圖B:代碼相應(yīng)的程序集
AlphaDev:匯編版AlphaZero
眾所周知,DeepMind的強(qiáng)化學(xué)習(xí)模型,在圍棋、國(guó)際象棋和將棋等游戲中,屢次擊敗世界冠軍。 而我們這次的主角——AlphaDev,基于的正是AlphaZero。 AlphaDev的工作方式與之前的AlphaZero相似,后者結(jié)合了計(jì)算機(jī)推理和直覺(jué),在棋盤游戲中選擇每一步的走法。 只不過(guò),AlphaDev并不會(huì)選擇下一步怎么走棋,而是選擇添加哪些指令。 為了訓(xùn)練AlphaDev來(lái)發(fā)現(xiàn)新的算法, DeepMind將排序問(wèn)題轉(zhuǎn)化成了一個(gè)「匯編游戲」(Assembly Game)。 在每一輪中,AlphaDev都需要觀察它生成的算法以及中央處理器(CPU)中包含的信息,并通過(guò)在算法中添加一條指令來(lái)進(jìn)行移動(dòng)。 而這個(gè)匯編游戲非常困難,因?yàn)锳lphaDev必須有效地搜索大量可能的指令組合,從而找到一個(gè)可以排序且比當(dāng)前最佳算法更快的算法。 其中「可能的指令組合」,甚至可以直接類比于宇宙中的粒子數(shù)量,或者國(guó)際象棋(10^120局)和圍棋(10^700局)中可能的走法組合。 更進(jìn)一步的是,任何一個(gè)錯(cuò)誤的移動(dòng),都可能會(huì)使整個(gè)算法無(wú)效。 最后,DeepMind會(huì)根據(jù)AlphaDev正確排序數(shù)字的能力以及完成排序的速度和效率給予獎(jiǎng)勵(lì),而AlphaDev則需要通過(guò)發(fā)現(xiàn)一個(gè)正確且更快的程序來(lái)贏得游戲。
圖A:匯編游戲。玩家AlphaDev以系統(tǒng)狀態(tài)st為輸入,并通過(guò)選擇一條匯編指令將其添加到已經(jīng)生成的算法中來(lái)進(jìn)行一次移動(dòng)。
圖B:獎(jiǎng)勵(lì)計(jì)算。在每次移動(dòng)后,生成的算法會(huì)接受測(cè)試,智能體將根據(jù)算法的正確性和響應(yīng)時(shí)間獲得獎(jiǎng)勵(lì)。 具體來(lái)說(shuō),在進(jìn)行深入思考(deliberation)時(shí),AlphaZero會(huì)在每一個(gè)決策點(diǎn)琢磨下一步可能的行動(dòng),以及下一步的下一步的可能性。就像樹狀圖一樣,一步步往后推,算出哪些行動(dòng)最有可能成功。 但問(wèn)題在于,如果把每一個(gè)可能的情況分支都考慮到,所需的時(shí)間可能要比宇宙的年齡還長(zhǎng)。因此,研究人員使用類似直覺(jué)(intuition)的東西來(lái)縮小范圍。 在每一步中,程序?qū)?dāng)前狀態(tài)輸入神經(jīng)網(wǎng)絡(luò)(一個(gè)復(fù)雜的、可調(diào)的數(shù)學(xué)函數(shù)),以找到最合適的行為。同時(shí),在訓(xùn)練過(guò)程中,神經(jīng)網(wǎng)絡(luò)還會(huì)根據(jù)結(jié)果不斷進(jìn)行更新。有時(shí)還會(huì)故意不選評(píng)分最高的行為來(lái)進(jìn)行主動(dòng)探索。 AlphaDev可以采取的行動(dòng)一共有四種,包括比較不同值、移動(dòng)數(shù)值到另一個(gè)位置、或者跳轉(zhuǎn)到程序的不同部分。 在執(zhí)行完每一步之后,再試圖對(duì)一組列表進(jìn)行排序,并根據(jù)正確排序的列表中的數(shù)值數(shù)量獲得獎(jiǎng)勵(lì)。 如此這般,這般如此,一直到排完整個(gè)列表,或者達(dá)到程序長(zhǎng)度限制,從頭開始一個(gè)新的程序。
C++運(yùn)行速度提升70%
AlphaDev發(fā)現(xiàn)新的排序算法,為L(zhǎng)LVM libc++排序庫(kù)帶來(lái)了明顯的改進(jìn)。 對(duì)于較短的序列,速度提高了70%,而對(duì)于超過(guò)250,000個(gè)元素的序列,速度只提高了約1.7%。 研究人員專注于改進(jìn)3-5個(gè)元素較短的序列排序算法。 這些算法是使用最廣泛的算法之一,因?yàn)樗鼈兘?jīng)常作為更大排序函數(shù)的一部分被多次調(diào)用。 改進(jìn)這些算法可以為任何數(shù)量的項(xiàng)目的排序提升整體的速度。
為了使新的排序算法為所有人可用,研究人員還將其進(jìn)行了逆向工程,并將其翻譯成「程序猿」最常用的一種編碼語(yǔ)言C++。 目前,這些算法現(xiàn)在可以在LLVM libc++標(biāo)準(zhǔn)排序庫(kù)中找到。
散列函數(shù)效率提升30%
在發(fā)現(xiàn)更快的排序算法之后,DeepMind測(cè)試了AlphaDev是否能夠推廣并改進(jìn)不同的計(jì)算機(jī)科學(xué)算法——散列(Hash)。 散列是計(jì)算中的一種基本算法,用于檢索、存儲(chǔ)和壓縮數(shù)據(jù)。就像圖書管理員使用分類系統(tǒng)來(lái)找到特定的書籍一樣,散列算法幫助用戶知道他們正在尋找的內(nèi)容以及確切的位置。 這些算法將特定的key(例如用戶姓名「Jane Doe」)進(jìn)行散列處理,也就是,將原始數(shù)據(jù)轉(zhuǎn)換為唯一的字符串(例如1234ghfty)。然后,計(jì)算機(jī)會(huì)使用這個(gè)散列值來(lái)快速檢索與鍵相關(guān)的數(shù)據(jù),而不是搜索所有數(shù)據(jù)。 結(jié)果顯示,當(dāng)應(yīng)用于散列函數(shù)的9到16字節(jié)范圍時(shí),AlphaDev發(fā)現(xiàn)的算法比傳統(tǒng)算法快30%。 現(xiàn)在,DeepMind也將新的散列算法發(fā)布到了開源的Abseil庫(kù)中。據(jù)了解,這個(gè)算法預(yù)計(jì)每天都會(huì)被使用數(shù)萬(wàn)億次。
兩種新策略:「swap move」和「copy move」
AlphaDev不僅發(fā)現(xiàn)了更快的算法,還發(fā)現(xiàn)了新的方法。 它的排序算法包含新的指令序列,每次應(yīng)用時(shí)都會(huì)保存一條指令。這可能會(huì)產(chǎn)生巨大的影響,因?yàn)檫@些算法每天被使用數(shù)萬(wàn)億次。 研究人員將其稱之為「AlphaDev swap move」和「AlphaDev copy move」。 最新方法讓人想起AlphaGo讓人震驚的「第37步」。 2016年那場(chǎng)人機(jī)大戰(zhàn)中,AlphaGo下了一顆違反人類直覺(jué)的棋,一個(gè)簡(jiǎn)單的肩沖,擊敗了傳奇圍棋選手李世石。 通過(guò)這兩種策略,AlphaDev跳過(guò)了一個(gè)步驟,以一種看起來(lái)錯(cuò)誤,但實(shí)際上是快捷方式連接項(xiàng)目。 這表明,AlphaDev有能力發(fā)現(xiàn)原創(chuàng)性解決方案,并挑戰(zhàn)了我們對(duì)如何改進(jìn)計(jì)算機(jī)科學(xué)算法的思考方式。 如下圖示例原始sort3實(shí)現(xiàn),有min(A, B, C),使用AlphaDev Swap Move,AlphaDev發(fā)現(xiàn),你只需要min(A, B)。
再比如,原始實(shí)現(xiàn)用max(B, min(A ,C, D))中較大的排序算法對(duì)8個(gè)元素進(jìn)行排序。 AlphaDev發(fā)現(xiàn)使用其「swap and copy moves」時(shí)只需要max(B, min(A, C))。
優(yōu)化全世界的代碼,一次一個(gè)算法
通過(guò)優(yōu)化和推出全球開發(fā)者使用的改進(jìn)排序和散列算法,AlphaDev證明了,它有能力概括和發(fā)現(xiàn)世界級(jí)的新算法。 Google DeepMind認(rèn)為,AlphaDev是朝著開發(fā)AGI工具邁出的一步,這些工具有助于優(yōu)化整個(gè)計(jì)算生態(tài)系統(tǒng),還能解決其他有益于社會(huì)的問(wèn)題。 不過(guò),研究人員也承認(rèn),目前AlphaDev在低級(jí)匯編指令優(yōu)化能力非常強(qiáng),但是隨著算法的發(fā)展也存在局限性。 為了讓開發(fā)者更可用,AlphaDev用高級(jí)語(yǔ)言(如C++)優(yōu)化算法的能力正在探索中。 AlphaDev的新發(fā)現(xiàn),如「AlphaDev swap move」和「AlphaDev copy move」,不僅表明它可以改進(jìn)算法,還可以找到新的解決方案。 研究人員希望,這些發(fā)現(xiàn)能激勵(lì)研究人員和開發(fā)人員創(chuàng)造技術(shù)和方法,進(jìn)一步優(yōu)化基礎(chǔ)算法,以創(chuàng)建一個(gè)更強(qiáng)大、更可持續(xù)的計(jì)算生態(tài)系統(tǒng)。
網(wǎng)友熱評(píng)
英偉達(dá)科學(xué)家Jim Fan對(duì)AlphaDev做了一個(gè)深度總結(jié): 排序算法是所有關(guān)鍵軟件的基礎(chǔ)。DeepMind的AlphaDev將小序列(3-5項(xiàng))的排序速度提高了70%。要點(diǎn): - 主要的RL算法是基于最初下圍棋Go、Chess & Shogi的AlphaZero。同樣的想法也適用于搜索程序! - 研究人員沒(méi)有對(duì)C代碼進(jìn)行優(yōu)化,而是對(duì)匯編代碼進(jìn)行優(yōu)化。這是一個(gè)刻意的選擇,去低級(jí)別的擠壓每一條指令的保存。 - 匯編代碼然后被逆向工程為C++,并在LLVM中開源。 - 即使表征網(wǎng)絡(luò)使用了Transformer,它也不是一個(gè)基礎(chǔ)模型。整個(gè)流程只適用于排序,對(duì)于其他任務(wù)如散列,必須重新訓(xùn)練。
在使用ML的算法發(fā)現(xiàn)方面取得了另一個(gè)重要的里程碑!
AlphaDev是DeepMind的一個(gè)改變游戲規(guī)則的人工智能,它創(chuàng)新了核心計(jì)算機(jī)科學(xué)算法。它正在重新構(gòu)想排序方法,短序列的速度可提高70%。甚至散列算法的發(fā)現(xiàn)速度提高了30%。強(qiáng)化學(xué)習(xí)正在重塑算法的格局!
還有網(wǎng)友稱,在我們對(duì)語(yǔ)言模型感到興奮之余,也不要忘記其他深度學(xué)習(xí)算法的成功故事:AlphaZero、AlphaFold,以及現(xiàn)在的AlphaDev。
參考資料: https://www.deepmind.com/blog/alphadev-discovers-faster-sorting-algorithms
-
谷歌
+關(guān)注
關(guān)注
27文章
6106瀏覽量
104839 -
算法
+關(guān)注
關(guān)注
23文章
4581瀏覽量
92379 -
DeepMind
+關(guān)注
關(guān)注
0文章
129瀏覽量
10803
原文標(biāo)題:谷歌DeepMind打破十年算法封印,AlphaDev驚世登場(chǎng),顛覆人類算法格局!
文章出處:【微信號(hào):TheAlgorithm,微信公眾號(hào):算法與數(shù)據(jù)結(jié)構(gòu)】歡迎添加關(guān)注!文章轉(zhuǎn)載請(qǐng)注明出處。
發(fā)布評(píng)論請(qǐng)先 登錄
相關(guān)推薦
評(píng)論