Active top-K ranking from noisy comparisons

摘要

We explore the active top-K sorting problem, in which the goal is to recover the top-K items in order out of n items, from adaptive pairwise comparisons that are collected possibly in a sequential manner as per our design choice. 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 an upper bound on the sample size required for reliable top-K sorting. 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 log n/log log n to n2 log n/log log n. We also present an algorithm that runs linearly in n and which achieves the sample complexity bound. Our theoretical findings are corroborated via numerical experiments.