北大團(tuán)隊(duì)搞定ChatGPT都頭痛的算法優(yōu)化，普通筆電就能跑

衡宇 蕭簫 發(fā)自 凹非寺

量子位 | 公眾號(hào) QbitAI

連ChatGPT看了都直搖頭的算法優(yōu)化，被北大團(tuán)隊(duì)給搞定了。

測試表明，新研究能解驗(yàn)證集中90%的題目，包括NOIP、Codeforce、Leetcode等比賽中的分治和動(dòng)態(tài)規(guī)劃題目——這些題目，很多大模型也難以解決。

而且自家的普通筆電就能跑！

畢竟算法優(yōu)化這塊，是大模型乃至整個(gè)AI的能力盲區(qū)。

哪怕是Nature刊發(fā)過的DeepMind AlphaTensor，給程序合成領(lǐng)域帶來一些震撼不假，但實(shí)際作用對業(yè)內(nèi)專業(yè)人士來說，“還是不夠”。

所以，AI無法橫掃到的這個(gè)領(lǐng)域，算法優(yōu)化該咋提速提效？

北大一支團(tuán)隊(duì)，采取程序演算和程序枚舉相結(jié)合的辦法，做出了兩套算法優(yōu)化軟件。

一套可以搞定分治、并行化、增量計(jì)算、線段樹等算法的優(yōu)化，另一套則支持動(dòng)態(tài)規(guī)劃算法的優(yōu)化。

介紹動(dòng)態(tài)規(guī)劃算法的綜合方法一篇（《Synthesizing Efficient Memoization Algorithms 》），已經(jīng)被程序設(shè)計(jì)語言領(lǐng)域三大頂會(huì)之一的OOPSLA’23接收；另一篇關(guān)于分治類算法的論文也已經(jīng)在arXiv（2202.12193）公開。

而且這兩套軟件需要的硬件門檻并不高，Intel Core i7-8700 3.2GHz 6核處理器就能跑，平均用時(shí)6.53s。

據(jù)悉，這兩套軟件未來都會(huì)開源，還會(huì)做成更易用的服務(wù)，放到網(wǎng)上。

有些神奇的事是，兩篇論文共同的作者之一，北大副教授熊英飛，之前一度專研在AI領(lǐng)域，首次用CNN實(shí)現(xiàn)爐石傳說的代碼，就出自他之手。

帶著好奇，我們和熊英飛本人聊了聊。

為什么AI設(shè)計(jì)算法還不行？

算法設(shè)計(jì)，需要給出滿足規(guī)約的程序，并且在時(shí)間和空間復(fù)雜度上盡量優(yōu)化。

大模型的進(jìn)展有目共睹，因此，在“轉(zhuǎn)向”之前，熊英飛和團(tuán)隊(duì)確實(shí)也想過用ChatGPT來搞算法設(shè)計(jì)。

（包括Copilot等代碼補(bǔ)全和其他AI技術(shù)在內(nèi)，他們將所有會(huì)寫程序的AI都試了一遍，感覺ChatGPT最好用）

但即使是ChatGPT，在搞算法設(shè)計(jì)時(shí)也還是會(huì)出bug。

例如，將一些經(jīng)典任務(wù)交給ChatGPT，它能很好地完成，如求解一個(gè)背包問題；但一旦對經(jīng)典問題進(jìn)行小改動(dòng)，比如讓物品重量和價(jià)值從其他屬性組合得到，它輸出的代碼就會(huì)“一團(tuán)亂”，完全沒法用。

其關(guān)鍵原因，在于算法設(shè)計(jì)需要在程序語法語義、算法設(shè)計(jì)模式、算法復(fù)雜度分析等一系列專業(yè)知識(shí)的基礎(chǔ)上，進(jìn)行嚴(yán)密的邏輯推理。

現(xiàn)在，大模型主要在大量程序上做訓(xùn)練，很難僅靠訓(xùn)練就重新發(fā)現(xiàn)這些人類頂尖科學(xué)家研究了數(shù)十年的知識(shí)。

同時(shí)，雖然大模型具有少量分析能力，但要進(jìn)行復(fù)雜和嚴(yán)謹(jǐn)?shù)倪壿嬐评恚诂F(xiàn)在的神經(jīng)網(wǎng)絡(luò)架構(gòu)下還存在困難。

這樣寫出來的代碼，“即使跑得通，公司也不敢用”，因?yàn)樾辀ug的成本可能比寫bug還高（手動(dòng)狗頭）。

所以，有沒有什么方法可以解決這個(gè)問題？

熊英飛表示，團(tuán)隊(duì)其實(shí)兩種思路都在嘗試，包括“用AI”和“不用AI”的。

一方面，他們訓(xùn)練了一個(gè)幾億參數(shù)的小模型，也在嘗試使用AI來生成代碼，同時(shí)也在思考AI和常規(guī)方法結(jié)合的來保證代碼正確性的途徑；

另一方面，團(tuán)隊(duì)也嘗試將之前業(yè)界已有的兩種方法結(jié)合起來，結(jié)果發(fā)現(xiàn)效果不僅比現(xiàn)在的AI方法更好，而且速度上也要更快。

所以，這種神奇的新思路究竟是什么？

先“找規(guī)律”，再“暴力窮舉”

具體來說，熊英飛團(tuán)隊(duì)采用的新思路，結(jié)合了程序演算和程序枚舉兩種方法。

程序演算方法，簡單來說就是“找規(guī)律”。

目前針對算法，已經(jīng)有人總結(jié)出了許多不同的設(shè)計(jì)模式，有點(diǎn)像是一套代碼設(shè)計(jì)經(jīng)驗(yàn)的總結(jié)。

設(shè)計(jì)模式包含了許多算法優(yōu)化相關(guān)的程序變換規(guī)則，類比到解方程中，就是左右加減移項(xiàng)、以及兩邊同乘同除等技巧。

算法優(yōu)化也和解方程一樣，雖然我們能學(xué)會(huì)不同的變換規(guī)則，但真正到了解決復(fù)雜問題的時(shí)候，還是得自己運(yùn)用這套規(guī)則來對程序求解。

這種方法就和做數(shù)學(xué)題一樣，需要用到一些“程序員的智慧”。但如果程序員想不到更好的解決方法怎么辦呢？

因此，除了程序演算，此前還有一種思路是程序枚舉，顧名思義就是“暴力窮舉”。

這種方法就是讓電腦去試所有可能的程序，經(jīng)過驗(yàn)證后，總有一個(gè)程序是對的。例如給變量x和y，計(jì)算機(jī)就會(huì)嘗試x+y，x-y……

但這種方法同樣存在一個(gè)問題，就是雖然計(jì)算機(jī)很快，但世界上所有的程序太多了，而且基本上隨著程序長度增加呈指數(shù)型增長。

因此，直接暴力窮舉，對于計(jì)算機(jī)來說同樣是不可能的。

為此，熊英飛團(tuán)隊(duì)結(jié)合這兩種思路，設(shè)計(jì)了一種新的算法優(yōu)化方法。

簡單來說，就是先基于程序演算的思路，將問題縮小到只需要用程序去填寫幾個(gè)關(guān)鍵程序的情況，就像給“完形填空”挖空一樣。

然后，用窮舉法列舉需要“填空”的程序，最終驗(yàn)證得到結(jié)果。

當(dāng)然，這里面也用到了一些近似的技術(shù)，因?yàn)槔碚撋?，形式化?guī)約無法完全和需要“填空”的部分對應(yīng)起來，要填空的地方肯定也和其他地方有條件關(guān)系。

因此針對這種問題，團(tuán)隊(duì)也設(shè)計(jì)了一些技巧，確保在一定概率下這種方式不會(huì)出錯(cuò)。

相比AI而言，這種思路設(shè)計(jì)出來的算法優(yōu)化軟件，不僅正確率更高，解題過程也要更快。

目前，團(tuán)隊(duì)設(shè)計(jì)出了兩套算法優(yōu)化軟件AutoLifter和SynMem。

其中AutoLifter支持分治、并行化、增量計(jì)算、單通道、流算法、線段樹等算法的優(yōu)化，SynMem則支持動(dòng)態(tài)規(guī)劃算法的優(yōu)化。

所以，這兩套算法優(yōu)化軟件的效果究竟如何？

團(tuán)隊(duì)從Codeforces、NOIP全國青少年信息學(xué)奧林匹克聯(lián)賽、Leetcode上收集了所支持算法對應(yīng)的題目，對兩套方法進(jìn)行了測試

其中，在分治類的96個(gè)算法問題中，AutoLifter解出來了82題，相比之下另兩種此前最好的程序合成方法，只解出來不到一半。

硬件要求也不高，只需要Intel Core i7-8700 3.2GHz 6核處理器就能跑，平均用時(shí)在6.53秒左右。

在40道動(dòng)態(tài)規(guī)劃題目上，團(tuán)隊(duì)解出來了37道，而且平均用時(shí)僅僅1.87秒?（相比之下另外兩種方法幾乎沒有解出來多少）：

這兩套軟件，團(tuán)隊(duì)在未來都會(huì)開源，也會(huì)做成更方便使用的服務(wù)放到網(wǎng)上。

熊英飛表示，最終的目標(biāo)是希望做出一套軟件，能自動(dòng)檢測到代碼中需要優(yōu)化的算法，然后軟件自動(dòng)將它們優(yōu)化起來。

以App為例，即使啥都不做，用上這套算法后，對應(yīng)的APP運(yùn)行速度也能大幅增加。

當(dāng)然，達(dá)成這一目標(biāo)，可能還需要一段時(shí)間。

“發(fā)Nature耽誤拿獎(jiǎng)學(xué)金了”

AutoLifter這項(xiàng)工作背后的論文，是熊英飛團(tuán)隊(duì)3年前就開始的算法合成項(xiàng)目，完成的第一篇論文。

熊英飛給出的原因是之前的方法堪稱“理論大合集”，不僅有程序合成，還加上了程序演算、范疇論、概率論、隨機(jī)算法……總之，整篇論文充滿了數(shù)學(xué)符號(hào)。

“這樣一來，要找到合適的審稿人比較難?！毙苡w表示，2年間刪刪改改，現(xiàn)在論文已經(jīng)是一個(gè)“不依賴于特定領(lǐng)域的符號(hào)，基本大家都能讀懂的樣子了”。

交流期間，量子位問了句題外話，AlphaTensor能發(fā)Nature，咱們的論文2年沒被頂會(huì)接收，沒考慮過投投Nature？

熊老師開玩笑地回應(yīng)道：

我也勸我的博士生，不要跟程序設(shè)計(jì)頂會(huì)較勁，發(fā)篇Nature影響多大?。≡囍兑幌乱膊粫?huì)掉塊肉。

你知道他們怎么說？“不行，我要趕緊（在專業(yè)領(lǐng)域）發(fā)出來，不然明年獎(jiǎng)學(xué)金沒了！”

玩笑歸玩笑，言歸正傳，介紹一下AutoLifter和SynMem兩項(xiàng)工作的論文一作，兩位都是算法競賽圈的知名選手。

吉如一，AutoLifter工作論文一作。

北京大學(xué)編程語言實(shí)驗(yàn)室（PLL）博四在讀，研究方向是程序合成，導(dǎo)師為胡振江和熊英飛。

2016年，吉如一以全國青少年信息學(xué)奧林匹克競賽金牌獲得者保送北大信息科學(xué)與技術(shù)學(xué)院，后成為北大第一屆圖靈班的一員。

曾擔(dān)任ACM大賽北大隊(duì)隊(duì)長，第二次參賽時(shí)帶隊(duì)獲得金牌和全球第三、亞洲第一的成績。同時(shí)也是北京大學(xué)學(xué)生算法協(xié)會(huì)的創(chuàng)始人和第一任主席，人送外號(hào)“吉老師”。

孫奕燦，SynMem一作。

北京大學(xué)編程語言實(shí)驗(yàn)室（PLL）博三在讀，指導(dǎo)教師為熊英飛。

他同樣是全國青少年信息學(xué)奧林匹克競賽金牌保送北京大學(xué)。

他的研究方向?yàn)槌绦蚝铣?、決策過程和概率程序驗(yàn)證，也做過一些關(guān)于參數(shù)化復(fù)雜度制度下的不可近似性的工作。

本科時(shí)，他就讀于北京大學(xué)EECS學(xué)院圖靈班。他曾以共同一作的身份在編程語言的頂級會(huì)議PLDI上發(fā)表論文，并且有其它工作發(fā)表在編程語言頂級會(huì)議OOPSLA和人工智能頂級會(huì)議AAAI上。

兩篇論文的共同作者熊英飛，是上述二人的博士指導(dǎo)老師。

他的身份是北大信息科學(xué)技術(shù)學(xué)院軟件工程研究所長聘副教授、研究員，分別在電子科技大學(xué)、北京大學(xué)、日本東京大學(xué)獲得本碩博學(xué)位。

除了本文提到的程序合成，熊英飛的主要研究方向之一就還有缺陷修復(fù)領(lǐng)域，這也是他和所在組長期以來做的一項(xiàng)工作。

缺陷修復(fù)，俗稱修bug，他做的工作還是自動(dòng)修bug。

具體而言就是先讀程序，分析出程序有哪些地方需要改，然后想出一個(gè)新的程序的寫法。

熊英飛和團(tuán)隊(duì)提出的理論、方法和技術(shù)中，基于差別的修復(fù)模型已經(jīng)成為演化缺陷領(lǐng)域廣泛使用的模型之一，而基于統(tǒng)計(jì)的缺陷修復(fù)技術(shù)將程序缺陷修復(fù)的準(zhǔn)確率提升約40%。

采用他們工作的公司，包括華為、Linux內(nèi)核配置項(xiàng)目等。

之所以能達(dá)到這樣的效果，熊英飛介紹道，是因?yàn)閳F(tuán)隊(duì)是最早把概率引導(dǎo)傳統(tǒng)程序合成中的研究隊(duì)伍之一。

這項(xiàng)發(fā)表在2017年的工作，通過統(tǒng)計(jì)引導(dǎo)程序合成，把缺陷修復(fù)正確率最高水平從40%拉到了70%。

有意思的是，此后許多研究機(jī)構(gòu)都開始從概率統(tǒng)計(jì)和傳統(tǒng)機(jī)器學(xué)習(xí)下手研究程序合成，但那時(shí)的熊英飛團(tuán)隊(duì)，卻轉(zhuǎn)而琢磨如何利用深度學(xué)習(xí)做程序合成。

2018年，他們發(fā)表一篇論文，提出基于語法的結(jié)構(gòu)化CNN代碼生成器，用《爐石傳說》基準(zhǔn)數(shù)據(jù)集進(jìn)行實(shí)驗(yàn)。

結(jié)果表明，準(zhǔn)確性明顯優(yōu)于以往最先進(jìn)的方法5個(gè)百分點(diǎn)。

這篇論文最后被AAAI 2019收錄，論文中表示，他們是第一個(gè)成功將CNN解碼器用于代碼生成的團(tuán)隊(duì)。

2019年，團(tuán)隊(duì)又用Transformer替換了CNN解碼器，準(zhǔn)確性再次提升約5個(gè)百分點(diǎn)。熊英飛笑道，一不小心做了最早應(yīng)用Transformer生成代碼的工作，“見證了歷史”。

等到了2021年，團(tuán)隊(duì)再把上面的工作結(jié)合了基于差別的修復(fù)模型，做了一個(gè)缺陷修復(fù)工作?！澳谴尉褪巧疃葘W(xué)習(xí)修bug能力首次超過了傳統(tǒng)技術(shù)。”熊英飛說。

不過略戲劇的是，等學(xué)界多數(shù)團(tuán)隊(duì)開始用深度學(xué)習(xí)來做程序合成、缺陷修復(fù)時(shí)，熊英飛團(tuán)隊(duì)又開始專研傳統(tǒng)方法去了——結(jié)果就是，本文提到的兩套算法優(yōu)化軟件誕生了。

聽起來，他們團(tuán)隊(duì)在研究程序合成這條路上，頗有種“不管黑貓白貓”的精神。

還有一種大家一起摸魚的傳統(tǒng)美德：

其實(shí)算法優(yōu)化軟件暑期8月就該上線的，不過大伙兒都在摸魚哈哈。

Fine，現(xiàn)在已經(jīng)是11月了，不知道團(tuán)隊(duì)的摸夠了沒有哇？doge