Robust reductions from ranking to classification

M.F. Balcan, N. Bansal, A. Beygelzimer, D. Coppersmith, J. Langford, G.B. Sorkin

    Research output: Contribution to journalArticleAcademicpeer-review

    36 Citations (Scopus)

    Abstract

    We reduce ranking, as measured by the Area Under the Receiver Operating Characteristic Curve (AUC), to binary classification. The core theorem shows that a binary classification regret of r on the induced binary problem implies an AUC regret of at most 2r. This is a large improvement over approaches such as ordering according to regressed scores, which have a regret transform of r bar right arrow nr where n is the number of elements.
    Original languageEnglish
    Pages (from-to)139-153
    JournalMachine Learning
    Volume72
    Issue number1-2
    DOIs
    Publication statusPublished - 2008

    Cite this