Area Under ROC Optimisation using a Ramp Approximation
Alan Herschtal, Bhavani Raskutti, Peter K. Campbell · 2006
This paper introduces AURORA, an algorithm that builds binary classifiers to optimise the area under the ROC curve (the AUC). AURORA builds non-linear classifiers of the data by binarising the raw input features. Feature selection is performed using a fast heuristic routine, and gradient descent is used to optimise the coefficients of the selected features. Both feature selection and gradient descent are designed to be optimal for AUC. Non-differentiability of the objective function is overcome using a ramp-based approximation for the AUC. The use of this ramp-based approximation also allows the AUC to be calculated in near O(n) time, where n is the number of labelled observations available. The entire AURORA algorithm then also has computational complexity near O(n). AURORA is compared with several other classifiers, over eight binary classification tasks, and generally produces classifiers which are significantly more accurate. AURORA is also highly scalable with increasing number of training examples, and increasing number of input features.