Source-linked AI summary
Ranking via Sinkhorn Propagation
Ryan Prescott Adams, Richard S. Zemel
TL;DR
Learning to rank is difficult because queries contain varying numbers of documents and direct optimization over permutations can become intractable. The paper represents rank-linear objectives with doubly-stochastic matrices, learns them through Sinkhorn normalization and backpropagation, and finds the approach generally competitive with state-of-the-art methods, with a substantial advantage on TD2003.
Problem
Ranking algorithms must handle varying numbers of query documents, while directly optimizing over permutations can quickly become intractable.
Method
The method represents rank-linear objectives using doubly-stochastic matrices and learns them by backpropagating through iterative Sinkhorn normalization.
Results
The Sinkhorn approach is generally competitive with state-of-the-art ranking methods and appears to offer a substantial advantage on TD2003.
Takeaways & Limitations
Expected rank-linear gains can be computed from doubly-stochastic marginals, enabling gradient-based learning of ranking functions through Sinkhorn propagation.
Takeaways & Limitations
The single-permutation procedure has no theoretical guarantees for global matching optimality and can behave pathologically when row-wise distributions are highly multimodal.
Abstract
from arXiv · showhide
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.
1. Introduction
Learning to rank is difficult because queries contain varying numbers of documents, permutation spaces grow rapidly, and ordering-based objectives are nondifferentiable. The paper addresses these challenges with differentiable doubly-stochastic relaxations and Sinkhorn-based gradient learning.
- Ranking learns to order query documents by relevance using labeled training queries and document features.
- Queries with different document counts create varying input domains and output-ordering sizes.
- Permutation spaces grow rapidly, making direct uncertainty-aware optimization intractable for larger queries.
- Ordering-based objectives are piecewise-constant in model parameters, so their training gains may lack usable gradients.
- The paper develops an end-to-end supervised gradient-based framework using doubly-stochastic matrices as differentiable permutation relaxations.
- Expected values of the paper’s rank-linear objectives are preserved under the doubly-stochastic interpretation.
- Backpropagation through incomplete Sinkhorn normalization enables learning and supports variable-sized queries and integration with other ranking methods.
2. Optimizing Expected Ranking Objectives via Doubly-Stochastic Matrices
The paper replaces permutation-based ranking objectives with differentiable expectations represented by doubly-stochastic matrices, whose entries encode consistent marginal rank distributions. This enables expected NDCG, precision, and rank-biased precision objectives while retaining permutation selection at test time.
- Ranking objectives: Ranking objectives identify good and bad document orderings using relevance labels, including NDCG@K, P@K, and RBP.
- Rank-linear objectives: Rank-linear objectives decompose into element-wise sums over permutation-matrix entries, making their expectations depend only on entry-wise marginal probabilities.
- Doubly-stochastic matrices: A doubly-stochastic matrix represents marginal probabilities that items occupy ranks, with every row and column summing to one.
- Expected objectives: These marginals define differentiable expected versions of NDCG@K, P@K, and RBP, and recover the original objectives when the matrix is a permutation matrix.
- Choosing a permutation: At test time, selecting a single ordering is a bipartite matching problem, with Hungarian-algorithm complexity O(J^3) and a faster top-P shortcut costing O(K^2+P^3).The shortcut sorts documents by expected rank, then applies matching only to the top P documents.
- Choosing a permutation: The shortcut has no theoretical optimality guarantee, but focuses expensive computation on top-ranked documents because metrics such as NDCG emphasize them.
3. Learning to Rank with Sinkhorn Gradients
SinkProp relaxes permutation outputs into doubly-stochastic matrices, applies iterative Sinkhorn normalization, and backpropagates gradients through incomplete normalization to train ranking functions.
- Differentiable ranking representation: Doubly-stochastic matrices replace permutation outputs as differentiable ranking representations.They are constrained only through nonnegative square matrices that are approximately normalized into the Birkhoff polytope.
- Sinkhorn normalization: Sinkhorn normalization repeatedly normalizes rows and columns to convert a nonnegative square matrix into a doubly-stochastic matrix.When the procedure converges, its output has unit row and column sums.
- Convergence: Sinkhorn convergence is guaranteed for most nonnegative matrices but can fail when zero patterns prevent conversion to a doubly-stochastic matrix.When entries lie in [1, V], O(V | log ϵ|) steps suffice to reach ϵ-near double stochasticity.
- Incomplete normalization: Incomplete Sinkhorn normalization uses finite iterations to define ranking objectives over nonnegative square matrices before full convergence.This permits approximately normalized matrices to be evaluated during training.
- Gradient propagation: SinkProp computes gradients with respect to the initial unnormalized matrix by backpropagating through row and column normalizations.The procedure supports arbitrary-depth incomplete Sinkhorn normalization combined with a rank-linear objective.
4. Parameterizing the Pre-Sinkhorn Matrix
The paper parameterizes pre-Sinkhorn matrices from shared document-level functions, offering distributional and smoothed-indicator constructions for variable-sized ranking problems.
- Framework: The framework defines functions that map variable-sized document sets to unconstrained nonnegative square pre-Sinkhorn matrices.These matrices are subsequently normalized within the ranking pipeline.
- Distributional construction: A distributional construction forms each matrix row by binning a row-specific cumulative probability distribution parameterized by φ(x_j).The method uses equally spaced bins and can employ beta, probit, or logit-logistic distributions.
- Distributional construction: Greater probability mass near zero indicates a stronger preference for the corresponding document to appear higher in the ranking.
- Smoothed indicators: A smoothed-indicator construction introduces document interactions through a matrix based on sorted φ(x_j) values.Its limits recover the implied permutation matrix as σ approaches zero and an all-ones matrix as σ approaches infinity.
- Function parameterization: The document-level function φ can be linear or implemented with deep neural networks and other function approximators.For linear inputs, the base case is φ(x) = W x.
5. Empirical Evaluation on LETOR Data
SinkProp was evaluated on seven LETOR 3.0 data sets using standard five-fold procedures, and its performance was generally competitive with established ranking baselines.
- Experimental setup: The evaluation used seven LETOR 3.0 data sets with five folds containing distinct training, validation, and test splits.
- Experimental setup: Training used the objective from Eq. (4), with K set to the number of documents in the largest query.The reported configuration achieved the best performance in the authors' experiments, similar to results reported in prior work.
- Experimental setup: The training data were resampled into smaller derived queries, with twenty queries generated per original query and document counts sampled up to 200.The derived-query document count followed a Poisson distribution whose mean was determined by the original query.
- Results: SinkProp was generally competitive with AdaRank, ListNet, SmoothRank, and basic regression across the seven data sets.Testing NDCG was plotted as a function of truncation level for comparison.
- Results: On TD2003, Sinkhorn normalization appeared to offer a substantial advantage over the compared approaches.
6. Related Work
SinkProp extends prior expected-gain ranking methods by incorporating Sinkhorn normalization directly into training rather than using it only as a test-time or partial procedure.
- Prior approaches: Earlier learning-to-rank methods used surrogate gains because target ranking measures were nondifferentiable.More recent methods instead optimized expectations of target evaluation measures under ranking distributions.
- Prior approaches: SoftRank, BoltzRank, and SmoothRank differ in how they estimate distributions over rankings.Their approximations use rank-binomial sampling, fixed sampled ranks, or a softmax over noisy model scores, respectively.
- SinkProp: SinkProp also optimizes expected ranking gain, with scaling concentrating rank-distribution mass on a small set that peaks at the model's selected test-time rank.
- Sinkhorn applications: Sinkhorn scaling has also been applied to constraint satisfaction, probabilistic belief matrices, matrix permanents, and regret-minimization settings.
- Distinction from prior work: Unlike SoftRank's test-time Sinkhorn balancing, SinkProp incorporates Sinkhorn normalization into objective optimization during training.SmoothRank is described as using only half a Sinkhorn step.
7. Discussion and Future Work
The paper presents SinkProp as a practical method for learning doubly-stochastic ranking representations by backpropagating through Sinkhorn normalization. It also identifies extensions to non-text retrieval and other structured-prediction problems.
- Rank-linear objectives can be evaluated exactly from marginal distributions represented by doubly-stochastic matrices in the Birkhoff polytope.
- SinkProp learns appropriate doubly-stochastic matrices by backpropagating gradients through iterative Sinkhorn normalization.
- The approach was demonstrated on seven information retrieval datasets.
- Future directions: Backpropagated rank-linear gradients could support retrieval of non-text documents, including image and speech applications.
- Future directions: Iterative projection operators may also apply to structured outputs such as matching and image correspondence tasks.
- Future directions: The rank-linearity idea may extend to other structured-prediction tasks with DSM-like representations.