Robust Reductions from Ranking to Classification

Alina Beygelzimer
IBM Watson

Friday, April 20th, 2007, 3:30 pm
Wean Hall 7220

Abstract

We show how to convert any binary classifier learning algorithm into a
ranking algorithm. The reduction is robust in the sense that it transforms
classification regret R into AUC regret at most 2R. We show that this bound
is tight and that the reduction provides the same regret transform as an
optimal solution to the (NP-hard) feedback arc set problem. (Regret of an
algorithm on a given problem is the difference between the loss incurred by
the algorithm and the loss of the best predictor on the same problem.) This
is a large improvement over commonly used approaches such as ordering
according to regressed scores, which have a regret transform of R->NR, where
N is the number of elements.

Joint work with Nina Balcan, Nikhil Bansal, Don Coppersmith, John Langford,
and Greg Sorkin. To appear in COLT-07.