Approximate ranking from pairwise comparisons


Reinhard Heckel, Max Simchowitz, Kannan Ramchandran, Martin Wainwright ;
Proceedings of the Twenty-First International Conference on Artificial Intelligence and Statistics, PMLR 84:1057-1066, 2018.


A common problem in machine learning is to rank a set of n items based on pairwise comparison. Here, ranking refers to partitioning the items into sets of pre-specified sizes according to theirs scores, which includes identification of the top-k items as the most prominent special case. The score of a given item is defined as the probability that it beats a randomly chosen other item. In practice, in particular when n is large, finding an exact ranking typically requires a prohibitively large number of comparisons. What comes to our rescue here is that in practice, one is usually content with finding an approximate ranking. In this paper we consider the problem of finding approximate rankings from pairwise comparisons. We analyze an active ranking algorithm that counts the number of comparisons won, and decides whether to stop or which pair of items to compare next, based on confidence intervals computed from the data collected in previous steps. We show that this algorithm succeeds in recovering approximate rankings using a number of comparisons that is close to optimal up to logarithmic factors. We also present numerical results, showing that in practice, approximation can drastically reduce the number of comparisons required to estimate a ranking.

Related Material