[1]栾寻,高尉.优化AUC两遍学习算法[J].智能系统学报,2018,13(3):395-398.[doi:10.11992/tis.201706079]
LUAN Xun,GAO Wei.Two-pass AUC optimization[J].CAAI Transactions on Intelligent Systems,2018,13(3):395-398.[doi:10.11992/tis.201706079]
点击复制
LUAN Xun,GAO Wei.Two-pass AUC optimization[J].CAAI Transactions on Intelligent Systems,2018,13(3):395-398.[doi:10.11992/tis.201706079]
优化AUC两遍学习算法
《智能系统学报》[ISSN 1673-4785/CN 23-1538/TP] 卷:
13
期数:
2018年第3期
页码:
395-398
栏目:
学术论文—机器学习
出版日期:
2018-05-05
- Title:
- Two-pass AUC optimization
- Keywords:
- machine learning; AUC; ROC; one-pass learning; online learning; ranking; stochastic gradient descent; statistics
- 分类号:
- TP181
- 摘要:
- ROC曲线下的面积（简称AUC）是机器学习中一种重要的性能评价准则，广泛应用于类别不平衡学习、代价敏感学习、排序学习等诸多学习任务。由于AUC定义于正负样本之间，传统方法需存储整个数据而不能适用于大数据。为解决大规模问题，前人已提出优化AUC的单遍学习算法，该算法仅需遍历数据一次，通过存储一阶与二阶统计量来进行优化AUC学习。然而在实际应用中，处理二阶统计量依然需要很高的存储与计算开销。为此，本文提出了一种新的优化AUC两遍学习算法TPAUC （two-pass AUC optimization）。该算法的基本思想是遍历数据两遍，第一遍扫描数据获得正、负样本的均值，第二遍采用随机梯度下降方法优化AUC。算法的优点在于通过遍历数据两遍来避免存储和计算二阶统计量，从而提高算法的效率，最后本文通过实验说明方法的有效性。
- 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.
- 相似文献/References:
-
[1]叶志飞,文益民,吕宝粮.不平衡分类问题研究综述[J].智能系统学报,2009,4(2):148.
YE Zhi-fei,WEN Yi-min,LU Bao-liang.A survey of imbalanced pattern classification problems[J].CAAI Transactions on Intelligent Systems,2009,4():148.
[2]刘奕群,张 敏,马少平.基于非内容信息的网络关键资源有效定位[J].智能系统学报,2007,2(1):45.
LIU Yi-qun,ZHANG Min,MA Shao-ping.Web key resource page selection based on non-content inf o rmation[J].CAAI Transactions on Intelligent Systems,2007,2():45.
[3]马世龙,眭跃飞,许 可.优先归纳逻辑程序的极限行为[J].智能系统学报,2007,2(4):9.
MA Shi-long,SUI Yue-fei,XU Ke.Limit behavior of prioritized inductive logic programs[J].CAAI Transactions on Intelligent Systems,2007,2():9.
[4]姚伏天,钱沄涛.高斯过程及其在高光谱图像分类中的应用[J].智能系统学报,2011,6(5):396.
YAO Futian,QIAN Yuntao.Gaussian process and its applications in hyperspectral image classification[J].CAAI Transactions on Intelligent Systems,2011,6():396.
[5]文益民,强保华,范志刚.概念漂移数据流分类研究综述[J].智能系统学报,2013,8(2):95.[doi:10.3969/j.issn.1673-4785.201208012]
WEN Yimin,QIANG Baohua,FAN Zhigang.A survey of the classification of data streams with concept drift[J].CAAI Transactions on Intelligent Systems,2013,8():95.[doi:10.3969/j.issn.1673-4785.201208012]
[6]杨成东,邓廷权.综合属性选择和删除的属性约简方法[J].智能系统学报,2013,8(2):183.[doi:10.3969/j.issn.1673-4785.201209056]
YANG Chengdong,DENG Tingquan.An approach to attribute reduction combining attribute selection and deletion[J].CAAI Transactions on Intelligent Systems,2013,8():183.[doi:10.3969/j.issn.1673-4785.201209056]
[7]胡小生,钟勇.基于加权聚类质心的SVM不平衡分类方法[J].智能系统学报,2013,8(3):261.
HU Xiaosheng,ZHONG Yong.Support vector machine imbalanced data classification based on weighted clustering centroid[J].CAAI Transactions on Intelligent Systems,2013,8():261.
[8]丁科,谭营.GPU通用计算及其在计算智能领域的应用[J].智能系统学报,2015,10(1):1.[doi:10.3969/j.issn.1673-4785.201403072]
DING Ke,TAN Ying.A review on general purpose computing on GPUs and its applications in computational intelligence[J].CAAI Transactions on Intelligent Systems,2015,10():1.[doi:10.3969/j.issn.1673-4785.201403072]
[9]孔庆超,毛文吉,张育浩.社交网站中用户评论行为预测[J].智能系统学报,2015,10(3):349.[doi:10.3969/j.issn.1673-4785.201403019]
KONG Qingchao,MAO Wenji,ZHANG Yuhao.User comment behavior prediction in social networking sites[J].CAAI Transactions on Intelligent Systems,2015,10():349.[doi:10.3969/j.issn.1673-4785.201403019]
[10]姚霖,刘轶,李鑫鑫,等.词边界字向量的中文命名实体识别[J].智能系统学报,2016,11(1):37.[doi:10.11992/tis.201507065]
YAO Lin,LIU Yi,LI Xinxin,et al.Chinese named entity recognition via word boundarybased character embedding[J].CAAI Transactions on Intelligent Systems,2016,11():37.[doi:10.11992/tis.201507065]
备注/Memo
收稿日期:2017-06-24。
基金项目:国家自然科学基金青年科学基金项目（61503179）；江苏省青年基金项目（BK20150586）.
作者简介:栾寻,男,1994年生,硕士研究生,主要研究方向为大规模机器学习、推荐系统。
通讯作者:高尉.E-mail:gaow@lamda.nju.edu.cn.
更新日期/Last Update:
2018-06-25