2022/05/08 12:53

机器之心编辑部机器之心报道

DeepMind将范畴论、抽象代数组合，发现GNN与DP之间的联系

图神经网络 (GNN) 与动态规划 (DP)之间的关系应该如何描述？DeepMind 的研究者推导出了一个通用的积分变换图，证明 GNN 和 DP 之间存在着错综复杂的联系，远远超出对个别算法如 Bellman-Ford 的最初观察。

近年来，基于图神经网络 (GNN) 的神经算法推理的进步得益于算法式对齐（algorithmic alignment）概念的提出。从广义上讲，如果神经网络的各个组件与目标算法很好地对齐，那么神经网络将更好地学习执行推理任务（就样本复杂度而言）。具体来说，GNN 被认为与动态规划 (DP) 一致，而后者是一种表达多项式时间算法的通用问题解决策略。然而，这种对齐方式是否真正得到了证明和理论上的量化？

来自 DeepMind 的研究者使用范畴论和抽象代数的方法表明，GNN 和 DP 之间存在着错综复杂的联系，远远超出了 Bellman-Ford 等单个算法的最初观察结果。得知这种联系后，很容易验证文献中一些之前的发现，DeepMind 希望它能成为构建更强大算法式对齐 GNN 的基础。

论文地址：https://arxiv.org/pdf/2203.15544.pdf

总结而言，该研究描述了使用范畴论和抽象代数来显式地扩展 GNN-DP 连接，这在以前主要是在特定的例子上才能使用。该研究推导出了一个通用的积分变换图（基于标准的范畴概念，如拉回、推前和交换半群），并讨论了为什么它足够通用，可以同时支持 GNN 和 DP 计算。有了这个图，我们就可以立即将之前的大量工作统一起来，简单地在积分变换中操作一个箭头。

图神经网络是动态规划器

GNN 与 DP 连接的难点

在神经网络和 DP 之间建立严格的对应关系是比较困难的，因为它们的计算差异巨大。神经网络是基于实数线性代数构建而成，而 DP 通常是寻径（path-finding）问题的一种泛化，它通常发生在 (N∪{∞}，min， +) 这样的对象上，在数学中，这些对象通常被归为欧几里德空间的退化。GNN 与 DP 不能直接用简单的方程式进行连接。

然而，如果我们定义一个任意的潜在空间 R 并做出尽可能少的假设，我们可以观察到，对于 GNN 和 DP，我们关心的许多行为都是通过查看函数 S → R 产生的，其中 S 是一个有限集。在 GNN 下，R 可以看作是一组实值向量；在 DP 下，R 可以看作是热带数（tropical numbers）。所以 DeepMind 的主要研究对象是有限集类别以及 R 值的量化。这里的类别是指对象集合（所有有限集）以及可组合箭头（有限集之间的函数）的概念。

为了绘制 GNN-DP 连接，首先需要设计一个抽象对象，该对象可以捕获 GNN 的消息传递 / 聚合阶段（等式 1）和 DP 的评分 / 重组阶段（等式 2）。

DeepMind 将通过组合输入特征的变换来构建积分变换，这种方式将最小程度地依赖于 R 的特定选择。在此过程中，DeepMind 构建了一个计算图，该图将适用于 GNN 和 DP(以及它们自己选择的 R)，这种方式使得该研究将重点放在这些图的组件尽可能对齐上。

积分变换、拉回和前推

积分变换的一般情况是称为 span 的图，如下所示：

这里 V、E、W 是任意有限集，s、t 是任意函数。请注意，当 W = V 时，这正是 (V, E) 有向多重图结构所需的数据，其中 s(e)解释为边的源，而 t(e)则是一条边的目标。

这里需要描述两个操作，一个是沿着 s 的拉回（ pullback ） s^* 和一个沿着 t 的前推（pushforward） t_∗ 。对定义在 V 上的数据执行拉回的结果就是定义在 E 上的数据。然后前推应该获取 E 上定义的数据并给出 W 上定义的数据，尽管我们会看到它实际上给出了一个需要聚合的数据包。方便的是，这个过程自然会与 GNN 的聚合步骤以及 DP 的重组步骤保持一致。

数据包含函数 f : V → R，这使得定义拉回变得简单：s ^∗ f := f ◦ s （将边映射到它的发送节点，然后在 f 中查找特征）。

然而，前推是有问题的，因为 t 在使用函数组合时面临错误的方向。为了得到一个指向正确的箭头，需要原像（ preimage ） t^-1 : W → P(E)，它取 E 的幂集的值。原像定义为 t^-1 (w) = {e | t(e) = w}。

完成转换所缺少的只是一个聚合器，

。正如我们将在下一节中看到的，指定一个表现良好的聚合器与在 R 上施加一个可交换的幺半群结构相同。

积分变换的四个箭头

如前所述，有向图 G = (V, E)等价于 span：其中 s 和 t 分别为每条边的发送节点和接收节点。

从一些输入特征 f : V → R 开始，现在可以使用前面描述的所有对象来描述 f 的积分变换。最初，该研究关注重点是沿边 e ∈ E 发送的消息仅取决于发送者而不是接收者节点的情况。

该研究首先定义一个核变换 k：[E, R] → [E, R]，其在边缘特征上执行一些计算，例如在 Bellman-Ford 的情况下，将发送者距离 d_s(e)（之前通过 s^∗ 拉回边缘）添加到边缘权重 w_s(e)→t(e)。这里 DeepMind 使用 [E, R] 作为函数集 E → R 的简写符号。使用核，我们可以完成下图：

这四个箭头构成了整体变换：从节点特征开始，在边缘上执行计算，最后在接收器中聚合边缘消息。在此过程中，DeepMind 更新了初始节点特征（它们是 [V, R] 的元素）。

s^∗ 是先前定义的拉回箭头，如前所述，DeepMind 使用源函数预先组合节点特征。也就是说，(s^*f)(v) := f(s(v))。然后，将核应用于生成的边缘特征，将发送者的特征与任何提供的边缘特征（例如边缘权重）集成。

在应用核之后，将会得到边缘消息 m : E → R 作为结果。现在需要将这些消息发送到接收节点，DeepMind 为此使用了前推。如前所述，他们定义

，并将其解释为

中的形式和。直观地说，(t_∗m)(v) 是 v 处的传入值包。

最后，DeepMind 对每个接收器逐点应用先前定义的聚合器

来计算每个节点的更新特征。

上述设计的积分变换既能描述 GNN(公式 1)又能描述 DP(公式 2)，这使得 GNN 架构在算法上与目标 DP 算法对齐。也许最清楚的是最后一个箭头，聚合器 (

)。如果我们让 GNN 选择的聚合函数与目标算法使用的函数匹配，这应该会立即提高样本复杂性和泛化能力。事实上，这与算法推理中最早的研究路线之一非常吻合：将 GNN 与问题一致的聚合器部署。在组织现有研究和提出未来工作时，任何以这种方式分析 GNN 和 DP 的投入都可以提供丰厚的回报。

更多内容请参考论文原文。

理论动态规划图神经网络

相关数据

DeepMind机构

DeepMind是一家英国的人工智能公司。公司创建于2010年，最初名称是DeepMind科技（DeepMind Technologies Limited），在2014年被谷歌收购。在2010年由杰米斯·哈萨比斯，谢恩·列格和穆斯塔法·苏莱曼成立创业公司。继AlphaGo之后，Google DeepMind首席执行官杰米斯·哈萨比斯表示将研究用人工智能与人类玩其他游戏，例如即时战略游戏《星际争霸II》（StarCraft II）。深度AI如果能直接使用在其他各种不同领域，除了未来能玩不同的游戏外，例如自动驾驶、投资顾问、音乐评论、甚至司法判决等等目前需要人脑才能处理的工作，基本上也可以直接使用相同的神经网上去学而习得与人类相同的思考力。

https://deepmind.com/

动态规划技术

动态规划（也称为动态优化），是一种在数学、管理科学、计算机科学、经济学和生物信息学中使用的，通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。动态规划将复杂的问题分解成一系列相对简单的子问题，只解决一次子问题并存储它的解决方案（solution），下一次遇到同样的子问题时无需重新计算它的解决方案，而是简单地查找先前计算的解决方案，从而节省计算时间。动态规划适用于有最优子结构（Optimal Substructure）和重叠子问题（Overlapping Subproblems）性质的问题。

来源：Wikipedia

神经网络技术

（人工）神经网络是一种起源于 20 世纪 50 年代的监督式机器学习模型，那时候研究者构想了「感知器（perceptron）」的想法。这一领域的研究者通常被称为「联结主义者（Connectionist）」，因为这种模型模拟了人脑的功能。神经网络模型通常是通过反向传播算法应用梯度下降训练的。目前神经网络有两大主要类型，它们都是前馈神经网络：卷积神经网络（CNN）和循环神经网络（RNN），其中 RNN 又包含长短期记忆（LSTM）、门控循环单元（GRU）等等。深度学习是一种主要应用于神经网络帮助其取得更好结果的技术。尽管神经网络主要用于监督学习，但也有一些为无监督学习设计的变体，比如自动编码器和生成对抗网络（GAN）。

来源：机器之心

范畴论技术

范畴论是抽象地处理数学结构以及结构之间联系的一门数学理论，以抽象的方法来处理数学概念，将这些概念形式化成一组组的“物件”及“态射”。有些人开玩笑地称之为“一般化的抽象废话”。范畴论出现在很多数学分支中，以及理论计算机科学和数学物理的一些领域。

来源：百度百科

图神经网络技术

图网络即可以在社交网络或其它基于图形数据上运行的一般深度学习架构，它是一种基于图结构的广义神经网络。图网络一般是将底层图形作为计算图，并通过在整张图上传递、转换和聚合节点特征信息，从而学习神经网络基元以生成单节点嵌入向量。生成的节点嵌入向量可作为任何可微预测层的输入，并用于节点分类或预测节点之间的连接，完整的模型可以通过端到端的方式训练。

来源：机器之心

线性代数技术

线性代数是数学的一个分支，它的研究对象是向量，向量空间（或称线性空间），线性变换和有限维的线性方程组。向量空间是现代数学的一个重要课题；因而，线性代数被广泛地应用于抽象代数和泛函分析中；通过解析几何，线性代数得以被具体表示。线性代数的理论已被泛化为算子理论。由于科学研究中的非线性模型通常可以被近似为线性模型，使得线性代数被广泛地应用于自然科学和社会科学中。

来源：百度百科

量化技术

深度学习中的量化是指，用低位宽数字的神经网络近似使用了浮点数的神经网络的过程。

来源：Medium