計(jì)算的基礎(chǔ)就此改變了。
「通過(guò)交換和復(fù)制移動(dòng)，AlphaDev 跳過(guò)了一個(gè)步驟，以一種看似錯(cuò)誤，但實(shí)際上是捷徑的方式連接項(xiàng)目。」這種前所未見(jiàn)、違反直覺(jué)的思想不禁讓人回憶起 2016 年那個(gè)春天。
七年前，AlphaGo 在圍棋上擊敗人類(lèi)世界冠軍，如今 AI 又在編程上給我們上了一課。
今天凌晨，google DeepMind CEO 哈薩比斯的兩句話(huà)引爆了計(jì)算機(jī)領(lǐng)域：「AlphaDev 發(fā)現(xiàn)了一種全新且更快的排序算法，我們已將其開(kāi)源到主要 C++ 庫(kù)中供開(kāi)發(fā)人員使用。這只是 AI 提升代碼效率進(jìn)步的開(kāi)始。」
這一次，Google DeepMind 的全新強(qiáng)化學(xué)習(xí)系統(tǒng) AlphaDev 發(fā)現(xiàn)了一種比以往更快的哈希算法，這是計(jì)算機(jī)科學(xué)領(lǐng)域中的一種基本算法，AI 的成果現(xiàn)已被納入 LLVM 標(biāo)準(zhǔn) C++ 庫(kù) Abseil 并開(kāi)源。
這個(gè)成果有多重要？AlphaDev 的主要作者之一，Google DeepMind 研究科學(xué)家 Daniel J. Mankowitz 表示：「我們估計(jì)它發(fā)現(xiàn)的排序和哈希算法每天會(huì)在全世界被調(diào)用數(shù)萬(wàn)億次。」
AI 似乎從算法層面加速了世界的運(yùn)轉(zhuǎn)。
這些算法改進(jìn)了 LLVM libc++ 排序庫(kù)，對(duì)于較短的序列，排序庫(kù)的速度提高了 70%，對(duì)于超過(guò) 25 萬(wàn)個(gè)元素的序列，速度也能提高約 1.7%。Google DeepMind 表示，這是十多年來(lái)排序庫(kù)這部分的第一次變化。看起來(lái)，現(xiàn)在 AI 不僅可以幫人寫(xiě)代碼，而且可以幫我們寫(xiě)出更好的代碼。
在最新的博客中，新系統(tǒng)的作者們對(duì) AlphaDev 進(jìn)行了詳細(xì)介紹。
新的算法將改變計(jì)算基礎(chǔ)
數(shù)字社會(huì)推動(dòng)了對(duì)計(jì)算和能源日益增長(zhǎng)的需求。過(guò)去五十年里，數(shù)字時(shí)代依靠硬件的改進(jìn)來(lái)跟上需求。但是隨著微芯片接近其物理極限，改進(jìn)在其上運(yùn)行的代碼變得至關(guān)重要。對(duì)于每天運(yùn)行數(shù)萬(wàn)億次的代碼所包含的算法來(lái)說(shuō)，這尤其重要。
Google DeepMind 的這項(xiàng)研究就是因此產(chǎn)生的，相關(guān)論文已發(fā)表在《Nature》上，AlphaDev 是一個(gè) AI 系統(tǒng)，它使用強(qiáng)化學(xué)習(xí)來(lái)發(fā)現(xiàn)算法，甚至超越了科學(xué)家和工程師們幾十年來(lái)打磨出來(lái)的成果。
總體來(lái)說(shuō)，AlphaDev 發(fā)現(xiàn)了一種更快的排序算法。雖然數(shù)十億人每天都在使用這些算法，但卻沒(méi)有人意識(shí)到這一算法還存在優(yōu)化空間。排序算法應(yīng)用范圍廣泛，從在線(xiàn)搜索結(jié)果、社交帖子排序，到計(jì)算機(jī)以及手機(jī)上的各種數(shù)據(jù)處理，都離不開(kāi)排序算法。利用 AI 生成更好的算法將改變?nèi)祟?lèi)編程計(jì)算機(jī)的方式，對(duì)日益數(shù)字化的社會(huì)將產(chǎn)生重大影響。
通過(guò)在主要的 C++ 庫(kù)中開(kāi)源新排序算法，全球數(shù)百萬(wàn)開(kāi)發(fā)人員和公司現(xiàn)在可以在云計(jì)算、在線(xiàn)購(gòu)物和供應(yīng)鏈管理等各行各業(yè)的人工智能應(yīng)用中使用它。這是十多年來(lái)對(duì)排序庫(kù)的首次更改，也是通過(guò)強(qiáng)化學(xué)習(xí)設(shè)計(jì)的算法首次被添加到該庫(kù)中。這將這視為使用人工智能逐步優(yōu)化世界代碼的重要里程碑。
關(guān)于排序
排序算法是一種按照特定順序?qū)δ承┤蝿?wù)進(jìn)行排列的方法。例如，按字母先后順序排列三個(gè)字母，從大到小排列五個(gè)數(shù)字，或者對(duì)數(shù)百萬(wàn)條記錄的數(shù)據(jù)庫(kù)進(jìn)行排序。
這種算法由來(lái)已久，并得到了很好的演進(jìn)。其中關(guān)于排序的最早一個(gè)示例可追溯到公元 2 世紀(jì)和 3 世紀(jì)，當(dāng)時(shí)學(xué)者們?cè)趤啔v山大圖書(shū)館的書(shū)架上手工按字母順序排列了數(shù)千本書(shū)。隨著工業(yè)革命的到來(lái)，出現(xiàn)了可以幫助人們進(jìn)行排序的機(jī)器，其中制表機(jī)使用打孔卡片存儲(chǔ)信息，這些卡片被用于收集美國(guó) 1890 年的人口普查結(jié)果。
隨著上世紀(jì) 50 年代商用計(jì)算機(jī)的興起，最早用于排序算法的計(jì)算機(jī)科學(xué)算法開(kāi)始發(fā)展。如今，在全球的代碼庫(kù)中有許多不同的排序技術(shù)和算法被用于處理海量的在線(xiàn)數(shù)據(jù)。
將一系列未排序的數(shù)字輸入到算法中，輸出已排序的數(shù)字。
經(jīng)過(guò)計(jì)算機(jī)科學(xué)家和程序員們幾十年的研究，目前的排序算法已經(jīng)非常高效，以至于很難再實(shí)現(xiàn)進(jìn)一步的改進(jìn)，這有點(diǎn)類(lèi)似于試圖找到一種新的節(jié)省電力或更高效的數(shù)學(xué)方法，而這些算法也是計(jì)算機(jī)科學(xué)的基石。
探索新算法：匯編指令
AlphaDev 從頭開(kāi)始探索更快的算法，而不是基于現(xiàn)有算法之上，除此以外，AlphaDev 還能用于尋找大多數(shù)人所不涉足的領(lǐng)域：計(jì)算機(jī)匯編指令。
匯編指令可用于創(chuàng)建計(jì)算機(jī)執(zhí)行的二進(jìn)制代碼。開(kāi)發(fā)人員使用諸如 C++ 之類(lèi)的高級(jí)語(yǔ)言編寫(xiě)代碼，但必須將其轉(zhuǎn)換為計(jì)算機(jī)能夠理解的「低級(jí)」匯編指令。
Google DeepMind 認(rèn)為這個(gè)層次存在許多改進(jìn)的空間，而這些改進(jìn)在更高級(jí)的編程語(yǔ)言中可能很難被發(fā)現(xiàn)。在這個(gè)層次上，計(jì)算機(jī)的存儲(chǔ)和操作更加靈活，這意味著存在更多潛在的改進(jìn)可能性，這些改進(jìn)可能對(duì)速度和能源使用產(chǎn)生更大的影響。
代碼通常是用高級(jí)編程語(yǔ)言（如 C++）編寫(xiě)的。然后，編譯器將其轉(zhuǎn)換為低級(jí) CPU 指令，稱(chēng)為匯編指令。匯編器將匯編指令轉(zhuǎn)換為可執(zhí)行的機(jī)器碼，以便計(jì)算機(jī)可以運(yùn)行。
圖 A：C++ 算法示例，該算法可對(duì)最多兩個(gè)元素進(jìn)行排序；圖 B：相應(yīng)的匯編表示形式。
用 AlphaGo 的方法尋找最佳算法
AlphaDev 基于 Google DeepMind 此前的一項(xiàng)成果：在圍棋、國(guó)際象棋和象棋等游戲中打敗世界冠軍的強(qiáng)化學(xué)習(xí)模型 AlphaZero。而 AlphaDev 展示了這個(gè)模型如何從游戲轉(zhuǎn)移到科學(xué)挑戰(zhàn)，以及從模擬到現(xiàn)實(shí)世界的應(yīng)用。
為了訓(xùn)練 AlphaDev 發(fā)現(xiàn)新的算法，團(tuán)隊(duì)將排序變成了一個(gè)單人的「組裝游戲」。在每個(gè)回合中，AlphaDev 觀察它所產(chǎn)生的算法和 CPU 中包含的信息，然后通過(guò)選擇一條指令添加到算法中來(lái)下一步棋。
匯編游戲是非常困難的，因?yàn)?AlphaDev 必須在大量可能的指令組合中進(jìn)行高效搜索，以找到一個(gè)可以排序的算法，并且比當(dāng)前的最佳算法更快。指令的可能組合數(shù)量類(lèi)似于宇宙中的粒子數(shù)量，或者國(guó)際象棋（10^120 局）和圍棋（10^700 局）中可能的動(dòng)作組合的數(shù)量，而一個(gè)錯(cuò)誤的動(dòng)作就可以使整個(gè)算法失效。
圖 A：組裝游戲。玩家 AlphaDev 接收系統(tǒng) st 的狀態(tài)作為輸入，并通過(guò)選擇一條匯編指令添加到目前已生成的算法中來(lái)下棋。圖 B：獎(jiǎng)勵(lì)計(jì)算。每次移動(dòng)后，生成的算法都會(huì)輸入測(cè)試輸入序列 —— 對(duì)于 sort3，這對(duì)應(yīng)于三個(gè)元素序列的所有組合。該算法然后生成一個(gè)輸出，將其與排序情況下排序序列的預(yù)期輸出進(jìn)行比較。智能體根據(jù)算法的正確性和延遲獲得獎(jiǎng)勵(lì)。
在構(gòu)建算法時(shí)，對(duì)于每次的一條指令，AlphaDev 通過(guò)將算法的輸出與預(yù)期結(jié)果進(jìn)行比較來(lái)檢查它是否正確。對(duì)于排序算法，這意味著無(wú)序數(shù)字進(jìn)入，正確排序的數(shù)字出來(lái)。團(tuán)隊(duì)會(huì)獎(jiǎng)勵(lì) AlphaDev 對(duì)數(shù)字的正確排序以及排序的速度和效率，然后 AlphaDev 通過(guò)發(fā)現(xiàn)正確、更快的程序來(lái)贏得比賽。
它發(fā)現(xiàn)了更快的排序算法
AlphaDev 發(fā)現(xiàn)了新的排序算法，這些算法導(dǎo)致 LLVM libc++ 排序庫(kù)得到改進(jìn)：對(duì)于較短的序列，排序庫(kù)的速度提高了 70%，對(duì)于超過(guò) 25 萬(wàn)個(gè)元素的序列，速度提高了約 1.7%。
其中，Google DeepMind 團(tuán)隊(duì)更專(zhuān)注于改進(jìn)三到五個(gè)元素的短序列排序算法。這些算法是使用最廣泛的算法之一，因?yàn)樗鼈兺ǔＷ鳛楦笈判蚝瘮?shù)的一部分被多次調(diào)用，改進(jìn)這些算法可以提高對(duì)任意數(shù)量項(xiàng)目進(jìn)行排序的整體速度。
為了讓新的排序算法對(duì)人們更有用，團(tuán)隊(duì)對(duì)算法進(jìn)行了逆向工程并將它們翻譯成 C++，這是開(kāi)發(fā)人員使用的最流行的編程語(yǔ)言之一。
目前，這些算法已在 LLVM libc++ 標(biāo)準(zhǔn)排序庫(kù)（
https://reviews.llvm.org/D118029）中提供，被全球數(shù)百萬(wàn)開(kāi)發(fā)人員和公司使用。
「交換和復(fù)制動(dòng)作」，神之一手重現(xiàn)？
事實(shí)上，AlphaDev 不僅發(fā)現(xiàn)了更快的算法，而且還發(fā)現(xiàn)了新的方法。它的排序算法包含新的指令序列，每次應(yīng)用時(shí)都會(huì)節(jié)省一條指令 —— 這顯然會(huì)產(chǎn)生巨大的影響，因?yàn)檫@些算法每天都要使用數(shù)萬(wàn)億次。他們把這些稱(chēng)為「AlphaDev 交換和復(fù)制動(dòng)作」。
這種新穎的方法讓人聯(lián)想到 AlphaGo 的「第 37 步」—— 當(dāng)時(shí)這這種反直覺(jué)的下法讓圍觀者目瞪口呆，并導(dǎo)致李世石這位傳奇圍棋選手被打敗。通過(guò)交換和復(fù)制動(dòng)作，AlphaDev 跳過(guò)了一個(gè)步驟，以一種看起來(lái)像錯(cuò)誤但實(shí)際上是捷徑的方式連接項(xiàng)目。這表明 AlphaDev 有能力發(fā)掘出原創(chuàng)性的解決方案，并挑戰(zhàn)人類(lèi)對(duì)如何改進(jìn)計(jì)算機(jī)科學(xué)算法的思考方式。
左圖：min (A,B,C) 原始的 sort3 實(shí)現(xiàn)；右圖：AlphaDev 交換移動(dòng) ——AlphaDev 發(fā)現(xiàn)你只需要 min (A,B)。
左圖：在一個(gè)更大的排序算法中使用 max（B，min（A，C，D））的原始實(shí)現(xiàn)，用于排序八個(gè)元素；右圖：AlphaDev 發(fā)現(xiàn)，使用其復(fù)制動(dòng)作時(shí)，只需要 max（B，min（A，C））。
擴(kuò)展能力測(cè)驗(yàn)：從「排序」到「哈希」
在發(fā)現(xiàn)更快的排序算法后，團(tuán)隊(duì)測(cè)試了 AlphaDev 是否可以概括和改進(jìn)不同的計(jì)算機(jī)科學(xué)算法：哈希。
哈希是計(jì)算中用于檢索、存儲(chǔ)和壓縮數(shù)據(jù)的基本算法。就像使用分類(lèi)系統(tǒng)來(lái)定位某本書(shū)的圖書(shū)管理員一樣，哈希算法可以幫助用戶(hù)知道他們正在尋找什么以及在哪里可以找到它。這些算法獲取特定密鑰的數(shù)據(jù)（例如用戶(hù)名 “Jane Doe”）并對(duì)其進(jìn)行哈希處理 —— 這是一個(gè)將原始數(shù)據(jù)轉(zhuǎn)換為唯一字符串（例如 1234ghfty）的過(guò)程。計(jì)算機(jī)使用此哈希來(lái)快速檢索與密鑰相關(guān)的數(shù)據(jù)，而不是搜索所有數(shù)據(jù)。
團(tuán)隊(duì)將 AlphaDev 應(yīng)用于數(shù)據(jù)結(jié)構(gòu)中最常用的哈希算法之一，嘗試發(fā)現(xiàn)更快的算法。當(dāng)將其應(yīng)用于 9-16 字節(jié)范圍的哈希函數(shù)時(shí)，AlphaDev 發(fā)現(xiàn)的算法速度提高了 30%。
今年，AlphaDev 的新哈希算法已被發(fā)布到開(kāi)源 Abseil 庫(kù)中，可供全球數(shù)百萬(wàn)開(kāi)發(fā)人員使用，它現(xiàn)在大概每天被使用數(shù)萬(wàn)億次。
開(kāi)源地址：
https://Github.com/abseil/abseil-cpp/commit/74eee2aff683cc7dcd2dbaa69b2c654596d8024e
結(jié)語(yǔ)
Google DeepMind 通過(guò)優(yōu)化和推出改進(jìn)的排序和哈希算法，供世界各地的開(kāi)發(fā)人員使用，AlphaDev 展示了其概括和發(fā)現(xiàn)具有現(xiàn)實(shí)影響的新算法的能力。AlphaDev 可被視為開(kāi)發(fā)通用 AI 工具的一步，它可以幫助優(yōu)化整個(gè)計(jì)算生態(tài)系統(tǒng)并解決其他造福社會(huì)的問(wèn)題。
雖然在低級(jí)匯編指令空間中進(jìn)行優(yōu)化非常強(qiáng)大，但隨著算法的增長(zhǎng)， AlphaDev 仍存在局限性，團(tuán)隊(duì)目前正在探索其直接在高級(jí)語(yǔ)言（如 C++）中優(yōu)化算法的能力，這對(duì)開(kāi)發(fā)人員來(lái)說(shuō)更加有用。
AlphaDev 的發(fā)現(xiàn)，例如交換和復(fù)制動(dòng)作，不僅表明它可以改進(jìn)算法，還可以找到新的解決方案。這些發(fā)現(xiàn)或許能夠激勵(lì)研究人員和開(kāi)發(fā)人員創(chuàng)建可以進(jìn)一步優(yōu)化基礎(chǔ)算法的技術(shù)和方法，以創(chuàng)建更強(qiáng)大和可持續(xù)的計(jì)算生態(tài)系統(tǒng)。
參考內(nèi)容：
https://www.deepmind.com/blog/alphadev-discovers-faster-sorting-algorithms?utm_source=Twitter&utm_medium=social&utm_campaign=OCS
https://news.ycombinator.com/item?id=36228125
https://twitter.com/DJ_Mankowitz/status/1666468646863130631
