Pointer Networks
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 [1] and Neural Turing Machines [2], 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.
This paper addresses the question of using neural networks to solve computational geometry problems, such as Traveling Salesman Problem (TSP), finding the convex hull in the plane, or finding Delaunay triangulations. To that end, the authors propose a slight variant of recent content-based attention mechanisms allowing them to predict a sequence of positions (or indices) of the input sequence, and thus train on the aforementioned tasks. Numerical results show that their model learns approximate solutions and is able to generalize beyond the sizes used during training.The main contribution of this paper is the problem set-up, casting some fundamental computational geometry problems as particular instances of "sequence-to-sequence" tasks, similarly as other recent efforts (such as "Learning to Execute" by Zaremba & Sutskever), and asking whether data-driven algorithms can compete with their analytical counterparts. Besides the practical interest (which might be relevant for the TSP, since it is NP hard and therefore we typically rely on approximate algorithms), this is a scientifically interesting question.This work might serve as motivation and benchmark for future efforts in that direction. The paper is clearly written (although some aspects are discussed in too broad terms cf below comments), the set-up is well presented and the three problems are described with enough detail. As I mentioned before, the paper is original in its set-up, less so in its proposed architecture. As pointed out by the authors themselves, the so-called Pointer Networks are a minor variant of the attention model of [5], so that it can be used in the setting where the output of the network are the attention positions themselves rather than some exterior targets.However, despite these positive aspects, I would like to point out some comments, in the hope to see them addressed in the rebuttal:--> Although it is true that some recent architectures are unable to adapt to variable output dictionary size, my impression is that other works do permit this setup, such as "Inferring Algorithmic Patterns with stack-augmented recurrent nets", by A.Joulin and T.Mikolov, or the Memory networks by J.Weston. If that is the case, it would be interesting to compare the performance of these methods and to report the results.--> Training procedure. A convex hull is presented here as a sequence of input points. However, there is a natural equivalence class in the output space, since the starting point and the direction are arbitrary. After the first two points of the output are known, the conditional probabilities of the next point do not suffer from this ambiguity, but couldn't the model be improved by resolving the ambiguity? In Section 3.2, where the outputs define an even larger equivalence class, the authors choose a lexicographic ordering (thus choosing one representative of the equivalence class). Why not do the same thing for the convex hull? --> I found the analysis of the results to be a bit superficial, I would have liked to see more introspection into what is happening. For example, in Section 4.2, the authors stress the fact that their model generalizes to larger sequence lengths. My impression is that, while true, this claim should be studied more carefully. In this task, there are two essential cardinal quantities, the length n of the input sequence, and the size k of the convex hull. In the setup of points distributed iid in the square, k is typically of the order of o(4 log n) (see for example "On the expected complexity of random convex hulls" ), and it is unclear which quantity is more relevant to measure the generalization of the model, n or k. The latter typically grows at logarithmic rate. --> Lines 403-404 mentions one of the most interesting numerical results of the paper, namely that the network seems to "regularize" the A1 algorithm. Why? Even if it is a conjecture, this seems to be one of the essential messages of the paper, replacing a priori operations by data-driven modules. --> Lastly, in lines 406-410, the authors compare the generalization performance of the network between the convex hull problem and the TSP. They explain the worse generalization of the TSP case from the complexity of the underlying algorithm (NP-complete vs n log(n)). While this is a valid point, I am wondering if there is another even more important aspect, namely the effective size of the output. In the case of the convex hull, as mentioned earlier, the typical size of the set is o(4 log n), and thus the number of bits to encode the output solution is of the order of log ( binomial (n, 4log n) ) = o( (log n)^2 ), whereas for the TSP, the output is essentially any permutation of the input, which requires of the order of log (n !) = n log(n) bits. Therefore, one could argue that in the convex hull case, the network needs to learn over a space of outputs which is of significantly smaller dimension than in the TSP. The fact is that there exsit o(n^2) approximate algorithms (A2) that do well -- but learning those operations over a large output space is challenging.--> A fundamental tool to fight curse of dimensionality and NP-hardness is to rely on dynamic programming or multiscale tools. The paper proposes a very small variant of a readily available model, which has the advantage of being simple, but does not address this property. However, I am wondering if the interest of this line of work is precisely the class of intractable problems, in which being able to learn this multiscale structure seems a necessary step (similar in spirit to the fast multipole transform). --> Even if it is not in the spirit of what is presented here, a natural question is why not try to learn the TSP by optimizing the length of the path (assuming one could backpropagate a continuous relaxation), or perhaps a fine-tuning step similar to a Viterbi decoding.