AI 首次攻克难倒陶哲轩数学难题：DeepMind 里程碑算法登上 Nature_风闻

困扰数学家多年、让陶哲轩直呼喜欢的上限集问题数学难题，竟然被 DeepMind 的新算法破解了？这是史上首个用 LLM 发现的算法，堪称里程碑级研究，一经发布立马登 Nature。

上限集问题，是困扰数学家们多年的开放性问题。

著名数学家陶哲轩，就曾将上限集问题描述为自己最喜欢的开放性问题。

陶哲轩博客

而大语言模型，竟然在这个问题上做出了新发现。

今天，Google DeepMind、威斯康星大学麦迪逊分校和里昂大学的研究人员联手提出全新方法 ——FunSearch，竟首次利用 LLM 发现数学科学中的开放问题！

AI 通过搜索计算机代码编写的「函数」，因此得名 FunSearch。

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

简单来说，FunSearch 将预训练的 LLM 与自动「评估器」配对使用。前者的目标是以计算机代码的形式提供创造性的解决方案，后者则防止幻觉和错误的想法。

通过在这两个组件之间来回迭代，初始解决方案「进化」为新知识。

DeepMind 为了让所有人见证这一历史性时刻，先把未编辑的版本发了出来。

Nature 新闻稿更是直言：DeepMind 的 AI 在未解难题上胜过了人类数学家！

这是人类首次使用 LLM 挑战科学或数学中的开放性问题，并做出了新发现。

另外，为了证明 FunSearch 的实用性，DeepMind 专家还尝试用它解决「装箱问题」，这个问题应用范围很广，可以提高数据中心的效率。

而对于这个问题，FunSearh 同样发现了更有效的算法。

DeepMind 专家表示，科学进步非常依赖分析新知识的能力，而 FunSearch 之所以成为强大的科学工具，就是因为它输出的程序不仅提出了解决方案，还揭示了解决方案是如何构建的。

这样，使用 FunSearch 的科学家就能进一步被启发出新的想法，进入「改进-发现」的良性循环。

LLM 通过「进化」推动科学发现

大模型最擅长解决问题，但可以发现全新的知识吗？

由于 LLM 无法避免「幻觉」输出事实不正确的信息，因此依靠它们获得事实上正确的新发现非常困难。

但是，如果我们能识别和扩展 LLM 最好的创意，将其创造力发挥到极致如何？

FunSearch 利用大模型的力量，通过一种「进化」的方法发展和保留最优秀的创意想法。

这些想法用计算机代码表达出来，可以自动运行和评分。

首先，用户以代码的形式对问题进行描述。此描述包括一个用于评估程序的过程，以及一个用于初始化程序池的种子程序。

FunSearch 是一种迭代程序，每次迭代时，系统都会从当前程序池中选择一些程序，并将其输入 LLM。

LLM 在此基础上创造性地生成新程序，并自动对其进行评估。

评分最高的程序会被添加回现有程序池中，形成一个自我改进的循环。

值得一提的是，FunSearch 使用的是谷歌的 PaLM 2，但它也兼容其他经过代码训练的 LLM。

FunSearch 整体流程示意图：向 LLM 展示它迄今为止生成的最佳程序（从程序数据库中检索），并要求生成一个更好的程序。LLM 提出的程序会被自动执行和评估。最好的程序会被添加到数据库中，供后续循环选择。用户可以随时检索迄今为止得分最高的程序。

在不同领域发现新的数学知识和算法，是一项众所周知的艰巨任务。很大程度上，这远远超出了最先进的 AI 系统的能力范围。

为了利用 FunSearch 解决此类难题，DeepMind 研究人员引入了多个关键组件。

并非从 0 开始，而是从有关问题的常识开始「进化」过程，让 FunSearch 专注于寻找最关键的想法，以实现新的发现。

此外，进化过程还使用一种策略来提高想法的多样性，以避免停滞不前。最后，DeepMind 团队并行运行进化过程，进而提高了 LLM 的效率。

开天辟地的数学发现

上限集问题是一个开放性挑战，几十年来一直困扰着多个研究领域的数学家。

这一次，DeepMind 研究者与威斯康星大学麦迪逊分校的数学教授 Jordan Ellenberg 合作，Ellenberg 教授在上限集问题上取得了重要突破。

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

上限集问题的关键之一，就是在高维网络中查找最大的点集（即上限集），在这个点集中，任何三个点都不能位于同一条线上。

上限集问题之所以如此重要，就是因为它可以作为极端组合学中其他问题的模型，这些问题会研究数字、图形或其他对象的集合最大能有多大，最小能有多小。

然而，要解决上限集问题，靠蛮力的计算方法肯定是行不通的，因为要考虑的可能性实在太多了，很快就会超过宇宙中的原子数量。

陶哲轩对于上限集问题为何重要的解释

对此，FunSearch 通过程序的形式生成了解决方案，在某些设定中，发现了有史以来最大的上限集。

这个发现，代表了过去 20 年中上限规模的最大增幅！

而且，FunSearch 的表现也优于最先进的计算求解器，因为这个问题的扩展远远超出计算求解器目前的能力。

下面这张交互式图，展示的就是从顶部的种子程序到底部的更高评分新函数的演变。

其中，每个圆圈都是一个程序，其大小与分配给它的分数成正比。右侧是 FunSearch 为每个节点生成的对应函数。（函数的完整程序，可以参考原论文）

交互体验链接：https://storage.googleapis.com/ deepmind-media / DeepMind.com/ Blog / funsearch / index.html

以上结果表明，FunSearch 技术有能力突破复杂组合问题的既定研究成果。而在这类问题中，建立直观理解通常非常困难。

研究人员表示，非常期待这种方法能够在组合学的其他类似理论问题中为新发现出力，甚至在未来为传播理论领域开辟新的可能性。

FunSearch 打开「黑盒」，与数学家合作成典范

FunSearch 偏爱简洁，且人工可解释的程序。

虽然发现新的数学知识本身就很重要，但与传统的计算机搜索技术相比，FunSearch 方法还具有额外的优势。

这是因为，FunSearch 并不是一个仅仅生成问题解决方案的「黑匣子」。

相反，它会生成描述「这些解决方案是如何实现」的程序。

这种「展示工作过程」（show-your-working）的方法，类似于科学家的工作方式，可以更好地解释和复现新发现的过程。

FunSearch 倾向于由「高度紧凑的程序」表示的解决方案 —— 具有低柯尔莫哥洛夫复杂性（Kolmogorov complexity）的解决方案。

简短的程序可以描述非常大的对象，从而使 FunSearch 能够扩展到海量数据中寻找小目标的问题。

此外，这也让研究人员更容易理解 FunSearch 的程序输出。

美国数学家 UW-Madison 教授，论文盒著者 Jordan S. Ellenberg 称，「FunSearch 为制定攻击策略提供了一种全新的机制。FunSearch 生成的解决方案在概念上要比单纯的数字列表丰富得多。当我研究它们时，我学到了一些东西」。

更重要的是，FunSearch 程序的这种可解释性，可以为研究人员提供可操作的见解。

比如，当使用 FunSearch 时，它的一些高分输出的代码中，存在耐人寻味的对称性。

这让研究人员对问题有了新的了解，并利用这种见解来完善 FunSearch 中引入的问题，从而得出更好的解决方案。

DeepMind 认为，「这是人类和 FunSearch 之间在许多数学问题上进行协作的典范」。

左：通过检查 FunSearch 生成的代码，研究人员获得了更多可操作的见解（标亮）。右：使用左侧更短的程序构建的原始「可接受」集合。解决计算机领域「装箱问题」重大挑战

既然能够在理论上限集问题上取得成功，DeepMind 研究人员尝试探索 FunSearch 在计算机科学领域的灵活性。

应用在计算机科学中一个重要的实际挑战，来探索全新方法的灵活性。

这里，采用了一个具有挑战性的「装箱问题」（bin packing），即将不同大小的物品打包到最小数量的箱子或容器之中。

这一问题是解决许多实际问题的核心，从物品装入集装箱，到在数据中心分配计算作业，以最大限度地降低成本。

在线装箱问题，通常是使用基于人类经验的算法经验法则（启发式）来解决的。

但是，为每种不同规模、时间或容量的特定情况找到一组规则，就可能有挑战性。

尽管与上限集问题有很大不同，但为这个问题设置 FunSearch 却很容易。

FunSearch 提供了一个自动定制的程序来适应数据的具体情况，性能要优于以往的启发式方法 —— 使用更少的箱子来包装相同数量的物品。

现有启发式算法：最佳适应启发式算法（左）和 FunSearch 启发式算法（右）「装箱问题」的示例。

在线装箱这类困难组合问题，也可以使用其他 AI 方法来解决，比如神经网络和强化学习。这些方法都被证明是有效的，但是要部署它们，很可能需要大量资源。

而 FunSearch 输出的代码，却可以轻松地检查和部署，这就意味着：这种解决方案可以应用于现实世界的工业系统中，快速带来好处。

LLM 驱动的科学及其他领域的发现

FunSearch 的设计表明可以防止 LLM 产生「幻觉」。

这些模型的力量不仅可以助力数学领域的新发现，还可以找到解决实际问题的最佳解。

DeepMind 认为，对于科学和工业中的许多问题，其中无论是长期存在的还是新的问题，使用 LLM 驱动的方法来生成有效且定制的算法，将会是常见的实践。

事实上，FunSearch 开创性工作仅仅是个开始。

随着 LLM 的能力范围进一步扩展，FunSearch 也会自然得到改进。

与此同时，DeepMind 还将努力扩展其能力，以应对各种社会迫切需要解决的的科学和工程挑战。

网友热议

如果所有的幻觉都是准确的，全新的见解将加速基础科学的发现。

还有人表示 AGI 的门槛就是做出新的发现，那么我猜我们现在已经有 AGI 了。

2007 年，世界上最伟大的数学家陶哲轩称「上限集问题」是他最喜欢的开放性问题。现在，谷歌的 DeepMind 的 FunSearch 成功解决了这个问题。

「LLM 不能发现任何新东西，它们只是随机的鹦鹉」。FunSearch 实际上可以在数学和计算机科学中发现新的有用的东西。

这句话明着点名 LeCun 本人。

那么，P=NP 的证明何时实现？

参考资料：

https://deepmind.google/discover/blog/funsearch-making-new-discoveries-in-mathematical-sciences-using-large-language-models/