[1]LUAN Xun,GAO Wei.Two-pass AUC optimization[J].CAAI Transactions on Intelligent Systems,2018,13(3):395-398.[doi:10.11992/tis.201706079]
Copy

Two-pass AUC optimization

CAAI Transactions on Intelligent Systems[ISSN 1673-4785/CN 23-1538/TP] Volume: 13 Number of periods: 2018 3 Page number: 395-398 Column: 学术论文—机器学习 Public date: 2018-05-05
Title:
Two-pass AUC optimization
Author(s):
LUAN Xun;  GAO Wei
National Key Laboratory for Novel Software Technology, Nanjing University, Nanjing 210023, China
Keywords:
machine learning; AUC; ROC; one-pass learning; online learning; ranking; stochastic gradient descent; statistics
CLC:
TP181
DOI:
10.11992/tis.201706079
Abstract:
The area under an ROC curve (AUC) has been an important performance index for class-imbalanced learning, cost-sensitive learning, learning to rank, etc. Traditional AUC optimization requires the entire dataset to be stored because AUC is defined as pairs of positive and negative instances. To solve this problem, the one-pass AUC (OPAUC) algorithm was introduced previously to scan the data only once and store the first- and second-order statistics. However, in many real applications, the second-order statistics require high storage and are computationally costly, especially for high-dimensional datasets. We introduce the two-pass AUC (TPAUC) optimization to calculate the mean of positive and negative instances in the first pass and then use the stochastic gradient descent method in the second pass. The new algorithm requires the storage of the first-order statistics but not the second-order statistics; hence, the efficiency is improved. Finally, experiments are used to verify the effectiveness of the proposed algorithm.
References:
[1] HSIEH F, TURNBULL B W. Nonparametric and semiparametric estimation of the receiver operating characteristic curve[J]. The annals of statistics, 1996, 24(1):25-40.
[2] ELKAN C. The foundations of cost-sensitive learning[C]//Proceedings of the 17th International Joint Conference on Artificial Intelligence. Seattle, WA, 2001:973-978.
[3] GAO Wei, JIN Rong, ZHU Shenghuo, et al. One-pass AUC optimization[C]//Proceedings of the 30th International Conference on Machine Learning. Atlanta, GA, 2013:906-914.
[4] HAND D J. Measuring classifier performance:a coherent alternative to the area under the ROC curve[J]. Machine learning, 2009, 77(1):103-123.
[5] EGAN J P. Signal detection theory and ROC analysis, series in cognition and perception[M]. New York:Academic Press, 1975.
[6] WU Jianxin, BRUBAKER S C, MULLIN M D, et al. Fast asymmetric learning for cascade face detection[J]. IEEE transactions on pattern analysis and machine intelligence, 2008, 30(3):369-382.
[7] BREFELD U, SCHEFFER T. AUC maximizing support vector learning[C]//Proceedings of ICML 2005 Workshop on ROC Analysis in Machine Learning. Bonn, Germany, 2005.
[8] JOACHIMS T. A support vector method for multivariate performance measures[C]//Proceedings of the 22nd International Conference on Machine Learning. Bonn, Germany, 2005:377-384.
[9] FREUND Y, IYER R, SCHAPIRE R, et al. An efficient boosting algorithm for combining preferences[J]. Journal of machine learning research, 2003, 4:933-969.
[10] RUDIN C, SCHAPIRE R E. Margin-based ranking and an equivalence between AdaBoost and RankBoost[J]. Journal of machine learning research, 2009, 10:2193-2232.
[11] HERSCHTAL A, RASKUTTI B. Optimising area under the ROC curve using gradient descent[C]//Proceedings of the 21st International Conference on Machine Learning. Banff, Alberta, Canada, 2004.
[12] AGARWAL S, ROTH D. Learnability of bipartite ranking functions[C]//Proceedings of the 18th Annual Conference on Learning Theory. Bertinoro, Italy, 2005:16-31.
[13] GAO Wei, ZHOU Zhihua. Uniform convergence, stability and learnability for ranking problems[C]//Proceedings of the 23rd International Joint Conference on Artificial Intelligence. Beijing, China, 2013:1337-1343.
[14] ZHAO Peilin, HOI S C H, JIN Rong, et al. Online AUC maximization[C]//Proceedings of the 28th International Conference on Machine Learning. Bellevue, WA, 2011:233-240.
[15] GAO Wei, WANG Lu, JIN Rong, et al. One-pass AUC optimization[J]. Artificial intelligence, 2016, 236:1-29.
[16] SHALEV-SHWARTZ S, SINGER Y, SREBRO N, et al. Pegasos:primal estimated sub-gradient solver for SVM[J]. Mathematical programming, 2011, 127(1):3-30.
[17] CESA-BIANCHI N, LUGOSI G. Prediction, learning, and games[M]. New York:Cambridge University Press, 2006.
[18] HAZAN E, KALAI A, KALE S, et al. Logarithmic regret algorithms for online convex optimization[C]//Proceedings of the 19th Annual Conference on Learning Theory. Pittsburgh, PA, 2006:499-513.
[19] DEVROYE L, GY?RFI L, LUGOSI G. A probabilistic theory of pattern recognition[M]. New York:Springer, 1996.
[20] KOT?OWSKI W, DEMBCZY?SKI K, HüLLERMEIER E. Bipartite ranking through minimization of univariate loss[C]//Proceedings of the 28th International Conference on Machine Learning. Bellevue, WA, 2011:1113-1120.
Similar References:

Memo

-

Last Update: 2018-06-25

Copyright © CAAI Transactions on Intelligent Systems