Source-linked AI summary
Order Matters: Sequence to sequence for sets
Oriol Vinyals, Samy Bengio, Manjunath Kudlur
TL;DR
Seq2seq models are effective for ordered data, but many tasks involve variable-sized input or output sets without a natural ordering. The paper studies ordering, extends seq2seq to input sets, and searches over output orders during training. Its experiments show that ordering matters and support the proposed set-handling modifications across language, parsing, sorting, and joint-probability tasks.
Problem
Seq2seq lacks a principled representation for variable-sized inputs or outputs that are unordered or have multiple valid orderings.
Method
The paper extends seq2seq to input sets and trains output models by selecting among possible orderings for applying the chain rule.
Results
The experiments show that input and output ordering affects performance and evaluate set-handling extensions on language, parsing, sorting, and joint-probability tasks.
Takeaways & Limitations
Order should be treated as a modeling choice, while unordered inputs and outputs can be handled through set-aware seq2seq extensions.
Takeaways & Limitations
Naively maximizing over output orderings is not scalable and can lock the model into a random ordering determined by initialization.
Abstract
from arXiv · showhide
Sequences have become first class citizens in supervised learning thanks to the resurgence of recurrent neural networks. Many complex tasks that require mapping from or to a sequence of observations can now be formulated with the sequence-to-sequence (seq2seq) framework which employs the chain rule to efficiently represent the joint probability of sequences. In many cases, however, variable sized inputs and/or outputs might not be naturally expressed as sequences. For instance, it is not clear how to input a set of numbers into a model where the task is to sort them; similarly, we do not know how to organize outputs when they correspond to random variables and the task is to model their unknown joint probability. In this paper, we first show using various examples that the order in which we organize input and/or output data matters significantly when learning an underlying model. We then discuss an extension of the seq2seq framework that goes beyond sequences and handles input sets in a principled way. In addition, we propose a loss which, by searching over possible orders during training, deals with the lack of structure of output sets. We show empirical evidence of our claims regarding ordering, and on the modifications to the seq2seq framework on benchmark language modeling and parsing tasks, as well as two artificial tasks -- sorting numbers and estimating the joint probability of unknown graphical models.
1 INTRODUCTION
Seq2seq models work naturally for ordered data, but many tasks involve input or output sets without an obvious order. This paper shows that ordering can affect performance and proposes principled ways to handle sets.
- Seq2seq models encode inputs and decode target sequences using recurrent networks and the chain rule.An encoder reads the input, and a decoder LSTM produces the target one token at a time.
- Sets create a representation problem because their elements may have no obvious input or output order.The paper motivates this with sorting numbers and producing detected objects without a known ordering.
- The paper shows that an ordering can improve performance even when no natural order is known.It also proposes approaches for treating sets as inputs and outputs and evaluates them on artificial and real datasets.
2 RELATED WORK
Related work establishes seq2seq as a framework for mapping between sequences and contrasts this paper's approach with memory-based and structured prediction methods.
- Seq2seq models have been applied to mappings such as images to sentences, sentences to parse trees, and problem statements to computations.
- External-memory models use differentiable reading or attention mechanisms to access stored information.Examples include RNNSearch, Memory Networks, and Neural Turing Machines.
- Unlike traditional structured prediction, this approach serializes output variables with the chain rule and LSTMs without assuming a known structured input.
3 NEURAL NETWORKS FOR SEQUENCES AND SETS
The seq2seq framework models conditional sequence probabilities by encoding inputs recurrently and generating outputs step by step. The paper extends this perspective to unordered inputs and outputs by considering alternative representations and orderings.
- Seq2seq represents paired inputs and targets as variable-length sequences and models P(Y|X) with the chain rule.
- An encoder RNN reads each input element sequentially, while a decoder RNN produces target elements one at a time from its state and the previous symbol.
- The chain rule avoids conditional-independence assumptions, but it leaves open how to encode unordered inputs and produce unordered targets.
- Sequences can be converted into sets by pairing each element with its position, while alternative output orders may support strategies such as divide-and-conquer sorting.
- The paper extends seq2seq to input and output sets and evaluates the importance of ordering across multiple tasks.
4 INPUT SETS
The paper argues that input ordering affects seq2seq learning and introduces an attention-based architecture that processes unordered input sets while preserving permutation invariance. Experiments show that suitable processing and attention improve set-to-sequence sorting performance.
- Input-set encoding: Set encodings should be permutation invariant, so swapping two input elements must not change the representation.Reduction operations satisfy this invariance, but fixed-dimensional embeddings become inefficient as set length grows.
- Input order matters: Input order can affect seq2seq performance despite recurrent encoders' expressive capacity, likely because of non-convex optimization and prior structure.Reversing source sentences improved machine translation by 5.0 BLEU and constituency parsing by 0.5% absolute F1.
- Input order matters: Sorting convex-hull points by angle reduced task complexity from O(n log n) to O(n) and increased accuracy by up to 10% absolute.The ordering is input-dependent and made the models faster to train and better on the most challenging cases.
- Read, process, write: The proposed Read-Process-and-Write model reads elements into shared memory, repeatedly attends to them, and uses a pointer network to write outputs.Its process state is permutation invariant, and attention-based memory reads are unaffected by shuffling memory vectors.
- Read, process, write: The model processes input sets without assuming an input order, while its pointer-based write block selects input elements sequentially for combinatorial outputs.The architecture can also use an LSTM writer when outputs come from a fixed dictionary.
- Sorting experiment: In number sorting, Read-Process-and-Write outperformed the baseline once at least one processing step was allowed, while glimpses substantially improved both models.In the most challenging cases, adding attention before pointing more than doubled accuracy.
5 OUTPUT SETS
The paper shows that output ordering materially affects seq2seq performance, even when the chain rule permits any ordering in principle. It proposes learning favorable output orders for sets and demonstrates this across language modeling, parsing, sorting, and joint-probability estimation.
- 5.1.1 LANGUAGE MODELING: 86 perplexity was achieved by both natural and reverse word orderings, while 3-word reversal reached 96 perplexity.The 3-word reversal also raised training perplexity by 10 points, indicating difficulty modeling the scrambled structure.
- 5.1.2 PARSING: 89.5% F1 for depth-first parsing exceeded 81.5% F1 for breadth-first parsing.The breadth-first decoder often failed to produce valid trees, so its actual F1 was likely lower.
- 5.1.3 COMBINATORIAL PROBLEMS: Randomly permuted sorting outputs create n! valid configurations for one input, making the mapping statistically less efficient.When outputs were treated as unordered sets, convergence failed to match the same performance even for n as small as 5.
- 5.1.4 GRAPHICAL MODELS: The optimal ordering was easier to learn except with 20,000 training examples or nearly deterministic marginal distributions.In other settings, including varying numbers of variables and some marginal randomness, the optimal order consistently helped.
- 5 OUTPUT SETS: The proposed output-set approach searches over orderings during training so the model can learn an ordering that simplifies the task.The method targets p(Y_π(X)|X), but naive maximization can select a random ordering and remain stuck there.
- 5.2.1 5-GRAM MODELING: On 5-gram modeling, natural ordering achieved validation perplexity 225.2, whereas ordering (5, 1, 3, 4, 2) reached 280.With ordering search, the model settled on good orders and achieved final perplexity 225 without prior ordering knowledge.
6 CONCLUSION
The paper shows that ordering affects seq2seq performance and extends the framework to unordered input and output sets. It evaluates these approaches across sorting, graphical models, language modeling, and parsing.
- Order matters for seq2seq performance, even when input or output elements are unordered.
- The Read-Process-and-Write architecture handles unordered input data.
- An efficient training algorithm searches over possible output orders during training and inference.
- The proposed approaches are illustrated on sorting, graphical models, language modeling, and parsing experiments.