Order Matters: Sequence to sequence for sets

By Oriol Vinyals, Samy Bengio, Manjunath Kudlur. 2015

1,043 citations recorded by the source corpus.

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.

Subfields: Artificial Intelligence, Model Architectures

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Model Architectures

Citations in the corpus

End-to-End Object Detection with Transformers (2020, methodology): “A general approach is to use auto-regressive sequence models such as recurrent neural networks [48].”
Matching Networks for One Shot Learning (2016, methodology): “More generally, these architectures model P (B|A) where A and/or B can be a sequence (like in seq2seq models), or, more interestingly for us, a set [26].”
Adaptive Computation Time for Recurrent Neural Networks (2016, positive): “The evidence that increased depth leads to more performant networks is by now inarguable [5, 4, 19, 9], and recent results show that increased sequence length can be similarly beneficial [31, 33, 25].”
Deep Perm-Set Net: Learn to predict sets with unknown permutation and cardinality using deep neural networks (2018, background): “Set learning using deep networks is an emerging field of study that has generated substantial interest very recently Rezatofighi et al. (2017; 2018); Vinyals et al. (2015); Zaheer et al. (2017).”
DeepSetNet: Predicting Sets with Deep Neural Networks (2016, methodology): “First, the output represents a sequence and is thus highly dependent on the prediction order, as was shown recently by Vinyals et al. [34].”
Density estimation using Real NVP (2016, background): “The ordering of the dimensions, although often arbitrary, can be critical to the training of the model [66].”
PointNet: Deep Learning on Point Sets for 3D Classification and Segmentation (2016, methodology): “The attention method is similar to that in [22], where a scalar score is predicted from each point feature, then the score is normalized across points by computing a softmax.”
Multiset-Equivariant Set Prediction with Approximate Implicit Differentiation (2021, background): “As we have covered in this paper, most existing set predictors are either not multiset-equivariant (Vinyals et al., 2016; Stewart & Andriluka, 2016; Vaswani et al., 2017; Achlioptas et al., 2018; Li et al., 2018; Rezatoﬁghi et al., 2020) or set-equivariant (Lee et al., 2019; Locatello et al., 2020;…”
Neural Message Passing for Quantum Chemistry (2017, methodology): “Second is a set2set model from Vinyals et al. (2015).”
PointNet++: Deep Hierarchical Feature Learning on Point Sets in a Metric Space (2017, background): “A few very recent works [20; 28] have studied how to apply deep learning to unordered sets.”
Fast Graph Representation Learning with PyTorch Geometric (2019, methodology): “We additionaly oﬀer more sophisticated methods such as set-to-set (Vinyals et al., 2016), sort pooling (Zhang et al., 2018) or the global soft attention layer from Li et al. (2016).”
Towards a Neural Statistician (2016, background): “Set2Seq A highly related work is Vinyals et al. [31] where they explore architectures for mapping sets to sequences.”
Set Transformer (2018, background): “Other problems such as 3D shape recognition (Wu et al., 2015; Shi et al., 2015; Su et al., 2015; Charles et al., 2017), sequence ordering (Vinyals et al., 2016), and various set operations (Muandet et al., 2012; Oliva et al., 2013; Edwards & Storkey, 2017; Zaheer et al., 2017) can also be viewed as…”
Deep Graph Infomax (2018, methodology): “…readout to perform the best across all our experiments, we assume that its power will diminish with the increase in graph size, and in those cases, more sophisticated readout architectures such as set2vec (Vinyals et al., 2015) or DiffPool (Ying et al., 2018b) are likely to be more appropriate.”
Hierarchical Graph Representation Learning with Differentiable Pooling (2018, methodology): “• SET2SET replaces the global mean-pooling in the traditional GNN architectures by the aggregation used in SET2SET [37].”
Set2Graph: Learning Graphs From Sets (2020, methodology): “Earlier methods such as [34] used non-equivariant methods to learn set functions.”
GraphVAE: Towards Generation of Small Graphs Using Variational Autoencoders (2018, neutral): “This is conceptually similar to the approach for learning to output unordered sets by (Vinyals et al., 2015), where the closest ordering of the training data is sought.”
Graph Networks as a Universal Machine Learning Framework for Molecules and Crystals (2018, methodology): “In this work, the order-invariant set2set model 43 that embeds a set of vectors into one vector is applied on both atomic and bond attributes sets.”
Few-Shot Learning with Metric-Agnostic Conditional Embeddings (2018, background): “Matching networks take advantage of the set-to-set framework with an attention kernel over images in S k (Vinyals et al., 2015; 2016).”