Active Ranking in Practice: General Ranking Functions with Sample Complexity Bounds
Kevin Jamieson, Robert D. Nowak · 2011
This paper examines the problem of ranking a collection of objects using pairwise comparisons (rankings of two objects). In a companion paper in the regular NIPS 2011 program [1], we showed that if each object x ∈ R d is assigned a score f(x) =||x − r| | for some unknown r ∈ R d, then our recently proposed active ranking algorithm can recover the ranking of the scores using about d log n selectively chosen pairwise comparisons. Here we show that this same model contains all functions of the type g(x) =w T x for some unknown w ∈ R d, thus the same bound applies. We take advantage of this fact and use kernel methods to represent more general ranking functions. This extension includes popular ranking methods such as RankSVM, and we derive nontrivial query complexity bounds for active versions of such algorithms. The efficacy of the theory and method are demonstrated by applying our kernelized adaptive algorithm to two real datasets. 1 Problem statement Given a set of n objects Θ: = {θ1,..., θn}, we wish to discover how an oracle ranks these objects.