# Efficient and Accurate Learning of Mixtures of Plackett-Luce Models

arXiv: https://arxiv.org/abs/2302.05343 · HTML: https://mlsanity.com/paper/2302.05343/

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 12 of its 50 references that are in the map.
- First posted on arXiv 10 Feb 2023.

## Builds on (most cited first, 12 of 12)

- [Statistical guarantees for the EM algorithm: From population to sample-based analysis](https://mlsanity.com/paper/1408.2156/) (2014)
- [Consistency of spectral clustering in stochastic block models](https://mlsanity.com/paper/1312.2050/) (2013)
- [Understanding predictive information criteria for Bayesian models](https://mlsanity.com/paper/1307.5928/) (2013)
- [Minimax-optimal Inference from Partial Rankings](https://mlsanity.com/paper/1406.5638/) (2014)
- [Learning Mixtures of Plackett-Luce Models](https://mlsanity.com/paper/1603.07323/) (2016)
- [Leave-one-out Singular Subspace Perturbation Analysis for Spectral Clustering](https://mlsanity.com/paper/2205.14855/) (2022)
- [Antithetic and Monte Carlo kernel estimators for partial rankings](https://mlsanity.com/paper/1807.00400/) (2018)
- [NIMFA: A Python Library for Nonnegative Matrix Factorization](https://mlsanity.com/paper/1808.01743/) (2018)
- [Learning Mixtures of Plackett-Luce Models from Structured Partial Orders](https://mlsanity.com/paper/1910.11721/) (2019)
- [Bayesian mixture of Plackett-Luce models for partially ranked data](https://mlsanity.com/paper/1501.03519/) (2015)
- [Composite Marginal Likelihood Methods for Random Utility Models](https://mlsanity.com/paper/1806.01426/) (2018)
- [Learning RUMs: Reducing Mixture to Single Component via PCA](https://mlsanity.com/paper/1812.11917/) (2018)

## Built on by (most cited first, 3 of 3)

- [Estimation of partial rankings from sparse, noisy comparisons](https://mlsanity.com/paper/2501.02505/) (2025)
- [Sharp analysis of EM for learning mixtures of pairwise differences](https://mlsanity.com/paper/2302.10066/) (2023)
- [When the Universe is Too Big: Bounding Consideration Probabilities for Plackett-Luce Rankings](https://mlsanity.com/paper/2401.11016/) (2024)

## Abstract (arXiv)

Mixture models of Plackett-Luce (PL) -- one of the most fundamental ranking models -- are an active research area of both theoretical and practical significance. Most previously proposed parameter estimation algorithms instantiate the EM algorithm, often with random initialization. However, such an initialization scheme may not yield a good initial estimate and the algorithms require multiple restarts, incurring a large time complexity. As for the EM procedure, while the E-step can be performed efficiently, maximizing the log-likelihood in the M-step is difficult due to the combinatorial nature of the PL likelihood function (Gormley and Murphy 2008). Therefore, previous authors favor algorithms that maximize surrogate likelihood functions (Zhao et al. 2018, 2020). However, the final estimate may deviate from the true maximum likelihood estimate as a consequence. In this paper, we address these known limitations. We propose an initialization algorithm that can provide a provably accurate initial estimate and an EM algorithm that maximizes the true log-likelihood function efficiently. Experiments on both synthetic and real datasets show that our algorithm is competitive in terms of accuracy and speed to baseline algorithms, especially on datasets with a large number of items.