困擾數(shù)學(xué)家多年、讓陶哲軒直呼喜歡的上限集問題數(shù)學(xué)難題，竟然被 DeepMind 的新算法破解了？這是史上首個用 LLM 發(fā)現(xiàn)的算法，堪稱里程碑級研究，一經(jīng)發(fā)布立馬登 Nature。
上限集問題，是困擾數(shù)學(xué)家們多年的開放性問題。
著名數(shù)學(xué)家陶哲軒，就曾將上限集問題描述為自己最喜歡的開放性問題。
而大語言模型，竟然在這個問題上做出了新發(fā)現(xiàn)。
今天，Google DeepMind、威斯康星大學(xué)麥迪遜分校和里昂大學(xué)的研究人員聯(lián)手提出全新方法 ——FunSearch，竟首次利用 LLM 發(fā)現(xiàn)數(shù)學(xué)科學(xué)中的開放問題！
AI 通過搜索計(jì)算機(jī)代碼編寫的「函數(shù)」，因此得名 FunSearch。
簡單來說，F(xiàn)unSearch 將預(yù)訓(xùn)練的 LLM 與自動「評估器」配對使用。前者的目標(biāo)是以計(jì)算機(jī)代碼的形式提供創(chuàng)造性的解決方案，后者則防止幻覺和錯誤的想法。
通過在這兩個組件之間來回迭代，初始解決方案「進(jìn)化」為新知識。
DeepMind 為了讓所有人見證這一歷史性時刻，先把未編輯的版本發(fā)了出來。
Nature 新聞稿更是直言：DeepMind 的 AI 在未解難題上勝過了人類數(shù)學(xué)家！
這是人類首次使用 LLM 挑戰(zhàn)科學(xué)或數(shù)學(xué)中的開放性問題，并做出了新發(fā)現(xiàn)。
另外，為了證明 FunSearch 的實(shí)用性，DeepMind 專家還嘗試用它解決「裝箱問題」，這個問題應(yīng)用范圍很廣，可以提高數(shù)據(jù)中心的效率。
而對于這個問題，F(xiàn)unSearh 同樣發(fā)現(xiàn)了更有效的算法。
DeepMind 專家表示，科學(xué)進(jìn)步非常依賴分析新知識的能力，而 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)化」推動科學(xué)發(fā)現(xiàn)
大模型最擅長解決問題，但可以發(fā)現(xiàn)全新的知識嗎？
由于 LLM 無法避免「幻覺」輸出事實(shí)不正確的信息，因此依靠它們獲得事實(shí)上正確的新發(fā)現(xiàn)非常困難。
但是，如果我們能識別和擴(kuò)展 LLM 最好的創(chuàng)意，將其創(chuàng)造力發(fā)揮到極致如何？
FunSearch 利用大模型的力量，通過一種「進(jìn)化」的方法發(fā)展和保留最優(yōu)秀的創(chuàng)意想法。
這些想法用計(jì)算機(jī)代碼表達(dá)出來，可以自動運(yùn)行和評分。
首先，用戶以代碼的形式對問題進(jìn)行描述。此描述包括一個用于評估程序的過程，以及一個用于初始化程序池的種子程序。
FunSearch 是一種迭代程序，每次迭代時，系統(tǒng)都會從當(dāng)前程序池中選擇一些程序，并將其輸入 LLM。
LLM 在此基礎(chǔ)上創(chuàng)造性地生成新程序，并自動對其進(jìn)行評估。
評分最高的程序會被添加回現(xiàn)有程序池中，形成一個自我改進(jìn)的循環(huán)。
值得一提的是，F(xiàn)unSearch 使用的是谷歌的 PaLM 2，但它也兼容其他經(jīng)過代碼訓(xùn)練的 LLM。
在不同領(lǐng)域發(fā)現(xiàn)新的數(shù)學(xué)知識和算法，是一項(xiàng)眾所周知的艱巨任務(wù)。很大程度上，這遠(yuǎn)遠(yuǎn)超出了最先進(jìn)的 AI 系統(tǒng)的能力范圍。
為了利用 FunSearch 解決此類難題，DeepMind 研究人員引入了多個關(guān)鍵組件。
并非從 0 開始，而是從有關(guān)問題的常識開始「進(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)
上限集問題是一個開放性挑戰(zhàn)，幾十年來一直困擾著多個研究領(lǐng)域的數(shù)學(xué)家。
這一次，DeepMind 研究者與威斯康星大學(xué)麥迪遜分校的數(shù)學(xué)教授 Jordan Ellenberg 合作，Ellenberg 教授在上限集問題上取得了重要突破。
上限集問題的關(guān)鍵之一，就是在高維網(wǎng)絡(luò)中查找最大的點(diǎn)集（即上限集），在這個點(diǎn)集中，任何三個點(diǎn)都不能位于同一條線上。
上限集問題之所以如此重要，就是因?yàn)樗梢宰鳛闃O端組合學(xué)中其他問題的模型，這些問題會研究數(shù)字、圖形或其他對象的集合最大能有多大，最小能有多小。
然而，要解決上限集問題，靠蠻力的計(jì)算方法肯定是行不通的，因?yàn)橐紤]的可能性實(shí)在太多了，很快就會超過宇宙中的原子數(shù)量。
對此，F(xiàn)unSearch 通過程序的形式生成了解決方案，在某些設(shè)定中，發(fā)現(xiàn)了有史以來最大的上限集。
這個發(fā)現(xiàn)，代表了過去 20 年中上限規(guī)模的最大增幅！
而且，F(xiàn)unSearch 的表現(xiàn)也優(yōu)于最先進(jìn)的計(jì)算求解器，因?yàn)檫@個問題的擴(kuò)展遠(yuǎn)遠(yuǎn)超出計(jì)算求解器目前的能力。
下面這張交互式圖，展示的就是從頂部的種子程序到底部的更高評分新函數(shù)的演變。
其中，每個圓圈都是一個程序，其大小與分配給它的分?jǐn)?shù)成正比。右側(cè)是 FunSearch 為每個節(jié)點(diǎn)生成的對應(yīng)函數(shù)。（函數(shù)的完整程序，可以參考原論文）
以上結(jié)果表明，F(xiàn)unSearch 技術(shù)有能力突破復(fù)雜組合問題的既定研究成果。而在這類問題中，建立直觀理解通常非常困難。
研究人員表示，非常期待這種方法能夠在組合學(xué)的其他類似理論問題中為新發(fā)現(xiàn)出力，甚至在未來為傳播理論領(lǐng)域開辟新的可能性。
FunSearch 打開「黑盒」，與數(shù)學(xué)家合作成典范
FunSearch 偏愛簡潔，且人工可解釋的程序。
雖然發(fā)現(xiàn)新的數(shù)學(xué)知識本身就很重要，但與傳統(tǒng)的計(jì)算機(jī)搜索技術(shù)相比，F(xiàn)unSearch 方法還具有額外的優(yōu)勢。
這是因?yàn)?，F(xiàn)unSearch 并不是一個僅僅生成問題解決方案的「黑匣子」。
相反，它會生成描述「這些解決方案是如何實(shí)現(xiàn)」的程序。
這種「展示工作過程」（show-your-working）的方法，類似于科學(xué)家的工作方式，可以更好地解釋和復(fù)現(xiàn)新發(fā)現(xiàn)的過程。
FunSearch 傾向于由「高度緊湊的程序」表示的解決方案 —— 具有低柯爾莫哥洛夫復(fù)雜性（Kolmogorov complexity）的解決方案。
簡短的程序可以描述非常大的對象，從而使 FunSearch 能夠擴(kuò)展到海量數(shù)據(jù)中尋找小目標(biāo)的問題。
此外，這也讓研究人員更容易理解 FunSearch 的程序輸出。
美國數(shù)學(xué)家 UW-Madison 教授，論文盒著者 Jordan S. Ellenberg 稱，「FunSearch 為制定攻擊策略提供了一種全新的機(jī)制。FunSearch 生成的解決方案在概念上要比單純的數(shù)字列表豐富得多。當(dāng)我研究它們時，我學(xué)到了一些東西」。
更重要的是，F(xiàn)unSearch 程序的這種可解釋性，可以為研究人員提供可操作的見解。
比如，當(dāng)使用 FunSearch 時，它的一些高分輸出的代碼中，存在耐人尋味的對稱性。
這讓研究人員對問題有了新的了解，并利用這種見解來完善 FunSearch 中引入的問題，從而得出更好的解決方案。
DeepMind 認(rèn)為，「這是人類和 FunSearch 之間在許多數(shù)學(xué)問題上進(jìn)行協(xié)作的典范」。
解決計(jì)算機(jī)領(lǐng)域「裝箱問題」重大挑戰(zhàn)
既然能夠在理論上限集問題上取得成功，DeepMind 研究人員嘗試探索 FunSearch 在計(jì)算機(jī)科學(xué)領(lǐng)域的靈活性。
應(yīng)用在計(jì)算機(jī)科學(xué)中一個重要的實(shí)際挑戰(zhàn)，來探索全新方法的靈活性。
這里，采用了一個具有挑戰(zhàn)性的「裝箱問題」（bin packing），即將不同大小的物品打包到最小數(shù)量的箱子或容器之中。
這一問題是解決許多實(shí)際問題的核心，從物品裝入集裝箱，到在數(shù)據(jù)中心分配計(jì)算作業(yè)，以最大限度地降低成本。
在線裝箱問題，通常是使用基于人類經(jīng)驗(yàn)的算法經(jīng)驗(yàn)法則（啟發(fā)式）來解決的。
但是，為每種不同規(guī)模、時間或容量的特定情況找到一組規(guī)則，就可能有挑戰(zhàn)性。
盡管與上限集問題有很大不同，但為這個問題設(shè)置 FunSearch 卻很容易。
FunSearch 提供了一個自動定制的程序來適應(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ū)動的科學(xué)及其他領(lǐng)域的發(fā)現(xiàn)
FunSearch 的設(shè)計(jì)表明可以防止 LLM 產(chǎn)生「幻覺」。
這些模型的力量不僅可以助力數(shù)學(xué)領(lǐng)域的新發(fā)現(xiàn)，還可以找到解決實(shí)際問題的最佳解。
DeepMind 認(rèn)為，對于科學(xué)和工業(yè)中的許多問題，其中無論是長期存在的還是新的問題，使用 LLM 驅(qū)動的方法來生成有效且定制的算法，將會是常見的實(shí)踐。
事實(shí)上，F(xiàn)unSearch 開創(chuàng)性工作僅僅是個開始。
隨著 LLM 的能力范圍進(jìn)一步擴(kuò)展，F(xiàn)unSearch 也會自然得到改進(jìn)。
與此同時，DeepMind 還將努力擴(kuò)展其能力，以應(yīng)對各種社會迫切需要解決的的科學(xué)和工程挑戰(zhàn)。
網(wǎng)友熱議
如果所有的幻覺都是準(zhǔn)確的，全新的見解將加速基礎(chǔ)科學(xué)的發(fā)現(xiàn)。
還有人表示 AGI 的門檻就是做出新的發(fā)現(xiàn)，那么我猜我們現(xiàn)在已經(jīng)有 AGI 了。
2007 年，世界上最偉大的數(shù)學(xué)家陶哲軒稱「上限集問題」是他最喜歡的開放性問題?，F(xiàn)在，谷歌的 DeepMind 的 FunSearch 成功解決了這個問題。
「LLM 不能發(fā)現(xiàn)任何新東西，它們只是隨機(jī)的鸚鵡」。FunSearch 實(shí)際上可以在數(shù)學(xué)和計(jì)算機(jī)科學(xué)中發(fā)現(xiàn)新的有用的東西。
這句話明著點(diǎn)名 LeCun 本人。
那么，P=NP 的證明何時實(shí)現(xiàn)？
參考資料：
https://deepmind.google/discover/blog/funsearch-making-new-discoveries-in-mathematical-sciences-using-large-language-models/
廣告聲明：文內(nèi)含有的對外跳轉(zhuǎn)鏈接（包括不限于超鏈接、二維碼、口令等形式），用于傳遞更多信息，節(jié)省甄選時間，結(jié)果僅供參考，IT之家所有文章均包含本聲明。