Fast and Accurate Inference of Plackett-Luce Models

Lucas Maystre, Matthias GrossglauserNeurIPS 2015 · OpenReview

TL;DR

This paper reveals a deep connection between Maximum Likelihood (ML) estimation for Plackett-Luce ranking models and the stationary distribution of Markov chains. By leveraging this link, the authors introduce Luce Spectral Ranking (LSR) and its iterative counterpart (I-LSR), which provide significantly faster and more statistically efficient ways to aggregate rankings compared to traditional iterative and spectral methods.

What Problem Does This Paper Address?

How do you determine the "true" ranking of items when you only have partial, noisy data? This is a classic problem in sports ranking, econometrics, and recommendation systems. The Plackett-Luce model is the standard mathematical framework for this, generalizing the Bradley-Terry model (for pairs) to rankings of $k$ items.

The challenge lies in inference: finding the model parameters (item "strengths") that best explain the observed data. Existing methods fall into two camps:

  1. Iterative ML methods (like Hunter’s MM algorithm): These are the gold standard for accuracy but can be painfully slow to converge on large or sparse datasets.
  2. Spectral methods (like Rank Centrality): These are fast (one-pass) but often lose information by breaking complex rankings into simple pairs, leading to lower accuracy.

The authors aim to bridge this gap, creating an algorithm that is both as accurate as ML and as fast as spectral methods.

Methods

The core contribution is a mathematical proof showing that the optimality conditions for the Plackett-Luce log-likelihood are identical to the global balance equations of a specific Markov chain.

Based on this, they propose two algorithms:

Pseudocode for Luce Spectral Ranking (LSR) and Iterative LSR (I-LSR)
  • Luce Spectral Ranking (LSR): A non-iterative algorithm that constructs a transition matrix based on observed choices and finds its stationary distribution. Unlike previous spectral methods, LSR correctly weights transitions based on the size of the sets being compared, preserving more information from the original rankings.
  • Iterative LSR (I-LSR): By repeatedly updating the transition rates using the current estimate of item strengths, this algorithm is guaranteed to converge to the exact Maximum Likelihood estimate.

Datasets

The authors evaluated their approach on both synthetic data (to measure statistical efficiency) and five diverse real-world datasets:

  • NASCAR: Multiway partial rankings of drivers.
  • Sushi: Preferences over different types of sushi.
  • YouTube: Pairwise comparisons of video quality.
  • GIFGIF: Pairwise comparisons of emotions in GIFs.
  • Chess: Pairwise game outcomes (notably including ties, handled via an extension of the model).

Key Insights and Ideas

  • The Markov Chain Link: The core breakthrough is realizing that the odds of choosing item $i$ over item $j$ can be viewed as transition rates in a continuous-time Markov chain. The stationary distribution of this chain represents the relative "strengths" of the items.
  • Rank-Breaking is Lossy: Most spectral methods break a ranking (e.g., $A > B > C$) into independent pairs ($A>B, A>C, B>C$). The authors show this is statistically inefficient. LSR avoids this by treating the ranking as a sequence of choices, leading to much higher accuracy.
  • Robustness to Graph Structure: Traditional ML algorithms (MM) slow down significantly if the "comparison graph" (who was compared to whom) is sparse or poorly connected. I-LSR is shown to be much more robust to these structural properties, maintaining high speed even on "difficult" data.

Key Results

  • Superior Accuracy: On multiway ranking datasets (NASCAR, Sushi), LSR was nearly 4x more accurate than previous state-of-the-art spectral methods (GMM-F).
  • Massive Speedups: I-LSR reached the ML estimate consistently faster than the standard MM algorithm.
Performance comparison of I-LSR against MM and Newton methods across real-world datasets

As shown in the performance table above, on the YouTube dataset, I-LSR converged in just over 400 seconds, making it over 50 times faster than the MM algorithm (which took over 22,000 seconds).

  • Predictable Convergence: While the Newton-Raphson method often failed to converge on real-world data due to ill-conditioning, I-LSR converged reliably across all tests.

Limitations and Future Work

  • Choice Axiom Dependency: The method relies strictly on Luce’s choice axiom (the "Independence of Irrelevant Alternatives"). It cannot be directly applied to models that violate this, such as Thurstone’s model.
  • Connectivity Requirements: Like all Plackett-Luce inference, the comparison graph must be "strongly connected" (there must be a path of "wins" between any two items) for a unique solution to exist.
  • Future Directions: The authors suggest their stationary-distribution perspective could be extended to even broader classes of choice models, potentially simplifying inference for complex behavioral models.

Summary updated

Abstract

We show that the maximum-likelihood (ML) estimate of models derived from Luce's choice axiom (e.g., the Plackett-Luce model) can be expressed as the stationary distribution of a Markov chain. This conveys insight into several recently proposed spectral inference algorithms. We take advantage of this perspective and formulate a new spectral algorithm that is significantly more accurate than previous ones for the Plackett--Luce model. With a simple adaptation, this algorithm can be used iteratively, producing a sequence of estimates that converges to the ML estimate. The ML version runs faster than competing approaches on a benchmark of five datasets. Our algorithms are easy to implement, making them relevant for practitioners at large.
BibTeX
@inproceedings{maystre2015fast,
  author = {Lucas Maystre and Matthias Grossglauser},
  title = {{Fast and Accurate Inference of Plackett-Luce Models}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2015},
  url = {https://openreview.net/forum?id=SkVJMK-O-B},
}
Figure