Attention,attention机制( 三 )

这个辅助方程是人为设计用于解决特定问题的，而这恰恰是我们想要避免的。这种基于图例的展现方式非常容易理解，因为许多组合优化问题可以自然而然地以这种方式呈现出来，就如下面这个TSP图例所展示的一样：图中的每个节点代表每个城市，节点边缘包含了城际间的距离，如果不考虑边缘属性，类似的图形也能够构建起来（如果我们出于某种原因不考虑距离因素在内的话）。
近年来，基于图形的神经网络模型（无关乎是否具备架构知识）以令人难以置信的速度流行开来。尤其令人瞩目的是自然语言处理领域，它所使用的Transformer架构模型已经成为业内众多任务处理的最先进技术。有许多优秀的文章详细地解释了Transformer 架构，所以本文不再深入剖析，而是做一个简述。Transformer架构是由谷歌研究人员在一篇题为“Attention Is All You Need”的论文中所介绍的。
在这篇著名的论文中，Transformer架构被用于处理NLP中所面对的序列难题。不同之处在于，我们可以向递归神经网络，如长短记忆网络（LSTM），直观输入一系列的输入向量，而Transformer架构中只能以一系列对象的形式输入，且必须采用特殊的方式来让它看见“序列”的排列顺序。这个Transformer是由一个多头自注意力子层和一个完全连接的子层所组成的。
它与图谱的关系在注意力层变得明显起来，而这个注意力层实际上是输入“节点”间的一种信息传递机制。每一个节点都会观察其他节点，同时定向那些对于它们自己看起来更“有意义”的节点。这与在图谱注意力机制（Graph Attention Network）中运行的过程非常相似。实际上，如果使用一个掩码来阻止单个节点向不相邻的节点传递信息，我们将会得到一个等价的过程。
学习如何在没有人类知识的情况下解决问题在论文《注意！学习解决路由问题》中，作者们尝试解决了几个涉及图解路由代理的组合优化难题，包括我们现在熟悉的旅行商问题。将输入数据视为一个图，并将其投入一个经过调整的Transformer构架并在构架中嵌入了图的节点，然后依次选择添加到路由的节点直到完成构建一个完整的路由为止。
将输入数据视为图形是一个比向其提供节点序列更为“正确”的方法，因为只要它们的坐标不变，就能够消除对所输入城市顺序的依赖性。这意味着，不同于上述的节点序列法，无论我们如何改变输入城市的排列，给定图神经网络的输出值都将保持不变。在论文所提及的构架中，图谱是由Transformer 编码器嵌入的，它在为所有的节点生成嵌入层的同时也为全图生成单个嵌入向量。
为了生成解决方案，每次给予一个特殊的上下文向量时都会给出一个单独的解码器网络，这个网络由图嵌入、最后一个和第一个城市以及未访问城市的嵌入组成，并会输出一个未访问城市的概率分布，然后采样生成下一个将要访问的城市。这个解码器会按顺序生成要访问的城市直到整个行程结束，然后根据旅程的长度给予反馈。文中使用了一种名为REINFORCE的强化学习算法来训练模型，这是一种基于策略梯度的算法。
其版本所使用的伪代码如下图所示：文中使用一个滚轮网络来确切评估实例的难度，并定期使用策略网络的参数来更新这个滚轮网络。这种方法在解决几个难题上取得了不错的成效，性能上超越了前文所提到的其他方法。尽管如此，作者们仍在拥有至多100个节点的小型例子上训练和评估模型。虽然这些结果很有希望，但这些例子与现实生活中其他情况相比，犹如小巫见大巫。
扩展到大型问题最近，一篇题为《通过深度强化学习在大型图上学习启发式算法》的论文中向解决现实世界那般规模大小的问题迈出了重要一步。在文中，作者训练了一个图卷积网络来解决诸如最小顶点覆盖(MVC)和最大覆盖问题(MCP)这样的大型实例问题。针对这些问题，他们采用一种流行的贪心算法来训练神经网络进行嵌入图并预测每一阶段需要选择的下一个节点，在此之后使用DQN算法对其进行进一步的训练。