神经算法推理：让神经网络学会执行经典算法

在本文中，我们将讨论经典计算：即本科计算机科学课程中算法与数据结构课程里常见的那种计算[1]。想想最短路径查找、排序、将问题分解为更简单问题的巧妙方法，以及为高效检索和更新而组织数据的绝妙方式。当然，鉴于 The Gradient 对人工智能的关注，我们不会止步于此；我们还将研究如何用深度神经网络来捕捉这类计算。

也许值得先说明一下我对经典计算的切身兴趣从何而来。竞赛编程——即通过快速编写程序来解决问题的技艺，这些程序需要在给定时间内终止，并满足特定的内存限制——在我上中学时是一项非常受欢迎的活动。对我来说，它确实是进入计算机科学的敲门砖，我相信如今许多机器学习从业者和研究人员也有着类似的故事。我曾在国际编程竞赛中赢得数枚奖牌，例如 ACM-ICPC 西北欧区域赛，这是面向大学生的顶级计算机科学竞赛。希望我在竞赛编程中的成功也能让我有足够的资历撰写这个主题。

虽然这应该能说明我为什么关心经典计算，但我们所有人为什么都应该关心呢？为了得到这个答案，让我们思考一下经典算法具有的一些关键特性：

把所有这些特性放在一起看，它们似乎恰恰是困扰现代深度神经网络最严重的问题：你很少能保证它们的准确性，它们常常在分布外输入上崩溃，而且它们作为黑箱而臭名昭著，误差会累积，从而妨碍组合性。

然而，正是这些能力对于让 AI 具有启发性并对人类有用至关重要！例如，要让一个 AI 系统可靠且富有启发性地向人类教授一个概念，其输出的质量不应取决于输入的细微细节，并且它应该能够将该概念泛化到新情境中。可以说，这些能力也是构建通用智能体道路上缺失的关键一步。因此，如果我们能够朝着在深度神经网络中捕捉经典计算特征的方向取得任何进展，这很可能是一项非常有成果的探索。

我进入这一领域的旅程始于一个有趣但看似无关紧要的问题：

神经网络能学会执行经典算法吗？

这可以被视为一种很好的基准测试，用来衡量某些神经网络在多大程度上能够以算法方式行事；可以说，如果一个系统能够产生某种计算的输出，它就已经“捕捉”了这种计算。此外，学习执行提供了一个独特且构建良好的环境来评估机器学习模型：

当我们在 2019 年开始研究这一领域时，我们真的只把它当作一个非常巧妙的基准——但它无疑正在成为一个非常活跃的领域。与我们的努力同时，麻省理工学院的一个团队试图解决一个更雄心勃勃但密切相关的问题：

是什么让神经网络在拟合某些（算法）任务时表现更好（或更差）？

具有里程碑意义的论文《What Can Neural Networks Reason About?》[2] 为为什么某种架构可能更适合某项任务（就样本复杂度而言：将验证损失降至 epsilon 以下所需的训练样本数量）建立了数学基础。作者的主要定理指出，更好的算法对齐会带来更好的泛化。严格定义算法对齐超出了本文的范围，但可以非常直观地将其可视化：

在这里，我们可以看到图神经网络（GNN）[3] 如何与用于最短路径查找的经典 Bellman-Ford [4] 算法对齐的视觉分解。具体来说，Bellman-Ford 维护其对每个节点距离源节点多远的当前估计：图中每个节点 u 的距离变量（du）。在每一步，对于节点 u 的每个邻居 v，都会提出对 du 的更新：一种（最优地）到达 v，然后遍历连接 v 和 u 的边（du + wvu）的组合。然后，距离变量被更新为所有提议中的最优值。图神经网络的操作可以自然地分解，以遵循 Bellman-Ford 的数据流：

一般来说，可以证明，我们越能将神经网络分解为遵循算法的结构，在学习执行此类算法时所能期望的样本复杂度就越有利。Bellman-Ford 是动态规划（DP）算法[5]的一个典型实例，动态规划是一种通用的问题求解策略，它将问题分解为子问题，然后重新组合它们的解以找到最终解。

MIT团队提出了一个重要观察：GNN在算法上似乎与DP对齐，而由于DP本身可用于表达许多有用的经典计算形式，因此GNN应当是一种非常强大的通用模型，能够学习执行算法。这一点已通过若干精心构建的DP执行基准得到验证，在这些基准中，GNN这类关系模型明显优于归纳偏置较弱的架构。GNN一直是我长期关注的领域[6]，因此现在正是发布我们对该领域贡献的合适时机：

在与Xu等人[2]同期发布的本文[7]中，我们对使用GNN学习执行算法进行了全面的实证分析。我们发现，虽然算法对齐确实是模型类别选择的有力工具，但遗憾的是，它并不能让我们掉以轻心。也就是说，我们不能随便把任何表达力强的GNN应用于算法执行任务并期望获得好结果，尤其是在分布外的情况下——我们此前已指出，这是“真正”的推理系统应当表现良好的关键场景。与其他神经网络一样，GNN很容易过拟合训练输入分布的特征，学到“聪明的取巧手段”，从而绕开它试图执行的实际过程。

因此，我们总结出关于谨慎使用归纳偏置的三项关键观察，以进一步增强与某些寻路问题的算法对齐，并使其在测试时能够泛化到规模大5倍的输入：

上述三项改动共同造就了算法对齐更强的GNN。

必须强调，算法对齐这一直观理念——从计算机科学概念中汲取架构设计的灵感——绝非新颖！教科书式的例子是神经图灵机（NTM）和可微神经计算机（DNC）[13, 14]。这些工作具有决定性的影响力；事实上，NTM在尝试使随机存取存储器与基于梯度的优化兼容时，为我们提供了最早形式的基于内容的注意力之一，比Transformer[15]早了三年！

然而，尽管影响深远，这些架构如今在实践中几乎从未被使用。可能的原因有很多，但在我看来，是因为它们的设计过于脆弱：试图一次性将许多可微组件引入同一架构，却没有关于如何组合它们的明确指导，也没有在它们在新任务上未能显示出有用信号时便于调试的方法。我们的工作路线仍然想构建类似NTM的东西——但通过使用算法对齐更谨慎地单独原型化每个构建模块，并对哪些模块有助于执行哪些目标算法有更细粒度的认识，使其得到更成功的部署。

我们“玩算法对齐游戏”的方法似乎已经产生了一系列成功的专用（G）NN，现在我们已拥有值得称道的“细粒度”解决方案，可用于学习执行线性对数序列算法[16]、迭代算法[17]、基于指针的数据结构[18]以及持久辅助内存[19]。最终，这些洞见也延伸到了更细粒度的理论中。继我们的NEGA论文[7]之后，算法对齐的发明者将其理论完善为如今所称的线性算法对齐[10]，为包括我们使用最大聚合在内的诸多做法提供了依据。更近期的洞见表明，理解算法对齐可能需要因果推理[20,21]，将其恰当形式化可能需要范畴论[22]，而恰当描述它可能需要分析异步计算[23]。因此，算法对齐近年来正成为一个非常令人兴奋的、面向深度学习的数学方法领域。

尽管在解决我们最初的“玩具问题”方面似乎已取得许多有用的进展，但学习执行这一想法并不容易通过同行评审。我收到的最喜欢的审稿人评论——全文引用如下：“这篇论文无疑将加速构建算法模型的研究，而且肯定会有很多研究者从中受益，我只是不确定这项研究是否应该存在”。

作为论文的第一作者，收到这样的评价显然不是最令人愉快的。但还是让我们把自尊心放到一边，看看能从这类评审中汲取什么。这类评审显然提出了一个完全合理的观点：同义反复地说，目标算法执行自身的效果总会比我们能在其上学习到的任何GNN更好（或同样好）。显然，如果我们希望这些想法得到广泛认可，就需要展示学习执行如何能在“纯粹”执行之外的情境中有用地应用。

我们的探索带来了许多可能的想法，在本文的剩余部分，我将展示三个影响最大的想法。

首先，算法对齐的模型可以加速科学。如果你想找到明确的证据，看看《自然》杂志的封面[24]就够了。在我们的工作中，我们训练（G）NN来拟合数学家感兴趣的数学数据集，然后使用简单的梯度显著性方法向数学家发出信号，指示他们应关注输入的哪些部分。虽然这类信号往往噪声很大，但它们确实能让数学家只研究图中最显著的20-30个节点，而该图原本可能有数百或数千个节点，从而使模式发现变得容易得多。随后，发现的模式可以构成新定理的基础，和/或用于推导猜想。

借助这种简单的方法，我们得以在两个高度不同的数学领域推动独立贡献：纽结理论[25]和表示论[26]，两者随后都发表在各自领域的顶级期刊上，因此为我们赢得了《自然》的赞誉。但是，尽管我们的方法在原理上很简单，表示论分支中还是出现了一个问题：该用哪种（G）NN？标准的高表达力GNN并未产生清晰可解释的结果。

这正是算法对齐帮助我们之处：我们的表示论合作者Geordie Williamson提供了一个算法，只要我们能访问特权信息，它就能计算出我们所关心的输出。我们用一个GNN模型取得了最佳结果，该模型将其各组件显式地对齐到这个目标算法。

更一般地说：在这种情况下，存在一个目标算法，但执行它并不可行（由于特权输入）。算法对齐让我们无论如何都能嵌入来自它的“先验”。

其次，算法对齐的模型是快速的启发式方法。在最近与苏黎世联邦理工学院的计算机网络和机器学习合作者开展的工作中，我们研究了神经算法推理在计算机网络中的适用性[27]。具体而言，我们试图加速配置合成这一极具挑战性的任务：根据给定的计算机网络应满足的约束规范，生成相应的网络配置（一个指定网络中路由器及其连接的图）。一旦网络协议在其上执行，该配置就必须满足所有规范。

生成这些配置已知是一个极具挑战性的NP难问题——在实践中，通常用缓慢的SMT求解器来求解，这往往需要双指数复杂度。相反，我们选择使用算法推理的思想，通过反转协议（可视为一种图算法）来生成配置。具体而言，我们生成许多随机网络配置，在其上执行协议，并收集关于所得网络的所有真实事实，以提取相应的规范。这为我们提供了从规范到配置生成基于图的数据集所需的一切，并将一个算法对齐的GNN拟合到该数据集。

自然，由于只需对机器学习模型进行一次前向传播，这种方法在推理时比SMT求解器快得多：对于某些配置，我们观察到相比先前最先进方法超过490倍的加速。当然，天下没有免费的午餐：我们为这种加速付出的代价是测试时生成的配置偶尔不准确。话虽如此，在我们评估的所有相关分布上，平均满足的约束数量一直超过90%，这使得我们的方法已经可用于下游的人在回路使用——而且它很可能加速人类设计者，因为初始配置往往不可满足，这意味着SMT求解器会花费大量精力，却只是说找不到可满足的配置。在这段时间里，GNN的快速前向传播本可以允许快得多的迭代。

更一般地说：在这种情况下，目标算法只是被近似，但这样它提供了一种快速且相当准确的启发式方法，从而支持快速的人在回路迭代。

为了引出第三个也是最后一个想法，让我提出一个激励性任务：“找到我从A到B的最优路径”。你会如何回应这个提示？

很有可能，尤其是如果你像我一样有理论计算机科学背景，你会以一种非常单一的方式回答这个问题。也就是说，你会微妙地假设我给了你一个加权图，并询问你该图中两个特定顶点之间的最短路径。然后我们可以勤勉地应用我们最喜欢的寻路算法（例如Dijkstra算法[28]）来解答这个查询。我应该强调，至少在撰写本文时，当今大多数最先进的AI聊天机器人的情况并没有太大不同——当被提示上述任务时，虽然它们往往会寻求更多信息，但它们会迅速假设存在一个输入的加权图！

然而，我的问题中没有任何内容要求这两个假设中的任何一个成立。首先，现实世界往往极其嘈杂和动态，很少提供如此抽象化的输入。例如，该任务可能涉及在现实世界交通网络中两地之间旅行的最优方式，这是一个具有挑战性的路径规划问题，依赖于处理嘈杂、复杂的数据来估计实时交通速度——这是我在Google Maps中部署GNN时亲身学到的教训[29]。其次，为什么“最优”必须等于“最短”？在交通路径规划的背景下，并且取决于具体情境和目标，“最优”很可能意味着最具成本效益、污染最少等等。所有这些变化都使Dijkstra算法的直接应用变得困难，并且在实践中可能需要结合多种算法。

这两个问题都凸显出，我们常常需要在复杂的现实世界数据与适合运行目标算法的输入之间进行一种颇具挑战性的映射。历史上，这种映射是由人类完成的，要么手动进行，要么借助专门的启发式方法。这自然引出以下问题：一般而言，人类真的有可能指望手动找到所需的映射吗？我认为，至少自20世纪50年代以来，我们就已经知道这个问题的答案是否定的。直接引用Harris和Ross[30]的论文——这是关于最大流问题的最早论述之一（通过分析铁路网络）：

对铁路系统以及单条轨道容量的评估，在很大程度上是一门艺术。作者不知道有任何经过检验的数学模型或公式，能够纳入所有必须权衡的变数和不可预知因素。即使个人与其所评估的特定区域关系密切，最终答案无论多么准确，也很大程度上取决于判断和经验。

因此，即使是技艺高超的人类，在为每条铁路链路赋予单个标量“容量”值时，也常常需要做出有根据的猜测——而这必须在任何流算法能够在该输入网络上执行之前完成！此外，正如近期Amazon Last Mile Routing Research Challenge[31]中的以下陈述所表明的，

……理论路径规划与现实生活中的路径执行之间仍然存在一个重要差距，大多数基于优化的方法无法弥合这一差距。这一差距与以下事实有关：在现实运营中，一条路径的质量并不完全由其理论长度、时长或成本来定义，而是由众多因素决定，这些因素影响司机在现实条件下能够有效、安全且便捷地执行规划路径的程度。

因此，即使在当今高风险的大数据环境中，这些考量仍然具有相关性。这是经典算法与其最初设计所要解决的现实世界问题之间的根本性鸿沟！满足应用算法的严格前提条件，可能会导致从复杂的、自然产生的输入中严重丢失信息。或者，简而言之：

如果我们在错误的输入上执行算法，那么算法是否可证明正确就无关紧要了！

如果数据是部分可观测的、环境中存在对抗性行为者等，这个问题就会变得明显更加棘手。我必须强调，这不是理论计算机科学家倾向于关注的问题，而且很可能有充分的理由！在“抽象化”环境中专注于算法本身就已经颇具挑战性，并且它已经产生了若干最优美的计算例程，显著改变了我们的生活。话虽如此，如果我们想赋予这些例程“超能力”，并使它们能够远远超出其最初设想的输入类型而适用，我们就需要找到某种方式来弥合这一鸿沟。我们的提案——神经算法推理蓝图[32]——旨在通过将目标算法神经化来弥合这一鸿沟。

由于我们识别出的一个关键限制是需要手动进行输入特征工程，一个良好的首要切入点可能是简单地用神经网络编码器取代特征工程师。毕竟，取代特征工程正是深度学习取得重大突破的方式[33]！编码器将学习从原始数据预测算法的输入，然后我们可以在这些输入上执行算法，以获得我们关心的输出。

这种流水线非常流行[34]；近年来，已经出现了开创性成果，使得即使算法本身不可微，也能通过编码器进行反向传播[35]。然而，它存在算法瓶颈问题：也就是说，它完全受制于算法的输出[36]。也就是说，如果编码器对算法输入的预测很差，我们就会遇到与之前相同的问题——算法会在错误的环境中给出完美的答案。由于所需的输入通常是标量性质的（例如输入图每条边上的单个距离），编码器常常被要求将现实世界数据的极其丰富的结构映射为仅仅一个数字。这在低数据或部分可观测的场景中尤其成为问题。

为了打破算法瓶颈，我们转而选择将编码器和算法都表示为高维神经网络！现在，我们的算法模型是一个处理器神经网络——将高维嵌入映射到高维嵌入。为了恢复相关输出，我们可以随后将一个合适的解码器网络连接到处理器的输出嵌入上。如果我们能够保证这个处理器网络“捕捉了算法的计算”，那么我们就能同时解决之前识别出的所有问题：

所以，我们现在需要的只是一个能够捕捉计算的神经网络！但是，等等……这正是我们在这整篇博客文章中一直在谈论的内容！:)

我们已经得出了神经算法推理（NAR）蓝图[32]：

这张图简洁地总结了我们迄今为止所涵盖的一切：首先，我们通过算法对齐到目标算法，或通过在目标算法执行上进行预训练，或两者兼施，来获得一个合适的处理器网络P！一旦准备就绪，我们便将P纳入我们关心的任何基于原始（自然）数据的神经流水线中。这使我们能够将目标算法应用于“此前被认为无法为其所用的输入”，用原始NAR论文[32]的话来说。根据具体情况，我们可能希望也可能不希望一旦部署就将P的参数冻结，或者P甚至可能完全是非参数的[37,38]！

尽管最初只是一个提案，现在已经有多篇成功的NAR实例发表在顶级会议上[36,39,40,41]。在最近的一篇此类论文[41]中，我们旨在研究如何对小鼠大脑中的血管进行分类——这是一个跨越数百万个节点和边的极具挑战性的图任务[42]。然而，虽然直接从特征对血管进行分类并非易事，但可以相当有把握地假设血管的主要目的是输送血流——因此，一种用于流量分析的算法可能适合在此部署。据此，我们首先预训练了一个NAR处理器来执行相关的最大流和最小割算法[43]，然后成功将其部署到脑血管图上，超越了此前最先进的GNN。值得注意的是，脑血管图比我们用于学习执行的合成图大180,000倍，而且整个过程中只进行了极少的超参数调优！我们相信这一成功只是众多成功中的第一个。

虽然前面小节中给出的想法有望为捕捉经典计算的实用性提供良好的论据，但在实践中我们仍然需要知道要捕捉哪种计算！上面引用的所有NAR论文都使用了与下游任务高度相关的目标算法，并且处理器是使用基于这些算法构建的定制执行数据集来训练的。这通常既需要领域专业知识，也需要计算机科学专业知识，因此构成了明显的入门门槛！

自从我开始从事NAR以来，我一直对降低这一入门门槛抱有浓厚兴趣，同时也希望提供一组在各种任务中都应该有用的“基础处理器”。这促成了为期两年的工程努力，最终开源了CLRS算法推理基准（https://github.com/deepmind/clrs）[44]。

CLRS基准的灵感来自Cormen、Leiserson、Rivest和Stein的经典教材《算法导论》（CLRS）[1]，这是关于经典算法和数据结构最受欢迎的本科教材之一，也是竞赛程序员的“圣经”。尽管它有数千页之多，却只包含约90种不同的算法，而这些算法往往构成了整个软件工程职业生涯的基础！因此，CLRS中的算法可以构成我们所需的坚实的“基础处理器”集合，我们着手让构建和训练NAR处理器来执行CLRS中的算法变得容易。

在其第一个版本中，我们发布了CLRS-30，这是CLRS中三十种算法的数据集和处理器生成器集合，涵盖多种技能：排序、搜索、动态规划、图算法、字符串算法和几何算法。

CLRS-30的特别之处在于它向用户暴露了丰富多样的数据、模型和流水线：给定目标算法变量的适当规范、目标算法的实现以及理想的随机输入采样器，CLRS将自动以时空图结构格式生成该算法变量的完整执行轨迹、相关的编码器/解码器/处理器模型以及损失函数。因此，我们通常将CLRS称为“数据集和基线生成器”，而不是单个数据集。

例如，下面是对列表[5, 2, 4, 3, 1]进行插入排序时由CLRS生成的轨迹：

这条轨迹完整地暴露了算法的内部状态：列表的指针（绿色）如何随时间变化、当前正在排序的是哪个元素（红色），以及它需要被排序到的位置（蓝色）。默认情况下，这些可用于逐步监督，不过最近人们提出了更有趣的轨迹使用方式，例如Hint-ReLIC [21]。

如前所述，CLRS-30将三十种不同的算法转换为统一的图表示。这为一个显而易见的问题铺平了道路：我们能否学习一个处理器（使用单一权重集）来执行所有这些算法？需要明确的是，我们设想的是这样一个NAR处理器：

也就是说，一个单一的（G）NN，能够执行排序、寻路、凸包查找以及所有其他CLRS算法。由于不同算法之间的输入和输出维度可能差异巨大，我们仍然建议为每种算法使用单独的编码器和解码器——映射到处理器的潜在空间和从其中映射出来——然而，我们有意将这些保持为线性函数，以便将大部分计算工作放在P上。

然而，尽管基本思想在原则上很简单，但这被证明并非易事。大多数先前学习多种算法的尝试，例如NEGA [7]或其后继者NE++ [45]，都刻意专注于学习执行高度相关的算法，因为这些算法的学习信号很可能是良好相关的。相应地，我们最初在全部CLRS-30上进行的单处理器多任务训练运行结果产生了NaN。

我们已能够将单任务不稳定性确定为主要原因：如果任何单个算法任务的梯度有噪声或不稳定，这就会转化为全部三十个任务上的不稳定训练。因此，我们发起了一项为期两个月的专门“迷你攻坚”，以识别并修复单任务学习器中的学习稳定性问题。我们由此得到的模型Triplet-GMPNN [46]将CLRS-30上的绝对平均性能较此前最先进水平提升了20%以上，并使成功的多任务训练成为可能！更重要的是，我们现在拥有一个单一的通用Triplet-GMPNN，在分布外评估中，其平均表现与三十个专家Triplet-GMPNN相当：

尽管从这张图中可以明显看出，距离我们构建出一个完全“算法化”的NAR处理器库还有很长的路要走，但这一结果已被视为一个重要的“压缩”里程碑，类似于Gato [47]论文。我们的Triplet-GMPNN模型发布后，在Twitter、Reddit和HackerNews上引发了极其有趣的讨论，尤其是考虑到它对构建通用智能系统的意义。总体而言，过去仅仅三年里各个团队在NAR方面取得的进展令人惊叹。而我们才刚刚起步：既然我们原则上已经能够构建通用型NAR处理器，我对这为未来研究和产品带来的潜力感到无比兴奋。

毋庸赘言，本文并未涵盖大量材料——尤其是所讨论的许多论文的技术与实现细节。如果读到此处让你产生了进一步了解的兴趣，甚至想亲自把玩NAR模型，我推荐你查看LoG'22的NAR教程（https://algo-reasoning.github.io/），该教程由我与Andreea Deac和Andrew Dudzik共同讲授。在不到三个小时的时间里，我们涵盖了掌握开发、部署和深化神经算法推理器基础所需的全部理论，并附有大量代码指引和参考文献。当然，如果你有任何后续问题、有趣的讨论点，甚至是有趣的项目想法，也非常欢迎直接联系我！

Petar Veličković是Google DeepMind的资深研究科学家、剑桥大学附属讲师，以及剑桥克莱尔学院的Associate。Petar拥有剑桥大学（三一学院）计算机科学博士学位，师从Pietro Liò。他的研究涉及几何深度学习——设计能够尊重数据中不变性和对称性的神经网络架构（他还就此合著了一本雏形书）。

在学术语境或书籍中引用本作品时，请按以下格式引用：

Petar Veličković, "Neural Algorithmic Reasoning", The Gradient, 2023.

BibTeX引用：