We introduce a new neural architecture to learn the conditional probability of an output sequence with elements that are discrete tokens corresponding to positions in an input sequence. Such problems cannot be trivially addressed by existent approaches such as sequence-to-sequence and Neural Turing Machines, because the number of target classes in each step of the output depends on the length of the input, which is variable. Problems such as sorting variable sized sequences, and various combinatorial optimization problems belong to this class. Our model solves the problem of variable size output dictionaries using a recently proposed mechanism of neural attention. It differs from the previous attention attempts in that, instead of using attention to blend hidden units of an encoder to a context vector at each decoder step, it uses attention as a pointer to select a member of the input sequence as the output. We call this architecture a Pointer Net (Ptr-Net). We show Ptr-Nets can be used to learn approximate solutions to three challenging geometric problems -- finding planar convex hulls, computing Delaunay triangulations, and the planar Travelling Salesman Problem -- using training examples alone. Ptr-Nets not only improve over sequence-to-sequence with input attention, but also allow us to generalize to variable size output dictionaries. We show that the learnt models generalize beyond the maximum lengths they were trained on. We hope our results on these tasks will encourage a broader exploration of neural learning for discrete problems.
核心贡献 · Key contributions
提出指针网络（Ptr-Net），一种使用注意力机制作为指针来选择输入元素作为输出的新型神经架构。 Proposes Pointer Networks (Ptr-Net), a new neural architecture using attention as a pointer to select input elements as outputs.
通过使用 softmax 分布作为指针来解决可变大小输出字典的问题，从而能够处理组合优化问题。 Addresses variable-size output dictionaries by using softmax distribution as a pointer, enabling handling of combinatorial problems.
展示了 Ptr-Net 仅从训练示例中学习平面凸包、Delaunay 三角剖分和旅行商问题的近似解。 Demonstrates Ptr-Net learns approximate solutions to planar convex hull, Delaunay triangulation, and TSP from training examples alone.
展示了 Ptr-Net 能够泛化到训练时未见过的输入长度，优于带注意力的序列到序列模型。 Shows Ptr-Net generalizes to input lengths beyond those seen during training, outperforming sequence-to-sequence with attention.
提供了一种纯数据驱动的方法来处理计算上难以处理的离散问题，鼓励更广泛的探索。 Provides a purely data-driven approach to computationally intractable discrete problems, encouraging broader exploration.
局限 · Limitations
Ptr-Net 的 O(n^2)复杂度限制了其相对于精确算法在大规模输入上的可扩展性。 Ptr-Net's O(n^2) complexity limits scalability to very large inputs compared to exact algorithms.
模型在需要复杂推理的问题上性能下降，例如 n>30 的旅行商问题。 Model performance degrades for problems requiring complex reasoning, such as TSP beyond n=30.
输入顺序影响准确性；序列中较晚出现的点可能被遗漏。 Input order affects accuracy; points appearing late in the sequence may be missed.
模型在处理退化情况（如凸包中的共线点）时存在困难。 Model struggles with degenerate cases like collinear points in convex hull.