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.
Keywords Ranking - Classification - Reductions
Editors: Claudio Gentile, Nader H. Bshouty.