谷歌的人工智能研究實(shí)驗(yàn)室 DeepMind 通過其最新的 AI 系統(tǒng) AlphaDev，在計(jì)算機(jī)科學(xué)領(lǐng)域取得了一項(xiàng)重大成就。AlphaDev 是 AlphaZero 的一個專門版本，通過發(fā)現(xiàn)更快的排序和散列算法，為全球開發(fā)人員在數(shù)據(jù)排序、存儲和檢索方面提供了必不可少的處理過程，每天使用數(shù)萬億次。
DeepMind 在今天發(fā)表在科學(xué)雜志《自然》上的一篇論文中表示，與 C++庫中的算法相比，AlphaDev 的新算法在對短序列元素進(jìn)行排序時效率提高了 70%，對超過 250，000 個元素的序列提高了約 1.7%。因此，當(dāng)用戶提交搜索查詢時，AlphaDev 的算法可以更快地對結(jié)果進(jìn)行排序，從而在大規(guī)模應(yīng)用時節(jié)省大量時間和能源。
此外，該系統(tǒng)還發(fā)現(xiàn)了一種更快的散列算法，在數(shù)據(jù)中心中將哈希函數(shù)應(yīng)用于 9 到 16 字節(jié)范圍內(nèi)時，效率提高了 30%。
革新計(jì)算機(jī)科學(xué)
DeepMind 認(rèn)為這一重大成就將徹底改變計(jì)算機(jī)科學(xué)，并帶來效率和效果的提升。
DeepMind 的研究員表示：「AlphaDev 發(fā)現(xiàn)了改進(jìn)的排序算法，包括 AlphaDev 復(fù)制和交換移動等新穎創(chuàng)新?！顾€說：「類似于 AlphaGo 著名的『37 手』給圍棋這個古老游戲帶來了一套新的策略，AlphaDev 獨(dú)特的算法發(fā)現(xiàn)希望能激發(fā)出優(yōu)化基礎(chǔ)計(jì)算機(jī)科學(xué)算法的新視角和策略，并使其更快?！?/p>
Mankowitz 說，這是強(qiáng)化學(xué)習(xí)的一個重要里程碑，因?yàn)樗峁┝烁嘧C據(jù)證明其有能力做出新發(fā)現(xiàn)，尤其是在代碼優(yōu)化領(lǐng)域。
該公司還宣布打算通過 LLVM libc++標(biāo)準(zhǔn)排序庫將新算法提供給數(shù)百萬開發(fā)人員和各行各業(yè)的公司。值得注意的是，這次更新是排序庫這一部分十年來的首次修訂，也是通過強(qiáng)化學(xué)習(xí)開發(fā)的算法的首次納入。
Mankowitz 表示：「我們估計(jì)，我們公開發(fā)布的排序算法每天在全球被調(diào)用數(shù)萬億次，可以提供 2% 到 70% 的速度提升，這些算法可以為調(diào)用這些函數(shù)的開發(fā)人員和公司提供資源節(jié)省。我們相信這些算法將激發(fā)研究人員和實(shí)踐者開發(fā)出更多的新方法，從而發(fā)現(xiàn)新的和改進(jìn)的算法?！?/p>
利用強(qiáng)化學(xué)習(xí)增強(qiáng)傳統(tǒng)算法開發(fā)
DeepMind 表示，目前大多數(shù)計(jì)算算法已經(jīng)達(dá)到人類專家無法進(jìn)一步優(yōu)化的階段，導(dǎo)致了計(jì)算瓶頸的不斷加劇。該公司強(qiáng)調(diào)，使用深度強(qiáng)化學(xué)習(xí)可以通過生成精確高效的算法來增強(qiáng)開發(fā)方法。在進(jìn)行更有效的搜索和考慮準(zhǔn)確和快速程序的空間的同時，它通過優(yōu)化 CPU 指令級別的實(shí)際測量延遲來實(shí)現(xiàn)。
排序算法是系統(tǒng)地對項(xiàng)目按指定順序進(jìn)行排列的基礎(chǔ)。它們是計(jì)算機(jī)科學(xué)教育的基石。同樣，散列在數(shù)據(jù)存儲和檢索中有廣泛應(yīng)用，比如在客戶數(shù)據(jù)庫中。散列算法通常使用一個鍵（比如用戶名稱「Jane Doe」）生成與所需數(shù)據(jù)值（比如「訂單號 164335-87」）相對應(yīng)的唯一散列值，以便進(jìn)行檢索。類似于圖書管理員利用分類系統(tǒng)迅速找到特定書籍，散列系統(tǒng)使計(jì)算機(jī)能夠事先知道所需信息及其準(zhǔn)確位置。
雖然開發(fā)人員主要使用 C++等用戶友好的高級語言編寫代碼，但將這些語言轉(zhuǎn)化為低級匯編指令對于計(jì)算機(jī)理解來說是必不可少的。DeepMind 的研究人員認(rèn)為，在低級別存在許多改進(jìn)的空間，而在高級編程語言中揭示這些改進(jìn)可能面臨挑戰(zhàn)。匯編級別提供了計(jì)算機(jī)存儲和操作的靈活性，為能夠顯著影響速度和能源效率的改進(jìn)提供了巨大潛力。
為了在 C++中運(yùn)行算法，首先將其編譯成稱為匯編指令的低級 CPU 指令，這些指令在 CPU 上的內(nèi)存和寄存器之間操作數(shù)據(jù)。
Mankowitz 表示：「這提供了算法操作的更加細(xì)致的概述，因此更容易找到改進(jìn)算法的優(yōu)化方式。通過在匯編中進(jìn)行優(yōu)化，我們發(fā)現(xiàn)了 AlphaDev 復(fù)制和交換移動。這些是一系列匯編指令，當(dāng)應(yīng)用于一個匯編程序時，可以通過減少一個指令來減小程序的大小?！?/p>
DeepMind 發(fā)現(xiàn)更快算法的獨(dú)特方法
DeepMind 的 AlphaDev 采用了一種非常規(guī)的方法，通過探索人類鮮有涉足的計(jì)算機(jī)匯編指令領(lǐng)域，發(fā)現(xiàn)更快的算法。為了訓(xùn)練 AlphaDev 發(fā)現(xiàn)新算法，研究團(tuán)隊(duì)將排序重新構(gòu)想為「單人匯編游戲」。AlphaDev 利用強(qiáng)化學(xué)習(xí)觀察和生成算法，并結(jié)合 CPU 的信息。
在每一步中，AI 系統(tǒng)主動選擇一個指令并將其納入算法中，這是一個復(fù)雜且具有挑戰(zhàn)性的過程，因?yàn)闈撛诘闹噶罱M合數(shù)目龐大。
AlphaDev 逐步構(gòu)建算法的同時，還通過將算法的輸出與預(yù)期結(jié)果進(jìn)行比較來驗(yàn)證每一步的正確性。這種方法的最終目標(biāo)是發(fā)現(xiàn)一個正確且更快的程序，從而在游戲中取得勝利。
DeepMind 的 AI 系統(tǒng)發(fā)現(xiàn)了新穎的排序算法，使 LLVM libc++排序庫取得了顯著的改進(jìn)。研究主要集中在提高短序列的排序算法，這些算法通常被應(yīng)用于更大的排序函數(shù)中，提高它們的效率可以改善排序任意數(shù)量的項(xiàng)目時的整體速度。
為了提高可用性，DeepMind 對發(fā)現(xiàn)的算法進(jìn)行了逆向工程，并將其轉(zhuǎn)化為 C++代碼。
超越排序算法的領(lǐng)域
這些改進(jìn)主要針對對數(shù)字進(jìn)行排序的 sort3. sort4 和 sort5 程序。Mankowitz 解釋說：「每當(dāng)開發(fā)人員或應(yīng)用程序需要對這些數(shù)據(jù)類型進(jìn)行排序時，都可以調(diào)用我們的排序算法。根據(jù)要排序的項(xiàng)目數(shù)量，速度提升范圍在 2% 到 70% 之間。由于這些函數(shù)每天被調(diào)用數(shù)萬億次，開發(fā)人員和用戶將能夠在消耗更少資源的情況下運(yùn)行其應(yīng)用程序/使用各種服務(wù)。」
此外，AlphaDev 的能力超越了排序算法的領(lǐng)域。DeepMind 還探索了系統(tǒng)的潛力，將其方法泛化并改進(jìn)其他重要的計(jì)算機(jī)科學(xué)算法，包括散列算法。將 AlphaDev 的方法應(yīng)用于 9 到 16 字節(jié)范圍內(nèi)的散列算法，其速度提高了 30%。
DeepMind 表示，AlphaDev 是朝著創(chuàng)建能夠優(yōu)化整個計(jì)算生態(tài)系統(tǒng)并應(yīng)對各種社會挑戰(zhàn)的多功能 AI 工具的進(jìn)展中的重要里程碑。盡管優(yōu)化低級匯編指令已經(jīng)顯示出巨大的威力，但該公司表示，他們正在積極探索 AlphaDev 直接優(yōu)化高級語言（如 C++）中的算法的潛力，這對開發(fā)人員來說將更加有價值。他們還在嘗試優(yōu)化在運(yùn)行應(yīng)用程序和服務(wù)時更有效地調(diào)度資源，例如優(yōu)化 YouTube 的視頻壓縮流程以及優(yōu)化系統(tǒng)和應(yīng)用程序運(yùn)行的底層硬件。
Mankowitz 表示：「我們希望這些算法能夠?yàn)檠芯咳藛T和實(shí)踐者提供一種不同的視角，看待如何構(gòu)建算法?！?/p>
