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

Onderzoeksoutput: Hoofdstuk in Boek/Rapport/Congresprocedure › Conferentiebijdrage › Academic › peer review

16 Citaten (Scopus)

Samenvatting

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.

Originele taal-2	Engels
Titel	Learning theory (20th Annual Conference, COLT 2007, San Diego CA, USA, June 13–15, 2007. Proceedings)
Redacteuren	N.H. Bshouty, C. Gentile
Plaats van productie	Berlin
Uitgeverij	Springer
Pagina's	604-619
ISBN van geprinte versie	978-3-540-72925-9
DOI's	https://doi.org/10.1007/978-3-540-72927-3_43
Status	Gepubliceerd - 2007

Publicatie series

Naam	Lecture Notes in Computer Science
Volume	4539
ISSN van geprinte versie	0302-9743

Toegang tot document

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

Citeer dit

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 (editors), Learning theory (20th Annual Conference, COLT 2007, San Diego CA, USA, June 13–15, 2007. Proceedings) (blz. 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 \textbackslash{}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 (reds.), 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, blz. 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. et al.
Learning theory (20th Annual Conference, COLT 2007, San Diego CA, USA, June 13–15, 2007. Proceedings). reds. / N.H. Bshouty; C. Gentile. Berlin: Springer, 2007. blz. 604-619 (Lecture Notes in Computer Science; Vol. 4539).

Onderzoeksoutput: Hoofdstuk in Boek/Rapport/Congresprocedure › Conferentiebijdrage › 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, redacteurs, Learning theory (20th Annual Conference, COLT 2007, San Diego CA, USA, June 13–15, 2007. Proceedings). Berlin: Springer. 2007. blz. 604-619. (Lecture Notes in Computer Science). doi: 10.1007/978-3-540-72927-3_43

Robust reductions from ranking to classification

Samenvatting

Publicatie series

Toegang tot document

Vingerafdruk

Citeer dit