Ranking via Sinkhorn Propagation
arXiv:1106.1925
Abstract
It is of increasing importance to develop learning methods for ranking. In contrast to many learning objectives, however, the ranking problem presents difficulties due to the fact that the space of permutations is not smooth. In this paper, we examine the class of rank-linear objective functions, which includes popular metrics such as precision and discounted cumulative gain. In particular, we observe that expectations of these gains are completely characterized by the marginals of the corresponding distribution over permutation matrices. Thus, the expectations of rank-linear objectives can always be described through locations in the Birkhoff polytope, i.e., doubly-stochastic matrices (DSMs). We propose a technique for learning DSM-based ranking functions using an iterative projection operator known as Sinkhorn normalization. Gradients of this operator can be computed via backpropagation, resulting in an algorithm we call Sinkhorn propagation, or SinkProp. This approach can be combined with a wide range of gradient-based approaches to rank learning. We demonstrate the utility of SinkProp on several information retrieval data sets.
Submitted
References in corpus (1)
Cited by in corpus (34)
- Sparse Sinkhorn Attention
- A robust anomaly finder based on autoencoders
- Deep Graph Matching Consensus
- Learning with Differentiable Perturbed Optimizers
- Seq2Slate: Re-ranking and Slate Optimization with RNNs
- Learning Permutations with Sinkhorn Policy Gradient
- Stochastic Optimization of Sorting Networks via Continuous Relaxations
- Neural Graph Matching Network: Learning Lawler's Quadratic Assignment Problem with Extension to Hypergraph and Multiple-graph Matching
- GLMNet: Graph Learning-Matching Networks for Feature Matching
- Gradient Estimation with Stochastic Softmax Tricks
- DiffPrep: Differentiable Data Preprocessing Pipeline Search for Learning over Tabular Data
- Auto-labelling of Markers in Optical Motion Capture by Permutation Learning
- Scalable Optimal Transport Methods in Machine Learning: A Contemporary Survey
- Deep multi-class learning from label proportions
- The Limited Multi-Label Projection Layer
- Fast Differentiable Sorting and Ranking
- Differentiable Ranks and Sorting using Optimal Transport
- Spotting Virus from Satellites: Modeling the Circulation of West Nile Virus Through Graph Neural Networks
- Learning Representations of Sets through Optimized Permutations
- Backpropagation of Unrolled Solvers with Folded Optimization
- Learning Index Selection with Structured Action Spaces
- Deep graph matching meets mixed-integer linear programming: Relax at your own risk ?
- Learning Functions over Sets via Permutation Adversarial Networks
- Learning Randomly Perturbed Structured Predictors for Direct Loss Minimization
- Mapping in a cycle: Sinkhorn regularized unsupervised learning for point cloud shapes
- COMET: Learning Cardinality Constrained Mixture of Experts with Trees and Local Search
- Foresight of Graph Reinforcement Learning Latent Permutations Learnt by Gumbel Sinkhorn Network
- Improved Structural Discovery and Representation Learning of Multi-Agent Data
- Differentiable Sorting Networks for Scalable Sorting and Ranking Supervision
- Learning to Represent and Predict Sets with Deep Neural Networks
- From Alignment to Assignment: Frustratingly Simple Unsupervised Entity Alignment
- Set Cross Entropy: Likelihood-based Permutation Invariant Loss Function for Probability Distributions
- Unbiased Gradient Estimation with Balanced Assignments for Mixtures of Experts
- Deep Graph Matching under Quadratic Constraint