Active Learning for Top-$K$ Rank Aggregation from Noisy Comparisons
We explore an active top-$K$ ranking problem based on pairwise comparisons that are collected possibly in a sequential manner as per our design choice. We consider two settings: (1) top-$K$ sorting in which the goal is to recover the top-$K$ items in order out of $n$ items; (2) top-$K$ partitioning where only the set of top-$K$ items is desired. Under a fairly general model which subsumes as special cases various models (e.g., Strong Stochastic Transitivity model, BTL model and uniform noise model), we characterize upper bounds on the sample size required for top-$K$ sorting as well as for top-$K$ partitioning. As a consequence, we demonstrate that active ranking can offer significant multiplicative gains in sample complexity over passive ranking. Depending on the underlying stochastic noise model, such gain varies from around $\frac{\log n}{\log \log n}$ to $\frac{ n^2 \log n }{\log \log n}$. We also present an algorithm that is applicable to both settings.
Code (1)
Tasks
Active LearningSimilar Papers 제목 키워드 기반
Adaptive Sampling for Heterogeneous Rank Aggregation from Noisy Pairwise Comparisons
In heterogeneous rank aggregation problems, users often exhibit various accuracy levels when comparing pairs of items. Thus a uniform querying strategy over users may not be optimal. To address this issue, we propose an …
A Nearly Instance Optimal Algorithm for Top-k Ranking under the Multinomial Logit Model
We study the active learning problem of top-$k$ ranking from multi-wise comparisons under the popular multinomial logit model. Our goal is to identify the top-$k$ items with high probability by adaptively querying sets f…
Active LearningRank Aggregation via Heterogeneous Thurstone Preference Models
We propose the Heterogeneous Thurstone Model (HTM) for aggregating ranked data, which can take the accuracy levels of different users into account. By allowing different noise distributions, the proposed HTM model mainta…
Bayesian Decision Process for Cost-Efficient Dynamic Ranking via Crowdsourcing
Rank aggregation based on pairwise comparisons over a set of items has a wide range of applications. Although considerable research has been devoted to the development of rank aggregation algorithms, one basic question i…
Sample Complexity Bounds for Active Ranking from Multi-wise Comparisons
We study the sample complexity (i.e., the number of comparisons needed) bounds for actively ranking a set of $n$ items from multi-wise comparisons. Here, a multi-wise comparison takes $m$ items as input and returns a (no…