Robust reductions from ranking to classification
Balcan, M., Bansal, N., Beygelzimer, A., Coppersmith, D., Langford, J. & Sorkin, G. B.
(2008).
Robust reductions from ranking to classification.
Machine Learning,
72(1-2), 139-153.
https://doi.org/10.1007/s10994-008-5058-6
(2008).
Robust reductions from ranking to classification.
Machine Learning,
72(1-2), 139-153.
https://doi.org/10.1007/s10994-008-5058-6
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 ↦ nr where n is the number of elements.