An Active Learning Algorithm for Ranking from Pairwise Preferences with an Almost Optimal Query Complexity

Abstract

We study the problem of learning to rank from pairwise preferences, and solve a long-standing open problem that has led to development of many heuristics but no provable results for our particular problem. Given a set $V$ of $n$ elements, we wish to linearly order them given pairwise preference labels. A pairwise preference label is obtained as a response, typically from a human, to the question "which if preferred, u or v?$fortwoelements$u,v\in V$.Weassumepossiblenon-transitivityparadoxeswhichmayarisenaturallyduetohumanmistakesorirrationality.Thegoalistolinearlyordertheelementsfromthemostpreferredtotheleastpreferred,whiledisagreeingwithasfewpairwisepreferencelabelsaspossible.Ourperformanceismeasuredbytwoparameters:Thelossandthequerycomplexity(numberofpairwisepreferencelabelsweobtain).Thisisatypicallearningproblem,withtheexceptionthatthespacefromwhichthepairwisepreferencesisdrawnisfinite,consistingof${n\choose 2}$ possibilities only. We present an active learning algorithm for this problem, with query bounds significantly beating general (non active) bounds for the same error guarantee, while almost achieving the information theoretical lower bound. Our main construct is a decomposition of the input s.t. (i) each block incurs high loss at optimum, and (ii) the optimal solution respecting the decomposition is not much worse than the true opt. The decomposition is done by adapting a recent result by Kenyon and Schudy for a related combinatorial optimization problem to the query efficient setting. We thus settle an open problem posed by learning-to-rank theoreticians and practitioners: What is a provably correct way to sample preference labels? To further show the power and practicality of our solution, we show how to use it in concert with an SVM relaxation.

Fixed a tiny error in theorem 3.1 statement

References in corpus (1)

• Noisy Sorting Without Resampling

Cited by in corpus (19)

• Asking Easy Questions: A User-Friendly Approach to Active Reward Learning
• Batch Active Preference-Based Learning of Reward Functions
• Towards Black-box Iterative Machine Teaching
• Active Learning Using Smooth Relative Regret Approximations with Applications
• Analysis of Crowdsourced Sampling Strategies for HodgeRank with Sparse Random Graphs
• PAC Ranking from Pairwise and Listwise Queries: Lower Bounds and Upper Bounds
• Boosting the Learning for Ranking Patterns
• Here's What I've Learned: Asking Questions that Reveal Reward Learning
• Efficient Portfolio Selection through Preference Aggregation with Quicksort and the Bradley--Terry Model
• Bayesian Decision Process for Cost-Efficient Dynamic Ranking via Crowdsourcing
• Two-Sample Testing on Ranked Preference Data and the Role of Modeling Assumptions
• Bayes-Optimal Entropy Pursuit for Active Choice-Based Preference Learning
• Active Learning Methods based on Statistical Leverage Scores
• Arena Model: Inference About Competitions
• Fast Adaptive Algorithm for Robust Evaluation of Quality of Experience
• A Multiresolution Analysis Framework for the Statistical Analysis of Incomplete Rankings
• Aggregating Incomplete and Noisy Rankings
• ROIAL: Region of Interest Active Learning for Characterizing Exoskeleton Gait Preference Landscapes
• On the Sample Complexity of Rank Regression from Pairwise Comparisons