An efficient reduction of ranking to classification

Nir Ailon, Mehryar Mohri

Research output: Contribution to conferencePaper

Abstract

This paper describes an efficient reduction of the learning problem of ranking to binary classification. The reduction is randomized and guarantees a pairwise misranking regret bounded by that of the binary classifier, improving on a recent result of Balcan et al. (2007) which ensures only twice that upper-bound. Moreover, our reduction applies to a broader class of ranking loss functions, admits a simple proof, and the expected time complexity of our algorithm in terms of number of calls to a classifier or preference function is also improved from Ω(n2) to O(nlogn). 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 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. To further complement them, we also derive lower bounds for any deterministic reduction of ranking to binary classification, proving that randomization is necessary to achieve our reduction guarantees.

Original languageEnglish (US)
Pages87-97
Number of pages11
StatePublished - 2008
Event21st Annual Conference on Learning Theory, COLT 2008 - Helsinki, Finland
Duration: Jul 9 2008Jul 12 2008

Other

Other21st Annual Conference on Learning Theory, COLT 2008
CountryFinland
CityHelsinki
Period7/9/087/12/08

ASJC Scopus subject areas

  • Education

Fingerprint Dive into the research topics of 'An efficient reduction of ranking to classification'. Together they form a unique fingerprint.

  • Cite this

    Ailon, N., & Mohri, M. (2008). An efficient reduction of ranking to classification. 87-97. Paper presented at 21st Annual Conference on Learning Theory, COLT 2008, Helsinki, Finland.