Source-linked AI summary
Pointer Networks
Oriol Vinyals, Meire Fortunato, Navdeep Jaitly
TL;DR
Neural models struggle with problems whose output dictionary varies with input length, limiting their direct use for combinatorial tasks. Pointer Networks repurpose attention as a pointer to input elements, producing variable-sized outputs and approximate solutions to three geometric optimization problems. They generalize beyond training lengths and outperform baseline models on fixed-size problems.
Problem
Existing sequence models require fixed output dictionaries, preventing direct application to combinatorial problems whose output choices depend on input length.
Method
Pointer Networks use a softmax attention distribution as a pointer that selects input elements as output tokens.
Results
Ptr-Nets learn approximate solutions for three geometric optimization problems, generalize beyond training lengths, and outperform sequence-to-sequence baselines.
Takeaways & Limitations
Applying attention to outputs extends neural learning to problems with variable output dictionaries without artificial fixed-size assumptions.
Takeaways & Limitations
The paper leaves applicability to other input-selected tasks, such as sorting and additional combinatorial optimization problems, for future work.
Abstract
from arXiv · showhide
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.
1 Introduction
The paper introduces Pointer Networks (Ptr-Nets), which repurpose attention to point to input elements and address variable-size output dictionaries in combinatorial problems. It applies the architecture to three geometric algorithmic problems and reports generalization to test problems with more points than those used for training.
- Architecture: Pointer Networks repurpose attention as pointers to input elements, addressing output dictionaries whose size depends on input length.The model uses a softmax probability distribution as a pointer to represent variable-length dictionaries.
- Learning setup: The proposed architecture is trained from examples of inputs and desired outputs, without requiring explicit algorithmic supervision.The approach is presented as learning from examples alone.
- Applications: Ptr-Nets are applied to three distinct non-trivial algorithmic problems involving geometry.The paper context identifies these as planar convex hulls, Delaunay triangulations, and the planar Travelling Salesman Problem.
- Generalization: The learned model generalizes to test problems with more points than the training problems.This evaluates generalization beyond the point counts seen during training.
2 Models
The paper reviews sequence-to-sequence and attention-based baselines before introducing Pointer Networks, which use attention scores as pointers over input positions. The baselines are limited by fixed output dictionaries, whereas Ptr-Nets support output dictionaries whose size depends on input length.
- 2.1 Sequence-to-sequence model: The sequence-to-sequence model uses an RNN to estimate the conditional probability of an output index sequence given the input sequence.It uses separate encoder and decoder RNNs and makes no statistical independence assumptions.
- 2.1 Sequence-to-sequence model: Because its output dictionary is fixed at size n, sequence-to-sequence requires a separate model for each input length.This prevents learning solutions whose output dictionary size depends on the input sequence length.
- 2.2 Attention model: The attention baseline augments encoder and decoder RNNs with attention over the entire sequence of encoder states.At inference, attention performs n operations for each output, giving computational complexity O(n^2).
- 2.2 Attention model: Although the attention model performs significantly better than sequence-to-sequence on convex hull, it remains inapplicable when output dictionary size depends on input length.The paper notes that a simple reduction of the model resolves this limitation.
- 2.3 Pointer Network: The Pointer Network specifically targets problems whose discrete outputs correspond exactly to positions in the input sequence.Directly predicting coordinates would not guarantee that outputs map back to the inputs exactly.
- 2.3 Pointer Network: Ptr-Net uses the attention distribution as an output distribution over input positions rather than blending encoder states into a decoder context.To condition on the previous output, it copies the corresponding input element as the next decoder input.
3 Motivation and Datasets Structure
The datasets consist of uniformly sampled planar point sets paired with sequence representations of convex hulls, Delaunay triangulations, or planar symmetric TSP solutions. Canonical output orderings reduce representational ambiguity, while TSP data combines exact Held–Karp solutions for smaller instances with approximation algorithms for larger ones.
- Datasets: Inputs are planar point sets with uniformly sampled Cartesian coordinates in [0, 1] × [0, 1], paired with sequences representing the corresponding geometric solution.The outputs encode convex hulls, Delaunay triangulations, or Travelling Salesman Problem solutions.
- Convex Hull: Convex-hull outputs use indices into the input sequence plus beginning/end tokens, starting at the lowest-index point and proceeding counter-clockwise.This ordering is arbitrary but reduces training ambiguities.
- Delaunay Triangulation: Delaunay outputs encode triangle vertices as index triples, with triangles ordered lexicographically by incenter coordinates and each triangle using an increasing representation.Without ordering, the learned models were not as good because permutations represent the same triangulation.
- Travelling Salesman Problem: The planar symmetric TSP seeks the shortest tour visiting every city once and returning to the start, with equal distances in opposite directions; it is NP-hard.Cities are random points in the unit square, and training tours always start at the first city.
- Travelling Salesman Problem: Held–Karp generated exact TSP solutions in O(2^n n^2) up to n = 20, while larger instances also used O(n^2) approximations and O(n^3) Christofides solutions.Christofides is guaranteed to produce a route within a factor of 1.5 of the optimal length.
4 Empirical Results
Across the empirical tasks, the Ptr-Net was evaluated with largely shared architecture and training settings, achieving near-100% convex-hull area coverage and variable-length generalization. On TSP, it could learn from optimal or approximate data and generalize beyond training sizes, though performance broke down at larger sizes.
- Experimental setup: The experiments used virtually the same architecture across problems, without extensive architecture or hyperparameter search.The authors kept shared hyperparameters to strengthen the paper’s main message, while acknowledging tuning might improve results.
- Convex hull: The Ptr-Net achieved area coverage close to 100% on convex hulls, with most errors arising from aligned points.Aligned points are identified as a common source of convex-hull errors, including an example at n = 500.
- Convex hull: The model’s convex-hull accuracy decreased when true-hull points appeared late in the input, motivating attention over the whole input.The authors attribute this effect possibly to insufficient processing steps for updating the computed hull after later points arrive.
- Convex hull: A single Ptr-Net trained on lengths 5 to 50 performed well across trained lengths, while retaining the key advantage of inherently variable-length outputs.Some degradation at n = 50 was observed relative to a model trained only on that length.
- Travelling salesman problem: When trained on A1 data, the Ptr-Net outperformed the algorithm it was trying to imitate; optimal-data training generalized virtually perfectly to n = 25 and well to n = 30.Performance broke down for n = 40 and beyond, although it remained far better than chance.
5 Conclusions
Ptr-Net learns sequences of input positions for variable-sized inputs, enabling neural solutions to three combinatorial optimization problems with variable-sized output dictionaries. Its output-attention mechanism extends neural networks to problems with variable output dictionaries and motivates applications to sorting and other combinatorial optimization problems.
- Contributions: Ptr-Net learns conditional output sequences whose discrete tokens correspond to positions in an input sequence.The architecture supports variable-sized inputs and therefore variable-sized output dictionaries.
- Contributions: Ptr-Nets learn solutions to three different combinatorial optimization problems.
- Novelty: Applying attention to outputs addresses problems with variable output dictionaries that previous attention-based methods did not directly address.The authors describe this as opening a new class of problems for neural networks without artificial assumptions.
- Future work: Future work will examine sorting and other combinatorial optimization problems where outputs are chosen from inputs.