Active Ranking using Pairwise Comparisons

Abstract

This paper examines the problem of ranking a collection of objects using pairwise comparisons (rankings of two objects). In general, the ranking of $n$ objects can be identified by standard sorting methods using $nlo{g}_{2}n$ pairwise comparisons. We are interested in natural situations in which relationships among the objects may allow for ranking using far fewer pairwise comparisons. Specifically, we assume that the objects can be embedded into a $d$-dimensional Euclidean space and that the rankings reflect their relative distances from a common reference point in $R^d$. We show that under this assumption the number of possible rankings grows like $n^{2d}$ and demonstrate an algorithm that can identify a randomly selected ranking using just slightly more than $dlogn$ adaptively selected pairwise comparisons, on average. If instead the comparisons are chosen at random, then almost all pairwise comparisons must be made in order to identify any ranking. In addition, we propose a robust, error-tolerant algorithm that only requires that the pairwise comparisons are probably correct. Experimental studies with synthetic and real datasets support the conclusions of our theoretical analysis.

17 pages, an extended version of our NIPS 2011 paper. The new version revises the argument of the robust section and slightly modifies the result there to give it more impact

Cited by in corpus (30)

• Spectral MLE: Top-$K$ Rank Aggregation from Pairwise Comparisons
• Collaborative 20 Questions for Target Localization
• Estimation from Pairwise Comparisons: Sharp Minimax Bounds with Topology Dependence
• A practical guide and software for analysing pairwise comparison experiments
• Hybrid-MST: A Hybrid Active Sampling Strategy for Pairwise Preference Aggregation
• Data-driven Rank Breaking for Efficient Rank Aggregation
• Weak similarities of finite ultrametric and semimetric spaces
• Lagrangian Inference for Ranking Problems
• Top-$K$ Ranking from Pairwise Comparisons: When Spectral Ranking is Optimal
• Minimax Rates and Efficient Algorithms for Noisy Sorting
• Learning Combinatorial Functions from Pairwise Comparisons
• Worst-case vs Average-case Design for Estimation from Fixed Pairwise Comparisons
• Sync-Rank: Robust Ranking, Constrained Ranking and Rank Aggregation via Eigenvector and Semidefinite Programming Synchronization
• Individualized Rank Aggregation using Nuclear Norm Regularization
• Active Ranking from Pairwise Comparisons and when Parametric Assumptions Don't Help
• Analysis of Crowdsourced Sampling Strategies for HodgeRank with Sparse Random Graphs
• Actively Learning Hemimetrics with Applications to Eliciting User Preferences
• Ranking over Regression for Bayesian Optimization and Molecule Selection
• APRIL: Interactively Learning to Summarise by Combining Active Preference Learning and Reinforcement Learning
• A Nearly Instance Optimal Algorithm for Top-k Ranking under the Multinomial Logit Model
• Bayesian Decision Process for Cost-Efficient Dynamic Ranking via Crowdsourcing
• Dueling Bandits with Dependent Arms
• Extremal properties and morphisms of finite ultrametric spaces and their representing trees
• Noise-Tolerant Interactive Learning from Pairwise Comparisons
• Robust Ordinal Embedding from Contaminated Relative Comparisons
• Accurate, Data-Efficient Learning from Noisy, Choice-Based Labels for Inherent Risk Scoring
• Dueling Bandits With Weak Regret
• Learning from Noisy Similar and Dissimilar Data
• Adaptive Questionnaires for Direct Identification of Optimal Product Design
• Rank-Regret Minimization