Robust reductions from ranking to classification

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

doi:10.1007/s10994-008-5058-6

Robust reductions from ranking to classification

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

Research output: Contribution to journal › Article › Academic › peer-review

39 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 language	English
Pages (from-to)	139-153
Journal	Machine Learning
Volume	72
Issue number	1-2
DOIs	https://doi.org/10.1007/s10994-008-5058-6
Publication status	Published - 2008

Access to Document

10.1007/s10994-008-5058-6

Cite this

@article{bab7dc94c63a4762839c35798d94ac78,

title = "Robust reductions from ranking to classification",

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.",

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

year = "2008",

doi = "10.1007/s10994-008-5058-6",

language = "English",

volume = "72",

pages = "139--153",

journal = "Machine Learning",

issn = "0885-6125",

publisher = "Springer",

number = "1-2",

}

TY - JOUR

T1 - Robust reductions from ranking to classification

AU - Balcan, M.F.

AU - Bansal, N.

AU - Beygelzimer, A.

AU - Coppersmith, D.

AU - Langford, J.

AU - Sorkin, G.B.

PY - 2008

Y1 - 2008

N2 - 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.

AB - 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.

U2 - 10.1007/s10994-008-5058-6

DO - 10.1007/s10994-008-5058-6

M3 - Article

SN - 0885-6125

VL - 72

SP - 139

EP - 153

JO - Machine Learning

JF - Machine Learning

IS - 1-2

ER -

Robust reductions from ranking to classification

Abstract

Access to Document

Fingerprint

Cite this