·排序算法是世界各地的計(jì)算機(jī)不斷使用的基本功能，雖然數(shù)十億人每天都在使用該算法，但沒(méi)有人意識(shí)到算法還存在優(yōu)化空間。Google DeepMind表示：“看起來(lái)，現(xiàn)在AI不僅可以幫人寫(xiě)代碼，而且可以幫我們寫(xiě)出更好的代碼?！?/em>

·“通過(guò)優(yōu)化和推出全球開(kāi)發(fā)人員使用的改進(jìn)排序和哈希算法，AlphaDev展示了其具有真實(shí)世界影響的泛化和發(fā)現(xiàn)新算法的能力。我們將AlphaDev視為發(fā)展通用人工智能工具的一步，這些工具可以幫助優(yōu)化整個(gè)計(jì)算生態(tài)系統(tǒng)，并解決其他有益于社會(huì)的問(wèn)題?！?/em>

(資料圖)

當(dāng)?shù)貢r(shí)間6月7日，最近剛剛合并而成的Google DeepMind宣布推出Alpha家族的新成員——AlphaDev，這是一種利用強(qiáng)化學(xué)習(xí)來(lái)改進(jìn)計(jì)算機(jī)科學(xué)算法的人工智能系統(tǒng)，其發(fā)現(xiàn)了一種速度更快的排序算法，被譽(yù)為打破了十年來(lái)的算法“封印”，并成為使用人工智能優(yōu)化代碼的重要里程碑。

Google DeepMind首席執(zhí)行官戴密斯·哈薩比斯（Demis Hassabis）在社交平臺(tái)上宣布：“AlphaDev發(fā)現(xiàn)了一種全新且更快的排序算法，我們已將其開(kāi)源到主要C++庫(kù)中供開(kāi)發(fā)人員使用。這只是AI提升代碼效率進(jìn)步的開(kāi)始。”

對(duì)于較短的序列，這一新算法可將排序庫(kù)速度提高70%，對(duì)于超過(guò)25萬(wàn)個(gè)數(shù)據(jù)的序列，速度也能提高約1.7%，超越了人類科學(xué)家和工程師幾十年來(lái)的精心打磨。從在線搜索結(jié)果、社交帖子，到計(jì)算機(jī)和手機(jī)數(shù)據(jù)處理方式，算法存在于互聯(lián)網(wǎng)的每一處，且每天都要執(zhí)行數(shù)萬(wàn)億次。利用AI生成更好的算法，將改變我們對(duì)計(jì)算機(jī)編程的方式，并影響我們數(shù)字化社會(huì)的方方面面。

該成果現(xiàn)已被納入LLVM標(biāo)準(zhǔn)C++庫(kù)Abseil并開(kāi)源，這是十多年來(lái)C++排序庫(kù)首次更改，也是通過(guò)強(qiáng)化學(xué)習(xí)設(shè)計(jì)的算法首次被添加到該庫(kù)中。相關(guān)研究論文以“Faster sorting algorithms discovered using deep reinforcement learning”為題，已發(fā)表在權(quán)威科學(xué)期刊《自然》（Nature）上。

Alpha家族新AI打破代碼瓶頸，數(shù)十億人使用的算法效率提高70%。

通過(guò)游戲找到提速算法最優(yōu)解

排序算法是世界各地計(jì)算機(jī)不斷使用的基本功能，雖然數(shù)十億人每天都在使用該算法，但沒(méi)有人意識(shí)到算法還存在優(yōu)化空間。Google DeepMind表示：“看起來(lái)，現(xiàn)在AI不僅可以幫人寫(xiě)代碼，而且可以幫我們寫(xiě)出更好的代碼?！?/p>

據(jù)介紹，AlphaDev基于AlphaZero強(qiáng)化學(xué)習(xí)模型構(gòu)建，其工作方式與AlphaZero相似，后者結(jié)合計(jì)算機(jī)推理和直覺(jué)，曾在圍棋、國(guó)際象棋等游戲中屢次擊敗世界冠軍。在棋盤(pán)游戲中，AlphaZero有能力選擇每一步的走法，不過(guò)AlphaDev只能選擇添加指令，并不會(huì)選擇下一步怎么走棋。

值得一提的是，DeepMind選擇了現(xiàn)在已很少見(jiàn)的匯編語(yǔ)言，這是C++等語(yǔ)言編寫(xiě)的代碼在運(yùn)行之前被翻譯成的語(yǔ)言，由計(jì)算機(jī)芯片處理。匯編的優(yōu)點(diǎn)是它允許將算法分解為更小的步驟，如果它要尋找更快的方法，這是一個(gè)很好的起點(diǎn)。

為了訓(xùn)練AlphaDev來(lái)發(fā)現(xiàn)新的算法，Google DeepMind將排序問(wèn)題轉(zhuǎn)化成了一個(gè)“匯編游戲”（Assembly Game）。在每一輪中，AlphaDev都需要觀察它生成的算法以及中央處理器（CPU）中包含的信息，并通過(guò)在算法中添加一條指令來(lái)進(jìn)行移動(dòng)。而這個(gè)匯編游戲非常困難，因?yàn)锳lphaDev必須有效地搜索大量可能的指令組合，從而找到一個(gè)可以排序且比當(dāng)前最佳算法更快的算法。

其中AlphaDev需要操作的“可能的指令組合”的數(shù)量，堪比宇宙中的粒子數(shù)量，或者國(guó)際象棋（10的120次方局）和圍棋（10的700次方局）中可能的走法組合數(shù)。更為嚴(yán)苛的是，任何一個(gè)錯(cuò)誤的移動(dòng)，都可能會(huì)使整個(gè)算法無(wú)效。DeepMind的突破在于將尋找更快算法的問(wèn)題視為一場(chǎng)游戲，然后讓它的人工智能贏得這場(chǎng)游戲，最后根據(jù)AlphaDev正確排序數(shù)字的能力以及完成排序的速度和效率給予獎(jiǎng)勵(lì)，而AlphaDev則需要通過(guò)發(fā)現(xiàn)一個(gè)正確且更快的程序來(lái)贏得游戲。如果AlphaDev的算法既正確又比現(xiàn)有算法快，那么它就贏了。

或可解決摩爾定律放緩問(wèn)題

排序算法使得LLVM libc++排序庫(kù)得到改進(jìn)：對(duì)于較短的序列，排序庫(kù)的速度提高了70%，對(duì)于超過(guò)25萬(wàn)個(gè)數(shù)據(jù)的序列，速度提高了約1.7%。

其中，Google DeepMind團(tuán)隊(duì)更專注于改進(jìn)3到5個(gè)元素的短序列排序算法。這些算法是使用最廣泛的算法之一，因?yàn)樗鼈兺ǔＷ鳛楦笈判蚝瘮?shù)的一部分被多次調(diào)用，改進(jìn)這些算法可以提高對(duì)任意數(shù)量項(xiàng)目進(jìn)行排序的整體速度。

而事實(shí)上，AlphaDev不僅發(fā)現(xiàn)了更快的算法，還發(fā)現(xiàn)了新的方法。它的排序算法包含新的指令序列，每次應(yīng)用時(shí)都會(huì)節(jié)省一條指令——這顯然會(huì)產(chǎn)生巨大的影響，因?yàn)檫@些算法每天都要使用數(shù)萬(wàn)億次。研究人員把這些稱為“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)人類對(duì)如何改進(jìn)計(jì)算機(jī)科學(xué)算法的思考方式。

“說(shuō)實(shí)話，我們沒(méi)有想到會(huì)取得更好的成績(jī)：這是一個(gè)非常短的程序，這些類型的程序已經(jīng)被研究了幾十年。”論文的第一作者、Google DeepMind的研究科學(xué)家丹尼爾·曼科維茨（Daniel Mankowitz）說(shuō)，“我們最初以為它犯了一個(gè)錯(cuò)誤，或者有一個(gè)bug或其他東西，但是，當(dāng)我們分析這個(gè)程序時(shí)，我們意識(shí)到AlphaDev實(shí)際上已經(jīng)發(fā)現(xiàn)了更快的東西?！?/p>

曼科維茨表示：“優(yōu)化每天被調(diào)用數(shù)萬(wàn)億次的基本函數(shù)的代碼，有望帶來(lái)足夠大的好處，鼓勵(lì)人們嘗試執(zhí)行更多這些函數(shù)，并將其作為解決摩爾定律放緩瓶頸的途徑之一?！?/p>

英國(guó)伯明翰大學(xué)教授馬克·李（Mark Lee）則認(rèn)為，AlphaDev很有意思，即使是1.7%的速度提升也很有用，但尚不能確定這種方法是否可以彌補(bǔ)摩爾定律的瓶頸，因?yàn)樗荒茉诟鼜?fù)雜的情況下取得同樣的收益。

哈希算法速度提高30%

在發(fā)現(xiàn)更快的排序算法后，團(tuán)隊(duì)測(cè)試了AlphaDev是否可以概括和改進(jìn)不同的計(jì)算機(jī)科學(xué)算法：哈希。

哈希是計(jì)算中用于檢索、存儲(chǔ)和壓縮數(shù)據(jù)的基本算法。就像使用分類系統(tǒng)來(lái)定位某本書(shū)的圖書(shū)管理員一樣，散列算法可以幫助用戶知道他們正在尋找什么以及在哪里可以找到它。這些算法獲取特定密鑰的數(shù)據(jù)（例如用戶名“Jane Doe”）并對(duì)其進(jìn)行哈希處理——這是一個(gè)將原始數(shù)據(jù)轉(zhuǎn)換為唯一字符串（例如1234ghfty）的過(guò)程。計(jì)算機(jī)使用此散列來(lái)快速檢索與密鑰相關(guān)的數(shù)據(jù)，而不是搜索所有數(shù)據(jù)。當(dāng)團(tuán)隊(duì)將AlphaDev應(yīng)用于散列函數(shù)的9-16字節(jié)范圍時(shí)，AlphaDev發(fā)現(xiàn)的算法速度提高了30%。

目前，Google DeepMind正在探索AlphaDev在C++等高級(jí)語(yǔ)言中直接優(yōu)化算法的能力，這對(duì)于開(kāi)發(fā)人員來(lái)說(shuō)將更加有用。

Google DeepMind在官方博客中寫(xiě)道：“通過(guò)優(yōu)化和推出全球開(kāi)發(fā)人員使用的改進(jìn)排序和哈希算法，AlphaDev展示了其具有真實(shí)世界影響的泛化和發(fā)現(xiàn)新算法的能力。我們將AlphaDev視為發(fā)展通用人工智能工具的一步，這些工具可以幫助優(yōu)化整個(gè)計(jì)算生態(tài)系統(tǒng)，并解決其他有益于社會(huì)的問(wèn)題?！?/p>

（原標(biāo)題：《用AI優(yōu)化代碼！Google DeepMind打破十年算法瓶頸》）