AI首次攻破经典数学难题:Nature发布重要成果

人工智能(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 时,它的一些高分输出的代码中存在有趣的对称性。

图|检查 FunSearch 生成的代码产生了进一步的可操作的见解(左);使用左侧(更短的)程序构建的原始“可接受”集(右)。

上限集问题的研究结果表明,FunSearch 技术可以超越困难组合问题的既定结果,而在这些问题上很难建立直觉。研究人员期望这种方法能够在组合学中类似理论问题的新发现中发挥作用,并在通信理论等领域开辟新的可能性。

另外,在线装箱等硬组合问题可以使用其他 AI 方法来解决,例如神经网络和强化学习。事实证明,FunSearch 的方法也有效,但也可能需要大量资源来部署。另一方面, 该方法输出的代码可以轻松检查和部署,这意味着其解决方案有可能被植入到各种现实世界的工业系统中,以带来快速的效益。

FunSearch 表明,如果能够防范 LLMs 的幻觉,这些模型的力量不仅可以用来产生新的数学发现,还可以揭示对重要现实世界问题的潜在有效解决方案。

研究团队预计,对于科学和工业中的许多问题(无论是长期存在的还是新的),使用 LLMs 驱动的方法生成有效且定制的算法将成为普遍做法。

事实上,这只是一个开始。研究人员表示:“我们还将努力扩大其能力,以解决社会各种紧迫的科学和工程挑战。”