Preference-Based Learning to Rank
Machine Learning Journal, vol. 8 (2010), pp. 189-211
Nir Ailon, Mehryar Mohri
Our algorithm is randomized, but we prove a lower bound for any deterministic reduction of ranking to binary classiﬁcation showing that randomization is necessary to achieve our guarantees. This, and a recent result by Balcan et al., who show a regret bound of two for a deterministic algorithm in the bipartite case, suggest a trade-off between achieving low regret and determinism in this context. Our reduction also admits an improved running time guarantee with respect to that deterministic algorithm. In particular, the number of calls to the preference function in the reduction is improved from Ω(n^2) to O(n log n). In addition, when the top k ranked elements only are required (k≪n), as in many applications in information extraction or search engine design, the time complexity of our algorithm can be further reduced to O(k log k+n). Our algorithm is thus practical for realistic applications where the number of points to rank exceeds several thousand.