关键词:  机器学习;优化方法;AUC;对偶坐标下降;支持向量机

    在机器学习中,预测精度(或错误率)被普遍作为分类算法的性能评价指标 [1] .但是,如果遇到错分代价不相等或处理分类不平衡数据库等情况时,单一使用预测精度作为评价指标就不能完整地反映算法的真实性能 [2,3] .而基于接收者操作特性(receiver operation characteristic,简称 ROC)分析的 ROC 曲线下面积(area under the ROC curve,简称 AUC) [4] 则能很好地度量算法的整体性能,因此在机器学习中备受关注.

    目前,国内外许多著名学者对 AUC优化问题的求解进行了深入的研究,并提出了多种求解算法 [5] ,主要有基于 Hinge 损失的 SVM(support vector machine,简称 SVM)型算法、基于平方损失的最小二乘型算法、基于指数损失的AdaBoost型算法等.这些算法的主要区别在于使用了不同的代理损失函数,其中,基于Hinge损失的SVM型算法受到了广泛的关注 [6,7] .由于求解 AUC 问题需要优化来自两个不同类别的样本对构成的损失,损失数与样本数呈平方增长,导致对目标函数的优化时间长,收敛速度慢.在 2011 年的 ICML 会议上,Zhao 等人 [8] 首次提出了求解AUC优化问题的在线算法(online AUC maximization,简称OAM),通过引进两个缓冲(buffer),极大地缩减了需要优化的损失函数的个数,从而减少了训练次数,并且在分类不均衡数据库上获得了较好的实验结果.众所周知,在线方法考虑样本是随时间序列逐个产生的,每次只用一个样本更新解向量,即,来一个样本训练 1 次,训练之后的样本则被丢弃,不需要存储所有训练样本,有别于传统的批处理算法,因此可用于处理大规模数据库.2003 年,Zinkevich 在投影次梯度方法的基础上,针对一般凸问题提出了第一个在线优化算法 [9] ,并证明了 ( ) O T 的 regret 界 . 

    随后 ,Hazan 针对强凸问题得到了 O (log T ) 的 regret 界 [10] , 保证了算法的性能 .2007 年 ,Shalev-Shwartz 等人提出的投影次梯度算法 Pegasos [11] , 首次在大规模数据上进行实验并得到了很好的结果 , 在线方法也重新引起了人们的广泛关注 . 考虑到 AUC 优化问题的优化目标是来自不同类别的样本对构成的损失之和 , 需要存储所有样本 , 因此不能直接使用在线方法求解 . 文献 [8] 巧妙地使用 reservoir sampling 技术引进两个缓冲 , 并设定缓冲大小 , 分别用于存储正负样本 , 当处理一个样本时 , 首先判断该样本的类别并存储于相应缓冲 ,然后与另一缓冲里的所有样本组合构成损失对 , 当缓冲满时 , 用新样本随机替换缓冲里的样本 , 以达到更新缓冲的目的 . 

由于仅对缓冲内的样本进行优化 , 因此大大减少了损失函数的个数 . 文献 [8] 给出两种算法—— OAMseq和 OAMgra, 并给出 OAM 在缓冲为无限大时的算法 OAMinf, 其中 ,OAMinf 算法的 AUC 性能最好 .本文通过对文献 [8] 的分析发现 :OAM 算法在每次更新解向量时 , 没有使用上一步更新的解信息 , 使算法的收敛速度很慢 , 并且算法运行时所使用的平衡参数随着缓冲的改变而改变 , 使得参数选择过于复杂 . 为了更好地解决这些问题 , 本文提出一种求解 AUC 优化问题的对偶坐标下降方法 (AUC-DCD). 坐标下降 (coordinatedescend, 简称 CD) 方法的思路比较简单 , 在计算时固定解的其他维坐标 , 一次仅对选中的一维坐标进行优化求解 . 根据所优化目标函数的不同 ,CD 可分为对偶坐标下降 (DCD) [12] 和原始坐标下降 (PCD) [13] .DCD 是 2008 年台湾大学林智仁教授领导的研究小组针对 SVM 的对偶问题提出来的 , 并且在大量的数据库上取得了比 PCD 和当前一些流行算法更快的收敛效果 , 被认为是处理大规模数据特别是文本数据的首选算法 [14] .DCD 以简洁的操作流程、低廉的计算代价和快速的实际收敛效果 , 成为处理优化问题最有效的方法之一 , 能够克服 AUC 优化问题的缺点 .

    此外 ,2012 年 ,Shalev-Shwartz [15] 在对 DCD 方法进行分析时 , 曾使用 Modified-SGD 算法为对偶变量赋初值 , Modified-SGD 算法与随机梯度 (stochastic gradient descent, 简称 SGD) 算法类似 , 但使用了目标函数的对偶信息求取步长 . 由于 Modified-SGD 算法无需额外的内存开销 , 且优化的目标函数与样本数无关 , 因此可用于 AUC问题处理大规模数据库的情况 .在线方法与对偶坐标下降方法在求解子问题的过程中均是在每一步迭代时求解单个样本关于所有维数的子优化问题 , 两者有着密切的联系 . 本文采用基于 Hinge 损失的最小化 SVM 模型 , 提出一种求解 AUC 优化问题的对偶坐标下降方法 (AUC-DCD), 相应地 , 给出 3 种算法 , 并发现其中 OAM 算法是 AUC-DCD 的一种特殊情形 .最后 , 通过在大量数据库上进行比较实验 , 进一步验证了 AUC-DCD 的有效性 .

    1 AUC 优化问题

    求解 AUC 优化问题面临的一个关键问题就是如何计算 AUC 值 , 在机器学习领域 , 较常用的方法是非参数假定的 AUC 估计 [16] , 它在数值上等价于排序的 WMW(Wilcoxon-Mann-Whitney) 统计 [17,18] . 对于给定的独立同分布的训练样本集 S ={( x i , y i ) R d  {  1,+1}| i [ n ]}, 把集合 S 分为正负两个样本集 { | [ ]} { |i jS i n S j        和 x x[ ]}, n  其中 , n + 和n  分别表示正负样本数 , 且n = n + + n  ,0< n + < n . 非参数假定的 AUC 估计反映的是决策函数g = w T t + b代入一个随机抽取的正类样本的函数值大于一个随机抽取的负类样本的函数值的概率 ,AUC 值越大 , 则所求解的分类器性能就越优 , 其表达式为1 1( ( ) ( ))n ni ji jI g gAUCn n     x x(1)其中 , I ( x ) 为指标函数 (indicator function), 即 :1,( )0,xI xx 为真为假.在决策函数 g= w T t +b 中,b 为偏置,可通过对数据进行扩维.将偏置 b 放入权重 w 中统一进行处理,即:[ x T ,1]x T ,[ w T ,b] w T ,此时,决策函数可写为 g= w T t ,代入公式(1)可得:1 1 1 1( ) ( )1 .n n n nT T T Ti j i ji j i jI IAUCn n n n                 ≤ w x w x w x w x对特定的数据库,使 AUC 为极大值的点等价于使1 1( )n nT Ti ji jI n n      ≤ w x w x 为极小值的点,因为 I(x)可视为 0-1 损失函数,非凸且不可微,在此选取其代理函数 Hinge 损失函数进行优化.在机器学习领域,一般在“损失函数+正则化项”的框架下对机器学习问题进行研究 [19] ,常用的正则化项有L1和L2正则化,其中,L2正则化具有二阶可导、 对偶、 强凸等特性,常用的 SVM 模型即采用 L2 正则化.在此,采用 SVM 模型讨论 AUC 优化问题,即,正则化项使用 L2 正则化,用于调节分类器的泛化性.因此,最终优化目标函数为21 11|| || ( ( mi )2n )n nTi ji jln n       ww w x x (2)其中,参数  >0.Hinge 损失函数为 ( ( )) max{0,1 ( )}.T Ti j i jl       w x x w x x

    2 求解 AUC 优化问题的对偶坐标下降方法

    对偶坐标下降方法有多种形式,根据选取优化坐标方式的不同,可以分为循环对偶坐标下降(cyclic-DCD)算法、随机对偶坐标下降(stochastic-DCD)算法和使用 Permutation 策略的置换对偶坐标下降(stochastic-DCDperm)算法等.同理,本文给出 3 种求解 AUC 优化问题的算法,即,AUC-SDCD,AUC-SDCDperm 和 AUC-MSGD,其中,AUC-MSGD 也是随机选取一维坐标进行优化.为便于说明,本文使用 SDCD,SDCDperm 和 MSGD作为相应算法的简记形式.若无特别说明,文中的 AUC 在线方法均指 OAM 算法.

    2.1 3种求解算法讨论对偶坐标下降方法时,首先需要求解出原优化问题的对偶问题.为方便说明,本文记:1 1, , ( ) max{0,1 }, , [ ], [ ,  ],T Tij i j ij ij ijn ni jijk n n l i n j n               其中 z x x z w z w则公式(2)可写为21min ( ), , ( ) || || ( )2Tij ijijP P lk 其中ww w w z w  (3)容易求得公式(3)的对偶问题(求解过程见附录 1)为21 1max ( ), , ( ) , [0,1]2ij ij ij ijij ijD Dk k     其中 并且 z   (4)其中,   为对偶变量,且11[ ,..., ,..., ] .Tijn n      通过求解过程易知 , 有关系式1ij ijijkw z 成立 . 为方便起见 , 本文使用上述问题的等价问题进行求解 , 即 :21 1min , [0,1]2ij ij ij ijij ijk k     z (5)由于每次仅更新对偶变量   的一维 , 设第 t 次迭代时使向量   的 a ij 维完成从1 tija到tija 的更新 , 并设Δ ,t tij ij ija a   所以公式 (5) 的单维变量子问题为21 11min ( )2s.t. 0 1ijt tij ij ij ijtijkaka       ≤ ≤w z(6)式(6)为关于  ij 的二次函数,易求得其解析解为1(1 ) .T t Tij ij ij ijk     z w z z算法 1 为 AUC-SDCD 的更新过程.算法 1 . AUC-SDCD.0 0 01 111•Given  and the correspondingRepeat =1,2,...,1. Randomly choose  [ ], [ ]2. Let  min(max( (1 ) ,0),1)3.  (ij ijijt t T t Tij ij ij ij ijt tijkt Ti n j nk        ?w zz w z zw w 1 )Endt tij ijk  ?z算法 1 从初始化   开始 ( 一般初始化为零向量 ), 每次迭代随机挑选对偶变量   的一维 , 通过解决单变量子问题 (6) 进行更新 , 最后 , 利用原问题解与对偶问题解之间的关系达到更新原问题解 w 的目的 .算法 2 . AUC-SDCDperm.0 0 01 21•Given  and the correspondingRepeat =1,2,...,1. Let { , ,..., } be a random permutation of {1,2,..., }2. Repeat 1,2,...,(1)ij ijijn nkt Tp p p n ns n na   ?  w z, ( 1) 1, ( 1)mod 1(2) Do Step 2 ~ Step 3 of AUC-SDCDEndEndsp i a n j a n      ?算法 2 为 AUC-SDCDperm 的执行过程 .SDCDperm 算法与 SDCD 算法的处理过程类似 ,SDCDperm 在遍历1 次样本时 , 仅对向量   的每一维更新 1 次 , 但 SDCD 算法则可能对   的某一维重复更新 .算法 1 、 算法 2 每次更新解向量时均使用了上一步更新的解信息 , 因此需要额外的存储空间 , 当处理大规模数据库时 , 所花费的内存代价相当惊人 . 为解决存储问题 , 我们给出 AUC-MSGD 算法 , 具体流程见算法 3.算法 3 . AUC-MSGD.011•InitializeRepeat =1,2,...,1. Randomly choose  [ ], [ ]2. Let  min(max( (1 ) ,0),1)3.  (1 1 )EndT t Tij ij ij ijt tij ijt Ti n j ntt t        0??wz w z zw w zMSGD 算法对对偶变量的更新与 SDCD 算法稍有不同 , 主要在于两种算法所解决的单变量子问题不同 ,MSGD 算法在第 t 次迭代时通过解决如下子问题对解向量进行更新与公式(6)比较易发现:SDCD 算法子问题的样本数是固定的,即,对某一数据库 k=n + n  是定值;而 MSGD 算法求解的子问题(7)则是随迭代次数 t 的增加产生变化.

    2.2 AUC - SDCD 与 OAM 的区别文献[8]提出了求解 AUC 优化问题的在线算法(OAM),并给出缓冲取无限大时的算法 OAMinf,OAMinf 通过解决如下子问题来更新解向量 w:2min || || ( )2t Tij ijkl ww w z w (8)Crammer [20] 在 2006 年通过问题(8)的对偶问题求得解析解tij ijk     w w z (求解过程见附录 2),其中,min(max( (1 ) ,0),1).T t Tij ij ij ijk     z w z z该子问题的求解方法本质上与公式(6)给出的求解方法相同.通过与算法 1 比较容易发现:若初始化向量  = 0 ,OAMinf 算法是 SDCD 算法按顺序遍历 1 次所有样本时的特殊情况,但 SDCD 算法却能够得到比 OAMinf算法更快的收敛速度,本文实验部分对这一结论进行了详细验证.

    2.3 收敛性分析对于一般形式坐标下降算法的收敛性问题,Luo 和 Tseng 进行了深入而系统的研究 [21] .针对求解 SVM 对偶优化问题的 DCD 方法,文献[12]指出:当遍历 k 次样本集时,能够得到(1u) k ,0<u<1 的线性收敛速度.但 Shalev-Shwartz 等人 [15] 对此给出两点质疑:一是参数 u 可能无限逼近 0,且迭代次数没有限制,可以无限大;二是所作的收敛性分析只是针对对偶目标函数,而优化的最终目的是原始目标函数,即,对偶问题的收敛速度并不能说明原问题具有同样的收敛速度.在文献[15]中,Shalev-Shwartz 和 Zhang 两位著名学者使用 Fenchel-Young 不等式 [22]通过对偶间隙使得原始目标函数与对偶目标函数之间建立关系,从而给出原目标函数的收敛速度.设算法进行 T 0 次迭代后,令0 0*0 01 11 ( ) , 1 ( ) , argmin ( ),T Tt tt T t TT T T T P        ww w w w   由于原目标函数 P(w)为凸函数,根据凸函数性质可知001( ) 1 ( ) ( )Ttt TP T T P ≤ w w ,又因为原目标函数与对偶目标函数满足关系式*( ) ( ), P D ≥ w   所以有*[ ( )] ( ) [ ( ) ( )]. E P P E P D   ≤ w w w   这表明,可以用对偶间隙的收敛速度衡量原目标函数的收敛速度.因此,关于 AUC-SDCD 算法的收敛性,本文给出如下引理.引理 1 . 假设 AUC-SDCD 算法初始化   = 0 ,  >0 是迭代若干步后目标函数值与理论最优目标函数值之间的误差,当迭代次数 T>T 0 时,若使对偶间隙满足 [ ( ) ( )] , E P D   ≤ w   则迭代次数 T 需满足: 04 20max 0, log( 2) , T T k k k k        ≥ ≥其中,k=n + n  ,E 表示对随机抽取的样本对序列取期望.类似地,AUC-SDCDperm 算法的收敛性与 AUC-SDCD 算法相同.针对 Modified-SGD 算法,当算法遍历 1 次 n 个样本的数据库时,文献[15]给出对偶目标函数 O((logn)/n)的收敛速度.同样,对于 AUC-MSGD 算法本文给出引理 2.引理 2 . 假设样本满足独立同分布,令*argmax ( ), D      当 AUC-MSGD 算法遍历 1 次样本时有:*2log( )[ ( ) ( )] ,ekE D Dk  ≤  其中,k=n + n  ,E 表示对随机抽取的样本对序列取期望.由于引理 1、引理 2 的证明与文献[15]中的定理 1、定理 3 类似,这里不再赘述.

    3 数值实验本节通过实验对文中所提算法的正确性和有效性进行验证.实验中,算法在 LIBLINEAR [23] 平台上实现,该平台设计了科学、合理的数据结构,可以高效地处理数据和安排内存开销,并用多种编程语言实现,便于开发新算法,受到了众多国家教育科研机构的青睐.

3.1 算法及数据库描述实验在 10 个数据库上实现,这些数据库可从 LIBSVM 网站中获得,具体下载地址为     http://www.csie.ntu.edu.tw/~cjlin/libsvmtools/datasets/,表 1 给出数据库的相关描述.Table 1 Details of the datasets表 1 数据库描述数据库  样本数 样本维数 失衡率sonar  208  60  1.144 3fourclass  862  2  1.807 8german  1 000  24  2.333 3svmguide3 1 243  22  3.199 3dna  2 000  180  3.310 3svmguide4 300  10  5.818 2pendigits 7 494  16  8.620 0vowel  528  10  10.000 0letter  15 000 16  24.252 5sector  6 412  55 197  148.116 3表 1 中,sonar,fourclass,german 和 svmguide3 为二分类数据库,其余为多分类数据库.实验未对数据进行任何预处理,假设正样本为少数样本,为了构造不平衡数据库,对多分类数据库,采取把其中一类作为正样本,其他类作为负样本的处理策略.表中失衡率定义为负样本数与正样本数之比.文献[8]给出两种求解 AUC 优化问题的在线算法:OAMseq 和 OAMgra,并给出 OAM 算法在缓冲无限大时的算法 OAMinf.其中,OAMinf 算法得到的 AUC 性能优于 OAMseq 和 OAMgra.因此,本节实验仅对算法OAMinf,SDCD,SDCDperm 和 MSGD 进行比较验证.为公平比较,实验中,算法 SDCD 和 MSGD 的迭代次数均取T=n + n  ,且 SDCDperm 算法仅执行 1 次外循环,即,保证 4 种算法迭代次数相同.

    3.2 实验结果及结论实验把每个数据库随机平均分成 5 组,其中 4 组作为训练样本,剩下 1 组作为测试样本,每次分组求得 5 组AUC 值,每个数据库进行 4 次随机分组,最终结果为 20 组 AUC 值的平均值和方差.4 种算法的参数选择范围为 10 9 ~10 1 ,在实验中选取最优参数.图 1 给出 4 种算法在各数据库上的参数取值与 AUC 值的关系.表 2 列出了 4 种算法在相应数据库上的实验结果,其中,记号“AB”中 A 为 AUC 平均值,B 为相应的均方差(mean square error).均方差按照公式211 ( 1) ( )niiMSE n x x  (n=20,x i 表示 AUC 值, x 表示 AUC 的平均值)来计算. 从表中 2 可以看出:在 AUC 值的比较上,SDCDperm 算法在多数数据库上明显优于 OAMinf,SDCD 和MSGD 算法;从均方差的比较中也可以看出,SDCDperm 算法的稳定性较好.SDCD 和 MSGD 算法的 AUC 性能仅在部分数据库上好于 OAMinf 算法,这与随机抽取的样本对的顺序有关. 为了说明 AUC-DCD 方法在收敛速度这一性能上优于在线算法,图 2 给出 4 种算法每次迭代求解的 AUC值和目标函数值的下降速度比较实验(20 次结果的平均值).限于篇幅,这里仅给出在 sonar,svmguide4 和 vowel数据库上的实验结果. 图 2 中,6 幅图的横坐标均为迭代次数,每迭代运行 100 步做一个记录点.由于在执行一定的迭代次数之后算法已接近收敛,因此,图中仅画出算法迭代 5 000 次的实验结果.为方便比较,图中用“1-AUC”表示 AUC 值的收敛速度,用相对目标函数值(relative function value difference)表示目标函数值的下降速度.其中,相对目标函数值=(当前目标函数值最优目标函数值)/最优目标函数值.计算时,最优目标函数值用最小的目标函数值代替.从上述图中可以得出如下结论:(1) 算法 MSGD,SDCD 和 SDCDperm 无论是在 AUC 的收敛速度还是目标函数值的收敛速度上都明显快于 OAMinf 算法;特别地,在 sonar 数据库,MSGD 的收敛速度快于其他 3 种算法;(2) SDCD 算法的目标函数值的下降速度稍快于 SDCDperm;(3) 当迭代次数足够大时,SDCDperm 算法得到的 AUC 性能总是最优.4 总 结本文提出一种求解 AUC 优化问题的对偶坐标下降(AUC-DCD)方法,并给出相应的 3 种算法.理论分析表明,求解 AUC 优化问题的在线方法(OAM)是一种特殊的坐标下降方法.并且指出,AUC-DCD 方法可以得到比OAM 方法更优的 AUC 性能及更快的收敛速度.最后,通过实验,对我们的结论进行了验证.

    References :[1] Duda RO, Hart P E, Stork DG. Pattern Classification. 2nd., New York: Wiley, 2001. [2] Cortes C, Mohri M. AUC optimization vs. error rate minimization. Advances in Neural Information Processing Systems, 2004,16(16):313-320.[3] Maloof MA. Learning when data sets are imbalanced and when costs are unequal and unknown. In: Proc. of the Workshop onLearning from Imbalanced Data Sets II (ICML). Washington, 2003. 421-428. http://www.informatik.uni-trier.de/~ley/db/conf/icml/icml2003.html[4] Hanely JA, McNeil BJ. The meaning and use of the area under a receiver operating characteristic (ROC) curve. Radiology, 1982,143(1):29-36. [doi: 10.1148/radiology.143.1.7063747][5] Wang YN, Chen SC. A survey of evaluation and design for classifier based on AUC. Pattern Recognition and Artificial Intelligence,2011,24(1):64-71 (in Chinese with English abstract).[6] Rakotomamonjy A. Optimizing area under roc curve with SVMs. In: Proc. of the European Conf. on Artificial IntelligenceWorkshop on ROC Analysis and Artificial Intelligence. Valencia: IOS Press, 2004. 71-80.[7] Brefeld U, Scheffer T. AUC maximizing support vector learning. In: Proc. of the ICML 2005 Workshop on ROC Analysis inMachine Learning. Bonn, 2005. 377-384. http://users.dsic.upv.es/~flip/ROCML2005/papers.html[8] Zhao PL, Hoi SCH, Jin R, Yang TB. Online AUC maximization. In: Proc. of the 28th Int’l Conf. on Machine Learning. 2011.233-240. http://www.informatik.uni-trier.de/~ley/db/conf/icml/icml2011.html[9] Zinkevich M. Online convex programming and generalized infinitesimal gradient ascent. In: Proc. of the 20th Annual Int’l Conf. onMachine Learning. 2003. 856-863. http://www.informatik.uni-trier.de/~ley/db/conf/icml/icml2003.html[10] Hazan E, Agarwal A, Kale S. Logarithmic regret algorithms for online convex optimization. Machine Learning, 2007,69(2-3):169-192. [doi: 10.1007/s10994-007-5016-8][11] Shalev-Shwartz S, Singer Y, Srebro N. Pegasos: Primal estimated sub-gradient solver for SVM. In: Proc. of the Int’l Conf. onMachine Learning. 2007. 807-814. [doi: 10.1145/1273496.1273598][12] Hsieh CJ, Chang KW, Lin CJ, Keerthi SS, Sundararajan S. A dual coordinate descent method for large-scale linear SVM. In: Proc.of the 28th Int’l Conf. on Machine Learning. 2008. 408-415. [doi: 10.1145/1390156.1390208][13] Chang KW, Hsieh CJ, Lin CJ. Coordinate descent method for large-scale l2-loss linear support vector machines. Journal ofMachine Learning Research, 2008,9:1369-1398.[14] Yuan GX, Chang KW, Hsieh CJ, Lin CJ. A comparison of optimization methods and software for large-scale l1-regularized linearclassification. The Journal of Machine Learning Research, 2010,9999:3183-3234.[15] Shalev-Shwartz S, Zhang T. Stochastic dual coordinate ascent methods for regularized loss minimization. Journal of MachineLearning Research, 2013,14:567-599.[16] Wu SM, Flach P. A scored AUC metric for classifier evaluation and selection. In: Proc. of the ICML 2005 Workshop on ROCAnalysis in Machine Learning. Bonn, 2005. 378-389. http://users.dsic.upv.es/~flip/ROCML2005/papers.html[17] Mann HB, Whitney DR. On a test of whether one of two random variables is stochastically larger than the other. The Annals ofMathematical Statistics, 1947,18(1):50-60. [doi: 10.1214/aoms/1177730491][18] Yan L, Dodier R, Mozer MC, Wolniewicz R. Optimizing classifier performance via an approximation to the Wilcoxon-Mann-Whitney statistic. In: Proc. of the Int’l Conf. on Machine Learning. Washington, 2003. 848-855. http://www.informatik.uni-trier.de/~ley/db/conf/icml/icml2003.html[19] Sun ZY, Tao Q. Statistical machine learning: A review of the loss function and optimization. Communications of The CCF, 2009,5(8):7-14 (in Chinese with English abstract).[20] Crammer K, Dekel O, Keshet J, Shalev-Shwartz S, Singer Y. Online passive-aggressive algorithms. The Journal of MachineLearning Research, 2006,7:551-585.[21] Luo ZQ, Tseng P. On the convergence of the coordinate descent method for convex differentiable minimization. Journal ofOptimization Theory and Applications, 1992,72(1):7-35. [doi: 10.1007/BF00939948][22] Shalev-Shwartz S, Singer Y. Convex repeated games and fenchel duality. In: Advances in Neural Information Processing Systems.2006. 1265-1272. http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.87.1617[23] Fan RE, Chang KW, Hsieh CJ, Wang XR, Lin CJ. LIBLINEAR: A library for large linear classification. The Journal of MachineLearning Research, 2008,9:1871-1874.附中文参考文献 :[5] 汪云云,陈松灿.基于 AUC 的分类器评价和设计综述.模式识别与人工智能,2011,24(1):64-71.[19] 孙正雅,陶卿.统计机器学习综述:损失函数与优化求解.中国计算机学会通讯,2009,5(8):7-14.