Boosting the Area under the ROC Curve

We show that any weak ranker that can achieve an area under the ROC curve slightly better than 1/2 (which can be achieved by random guessing) can be effi- ciently boosted to achieve an area under the ROC curve arbitrarily close to 1. We further show that this boosting can be performed even in the presence of indepen- dent misclassification noise, given access to a noise-tolerant weak ranker.