克雷西 發自 凹非寺
量子位 | 公衆号 QbitAI
用大模型解決困擾數學家60多年的問題，谷歌DeepMind最新成果再登Nature。
作者之一、谷歌DeepMind研究副總裁Pushmeet Kohli表示：
訓練資料中不會有這個方案，它之前甚至根本不為人類所知。
這項技術名為FunSearch，其中的Fun是函數（Function）一詞的簡寫。
利用大模型解決長期存在的科學難題，産生以前不存在的可驗證且有價值*的新資訊。
在Nature論文配套的新聞解讀中，DeepMind負責人稱“我們使用大模型的方式是當做創造力引擎”。
這是第一次有人證明基于大模型的系統可以超越數學家和計算機科學家的認知。
它不僅新穎，而且比當今存在的任何其他東西都更有效。
針對這項成果，有網友感慨：
如果這是真的，那可是人類自火之後最重要的發現了。
那麼，FunSearch都解決了哪些問題呢？
找到NP-hard問題更優解法
DeepMind具體展示了兩類問題，它們都屬于NP-hard問題。
在學界看來，沒有而且可能永遠也不會有一種算法能在所有情況下都在多項式時間内找到NP-hard問題的精确解。
面對這樣的問題，研究者通常會尋找近似解或适用于特定情況的有效算法。
具體到FunSearch，它解決的第一類NP-hard問題是Cap set問題，是上限集問題的一種，它的描述是這樣的：
在一個n維空間中的每個次元上都有等距的n個點（共n^n個，比如3維就是3*3*3），從中找出盡可能多的點構成一個集合，要求集合中任選3個點均不共線，這樣的集合中最多有多少個點？
如果看上去有些難以了解，不妨再了解一下Cap set問題的前身——上世紀70年代遺傳學家Marsha Falco發明的一套卡牌遊戲。
這套卡牌遊戲中一共有81張牌，每張牌中都有1至3個顔色圖案，同一張牌中的圖案顔色、形狀和陰影完都全相同。
這套牌一共有3種顔色、3種形狀和3種陰影，加上圖案數量的不同，一共有3*3*3*3=81張，玩家需要翻開一些紙牌，找到3張牌的特殊組合。
如果把這種“特殊組合”的具體方式用離散幾何形式進行表達，就得到了Cap set問題。
Cap set問題同樣誕生于70年代，由牛津大學數學家Ron Graham提出，而第一個重要結果直到90年代才出現。
2007年，陶哲軒在一篇部落格文章中提到，這是他最喜歡的開放式數學問題。
在FunSearch出現之前，Cap set問題最重大的突破是美國數學家Jordan Ellenberg和荷蘭數學家Dion Gijswijt于2016年提出的。
通過多項式方法，Ellenberg和Gijswijt将n>6時（n≤6時可精确找到最大集合）此類問題解的上确界縮小到了2.756^n。
同樣在n>6時，下确界的較新數字則是2.218^n，由布裡斯托大學博士生Fred Tyrrell在2022年提出。
但這個下确界僅僅存在于理論上——當n=8時，人類能建構出的最大集合中隻有496個點，而按照Tyrrell的結論，點的數量應不少于585.7個。
FunSearch則将集合規模擴大到了512個點——雖然和理論值依舊存在差距，但仍被視為20年來在此問題上最重大的突破。
同時，Cap set集合大小的下确界也被FunSearch提高到了2.2202^n。
第二類是線上裝箱問題：
假設有一組容量為C的标準集裝箱和n個物品序列（物品大小不超過C），這些物品按一定順序到達。
“線上”是指操作者無法事先看到所有的物品，但必須在物品到達時立刻決定将物品裝入哪個集裝箱。
最終的目标，是使所用集裝箱數量盡可能小。
線上裝箱問題引起廣泛研究是從上世紀70年代開始的，最早更是可以追溯到1831年高斯所研究的布局問題。
經過近200年的研究，仍然沒有成熟的理論和有效的數值計算方法。
傳統上常用的貪心算法包括First Fit和Best Fit兩種：
- First Fit是指将每個物品放入第一個能容納它的箱子中。
- Best Fit則是将每個物品放入能容納它的且箱子中剩餘空間最小的箱子。
而FunSearch則提出了新的算法，該算法在OR和Weibull兩個測試資料集中，所用集裝箱的數量均大幅下降。
特别是在當測試集物品數目達到10萬時，FunSearch找到的方案，消耗集裝箱數量隻比理論下界多出了0.03%。
（下表中的資料表示與理論下界的差異，數字越小表現越好）
那麼，FunSearch是如何實作的呢？
搜尋“程式”而不是“答案”
整體上看，FunSearch的工作流程是一個疊代過程，核心是搜尋能解決問題的程式，而不是問題答案本身。
搜尋，正是DeepMind自AlphaGo以來一直堅持探索的路線。
聯合創始人Shane Legg曾在一次訪談中作出解釋：
AlphaGo擊敗李世石的關鍵“第37步”從何而來？不是來自人類對弈資料，而是來自對機率空間的搜尋。
目前大模型隻是模仿、混合不同的訓練資料，要想産生真正的創造力并超越目前的架構，就需要結合搜尋。
回到最新成果FunSearch，系統當中有一個程式庫，每次疊代時，系統會從其中搜尋初始程式并輸入大模型（實驗用PaLM2，其他隻要支援代碼也相容）。
大模型在此基礎上建構生成新的程式，并交給自動評估系統，得分最高的程式會被加入程式庫，進而實作自我循環。
其中，評估系統會根據使用者的問題生成測試用例，然後判斷候選程式的輸出是否正确。
根據複雜程度不同，判斷正誤的方法既包括直接檢查輸出值，也包括對相關函數進行調用。
同時評估系統還設定有容錯邏輯，避免逾時等問題影響整體流程。
最終，系統會根據備選程式在這些測試用例上的行為給出整體評分，為結果生成和後續程式庫更新提供依據。
論文合著者威斯康星大學麥迪遜分校的Jordan Ellenberg認為，FunSearch的一個重要特點是，人們可以看到AI産生的成功解決方案并從中學習，與之前AI的黑箱模式完全不同。
對我來說最令人興奮的是建立人機協作的新模式，我不希望用它們來替代人類數學家，而是作為力量倍增器。
論文位址：
https://www.nature.com/articles/s41586-023-06924-6
參考連結：
[1]https://deepmind.google/discover/blog/funsearch-making-new-discoveries-in-mathematical-sciences-using-large-language-models/
[2]https://www.technologyreview.com/2023/12/14/1085318/google-deepmind-large-language-model-solve-unsolvable-math-problem-cap-set/
[3]https://www.nature.com/articles/d41586-023-04043-w
— 完 —
量子位 QbitAI · 頭條号簽約
關注我們，第一時間獲知前沿科技動态