Learning to Top-K Search using Pairwise Comparisons

Given a collection of N items with some un-known underlying ranking, we examine how to use pairwise comparisons to determine the top ranked items in the set. Resolving the top items from pairwise comparisons has ap-plication in diverse elds ranging from rec-ommender systems to image-based search to protein structure analysis. In this paper we introduce techniques to resolve the top ranked items using signicantly fewer than all the possible pairwise comparisons using both random and adaptive sampling method-ologies. Using randomly-chosen comparisons, a graph-based technique is shown to e-ciently resolve the top O (logN) items when there are no comparison errors. In terms of adaptively-chosen comparisons, we show how the top O (logN) items can be found, even in the presence of corrupted observations, us-ing a voting methodology that only require