Journal of Software:2014.25(10):2282-2292

(中国人民解放军 陆军军官学院 十一系, 安徽 合肥 230031)
Dual Coordinate Descent Method for Solving AUC Optimization Problem
JIANG Ji-Yuan,TAO Qing,GAO Qian-Kun,CHU De-Jun
(11th Department, Army Officer Academy of PLA, Hefei 230031, China)
Chart / table
Similar Articles
Article :Browse 2050   Download 2398
Received:January 30, 2013    Revised:September 30, 2013
> 中文摘要: AUC被广泛作为衡量不平衡数据分类性能的评价标准.与二分类问题不同,AUC问题的损失函数由来自两个不同类别的样本对组成.如何提高其实际收敛速度,是一个值得研究的问题.目前的研究结果表明:使用reservoir sampling技术的在线方法(OAM)表现出很好的AUC性能,但OAM仍存在诸如收敛速度慢、参数选择复杂等缺点.针对AUC优化问题的对偶坐标下降(AUC-DCD)方法进行了系统的研究,给出3种算法,即AUC-SDCD,AUC- SDCDperm和AUC-MSGD,其中,AUC-SDCD和AUC-SDCDperm与样本数目有关,AUC-MSGD与样本数目无关.理论分析指出,OAM是AUC-DCD的一种特殊情形.实验结果表明,AUC-DCD在AUC性能和收敛速度两方面均优于OAM.研究结果表明,AUC-DCD是求解AUC优化问题的首选方法.
Abstract:AUC is widely used as a measure for the imbalanced classification problems. The AUC loss problem is a pairwise function between two instances from different classes, which is obviously different from that in standard binary classifications. How to improve its real convergence speed is an interesting problem. Recent study shows that the online method (OAM) using the reservoir sampling technique has better performance. However, there exist some shortcomings such as slow convergence rate and difficult parameter selection. This paper conducts a systematic investigation for solving AUC optimization problem by using the dual coordinate descent methods (AUC-DCD). It presents three kinds of algorithms: AUC-SDCD, AUC-SDCDperm and AUC-MSGD, where the first two algorithms depend on the size of training set while the last does not. Theoretical analysis shows that OAM is a special case of the AUC-DCD. Experimental results show that AUC-DCD is better than OAM on the AUC performance as well as the convergence rate. Therefore AUC-DCD is among the first optimization schemes suggested for efficiently solving AUC problems.
文章编号:     中图分类号:    文献标志码:
基金项目:国家自然科学基金(61273296,60975040);安徽省自然科学基金(1308085QF121) 国家自然科学基金(61273296,60975040);安徽省自然科学基金(1308085QF121)
Foundation items:
Reference text:


JIANG Ji-Yuan,TAO Qing,GAO Qian-Kun,CHU De-Jun.Dual Coordinate Descent Method for Solving AUC Optimization Problem.Journal of Software,2014,25(10):2282-2292