Nature 速递：利用大模型程序搜索产生数学发现

关键词：大语言模型，数学发现，组合优化，计算机搜索，可解释性

论文题目：Mathematical discoveries from program search with large language models

论文来源：Nature

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

斑图地址：https://pattern.swarma.org/paper/21c6c47a-9ad5-11ee-bc79-0242ac17000e

从定量推理到理解自然语言，大语言模型（LLMs）在解决复杂任务方面展现出强大能力。然而，LLMs有时会出现混淆（或幻觉），导致它们做出似是而非的陈述，这阻碍了当前大模型在科学发现中的使用。近日，Nature 杂志以未编辑手稿文章的形式，提前发布 Deepmind 团队关于“利用大语言模型程序搜索的数学发现”的新工作。该研究开发的 FunSearch 基于大语言模型，可以超越数学家和计算机科学家的认知，发现针对组合优化问题的全新且性能更好的解决方案。组合优化是一个研究如何计算包含有限多个对象的集合的可能排列的数学领域。

FunSearch 的工作原理是将预先训练好的 LLM 与自动评估器配对，前者的目标是以计算机代码的形式提供创造性的解决方案，后者则负责防止出现幻觉和不正确的想法。通过这两个组件之间的来回迭代，初始解决方案“进化”为新知识。该系统搜索用计算机代码编写的“函数”，因此得名 FunSearch（searching in the function space 的简称，即在函数空间中搜索）。

FunSearch 使用由 LLM 支持的进化方法，促进和发展得分最高的创意。这些想法以计算机程序的形式表达，因此可以自动运行和评估。首先，用户以代码的形式对问题进行描述。该描述包括一个用于评估程序的程序和一个用于初始化程序池的种子程序。FunSearch 会自动向经过专门训练的 LLM 发出请求，要求它编写简短的计算机程序，以生成特定数学问题的解决方案。

然后，系统会快速检查这些解决方案是否优于已知解决方案。如果不是，系统就会向 LLM 提供反馈，以便它在下一轮中加以改进。LLM 在此基础上创造性地生成新程序，并自动对其进行评估。最好的程序会被添加回现有程序库，形成一个自我完善的循环。FunSearch 使用的是谷歌的 PaLM 2，但它也兼容其他经过代码训练的 LLM。

图1：FunSearch的工作模式示意图

用于测试FunSearch的问题由遗传学家Marsha Falco在 20 世纪 70 年代发明的游戏 Set （the cap set problem）演化而来，知名数学家陶哲轩（Terence Tao）曾说这是他最喜欢的开放性问题。Set 卡组包含 81 张牌。每张牌上都有一个、两个或三个在颜色、形状和阴影上完全相同的符号，每个符号都有三种可能的选择。这些可能性加起来就是 3 × 3 × 3 × 3 = 81。玩家必须翻开扑克牌，找出三张牌的特殊组合，这种组合被称为“套牌”。FunSearch 通过生成满足游戏所有要求的牌组，改进了 n = 8 的下限。为了证明 FunSearch 的实用性，研究中还利用它为“bin packing”问题发现了优于现有算法的程序，该问题的应用无处不在，比如提高数据中心的效率。

表1：Bin 搜索问题的理论最优解，已知解及 FunSearch 得到的解

像在线 bin packing 这样的困难组合问题，可以使用神经网络和强化学习等其他人工智能方法来解决。事实证明，这些方法也很有效，但部署起来可能也需要大量资源。另一方面，FunSearch 输出的代码易于检查和部署，这意味着它的解决方案有可能被应用到各种现实世界的工业系统中，从而迅速带来效益。

尽管发现新的数学知识本身意义重大，但与传统的计算机搜索技术相比，FunSearch 方法还提供了额外的优势。这是因为，FunSearch 并不是一个仅仅生成问题解决方案的黑盒子，相反，它生成的程序会描述这些解决方案是如何得出的。这种“展示你的工作”（show-your-working）的方法通常是科学家的工作方式，通过产生新发现或新现象的过程来解释它们。

FunSearch 喜欢用高度紧凑的程序来寻找解决方案，即具有较低 Kolmogorov 复杂性的解决方案。简短的程序可以描述非常庞大的对象，从而使 FunSearch 能够扩展到大型的问题。此外，这也让研究人员更容易理解 FunSearch 的程序输出。

更重要的是，FunSearch 程序的这种可解释性可以为研究人员提供可操作的见解。例如，在使用 FunSearch 的过程中注意到，它的一些高分输出的代码中存在着有趣的对称性。这让研究者对问题有新的认识，利用这种认识，可完善引入 FunSearch 的问题，从而找到更好的解决方案。这是人类与 FunSearch 在数学领域的许多问题上进行合作的典范。

FunSearch 证明，如果我们能防止 LLM 产生幻觉，那么大模型的力量不仅可以用来产生新的数学发现，还可以用来揭示重要现实世界问题的潜在解决方案。对于科学和工业领域的许多问题——无论是长期存在的问题还是新问题——使用 LLM 驱动的方法生成有效和量身定制的算法将成为常见做法。

编译｜郭瑞东

人工智能与数学读书会启动