神经算法推理

在本文中，我们将讨论经典计算：通常在本科计算机科学课程的算法和数据结构中发现的计算类型 [1]。考虑最短路径查找、排序、将问题分解为更简单问题的巧妙方法、组织数据以实现高效检索和更新的令人难以置信的方法。当然，考虑到The Gradient对人工智能的关注，我们不会就此止步；我们还将研究如何使用深度神经网络捕获此类计算。

为什么要捕捉经典计算？

也许值得首先澄清我对经典计算的既得兴趣从何而来。竞争性编程——通过快速编写需要在给定时间内终止并在一定内存限制内的程序来解决问题的艺术——在我的中学是一项非常受欢迎的活动。对我来说，它确实是进入计算机科学的门户，我相信今天的许多机器学习从业者和研究人员的故事都是相似的。我在国际编程竞赛中赢得了多枚奖牌，例如面向大学生的顶级计算机科学竞赛 ACM-ICPC 的西北欧地区赛。希望我在竞争性编程方面的成功也能给我一些撰写有关此主题的资格。

虽然这应该清楚地表明我为什么关心经典计算，但为什么我们都应该关心呢？为了得出这个答案，让我们思考一下经典算法具有的一些关键属性：

它们被证明是正确的，并且我们通常可以对计算终止所需的资源（时间或内存）有强有力的保证。
它们提供了很强的泛化性：虽然算法通常是通过观察几个小规模示例输入来设计的，但一旦实现，它们将在比此类示例大得多或分布不同的输入上正常工作。
从设计上来说，它们是可解释和组合的：它们的（伪）代码表示使得更容易推断计算实际在做什么，并且可以通过子例程轻松地将各种计算重新组合在一起以实现不同的功能。

将所有这些属性放在一起来看，它们似乎正是最困扰现代深度神经网络的问题：你很难保证它们的准确性，它们经常在分布外输入上崩溃，而且它们作为黑色网络而臭名昭著。框，其中存在可能妨碍组合性的复合错误。

然而，正是这些技能对于让人工智能对人类具有指导性和有用性非常重要！例如，要拥有一个能够可靠且有启发性地向人类传授概念的人工智能系统，其输出的质量不应依赖于输入的次要细节，并且应该能够将该概念推广到新的情况。可以说，这些技能也是构建通用智能代理的道路上缺失的关键一步。因此，如果我们能够在捕捉深度神经网络中经典计算的特征方面取得任何进展，这可能是一个非常富有成果的追求。

第一印象：算法对齐

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

神经网络可以学习执行经典算法吗？

这可以被视为衡量某些神经网络在算法上的表现能力的好方法。可以说，如果一个系统能够产生某种计算的输出，那么它就已经“捕获”了它。此外，学习执行为评估机器学习模型提供了一个独特的、构建良好的环境：

无限的数据源——因为我们可以生成任意数量的输入；
它们需要复杂的数据操作——这对于深度学习来说是一项具有挑战性的任务；
它们有明确指定的目标函数——简化可解释性分析。

当我们在 2019 年开始研究这个领域时，我们确实只是想了一个非常简洁的基准，但它确实正在成为一个非常活跃的领域。在我们努力的同时，麻省理工学院的一个团队尝试解决一个更雄心勃勃但密切相关的问题：

是什么让神经网络在适应某些（算法）任务方面更好（或更差）？

具有里程碑意义的论文“神经网络可以推理什么？” [2] 为为什么架构可能更适合某项任务建立了数学基础（就样本复杂性而言：将验证损失降低到 epsilon 以下所需的训练示例数量）。作者的主要定理指出，更好的算法对齐可以带来更好的泛化能力。严格定义算法对齐超出了本文的范围，但它可以非常直观地可视化：

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

距离变量对应于GNN维护的节点特征；
将边缘距离添加到距离变量对应于计算GNN的消息函数；
基于此度量选择最佳邻居对应于 GNN 的排列不变聚合函数⨁。

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

麻省理工学院团队做出了重要的观察，即 GNN 似乎在算法上与 DP 一致，并且由于 DP 本身可以用来表达许多有用的经典计算形式，因此 GNN 应该是一个非常有效的学习执行的通用模型。这得到了几个精心构建的 DP 执行基准的验证，其中像 GNN 这样的关系模型明显优于归纳偏差较弱的架构。GNN 一直是我的长期兴趣 [6]，所以现在是时候发布我们自己对该领域的贡献了：

图算法的神经执行

与 Xu等人同时发布的论文 [7] 。[2]，我们对使用 GNN 进行学习执行进行了彻底的实证分析。我们发现，虽然算法对齐确实是模型类选择的强大工具，但不幸的是，它不允许我们鲁莽行事。也就是说，我们不能仅仅将任何富有表现力的 GNN 应用于算法执行任务并期望得到很好的结果，尤其是分布外——我们之前将其确定为“真正的”推理系统应该表现良好的关键设置。与其他神经网络非常相似，GNN 很容易过度适应训练输入分布的特征，学习“聪明的黑客”并回避它们试图执行的实际程序。

因此，我们确定了关于仔细归纳偏差的三个关键观察结果，以进一步改进对某些路径寻找问题的算法对齐，并允许在测试时推广到5 倍大的输入：

大多数传统的深度学习设置都涉及具有不共享参数的一堆层。这从根本上限制了神经网络可以执行的计算量：如果在测试时，到达的输入远大于训练数据中的输入，则预计需要更多计算步骤 – 然而，非共享 GNN 没有方式来支持这一点。为了解决这个问题，我们采用编码-处理-解码范式[8]：单个共享处理器 GNN 迭代多个步骤，并且步骤数在训练和推理时都是可变的。这种架构还提供了一种巧妙的方式来在算法上与迭代计算对齐，因为大多数算法都涉及重复应用某种计算直到收敛。
由于大多数路径查找算法（包括 Bellman-Ford）都需要“局部”优化（即每一步都选择一个最佳邻居），因此我们选择使用最大聚合来组合 GNN 中发送的消息。虽然这似乎是一个非常直观的想法，但它强烈违背了当时的民间传说，因为理论上 max-GNN 在区分非同构图方面不如 sum-GNN [9]。（我们现在有坚实的理论证据 [10] 来证明为什么这是一个好主意。）
最后，虽然大多数深度学习设置只需要在给定输入的情况下产生输出，但我们发现这错过了指导模型与算法保持一致的大量方法。例如，算法有许多有趣的不变量可以显式地教授给 GNN。在 Bellman-Ford 的情况下，执行k 次迭代后，我们应该能够恢复距源节点不超过k跳的所有最短路径。因此，我们利用这种洞察力在每一步为 GNN提供逐步监督。近几个月来，这个想法似乎在大型语言模型设计中越来越受到关注 [11, 12]。

上述所有三个变化都有助于增强算法对齐的 GNN。

玩对齐游戏

必须强调的是，算法对齐的直观想法——从架构设计中的计算机科学概念中汲取灵感——绝不是新颖的！教科书上的例子是神经图灵机（NTM）和可微神经计算机（DNC）[13, 14]。这些作品具有决定性的影响力；事实上，在尝试使随机存取存储器与基于梯度的优化兼容时，NTM 为我们提供了最早的基于内容的注意力形式之一，比《变形金刚》早三年[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]）来解决这个查询。我应该强调的是，至少在撰写本文时，情况与当今大多数最先进的人工智能聊天机器人并没有太大不同——当提示执行上述任务时，虽然它们经常会寻求更多信息，他们会立即假设提供了输入加权图！

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

这两个问题都强调，我们经常需要在复杂的现实世界数据和适合运行目标算法的输入之间进行具有挑战性的映射。从历史上看，这种映射是由人类手动或通过专门的启发法执行的。这自然会引发以下问题：一般来说，人类是否希望能够手动找到必要的映射？我认为，至少从 20 世纪 50 年代起，我们就知道这个问题的答案是否定的。直接引用 Harris 和 Ross 的论文 [30]，这是最大流问题的第一个描述（通过分析铁路网络）：

在相当大的程度上，铁路系统和单个轨道容量的评估是一门艺术。作者知道没有经过测试的数学模型或公式包含所有必须权衡的变化和不可估量的因素。即使个人与他正在评估的特定领域密切相关，最终的答案无论多么准确，在很大程度上都是判断和经验的结果。

因此，即使是技术精湛的人在将单个标量“容量”值附加到每个铁路链路时也常常需要做出有根据的猜测，并且需要在通过输入网络执行任何流算法之前完成此操作！此外，正如最近的亚马逊最后一英里路由研究挑战赛[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 基准的灵感来自于C ormen、L eiserson、R ivest 和Stein [1] 的标志性算法导论(CLRS) 教科书，该教科书是最受欢迎的经典算法和数据结构本科教科书之一，也是“竞争程序员的圣经”。尽管有数千页，但它只包含约 90 种不同的算法，而这些算法往往构成软件工程整个职业生涯的基础！因此，CLRS 中的算法可以形成我们所需的可靠的“基础处理器”集，并且我们着手使构建和训练 NAR 处理器以执行 CLRS 中的算法变得容易。

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

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

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

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

为什么只停留在一种算法上？我们能学会全部三十个吗？

如前所述，CLRS-30 将 30 种不同的算法转换为统一的图形表示。这为一个明显的问题铺平了道路：我们可以学习一个处理器（具有一组权重）来执行所有这些吗？需要明确的是，我们设想的 NAR 处理器如下：

也就是说，单个 (G)NN，能够执行排序、路径查找、凸包查找和所有其他 CLRS 算法。由于不同算法之间的输入和输出维度可能有很大差异，因此我们仍然建议为每个算法使用单独的编码器和解码器（映射到处理器的潜在空间和映射出处理器的潜在空间），但是，我们故意将它们保留为线性函数以放置大多数算法P上的计算量。

然而，尽管基本思想原则上很简单，但事实证明这并非易事。大多数先前学习多种算法的尝试，例如 NEGA [7] 或其后继者 NE++ [45]，都故意专注于学习执行高度相关的算法，其中学习信号可能具有良好的相关性。因此，我们在所有 CLRS-30 上运行的初始单处理器多任务训练都导致了 NaN。

我们已经能够确定单任务不稳定性是造成这种情况的主要原因：如果任何单个算法任务的梯度有噪声或不稳定，这将转化为对所有30 个算法任务的不稳定训练。因此，我们发起了为期两个月的专门“小罢工”，以识别和解决单任务学习者的学习稳定性问题。我们的最终模型 Triplet-GMPNN [46] 与 CLRS-30 相比，绝对平均性能比之前最先进的技术提高了 20% 以上，并且能够成功进行多任务训练！更重要的是，我们现在有一个通用的Triplet-GMPNN，平均而言，它与30个专业Triplet-GMPNN相匹配，并进行了分布外评估：

虽然从这个图中可以明显看出，在我们生产出完全“算法”的 NAR 处理器库之前我们还有很长的路要走，但这一结果已被视为一个重要的“压缩”里程碑，类似于 Gato [47] 论文。我们的 Triplet-GMPNN 模型的发布在Twitter、Reddit和HackerNews上引发了极其有趣的讨论，特别是考虑到它对构建通用智能系统的影响。总的来说，在过去的三年里，各个团体在 NAR 方面取得的进展令人难以置信。我们才刚刚开始：现在我们原则上可以构建通用 NAR 处理器，我对这对未来研究和产品的潜力感到非常兴奋。

想知道更多？

不用说，本文没有涵盖很多材料，特别是本文讨论的许多论文的技术和实现细节。如果您在这里阅读的内容让您有兴趣了解更多信息，甚至亲自尝试 NAR 模型，我建议您查看 NAR 上的 LoG’22 教程 ( https://algo-reasoning.github.io/ )，我与Andreea Deac和Andrew Dudzik一起发表了这篇文章。在不到三个小时的时间里，我们涵盖了掌握开发、部署和深化神经算法推理器基础所需的所有理论，以及大量的代码指针和参考资料。当然，如果您有任何后续问题、有趣的讨论点，甚至有趣的项目想法，我们非常欢迎您直接联系！

参考

TH. Cormen, CE. Leiserson, RL. Rivest, and C. Stein. Introduction to Algorithms. MIT Press’22.
K. Xu, J. Li, M. Zhang, SS. Du, K-I. Kawarabayashi, and S. Jegelka. What Can Neural Networks Reason About?. ICLR’20.
P. Veličković. Everything is Connected: Graph Neural Networks. Current Opinion in Structural Biology’23.
R. Bellman. On a Routing Problem. Quarterly of Applied Mathematics’58.
R. Bellman. Dynamic Programming. Science’66.
P. Veličković, G. Cucurull, A. Casanova, A. Romero, P. Liò, and Y. Bengio. Graph Attention Networks. ICLR’18.
P. Veličković, R. Ying, M. Padovano, R. Hadsell, and C. Blundell. Neural Execution of Graph Algorithms. ICLR’20.
JB. Hamrick, KR. Allen, V. Bapst, T. Zhu, KR. McKee, JB. Tenenbaum, and PW. Battaglia. Relational inductive biases for physical construction in humans and machines. CCS’18.
K. Xu*, W. Hu*, J. Leskovec, and S. Jegelka. How Powerful are Graph Neural Networks?. ICLR’19.
K. Xu, M. Zhang, J. Li, SS. Du, K-I. Kawarabayashi, and S. Jegelka. How Neural Networks Extrapolate: From Feedforward to Graph Neural Networks. ICLR’21.
J. Uesato*, N. Kushman*, R. Kumar*, F. Song, N. Siegel, L. Wang, A. Creswell, G. Irving, and I. Higgins. Solving math word problems with process- and outcome-based feedback. arXiv’22.
H. Lightman*, V. Kosaraju*, Y. Burda*, H. Edwards, B. Baker, T. Lee, J. Leike, J. Schulman, I. Sutskever, and K. Cobbe. Let’s Verify Step by Step. arXiv’23.
A. Graves, G. Wayne, and I. Danihelka. Neural Turing Machines. arXiv’14.
A. Graves, G. Wayne, M. Reynolds, T. Harley, I. Danihelka, A. Grabska-Barwińska, S. Gómez Colmenarejo, E. Grefenstette, T. Ramalho, J. Agapiou, A. Puigdomènech Badia, KM. Hermann, Y. Zwols, G. Ostrovski, A. Cain, H. King, C. Summerfield, P. Blunsom, K. Kavukcuoglu, and D. Hassabis. Hybrid computing using a neural network with dynamic external memory. Nature’16.
A. Vaswani*, N. Shazeer*, N. Parmar*, J. Uszkoreit*, L. Jones*, AN. Gomez*, Ł. Kaiser*, and I. Polosukhin*. Attention is all you need. NeurIPS’17.
K. Freivalds, E. Ozoliņš, and A. Šostaks. Neural Shuffle-Exchange Networks – Sequence Processing in O(n log n) Time. NeurIPS’19.
H. Tang, Z. Huang, J. Gu, B-L. Lu, and H. Su. Towards Scale-Invariant Graph-related Problem Solving by Iterative Homogeneous GNNs. NeurIPS’20.
P. Veličković, L. Buesing, MC. Overlan, R. Pascanu, O. Vinyals, and C. Blundell. Pointer Graph Networks. NeurIPS’20.
H. Strathmann, M. Barekatain, C. Blundell, and P. Veličković. Persistent Message Passing. ICLR’21 SimDL.
B. Bevilacqua, Y. Zhou, and B. Ribeiro. Size-invariant graph representations for graph classification extrapolations. ICML’21.
B. Bevilacqua, K. Nikiforou*, B. Ibarz*, I. Bica, M. Paganini, C. Blundell, J. Mitrovic, and P. Veličković. Neural Algorithmic Reasoning with Causal Regularisation. ICML’23.
A. Dudzik*, and P. Veličković*. Graph Neural Networks are Dynamic Programmers. NeurIPS’22.
A. Dudzik, T. von Glehn, R. Pascanu, and P. Veličković. Asynchronous Algorithmic Alignment with Cocycles. ICML’23 KLR.
A. Davies, P. Veličković, L. Buesing, S. Blackwell, D. Zheng, N. Tomašev, R. Tanburn, P. Battaglia, C. Blundell, A. Juhász, M. Lackenby, G. Williamson, D. Hassabis, and P. Kohli. Advancing mathematics by guiding human intuition with AI. Nature’21.
A. Davies, A. Juhász, M. Lackenby, and N. Tomašev. The signature and cusp geometry of hyperbolic knots. Geometry & Topology (in press).
C. Blundell, L. Buesing, A. Davies, P. Veličković, and G. Williamson. Towards combinatorial invariance for Kazhdan-Lusztig polynomials. Representation Theory’22.
L. Beurer-Kellner, M. Vechev, L. Vanbever, and P. Veličković. Learning to Configure Computer Networks with Neural Algorithmic Reasoning. NeurIPS’22.
EW. Dijkstra. A note on two papers in connection with graphs. Numerische Matematik’59.
A. Derrow-Pinion, J. She, D. Wong, O. Lange, T. Hester, L. Perez, M. Nunkesser, S. Lee, X. Guo, B. Wiltshire, PW. Battaglia, V. Gupta, A. Li, Z. Xu, A. Sanchez-Gonzalez, Y. Li, and P. Veličković. ETA Prediction with Graph Neural Networks in Google Maps. CIKM’21.
TE. Harris, and FS. Ross. Fundamentals of a method for evaluating rail net capacities. RAND Tech Report’55.
M. Winkenbach, S. Parks, and J. Noszek. Technical Proceedings of the Amazon Last Mile Routing Research Challenge. 2021.
P. Veličković, and C. Blundell. Neural Algorithmic Reasoning. Patterns’21.
A. Krizhevsky, I. Sutskever, and GE. Hinton. ImageNet Classification with Deep Convolutional Neural Networks. NeurIPS’12.
Q. Cappart, D. Chételat, EB. Khalil, A. Lodi, C. Morris, and P. Veličković. Combinatorial optimization and reasoning with graph neural networks. JMLR’23.
M. Vlastelica*, A. Paulus*, V. Musil, G. Martius, and M. Rolínek. Differentiation of Blackbox Combinatorial Solvers. ICLR’20.
A. Deac, P. Veličković, O. Milinković, P-L. Bacon, J. Tang, and M. Nikolić. Neural Algorithmic Reasoners are Implicit Planners. NeurIPS’21.
B. Wilder, E. Ewing, B. Dilkina, and M. Tambe. End to end learning and optimization on graphs. NeurIPS’19.
M. Garnelo, and WM. Czarnecki. Exploring the Space of Key-Value-Query Models with Intention. 2023.
Y. He, P. Veličković, P. Liò, and A. Deac. Continuous Neural Algorithmic Planners. LoG’22.
P. Veličković*, M. Bošnjak*, T. Kipf, A. Lerchner, R. Hadsell, R. Pascanu, and C. Blundell. Reasoning-Modulated Representations. LoG’22.
D. Numeroso, D. Bacciu, and P. Veličković. Dual Algorithmic Reasoning. ICLR’23.
JC. Paetzold, J. McGinnis, S. Shit, I. Ezhov, P. Büschl, C. Prabhakar, MI. Todorov, A. Sekuboyina, G. Kaissis, A. Ertürk, S. Günnemann, and BH. Menze. Whole Brain Vessel Graphs: A Dataset and Benchmark for Graph Learning and Neuroscience. NeurIPS’21 Datasets and Benchmarks.
LR. Ford, and DR. Fulkerson. Maximal flow through a network. Canadian Journal of Mathematics’56.
P. Veličković, A. Puigdomènech Badia, D. Budden, R. Pascanu, A. Banino, M. Dashevskiy, R. Hadsell, and C. Blundell. The CLRS Algorithmic Reasoning Benchmark. ICML’22.
L-PAC. Xhonneux, A. Deac, P. Veličković, and J. Tang. How to transfer algorithmic reasoning knowledge to learn new algorithms?. NeurIPS’21.
B. Ibarz, V. Kurin, G. Papamakarios, K. Nikiforou, M. Bennani, R. Csordás, A. Dudzik, M. Bošnjak, A. Vitvitskyi, Y. Rubanova, A. Deac, B. Bevilacqua, Y. Ganin, C. Blundell, and P. Veličković. A Generalist Neural Algorithmic Learner. LoG’22.
S. Reed*, K. Żołna*, E. Parisotto*, S. Gómez Colmenarejo, A. Novikov, G. Barth-Maron, M. Giménez, Y. Sulsky, J. Kay, JT. Springenberg, T. Eccles, J. Bruce, A. Razavi, A. Edwards, N. Heess, Y. Chen, R. Hadsell, O. Vinyals, M. Bordbar, and N. de Freitas. A Generalist Agent. TMLR’22