Pointer Networks

Abstract

Pointer Networks introduce a new neural architecture that uses attention as a pointer to select input sequence elements for output, enabling solutions to problems with variable-sized output dictionaries like geometric combinatorial problems.

Introduction

Recurrent Neural Networks have evolved into sequence-to-sequence models with attention, but limitations remain for problems requiring variable output dictionaries, which Pointer Networks address by using attention as pointers to input elements.

Models

This section reviews sequence-to-sequence and attention models, then describes Pointer Networks (Ptr-Nets), which use a softmax distribution as a pointer to handle variable-length output dictionaries.

Content Based Input Attention

The attention model augments sequence-to-sequence models by allowing the decoder to attend to the encoder's hidden states, improving information flow but still requiring a fixed output dictionary size.

Ptr-Net

Ptr-Nets modify the attention model by using the attention mechanism's output distribution as a pointer to input elements, enabling the model to handle problems where the output dictionary size depends on the input sequence length.

Motivation and Datasets Structure

The paper considers convex hull, Delaunay triangulation, and Traveling Salesman Problem, using planar point sets as input and sequences representing solutions as output, with data sampled uniformly from [0, 1]x[0, 1].

Delaunay Triangulation and TSP

Delaunay triangulation outputs are sequences of triangle vertex indices, while TSP outputs are permutations representing the shortest route, with both problems being NP-hard and tested using generated data.

Empirical Results

Experiments compare Ptr-Nets with LSTM and LSTM with attention on convex hull and Delaunay triangulation, showing Ptr-Nets' superior performance and ability to generalize to variable input lengths.

Convex Hull Results

Ptr-Nets achieve high accuracy and area coverage on the convex hull problem, generalizing well to lengths beyond training data, unlike baseline models that require retraining for different lengths.

Delaunay Triangulation and TSP Results

Ptr-Net achieves 80.7% accuracy on Delaunay triangulation for n=5 but struggles with larger n, while on TSP, it learns a competitive approximate solver that generalizes to unseen lengths, outperforming imitated algorithms.

TSP Results

When trained on optimal TSP data, Ptr-Nets achieve near-optimal tour lengths, and even when trained on approximate algorithms like A1, the Ptr-Net outperforms the imitated algorithm and generalizes to unseen problem sizes.

Conclusions

Ptr-Nets offer a novel architecture for learning conditional probabilities of sequences where outputs point to inputs, successfully addressing problems with variable output dictionaries and outperforming baselines.