用大模型解決困擾數(shù)學(xué)家60多年的問(wèn)題，谷歌DeepMind最新成果再登Nature。

作者之一、谷歌DeepMind研究副總裁Pushmeet Kohli表示：

訓(xùn)練數(shù)據(jù)中不會(huì)有這個(gè)方案，它之前甚至根本不為人類所知。

這項(xiàng)技術(shù)名為FunSearch，其中的Fun是函數(shù)（Function）一詞的簡(jiǎn)寫。

利用大模型解決長(zhǎng)期存在的科學(xué)難題，產(chǎn)生以前不存在的可驗(yàn)證且有價(jià)值*的新信息。

在Nature論文配套的新聞解讀中，DeepMind負(fù)責(zé)人稱“我們使用大模型的方式是當(dāng)做創(chuàng)造力引擎”。

這是第一次有人證明基于大模型的系統(tǒng)可以超越數(shù)學(xué)家和計(jì)算機(jī)科學(xué)家的認(rèn)知。

它不僅新穎，而且比當(dāng)今存在的任何其他東西都更有效。

針對(duì)這項(xiàng)成果，有網(wǎng)友感慨：

如果這是真的，那可是人類自火之后最重要的發(fā)現(xiàn)了。

那么，F(xiàn)unSearch都解決了哪些問(wèn)題呢？

找到NP-hard問(wèn)題更優(yōu)解法

DeepMind具體展示了兩類問(wèn)題，它們都屬于NP-hard問(wèn)題。

在學(xué)界看來(lái)，沒有而且可能永遠(yuǎn)也不會(huì)有一種算法能在所有情況下都在多項(xiàng)式時(shí)間內(nèi)找到NP-hard問(wèn)題的精確解。

面對(duì)這樣的問(wèn)題，研究者通常會(huì)尋找近似解或適用于特定情況的有效算法。

具體到FunSearch，它解決的第一類NP-hard問(wèn)題是Cap set問(wèn)題，是上限集問(wèn)題的一種，它的描述是這樣的：

在一個(gè)n維空間中的每個(gè)維度上都有等距的n個(gè)點(diǎn)（共n^n個(gè)，比如3維就是3*3*3），從中找出盡可能多的點(diǎn)構(gòu)成一個(gè)集合，要求集合中任選3個(gè)點(diǎn)均不共線，這樣的集合中最多有多少個(gè)點(diǎn)？

如果看上去有些難以理解，不妨再了解一下Cap set問(wèn)題的前身——上世紀(jì)70年代遺傳學(xué)家Marsha Falco發(fā)明的一套卡牌游戲。

這套卡牌游戲中一共有81張牌，每張牌中都有1至3個(gè)顏色圖案，同一張牌中的圖案顏色、形狀和陰影完都全相同。

這套牌一共有3種顏色、3種形狀和3種陰影，加上圖案數(shù)量的不同，一共有3*3*3*3=81張，玩家需要翻開一些紙牌，找到3張牌的特殊組合。

如果把這種“特殊組合”的具體方式用離散幾何形式進(jìn)行表達(dá)，就得到了Cap set問(wèn)題。

Cap set問(wèn)題同樣誕生于70年代，由牛津大學(xué)數(shù)學(xué)家Ron Graham提出，而第一個(gè)重要結(jié)果直到90年代才出現(xiàn)。

2007年，陶哲軒在一篇博客文章中提到，這是他最喜歡的開放式數(shù)學(xué)問(wèn)題。

在FunSearch出現(xiàn)之前，Cap set問(wèn)題最重大的突破是美國(guó)數(shù)學(xué)家Jordan Ellenberg和荷蘭數(shù)學(xué)家Dion Gijswijt于2016年提出的。

通過(guò)多項(xiàng)式方法，Ellenberg和Gijswijt將n>6時(shí)（n≤6時(shí)可精確找到最大集合）此類問(wèn)題解的上確界縮小到了2.756^n。

同樣在n>6時(shí)，下確界的較新數(shù)字則是2.218^n，由布里斯托大學(xué)博士生Fred Tyrrell在2022年提出。

但這個(gè)下確界僅僅存在于理論上——當(dāng)n=8時(shí)，人類能構(gòu)建出的最大集合中只有496個(gè)點(diǎn)，而按照Tyrrell的結(jié)論，點(diǎn)的數(shù)量應(yīng)不少于585.7個(gè)。

FunSearch則將集合規(guī)模擴(kuò)大到了512個(gè)點(diǎn)——雖然和理論值依舊存在差距，但仍被視為20年來(lái)在此問(wèn)題上最重大的突破。

同時(shí)，Cap set集合大小的下確界也被FunSearch提高到了2.2202^n。

第二類是在線裝箱問(wèn)題：

假設(shè)有一組容量為C的標(biāo)準(zhǔn)集裝箱和n個(gè)物品序列（物品大小不超過(guò)C），這些物品按一定順序到達(dá)。

“在線”是指操作者無(wú)法事先看到所有的物品，但必須在物品到達(dá)時(shí)立刻決定將物品裝入哪個(gè)集裝箱。

最終的目標(biāo)，是使所用集裝箱數(shù)量盡可能小。

在線裝箱問(wèn)題引起廣泛研究是從上世紀(jì)70年代開始的，最早更是可以追溯到1831年高斯所研究的布局問(wèn)題。

經(jīng)過(guò)近200年的研究，仍然沒有成熟的理論和有效的數(shù)值計(jì)算方法。

傳統(tǒng)上常用的貪心算法包括First Fit和Best Fit兩種：

• First Fit是指將每個(gè)物品放入第一個(gè)能容納它的箱子中。
• Best Fit則是將每個(gè)物品放入能容納它的且箱子中剩余空間最小的箱子。

而FunSearch則提出了新的算法，該算法在OR和Weibull兩個(gè)測(cè)試數(shù)據(jù)集中，所用集裝箱的數(shù)量均大幅下降。

特別是在當(dāng)測(cè)試集物品數(shù)目達(dá)到10萬(wàn)時(shí)，F(xiàn)unSearch找到的方案，消耗集裝箱數(shù)量只比理論下界多出了0.03%。

（下表中的數(shù)據(jù)表示與理論下界的差異，數(shù)字越小表現(xiàn)越好）

那么，F(xiàn)unSearch是如何實(shí)現(xiàn)的呢？

搜索“程序”而不是“答案”

整體上看，F(xiàn)unSearch的工作流程是一個(gè)迭代過(guò)程，核心是搜索能解決問(wèn)題的程序，而不是問(wèn)題答案本身。

搜索，正是DeepMind自AlphaGo以來(lái)一直堅(jiān)持探索的路線。

聯(lián)合創(chuàng)始人Shane Legg曾在一次訪談中作出解釋：

AlphaGo擊敗李世石的關(guān)鍵“第37步”從何而來(lái)？不是來(lái)自人類對(duì)弈數(shù)據(jù)，而是來(lái)自對(duì)概率空間的搜索。

當(dāng)前大模型只是模仿、混合不同的訓(xùn)練數(shù)據(jù)，要想產(chǎn)生真正的創(chuàng)造力并超越目前的架構(gòu)，就需要結(jié)合搜索。

回到最新成果FunSearch，系統(tǒng)當(dāng)中有一個(gè)程序庫(kù)，每次迭代時(shí)，系統(tǒng)會(huì)從其中搜索初始程序并輸入大模型（實(shí)驗(yàn)用PaLM2，其他只要支持代碼也兼容）。

大模型在此基礎(chǔ)上構(gòu)建生成新的程序，并交給自動(dòng)評(píng)估系統(tǒng)，得分最高的程序會(huì)被加入程序庫(kù)，從而實(shí)現(xiàn)自我循環(huán)。

其中，評(píng)估系統(tǒng)會(huì)根據(jù)用戶的問(wèn)題生成測(cè)試用例，然后判斷候選程序的輸出是否正確。

根據(jù)復(fù)雜程度不同，判斷正誤的方法既包括直接檢查輸出值，也包括對(duì)相關(guān)函數(shù)進(jìn)行調(diào)用。

同時(shí)評(píng)估系統(tǒng)還設(shè)置有容錯(cuò)邏輯，避免超時(shí)等問(wèn)題影響整體流程。

最終，系統(tǒng)會(huì)根據(jù)備選程序在這些測(cè)試用例上的行為給出整體評(píng)分，為結(jié)果生成和后續(xù)程序庫(kù)更新提供依據(jù)。

論文合著者威斯康星大學(xué)麥迪遜分校的Jordan Ellenberg認(rèn)為，F(xiàn)unSearch的一個(gè)重要特點(diǎn)是，人們可以看到AI產(chǎn)生的成功解決方案并從中學(xué)習(xí)，與之前AI的黑箱模式完全不同。

對(duì)我來(lái)說(shuō)最令人興奮的是建立人機(jī)協(xié)作的新模式，我不希望用它們來(lái)替代人類數(shù)學(xué)家，而是作為力量倍增器。

論文地址：https://www.nature.com/articles/s41586-023-06924-6