Aggregating Incomplete and Noisy Rankings
arXiv:2011.00810
Abstract
We consider the problem of learning the true ordering of a set of alternatives from largely incomplete and noisy rankings. We introduce a natural generalization of both the classical Mallows model of ranking distributions and the extensively studied model of noisy pairwise comparisons. Our selective Mallows model outputs a noisy ranking on any given subset of alternatives, based on an underlying Mallows distribution. Assuming a sequence of subsets where each pair of alternatives appears frequently enough, we obtain strong asymptotically tight upper and lower bounds on the sample complexity of learning the underlying complete ranking and the (identities and the) ranking of the top-k alternatives from selective Mallows rankings. Moreover, building on the work of (Braverman and Mossel, 2009), we show how to efficiently compute the maximum likelihood complete ranking from selective Mallows rankings.
arXiv comment21 pages, 3 figures. Minor changes and experimental results added in this version. Corresponding to the camera-ready version that appeared in the 24th International Conference on Artificial Intelligence and Statistics (AISTATS 2021)
References in corpus (9)
- Determining Possible and Necessary Winners Given Partial Orders
- Noisy Sorting Without Resampling
- Simple, Robust and Optimal Ranking from Pairwise Comparisons
- An Active Learning Algorithm for Ranking from Pairwise Preferences with an Almost Optimal Query Complexity
- Estimation from Pairwise Comparisons: Sharp Minimax Bounds with Topology Dependence
- A Maximum Likelihood Approach For Selecting Sets of Alternatives
- Minimax-optimal Inference from Partial Rankings
- Data-driven Rank Breaking for Efficient Rank Aggregation
- Optimal Learning of Mallows Block Model