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.
|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|
|Publication status||Published - 2007|
|Name||Lecture Notes in Computer Science|