【论文阅读】注意力机制与二维 TSP 问题

前置知识

注意力机制

见 这篇

二维 TSP 问题

给定二维平面上 $n$ 个点的坐标 S={xi}i=1nS=\{x_i\}_{i=1}^nS={xi​}i=1n​，其中 $x_i\in [0,1{]}^2$，要找到一个 $1\sim n$ 的排列 $\pi$ ，使得目标函数
$$L(\pi |s)=\Vert x_{{\pi }_1}-x_{{\pi }_n}{\Vert }_2+\sum _{i=1}^{n-1}\Vert x_{{\pi }_i}-x_{{\pi }_{i+1}}{\Vert }_2$$
尽可能小。

Pointer Networks

论文链接

随意选择 ${\pi }_1$ ，然后依次预测 ${\pi }_2,{\pi }_3,...,{\pi }_n$ 。

预测方式利用了注意力机制（加性模型）：
$$u_j^i=v^T\tanh (W_1{e}_j+W_2{d}_i)$$
其中 $v,W_1,W_2$ 是可学习的参数，$e_j$ 是（节点 $j$ 的）encoder 隐状态，$d_i$ 是（已选 $i-1$ 个点的图的） decoder 隐状态。然后，直接将 softmax 后的 $u^i$ 作为输出：
$$P({\pi }_i|{\pi }_{1:i-1},\mathcal{P})=\text{softmax}(u^i)$$

encoder 和 decoder 的实现使用了单层 LSTM，训练使用 SGD。

效果如下：

传统的 RNN 的输出是固定词汇表上的分布，因此不能应对 $n$ 比训练集大的情况。而 Pointer Networks 的输出是输入序列上的分布，因此可以应对任意大小的 $n$ 。

Attention, Learn to Solve Routing Problems!

论文链接

引入强化学习，学习策略函数 $p_{\theta }(\pi |s)={\prod }_{t=1}^n{p}_{\theta }({\pi }_t|s,{\pi }_{1:t-1})$。

encoder 和 decoder 套用 Transformer 结构。