Robust reductions from ranking to classification

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

doi:10.1007/978-3-540-72927-3_43

Robust reductions from ranking to classification

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

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

16 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 \mapsto nr$ where n is the number of elements.

Original language	English
Title of host publication	Learning theory (20th Annual Conference, COLT 2007, San Diego CA, USA, June 13–15, 2007. Proceedings)
Editors	N.H. Bshouty, C. Gentile
Place of Publication	Berlin
Publisher	Springer
Pages	604-619
ISBN (Print)	978-3-540-72925-9
DOIs	https://doi.org/10.1007/978-3-540-72927-3_43
Publication status	Published - 2007

Publication series

Name	Lecture Notes in Computer Science
Volume	4539
ISSN (Print)	0302-9743

Access to Document

10.1007/978-3-540-72927-3_43

Cite this

Balcan, M. F., Bansal, N., Beygelzimer, A., Coppersmith, D., Langford, J., & Sorkin, G. B. (2007). Robust reductions from ranking to classification. In N. H. Bshouty, & C. Gentile (Eds.), Learning theory (20th Annual Conference, COLT 2007, San Diego CA, USA, June 13–15, 2007. Proceedings) (pp. 604-619). (Lecture Notes in Computer Science; Vol. 4539). Springer. https://doi.org/10.1007/978-3-540-72927-3_43

@inproceedings{aabef62b00e045b592ecb20e3b6b8e26,

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 \mapsto 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 = "2007",

doi = "10.1007/978-3-540-72927-3_43",

language = "English",

isbn = "978-3-540-72925-9",

series = "Lecture Notes in Computer Science",

publisher = "Springer",

pages = "604--619",

editor = "N.H. Bshouty and C. Gentile",

booktitle = "Learning theory (20th Annual Conference, COLT 2007, San Diego CA, USA, June 13–15, 2007. Proceedings)",

address = "Germany",

}

Balcan, MF, Bansal, N, Beygelzimer, A, Coppersmith, D, Langford, J & Sorkin, GB 2007, Robust reductions from ranking to classification. in NH Bshouty & C Gentile (eds), Learning theory (20th Annual Conference, COLT 2007, San Diego CA, USA, June 13–15, 2007. Proceedings). Lecture Notes in Computer Science, vol. 4539, Springer, Berlin, pp. 604-619. https://doi.org/10.1007/978-3-540-72927-3_43

Robust reductions from ranking to classification. / Balcan, M.F.; Bansal, N.; Beygelzimer, A.; Coppersmith, D.; Langford, J.; Sorkin, G.B.

Learning theory (20th Annual Conference, COLT 2007, San Diego CA, USA, June 13–15, 2007. Proceedings). ed. / N.H. Bshouty; C. Gentile. Berlin : Springer, 2007. p. 604-619 (Lecture Notes in Computer Science; Vol. 4539).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

TY - GEN

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 - 2007

Y1 - 2007

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 \mapsto 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 \mapsto nr$ where n is the number of elements.

U2 - 10.1007/978-3-540-72927-3_43

DO - 10.1007/978-3-540-72927-3_43

M3 - Conference contribution

SN - 978-3-540-72925-9

T3 - Lecture Notes in Computer Science

SP - 604

EP - 619

BT - Learning theory (20th Annual Conference, COLT 2007, San Diego CA, USA, June 13–15, 2007. Proceedings)

A2 - Bshouty, N.H.

A2 - Gentile, C.

PB - Springer

CY - Berlin

ER -

Balcan MF, Bansal N, Beygelzimer A, Coppersmith D, Langford J, Sorkin GB. Robust reductions from ranking to classification. In Bshouty NH, Gentile C, editors, Learning theory (20th Annual Conference, COLT 2007, San Diego CA, USA, June 13–15, 2007. Proceedings). Berlin: Springer. 2007. p. 604-619. (Lecture Notes in Computer Science). https://doi.org/10.1007/978-3-540-72927-3_43

Robust reductions from ranking to classification

Abstract

Publication series

Access to Document

Fingerprint

Cite this