Friday April 20th, 2007
3:30pm, WEH 7220
Robust Reductions from Ranking to Classification
Alina Beygelzimer, IBM Watson
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.
