上限集問題，是困擾數(shù)學(xué)家們多年的開放性問題。

著名數(shù)學(xué)家陶哲軒，就曾將上限集問題描述為自己最喜歡的開放性問題。

陶哲軒博客

而大語言模型，竟然在這個(gè)問題上做出了新發(fā)現(xiàn)。

今天，Google DeepMind、威斯康星大學(xué)麥迪遜分校和里昂大學(xué)的研究人員聯(lián)手提出全新方法——FunSearch，竟首次利用LLM發(fā)現(xiàn)數(shù)學(xué)科學(xué)中的開放問題！

AI通過搜索計(jì)算機(jī)代碼編寫的「函數(shù)」，因此得名FunSearch。

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

簡(jiǎn)單來說，F(xiàn)unSearch將預(yù)訓(xùn)練的LLM與自動(dòng)「評(píng)估器」配對(duì)使用。前者的目標(biāo)是以計(jì)算機(jī)代碼的形式提供創(chuàng)造性的解決方案，后者則防止幻覺和錯(cuò)誤的想法。

通過在這兩個(gè)組件之間來回迭代，初始解決方案「進(jìn)化」為新知識(shí)。

DeepMind為了讓所有人見證這一歷史性時(shí)刻，先把未編輯的版本發(fā)了出來。

Nature新聞稿更是直言：DeepMind的AI在未解難題上勝過了人類數(shù)學(xué)家！

這是人類首次使用LLM挑戰(zhàn)科學(xué)或數(shù)學(xué)中的開放性問題，并做出了新發(fā)現(xiàn)。

另外，為了證明FunSearch的實(shí)用性，DeepMind專家還嘗試用它解決「裝箱問題」，這個(gè)問題應(yīng)用范圍很廣，可以提高數(shù)據(jù)中心的效率。

而對(duì)于這個(gè)問題，F(xiàn)unSearh同樣發(fā)現(xiàn)了更有效的算法。

DeepMind專家表示，科學(xué)進(jìn)步非常依賴分析新知識(shí)的能力，而FunSearch之所以成為強(qiáng)大的科學(xué)工具，就是因?yàn)樗敵龅某绦虿粌H提出了解決方案，還揭示了解決方案是如何構(gòu)建的。

這樣，使用FunSearch的科學(xué)家就能進(jìn)一步被啟發(fā)出新的想法，進(jìn)入「改進(jìn)-發(fā)現(xiàn)」的良性循環(huán)。

LLM通過「進(jìn)化」推動(dòng)科學(xué)發(fā)現(xiàn)

大模型最擅長解決問題，但可以發(fā)現(xiàn)全新的知識(shí)嗎？

由于LLM無法避免「幻覺」輸出事實(shí)不正確的信息，因此依靠它們獲得事實(shí)上正確的新發(fā)現(xiàn)非常困難。

但是，如果我們能識(shí)別和擴(kuò)展LLM最好的創(chuàng)意，將其創(chuàng)造力發(fā)揮到極致如何？

FunSearch利用大模型的力量，通過一種「進(jìn)化」的方法發(fā)展和保留最優(yōu)秀的創(chuàng)意想法。

這些想法用計(jì)算機(jī)代碼表達(dá)出來，可以自動(dòng)運(yùn)行和評(píng)分。

首先，用戶以代碼的形式對(duì)問題進(jìn)行描述。此描述包括一個(gè)用于評(píng)估程序的過程，以及一個(gè)用于初始化程序池的種子程序。

FunSearch是一種迭代程序，每次迭代時(shí)，系統(tǒng)都會(huì)從當(dāng)前程序池中選擇一些程序，并將其輸入LLM。

LLM在此基礎(chǔ)上創(chuàng)造性地生成新程序，并自動(dòng)對(duì)其進(jìn)行評(píng)估。

評(píng)分最高的程序會(huì)被添加回現(xiàn)有程序池總，形成一個(gè)自我改進(jìn)的循環(huán)。

值得一提的是，F(xiàn)unSearch使用的是谷歌的PaLM 2，但它也兼容其他經(jīng)過代碼訓(xùn)練的LLM。

FunSearch整體流程示意圖：向LLM展示它迄今為止生成的最佳程序（從程序數(shù)據(jù)庫中檢索），并要求生成一個(gè)更好的程序。LLM提出的程序會(huì)被自動(dòng)執(zhí)行和評(píng)估。最好的程序會(huì)被添加到數(shù)據(jù)庫中，供后續(xù)循環(huán)選擇。用戶可以隨時(shí)檢索迄今為止得分最高的程序。

在不同領(lǐng)域發(fā)現(xiàn)新的數(shù)學(xué)知識(shí)和算法，是一項(xiàng)眾所周知的艱巨任務(wù)。很大程度上，這遠(yuǎn)遠(yuǎn)超出了最先進(jìn)的AI系統(tǒng)的能力范圍。

為了利用FunSearch解決此類難題，DeepMind研究人員引入了多個(gè)關(guān)鍵組件。

并非從0開始，而是從有關(guān)問題的常識(shí)開始「進(jìn)化」過程，讓FunSearch專注于尋找最關(guān)鍵的想法，以實(shí)現(xiàn)新的發(fā)現(xiàn)。

此外，進(jìn)化過程還使用一種策略來提高想法的多樣性，以避免停滯不前。最后，DeepMind團(tuán)隊(duì)并行運(yùn)行進(jìn)化過程，進(jìn)而提高了LLM的效率。

開天辟地的數(shù)學(xué)發(fā)現(xiàn)

上限集問題是一個(gè)開放性挑戰(zhàn)，幾十年來一直困擾著多個(gè)研究領(lǐng)域的數(shù)學(xué)家。

這一次，DeepMind研究者與威斯康星大學(xué)麥迪遜分校的數(shù)學(xué)教授Jordan Ellenberg合作，Ellenberg教授在上限集問題上取得了重要突破。

論文地址：https://arxiv.org/abs/1605.09223

上限集問題的關(guān)鍵之一，就是在高維網(wǎng)絡(luò)中查找最大的點(diǎn)集（即上限集），在這個(gè)點(diǎn)集中，任何三個(gè)點(diǎn)都不能位于同一條線上。

上限集問題之所以如此重要，就是因?yàn)樗梢宰鳛闃O端組合學(xué)中其他問題的模型，這些問題會(huì)研究數(shù)字、圖形或其他對(duì)象的集合最大能有多大，最小能有多小。

然而，要解決上限集問題，靠蠻力的計(jì)算方法肯定是行不通的，因?yàn)橐紤]的可能性實(shí)在太多了，很快就會(huì)超過宇宙中的原子數(shù)量。

陶哲軒對(duì)于上限集問題為何重要的解釋

對(duì)此，F(xiàn)unSearch通過程序的形式生成了解決方案，在某些設(shè)定中，發(fā)現(xiàn)了有史以來最大的上限集。

這個(gè)發(fā)現(xiàn)，代表了過去20年中上限規(guī)模的最大增幅！

而且，F(xiàn)unSearch的表現(xiàn)也優(yōu)于最先進(jìn)的計(jì)算求解器，因?yàn)檫@個(gè)問題的擴(kuò)展遠(yuǎn)遠(yuǎn)超出計(jì)算求解器目前的能力。

下面這張交互式圖，展示的就是從頂部的種子程序到底部的更高評(píng)分新函數(shù)的演變。

其中，每個(gè)圓圈都是一個(gè)程序，其大小與分配給它的分?jǐn)?shù)成正比。右側(cè)是FunSearch為每個(gè)節(jié)點(diǎn)生成的對(duì)應(yīng)函數(shù)。（函數(shù)的完整程序，可以參考原論文）

交互體驗(yàn)鏈接：https://storage.googleapis.com/deepmind-media/DeepMind.com/Blog/funsearch/index.html

以上結(jié)果表明，F(xiàn)unSearch技術(shù)有能力突破復(fù)雜組合問題的既定研究成果。而在這類問題中，建立直觀理解通常非常困難。

研究人員表示，非常期待這種方法能夠在組合學(xué)的其他類似理論問題中為新發(fā)現(xiàn)出力，甚至在未來為傳播理論領(lǐng)域開辟新的可能性。

FunSearch打開「黑盒」，與數(shù)學(xué)家合作成典范

FunSearch偏愛簡(jiǎn)潔，且人工可解釋的程序

雖然發(fā)現(xiàn)新的數(shù)學(xué)知識(shí)本身就很重要，但與傳統(tǒng)的計(jì)算機(jī)搜索技術(shù)相比，F(xiàn)unSearch方法還具有額外的優(yōu)勢(shì)。

這是因?yàn)?，F(xiàn)unSearch并不是一個(gè)僅僅生成問題解決方案的「黑匣子」。

相反，它會(huì)生成描述「這些解決方案是如何實(shí)現(xiàn)」的程序。

這種「展示工作過程」（show-your-working）的方法，類似于科學(xué)家的工作方式，可以更好地解釋和復(fù)現(xiàn)新發(fā)現(xiàn)的過程。

FunSearch傾向于由「高度緊湊的程序」表示的解決方案 ——具有低柯爾莫哥洛夫復(fù)雜性（Kolmogorov complexity）的解決方案。

簡(jiǎn)短的程序可以描述非常大的對(duì)象，從而使FunSearch能夠擴(kuò)展到海量數(shù)據(jù)中尋找小目標(biāo)的問題。

此外，這也讓研究人員更容易理解FunSearch的程序輸出。

美國數(shù)學(xué)家UW-Madison教授，論文盒著者Jordan S. Ellenberg稱，「FunSearch為制定攻擊策略提供了一種全新的機(jī)制。FunSearch生成的解決方案在概念上要比單純的數(shù)字列表豐富得多。當(dāng)我研究它們時(shí)，我學(xué)到了一些東西」。

更重要的是，F(xiàn)unSearch程序的這種可解釋性，可以為研究人員提供可操作的見解。

比如，當(dāng)使用FunSearch時(shí)，它的一些高分輸出的代碼中，存在耐人尋味的對(duì)稱性。

這讓研究人員對(duì)問題有了新的了解，并利用這種見解來完善FunSearch中引入的問題，從而得出更好的解決方案。

DeepMind認(rèn)為，「這是人類和FunSearch之間在許多數(shù)學(xué)問題上進(jìn)行協(xié)作的典范」。

左：通過檢查FunSearch生成的代碼，研究人員獲得了更多可操作的見解（標(biāo)亮）。右：使用左側(cè)更短的程序構(gòu)建的原始「可接受」集合。

解決計(jì)算機(jī)領(lǐng)域「裝箱問題」重大挑戰(zhàn)

既然能夠在理論上限集問題上取得成功，DeepMind研究人員嘗試探索FunSearch在計(jì)算機(jī)科學(xué)領(lǐng)域的靈活性。

應(yīng)用在計(jì)算機(jī)科學(xué)中一個(gè)重要的實(shí)際挑戰(zhàn)，來探索全新方法的靈活性。

這里，采用了一個(gè)具有挑戰(zhàn)性的「裝箱問題」（bin packing），即將不同大小的物品打包到最小數(shù)量的箱子或容器之中。

這一問題是解決許多實(shí)際問題的核心，從物品裝入集裝箱，到在數(shù)據(jù)中心分配計(jì)算作業(yè)，以最大限度地降低成本。

在線裝箱問題，通常是使用基于人類經(jīng)驗(yàn)的算法經(jīng)驗(yàn)法則（啟發(fā)式）來解決的。

但是，為每種不同規(guī)模、時(shí)間或容量的特定情況找到一組規(guī)則，就可能有挑戰(zhàn)性。

盡管與上限集問題有很大不同，但為這個(gè)問題設(shè)置FunSearch卻很容易。

FunSearch提供了一個(gè)自動(dòng)定制的程序來適應(yīng)數(shù)據(jù)的具體情況，性能要優(yōu)于以往的啟發(fā)式方法——使用更少的箱子來包裝相同數(shù)量的物品。

現(xiàn)有啟發(fā)式算法：最佳適應(yīng)啟發(fā)式算法（左）和FunSearch啟發(fā)式算法（右）「裝箱問題」的示例。

在線裝箱這類困難組合問題，也可以使用其他AI方法來解決，比如神經(jīng)網(wǎng)絡(luò)和強(qiáng)化學(xué)習(xí)。這些方法都被證明是有效的，但是要部署它們，很可能需要大量資源。

而FunSearch輸出的代碼，卻可以輕松地檢查和部署，這就意味著：這種解決方案可以應(yīng)用于現(xiàn)實(shí)世界的工業(yè)系統(tǒng)中，快速帶來好處。

LLM驅(qū)動(dòng)的科學(xué)及其他領(lǐng)域的發(fā)現(xiàn)

FunSearch的設(shè)計(jì)表明可以防止LLM產(chǎn)生「幻覺」。

這些模型的力量不僅可以助力數(shù)學(xué)領(lǐng)域的新發(fā)現(xiàn)，還可以找到解決實(shí)際問題的最佳解。

DeepMind認(rèn)為，對(duì)于科學(xué)和工業(yè)中的許多問題，其中無論是長期存在的還是新的問題，使用LLM驅(qū)動(dòng)的方法來生成有效且定制的算法，將會(huì)是常見的實(shí)踐。

事實(shí)上，F(xiàn)unSearch開創(chuàng)性工作僅僅是個(gè)開始。

隨著LLM的能力范圍進(jìn)一步擴(kuò)展，F(xiàn)unSearch也會(huì)自然得到改進(jìn)。

與此同時(shí)，DeepMind還將努力擴(kuò)展其能力，以應(yīng)對(duì)各種社會(huì)迫切需要解決的的科學(xué)和工程挑戰(zhàn)。

網(wǎng)友熱議

如果所有的幻覺都是準(zhǔn)確的，全新的見解將加速基礎(chǔ)科學(xué)的發(fā)現(xiàn)。

還有人表示AGI的門檻就是做出新的發(fā)現(xiàn)，那么我猜我們現(xiàn)在已經(jīng)有AGI了。

2007年，世界上最偉大的數(shù)學(xué)家陶哲軒稱「上限集問題」是他最喜歡的開放性問題。現(xiàn)在，谷歌的DeepMind的FunSearch成功解決了這個(gè)問題。

「LLM不能發(fā)現(xiàn)任何新東西，它們只是隨機(jī)的鸚鵡」。FunSearch實(shí)際上可以在數(shù)學(xué)和計(jì)算機(jī)科學(xué)中發(fā)現(xiàn)新的有用的東西。

這句話明著點(diǎn)名LeCun本人。

那么，P=NP的證明何時(shí)實(shí)現(xiàn)？