7.17 组会
刘皓铭

Chaitanya K. Joshi, Thomas Laurent, and Xavier Bresson. "An Efficient Graph Convolutional Network Technique for the Travelling Salesman Problem.", Computing Research Repository abs/1906.01227 (2019)

中的一样,神经网络的输出 表示该边在图的最优解中的概率,损失函数为 和最优解的交叉熵损失,即为将问题看作为一个分类问题。

得到 后,通过束搜索来求解问题。

Wouter Kool, Herke van Hoof, and Max Welling. "Attention, Learn to Solve Routing Problems!", arXiv: Machine Learning (2019)

文章由 提出了一个基于注意力层的模型,并用 算法来训练模型。

问题的解定义为 ,是节点的一个排列。基于问题实例 找到解 的随机策略:

Encoder

image

没有采用位置编码,输入的节点无次序之分。

先将维度为 的节点坐标特征 嵌入到维度为 的向量 中: 然后 通过 层注意力层来更新(实验中 ),类似于 ,注意力层每一层包含两个子层,一个 头注意力层()和一个全连接层(),每个子层中还有残差链接和批归一化: 通过 得到点嵌入 和图嵌入 ,都作为 的输入。

Attention mechanism

Multi-head attention

Feed-forward sublayer

Batch normalization

Decoder

image

由两层注意力层构成,一层多头注意力层,一层单头注意力,这里的注意力层没有采用残差连接、批归一化、全连接层操作,而是直接得到相关性分数。

时刻的输入来自 之前其本身的输出: 其中 是维度为 的学习到的参数。

计算: 然后和上面 中一样求出 头注意力层输出结果

最后用一个单头注意力层来求出输出概率 ,其中用 函数来将结果修正到

Train

policy gradient

论文中的梯度计算公式为: 其中 是累计奖励函数,对于 即为路径长度。,减去 后能减少 的方差,利于梯度更新。

image

是采取采样策略, 的概率选择当前概率最大的点输出, 的概率随机选择一个点输出。

是采取贪心策略,每次都是选择当前概率最大的点输出。

两个分布差异很大时,则用 来更新

 评论