Learning Latent Permutations with Gumbel-Sinkhorn Networks

By Gonzalo E. Mena, David Belanger, Scott W. Linderman, Jasper Snoek. International Conference on Learning Representations, 2018

344 citations recorded by the source corpus.

Permutations and matchings are core building blocks in a variety of latent variable models, as they allow us to align, canonicalize, and sort data. Learning in such models is difficult, however, because exact marginalization over these combinatorial objects is intractable. In response, this paper introduces a collection of new methods for end-to-end learning in such models that approximate discrete maximum-weight matching using the continuous Sinkhorn operator. Sinkhorn iteration is attractive because it functions as a simple, easy-to-implement analog of the softmax operator. With this, we can define the Gumbel-Sinkhorn method, an extension of the Gumbel-Softmax method (Jang et al. 2016, Maddison2016 et al. 2016) to distributions over latent matchings. We demonstrate the effectiveness of our method by outperforming competitive baselines on a range of qualitatively different tasks: sorting numbers, solving jigsaw puzzles, and identifying neural signals in worms.

Subfields: Artificial Intelligence, Computer Vision and Pattern Recognition

View Paper: https://www.semanticscholar.org/paper/23deae1e548bc055c8920fc8529e59bba0816685

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 Computer Vision and Pattern Recognition

Citations in the corpus

Git Re-Basin: Merging Models modulo Permutation Symmetries (2022, unknown): “Akin to differentiable permutation learning, many prior works have studied differentiable sorting (Grover et al., 2019; Prillo & Eisenschlos, 2020; Cuturi et al., 2019; Petersen et al., 2022; 2021; Mena et al., 2018).”
Sparse Sinkhorn Attention (2020, methodology): “While differentiable neural-based sorting has demonstrated some proof-of-concept promise (Mena et al., 2018), this work demonstrates the ﬁrst successful application in real large-scale problems.”
Rethinking Search: Making Experts out of Dilettantes (2021, background): “phenomena), and large pre-trained language models (LMs) [10, 54, 69] (which can capture information about the relationship between entities).”
SparseMAP: Differentiable Sparse Structured Inference (2018, background): “A popular approach for differentiable permutation learning involves mean-entropic optimal transport relaxations (Adams & Zemel, 2011; Mena et al., 2018).”
BCD Nets: Scalable Variational Approaches for Bayesian Causal Discovery (2021, methodology): “A proof of this fact is given in the appendix of [31].”
PRNet: Self-Supervised Learning for Partial-to-Partial Registration (2019, methodology): “One possible extension of our work to address this issue is to use Gumbel–Sinkhorn [72] to encourage bijectivity.”
Insertion-based Decoding with Automatically Inferred Generation Order (2019, methodology): “For future work, it is worth exploring a trainable inference model to directly predict the permutation (Mena et al., 2018) instead of beam-search.”
Gradient Estimation with Stochastic Softmax Tricks (2020, methodology): “When choosing Gumbel utilities, this recovers Gumbel-Sinkhorn [57].”
A Case for Object Compositionality in Deep Generative Models of Images (2018, background): “Although in principle the relational mechanism may account for this distinction, a more explicit mechanism may be preferred (Mena et al., 2018).”
Kaleidoscope: An Efficient, Learnable Representation For All Structured Linear Maps (2020, methodology): “Techniques to obtain posterior distributions over permutations have been developed, such as the exponential weights algorithm (Helmbold & Warmuth, 2009) and the Gumbel-Sinkhorn network (Mena et al., 2018).”
Learning Fast Algorithms for Linear Transforms Using Butterfly Factorizations (2019, unknown): “Attempts to learn general algorithms such as matching (Mena et al., 2018), sorting (Grover et al.”
Unbiased Gradient Estimation with Balanced Assignments for Mixtures of Experts (2021, methodology): “The Sinkhorn algorithm is a direct extension of the softmax function, which solves a soft (entropy-regularized) version of the assignment problem [6, 30, 29].”
Deep Set Prediction Networks (2019, background): “Methods like [16] and [31] learn to predict a permutation matrix for a set (set-to-set-of-position-assignments).”
FSPool: Learning Set Representations with Featurewise Sort Pooling (2019, background): “Instead of numerically sorting, Mena et al. (2018) and Zhang et al. (2019b) learn an ordering of set elements instead.”
Modeling Point Clouds With Self-Attention and Gumbel Subset Sampling (2019, background): “Optimization on the Gumbel Softmax distribution could be interpreted as solving a certain entropy-regularized linear program on the probability simplex [27].”
Seq2Slate: Re-ranking and Slate Optimization with RNNs (2018, methodology): “Followup work has focused on improved training and inference procedures, including a Gumbel softmax distribution to enable efficient learning [Mena et al., 2018], a reparameterization of the Birkhoff Polytope for variational inference [Linderman et al.”
Stochastic Optimization of Sorting Networks via Continuous Relaxations (2019, methodology): “Mena et al. (2018) propose an alternate method where the square matrix deﬁnes a latent distribution over the doubly-stochastic matrices themselves.”