Nature重磅：击败人类数学家，AI首次攻破经典数学难题

转载

337 天前

6549

学术头条

文章转载来源：学术头条

原文来源：学术头条

图片来源：由无界 AI生成

人工智能（AI）大模型，击败了人类数学家。

今天，在 Nature 上发表的一篇论文中，Google DeepMind 的研究团队介绍了一种搜索数学和计算机科学新解决方案的方法——FunSearch，它的工作原理是将预先训练的大型语言模型（LLMs）与自动“评估器”配对，从而防止幻觉和错误想法。通过在这两个组件之间来回迭代，最初的解决方案会演变成新的知识。

这项研究首次利用了 LLMs 在挑战科学或数学中的开放问题。FunSearch 发现了上限集问题的新解决方案，而这是数学中一个长期存在的开放问题。此外，为了展示 FunSearch 的实际用途，研究人员用它来发现更有效的算法来解决“装箱”问题，该问题具有无处不在的应用，例如提高数据中心的效率。

科学进步始终依赖于分享新理解的能力。FunSearch 成为特别强大的科学工具的原因在于，它输出的程序揭示了如何构建其解决方案，而不仅仅是解决方案是什么。论文作者表示，“希望这能够激发使用 FunSearch 的科学家的进一步见解，推动改进和发现的良性循环。”

威斯康星大学麦迪逊分校的合作者和数学教授 Jordan Ellenberg 表示：“FunSearch 生成的解决方案在概念上比单纯的数字列表要丰富得多。当我研究它们时，我学到了一些东西。”

发现最大上限集，解决“装箱”问题

FunSearch 采用由 LLMs 支持的进化方法，促进和开发得分最高的创意。这些想法被表达为计算机程序，以便它们可以自动运行和评估。

首先，用户以代码的形式编写问题的描述，该描述包括评估程序的过程和用于初始化程序池的种子程序。

FunSearch 是一个迭代过程。在每次迭代中，系统都会从当前的程序池中选择一些程序，并将其反馈到 LLMs。随后，LLMs 创造性地在此基础上构建，并生成新的程序，并自动评估。最好的程序将被添加回现有程序库中，从而创建一个自我改进的循环。

FunSearch 使用了 Google 的 PaLM 2，但它与其他受过代码训练的 LLMs 兼容。

图｜FunSearch 过程

研究重点关注了上限集问题，这是一项公开挑战，数十年来一直困扰着多个研究领域的数学家，著名数学家陶哲轩曾将其描述为他最喜欢的开放问题。

该问题包括在高维网格中找到最大的点集（称为上限集），其中没有三个点躺在一条线上。这个问题很重要，因为它可以作为极值组合学中其他问题的模型，研究数字、图形或其他对象的集合可以有多大或有多小。解决这个问题的强力计算方法不起作用，需要考虑的可能性数量很快就变得比宇宙中的原子数量还要多。

图｜交互式图表显示了从种子程序（上）到新的高分函数（下）的演变，每个圆圈都是一个程序，其大小与分配给它的分数成正比。

然而，FunSearch 以程序的形式在某些设置中发现了迄今为止发现的最大上限集，这是过去 20 年来上限规模最大增幅。此外，FunSearch 的性能还优于最先进的计算求解器。

此外，研究人员还将 FunSearch 应用于计算机科学中的实际挑战来探索 FunSearch 的灵活性。“装箱”问题着眼于如何将不同尺寸的物品装入最少数量的箱子中，这是许多现实世界问题的核心。

在线装箱问题通常使用基于人类经验的算法经验法则（启发式方法）来解决，但针对不同规模、时间或容量的具体方案可能难以提出。为此，FunSearch 提供了一个自动定制的程序（适应数据的具体情况），使用更少的箱子来包装相同数量的物品，性能优于既定的启发式方法。

这只是一个开始

在不同领域发现新的数学知识和算法是一项众所周知的艰巨任务，很大程度上超出了最先进的 AI 系统的能力。为了使用 FunSearch 解决此类具有挑战性的问题，该研究引入了多个关键组件。

值得一提的是，FunSearch 并不是一个仅仅生成问题解决方案的黑匣子。相反，它会生成程序来描述如何得出这些解决方案，而这种展示工作方法是科学家通常的运作方式。

FunSearch 倾向于寻找以高度紧凑的程序为代表的解决方案，具有低柯尔莫哥洛夫复杂度（low Kolmogorov complexity）的解决方案。短程序（Short programs）可以描述非常大的对象，使 FunSearch 能够扩展到大海捞针的大型问题。此外，FunSearch 的这种特点也使得其程序输出更容易让研究人员理解。

更重要的是，FunSearch 程序的这种可解释性可以为研究人员提供可行的见解。例如，当使用 FunSearch 时，它的一些高分输出的代码中存在有趣的对称性。