AI首次攻克难倒陶哲轩数学难题，DeepMind里程碑算法登Nature！LLM搜代码自我进化

2023-12-16,

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

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

陶哲轩博客

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

今天，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的证明何时实现？

PS:本文来源：AI首次攻克难倒陶哲轩数学难题，DeepMind里程碑算法登Nature！LLM搜代码自我进化,数学,算法,AI,人工智能,作者：新智元