ML Anthology

Robust Reductions from Ranking to Classification

Maria-Florina Balcan, Nikhil Bansal, Alina Beygelzimer, Don Coppersmith, John Langford, Gregory B. Sorkin
COLT 2007 pp. 604-619
doi:10.1007/978-3-540-72927-3_43 /colt/2007/balcan2007colt-robust/

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 2 r . This is a large improvement over approaches such as ordering according to regressed scores, which have a regret transform of r ↦ nr where n is the number of elements.

PDF COLT Semantic Scholar

Cite

Text

Balcan et al. "Robust Reductions from Ranking to Classification." Annual Conference on Computational Learning Theory, 2007. doi:10.1007/978-3-540-72927-3_43

Markdown

[Balcan et al. "Robust Reductions from Ranking to Classification." Annual Conference on Computational Learning Theory, 2007.](https://mlanthology.org/colt/2007/balcan2007colt-robust/) doi:10.1007/978-3-540-72927-3_43

BibTeX

@inproceedings{balcan2007colt-robust,
  title     = {{Robust Reductions from Ranking to Classification}},
  author    = {Balcan, Maria-Florina and Bansal, Nikhil and Beygelzimer, Alina and Coppersmith, Don and Langford, John and Sorkin, Gregory B.},
  booktitle = {Annual Conference on Computational Learning Theory},
  year      = {2007},
  pages     = {604-619},
  doi       = {10.1007/978-3-540-72927-3_43},
  url       = {https://mlanthology.org/colt/2007/balcan2007colt-robust/}
}