Title: An Efficient Reduction of Ranking to Classification 


(NYU-CS-TR903)

Authors: Nir Ailon and Mehryar Mohri 

Abstract:
This paper describes an efficient reduction of the learning  problem of
ranking to binary classification. As with a recent result of Balcan et
al. (2007), the reduction guarantees an average pairwise misranking 
regret of at most $2r$ using a binary classifier with regret $r$. 
However, our reduction applies to a broader class of ranking loss 
functions, admits a simpler proof, and the expected running time 
complexity of our algorithm in terms of number of calls to a classifier
or preference function is improved from $\Omega(n2)$ to $O(n \log n)$.
Furthermore, when the top $k$ ranked elements only are required 
($k \ll n$), as in many applications in information extraction or 
search engines, the time complexity of our algorithm can be further
reduced to $O(k \log k + n)$. Our reduction and algorithm are thus 
practical for realistic applications where the number of points to rank
exceeds several thousands. Much of our results also extend beyond the 
bipartite case previously studied.