|
Abstract:
|
In comparison to the misclassification error, the area under the receiver operating characteristic curve (AUC) is often considered as a more comprehensive measure for performance of a classifier. Maximizing the empirical AUC directly, however, is computationally challenging as a naive computation of the AUC requires O(n^2) time complexity, in comparison with the O(n) time complexity when computing the misclassification error, and further, optimizing over indicator functions is NP-hard. In this paper, we propose a non-convex differentiable surrogate function for the AUC, and further develop an efficient algorithm to optimize this surrogate function. The proposed algorithm takes advantage of the selection tree data structure and also uses a truncated Newton strategy so that the time complexity of the optimization scales at the rate of O(nlogn). In the setting of linear classifiers, we also show that the estimated coefficients enjoy theoretical asymptotic consistency. Finally, we compare the proposed method with the support vector machine (SVM) using both simulation studies and real-world datasets, and the results indicate that the proposed method outperforms the SVM in terms of AUC.
|
