Nature：DeepMind大模型突破60年数学难题，解法超出人类已有认知

克雷西 发自 凹非寺

量子位 | 公众号 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