【机器学习】优化AUC两遍学习算法（南京大学：栾寻、高尉）

第13卷第3期 智能系统学报 Vol.13 No.3 2018年6月 CAAI Transactions on Intelligent Systems Jun.2018 D0:10.11992/tis.201706079 网络出版地址：http:/kns.cnki.net/kcms/detail/23.1538.TP.20180408.1555.020.html 优化AUC两遍学习算法 栾寻，高尉 (南京大学计算机软件新技术国家重点实验室，南京210023) 摘要：ROC曲线下的面积（简称AUC)是机器学习中一种重要的性能评价准则，广泛应用于类别不平衡学习、代价 敏感学习、排序学习等诸多学习任务。由于AUC定义于正负样本之间，传统方法需存储整个数据而不能适用于大数 据。为解决大规模问题，前人已提出优化AUC的单遍学习算法，该算法仅需遍历数据一次，通过存储一阶与二阶统 计量来进行优化AUC学习。然而在实际应用中，处理二阶统计量依然需要很高的存储与计算开销。为此，本文提出 了一种新的优化AUC两遍学习算法TPAUC(wo-pass AUC optimization)。该算法的基本思想是遍历数据两遍，第一 遍扫描数据获得正、负样本的均值，第二遍采用随机梯度下降方法优化AUC。算法的优点在于通过遍历数据两遍来 避免存储和计算二阶统计量，从而提高算法的效率，最后本文通过实验说明方法的有效性。 关键词：机器学习；AUC:ROC:单遍学习：在线学习：排序：随机梯度下降：统计量 中图分类号：TP181文献标志码：A文章编号：1673-4785(2018)03-0395-04 中文引用格式：栾寻，高尉.优化AUC两遍学习算法J.智能系统学报，2018,133)：395-398. 英文引用格式：LUAN Xun,GAO Wei.Two-pass AUC optimization/J].CAAI transactions on intelligent systems,.2018,13(3): 395-398. Two-pass AUC optimization LUAN Xun,GAO Wei (National Key Laboratory for Novel Software Technology,Nanjing University,Nanjing 210023,China) 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 be- cause AUC is defined as pairs of positive and negative instances.To solve this problem,the one-pass AUC(OPAUC)al- gorithm 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 al- gorithm requires the storage of the first-order statistics but not the second-order statistics;hence,the efficiency is im- proved.Finally,experiments are used to verify the effectiveness of the proposed algorithm. Keywords:machine learning:AUC:ROC;one-pass learning;online learning;ranking:stochastic gradient descent;stat- istics 曲线ROC下的面积（简称AUC)是机器学习 别的数据显著多于其他类别，而类别不平衡性比例 中一种重要的性能评价准则1，广泛应用于类别不 可能为10之多。对AUC的研究可以追溯至20世 平衡学习、代价敏感学习、信息检索等诸多学习任 纪70年代的雷达信号探测分析，之后AUC被用于 务。例如，在邮件协调过滤或人脸识别中，某些类 心理学、医学检测以及机器学习。直观而言，AUC 收稿日期：2017-06-24.网络出版日期：2018-04-08. 用于衡量一种学习算法将训练数据中正类数据排在 基金项目：国家自然科学基金青年科学基金项目(61503179)：江苏 省青年基金项百(BK20150586. 负类数据之前的概率。 通信作者：高尉.E-mail:gaow@lamda.nju.edu.cn. 由于AUC的广泛实际应用，出现了很多优化

DOI: 10.11992/tis.201706079 网络出版地址: http://kns.cnki.net/kcms/detail/23.1538.TP.20180408.1555.020.html 优化 AUC 两遍学习算法 栾寻，高尉 （南京大学 计算机软件新技术国家重点实验室, 南京 210023） 摘 要：ROC 曲线下的面积 (简称 AUC) 是机器学习中一种重要的性能评价准则，广泛应用于类别不平衡学习、代价 敏感学习、排序学习等诸多学习任务。由于 AUC 定义于正负样本之间，传统方法需存储整个数据而不能适用于大数 据。为解决大规模问题，前人已提出优化 AUC 的单遍学习算法，该算法仅需遍历数据一次，通过存储一阶与二阶统 计量来进行优化 AUC 学习。然而在实际应用中，处理二阶统计量依然需要很高的存储与计算开销。为此，本文提出 了一种新的优化 AUC 两遍学习算法 TPAUC (two-pass AUC optimization)。该算法的基本思想是遍历数据两遍，第一 遍扫描数据获得正、负样本的均值，第二遍采用随机梯度下降方法优化 AUC。算法的优点在于通过遍历数据两遍来 避免存储和计算二阶统计量，从而提高算法的效率，最后本文通过实验说明方法的有效性。 关键词：机器学习；AUC；ROC；单遍学习；在线学习；排序；随机梯度下降；统计量 中图分类号：TP181 文献标志码：A 文章编号：1673−4785(2018)03−0395−04 中文引用格式：栾寻, 高尉. 优化 AUC 两遍学习算法[J]. 智能系统学报, 2018, 13(3): 395–398. 英文引用格式：LUAN Xun, GAO Wei. Two-pass AUC optimization[J]. CAAI transactions on intelligent systems, 2018, 13(3): 395–398. Two-pass AUC optimization LUAN Xun，GAO Wei (National Key Laboratory for Novel Software Technology, Nanjing University, Nanjing 210023, China) 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 be￾cause AUC is defined as pairs of positive and negative instances. To solve this problem, the one-pass AUC (OPAUC) al￾gorithm 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 al￾gorithm requires the storage of the first-order statistics but not the second-order statistics; hence, the efficiency is im￾proved. Finally, experiments are used to verify the effectiveness of the proposed algorithm. Keywords: machine learning; AUC; ROC; one-pass learning; online learning; ranking; stochastic gradient descent; stat￾istics 曲线 ROC 下的面积 (简称 AUC) 是机器学习 中一种重要的性能评价准则[1-5] ，广泛应用于类别不 平衡学习、代价敏感学习、信息检索等诸多学习任 务。例如，在邮件协调过滤或人脸识别中，某些类 别的数据显著多于其他类别，而类别不平衡性比例[6] 可能为 106 之多。对 AUC 的研究可以追溯至 20 世 纪 70 年代的雷达信号探测分析，之后 AUC 被用于 心理学、医学检测以及机器学习。直观而言，AUC 用于衡量一种学习算法将训练数据中正类数据排在 负类数据之前的概率。 由于 AUC 的广泛实际应用，出现了很多优化 收稿日期：2017−06−24. 网络出版日期：2018−04−08. 基金项目：国家自然科学基金青年科学基金项目 (61503179)；江苏 省青年基金项目 (BK20150586). 通信作者：高尉. E-mail：gaow@lamda.nju.edu.cn. 第 13 卷第 3 期 智 能 系 统 学 报 Vol.13 No.3 2018 年 6 月 CAAI Transactions on Intelligent Systems Jun. 2018

·396· 智能系统学报 第13卷 AUC学习方法，如支持向量机方法71、集成学习 数等。由于损失函数定义于一对正样本和负样本之 boosting算法9.10，以及梯度下降算法。这些方法 间，该替代函数又被称为“成对替代损失函数(pair- 需要存储整个训练数据集，算法在运行时需要扫描 wise surrogate loss)”。 数据多遍，因此难以解决大规模学习任务。在理论 借鉴于优化AUC单遍学习算法)，本文采用最 方面，AGARWAL和ROTHU2给出了优化AUC可 小二乘损失函数，即在式(2)中有 学习性的充分条件和必要条件，而GAO和ZHOU 1fx)-fx》=(1-fx)+fx)2 则根据稳定性给出了可学习性的充要条件。 为简洁起见，不妨假设样本总数为T,其中正样 针对大规模AUC优化学习，ZHAO等于 本数为T,负样本数为T,以及设优化函数为 2011年提出优化AUC的在线学习算法，该方法借 Lo)=∑《wL>y月 助于辅助存储器，随机采取正样本与负样本。而辅 Ts.Ts- 助存储器的大小与数据规模密切相关，因此很难应 式中(w)=(1-(w,x)+(w,x)》2,经过计算整理可得 用于大规模数据或不断增加的数据。为此，GAO L(w)=1+ 等于2013年提出优化AUC的单遍学习方法，该 ∑m,+元∑w,x- 算法仅需遍历数据一次，通过存储一阶与二阶统计 1 量优化AUC学习。 在实际应用中，存储与计算二阶统计量依旧需 T (w,x》 要较高的存储与计算开销。因此，本文提出了一种 新的优化AUC两遍学习算法TPAUC(two-pass 设正、负样例的协方差矩阵分别为 AUC optimization)。该算法遍历数据两遍：第一遍 统计正负样本均值，第二遍通过随机梯度方法进行 以及设正样例与负样例的均值分别为 优化AUC学习。新算法只需计算与存储一阶统计 量，而不需要存储二阶统计量，从而有效地提高效 率，最后本文通过实验验证了该算法的有效性。 因此表达式L()可以进一步化简、分解为 1 TPAUC学习方法 Lm)=∑Lw)/T (3) 设示例空间XcR和Y分别表示样本的输人空 当y,=1时，有 间和输出空间，本文关注二分类问题，于是有 L,(w)=1+(w,x,-c》2/T++(w,c-c》2-2w,c寸-c〉 Y=(+1,-1山。假设D表示空间X×Y上潜在的联合 当y,=-1时，有 分布。假设训练数据集为 L,(w)=1+(w,x,-c行》2/T.+(w,c行-c》2-2(w,c7-c〉 S={(x1,y),(x2,Jy2),…,(x,yn)》 考虑在损失函数中加入正则项，以防止模型过 其中每个训练样本是根据分布D独立同分布采样所 拟合。本文采用随机梯度下降方法s判因此 得。进一步假设分类器f:X→R为一个实值函数。 w,=w,-刀VL,(w-1) 给定样本S和函数f,AUC(f,S)定义为 只需得到关于w,-的梯度表达式，而梯度只需对式 (3)中L,(w)表达式直接求导可得。 If)>fx别+Lf)=f (1) 因此，本文的思想是不需存储协方差矩阵S和 Ts.Ts- S,需利用均值c和c,从而即可进行优化AUC学 式中：为指示函数，如果判定为真，其返回值为 习。本方法的核心只需要数据的一阶统计量，而不 1,否则为0；Ts和Ts分别表示训练集中正、负类样 需要二阶统计量，从而将算法空间复杂度降至 本的样本数。 O(d)。同时，该公式中c和c是整个样本空间中正 直接优化AUC往往等价于NP难问题，从而导 例和负例的均值，在第1次遍历数据时不可知，因 致计算不可行。在实际应用中，一种可行的方法是 此需要遍历数据两遍。 对优化表达式(1)进行一种替代损失函数： 本文方法的基本流程可以分为两步：第1步遍 f.S)=∑)-f>y (2) 历数据，统计正样本和负样本均值c时和c;第2步遍 Ts.Ts- 历将利用数据的均值计算得到梯度，然后利用随机 式中1：R→R是一个连续的凸函数，常用的函数包 梯度下降法更新w而完成优化AUC的学习，并在实 括指数损失函数、Hinge损失函数、Logistic损失函 验中取得很好的效果

AUC 学习方法，如支持向量机方法[7-8] 、集成学习 boosting 算法[9-10] ，以及梯度下降算法[11]。这些方法 需要存储整个训练数据集，算法在运行时需要扫描 数据多遍，因此难以解决大规模学习任务。在理论 方面，AGARWAL 和 ROTH[12]给出了优化 AUC 可 学习性的充分条件和必要条件，而 GAO 和 ZHOU[13] 则根据稳定性给出了可学习性的充要条件。 针对大规模 AUC 优化学习，ZHAO 等 [ 1 4 ]于 2011 年提出优化 AUC 的在线学习算法，该方法借 助于辅助存储器，随机采取正样本与负样本。而辅 助存储器的大小与数据规模密切相关，因此很难应 用于大规模数据或不断增加的数据。为此，GAO 等 [3]于 2013 年提出优化 AUC 的单遍学习方法，该 算法仅需遍历数据一次，通过存储一阶与二阶统计 量优化 AUC 学习。 在实际应用中，存储与计算二阶统计量依旧需 要较高的存储与计算开销。因此，本文提出了一种 新的优化 AUC 两遍学习算法 TPAUC (two-pass AUC optimization)。该算法遍历数据两遍：第一遍 统计正负样本均值，第二遍通过随机梯度方法进行 优化 AUC 学习。新算法只需计算与存储一阶统计 量，而不需要存储二阶统计量，从而有效地提高效 率，最后本文通过实验验证了该算法的有效性。 1 TPAUC 学习方法 X ⊂ R d Y Y = {+1,−1} X ×Y 设示例空间 和 分别表示样本的输入空 间和输出空间，本文关注二分类问题, 于是有 。假设 D 表示空间 上潜在的联合 分布。假设训练数据集为 S = {(x1, y1),(x2, y2),··· ,(xn, yn)} D f : X → R f AUC(f,S) 其中每个训练样本是根据分布 独立同分布采样所 得。进一步假设分类器 为一个实值函数。 给定样本 S 和函数 ， 定义为 ∑ i,j I[f(xi) > f(xj)]+ 1 2 I[f(xi) = f(xj)] TS + TS − (1) I[·] TS + TS + 式中： 为指示函数，如果判定为真，其返回值为 1，否则为 0； 和 分别表示训练集中正、负类样 本的样本数。 直接优化 AUC 往往等价于 NP 难问题，从而导 致计算不可行。在实际应用中，一种可行的方法是 对优化表达式 (1) 进行一种替代损失函数： L(f,S ) = ∑ i,j l(f(xi)− f(xj))I[yi > yj] TS + TS − (2) l : R → R 式中 +是一个连续的凸函数，常用的函数包 括指数损失函数、Hinge 损失函数、Logistic 损失函 数等。由于损失函数定义于一对正样本和负样本之 间，该替代函数又被称为“成对替代损失函数 (pair￾wise surrogate loss)”。 借鉴于优化 AUC 单遍学习算法[3] ，本文采用最 小二乘损失函数，即在式 (2) 中有 l(f(xi)− f(xj)) = (1− f(xi)+ f(xj))2 T T+ T− 为简洁起见，不妨假设样本总数为 ，其中正样 本数为 ，负样本数为 ，以及设优化函数为 L(w) = ∑ i,j l(w)I[yi > yj] TS + TS − l(w) = ( 1−⟨w, xi⟩+ ⟨ w, xj ⟩) 式中 2 ，经过计算整理可得 L(w) = 1+ 1 T+ ∑ i:yi=1 ⟨w, xi⟩ 2+ 1 T− ∑ i:yi=−1 ⟨w, xi⟩ 2− 1 T+T− ∑ i:yi=1 ⟨w, xi⟩ ∑ i:yi=−1 ⟨w, xi⟩− 2 T+ ∑ i:yi=1 ⟨w, xi⟩+ 2 T− ∑ i:yi=−1 ⟨w, xi⟩ 设正、负样例的协方差矩阵分别为 S + T = 1 T+ ∑ i:yi=1 xix T i , S − T = 1 T− ∑ i:yi=−1 xix T i 以及设正样例与负样例的均值分别为 c + T = 1 T+ ∑ i:yi=1 xi , c − T = 1 T− ∑ i:yi=−1 xi 因此表达式 L(w) 可以进一步化简、分解为 L(w) = ∑ t Lt(w)/T (3) 当 yt = 1 时，有 Lt(w) = 1+⟨w, xt − c + T ⟩ 2 /T+ +⟨w, c + T − c − T ⟩ 2 −2⟨w, c + T − c − T ⟩ 当 yt = −1 时，有 Lt(w) = 1+⟨w, xt − c − T ⟩ 2 /T− +⟨w, c − T − c + T ⟩ 2 −2⟨w, c − T − c + T ⟩ 考虑在损失函数中加入正则项，以防止模型过 拟合。本文采用随机梯度下降方法[15-19] ，因此 wt = wt −η∇Lt(wt−1) wt−1 Lt(w) 只需得到关于 的梯度表达式，而梯度只需对式 (3) 中 表达式直接求导可得。 S + T S − T c + T c − T O(d) c + T c − T 因此，本文的思想是不需存储协方差矩阵 和 ,需利用均值 和 ，从而即可进行优化 AUC 学 习。本方法的核心只需要数据的一阶统计量，而不 需要二阶统计量，从而将算法空间复杂度降至 。同时，该公式中 和 是整个样本空间中正 例和负例的均值，在第 1 次遍历数据时不可知，因 此需要遍历数据两遍。 c + T c − T w 本文方法的基本流程可以分为两步：第 1 步遍 历数据，统计正样本和负样本均值 和 ；第 2 步遍 历将利用数据的均值计算得到梯度, 然后利用随机 梯度下降法更新 而完成优化 AUC 的学习，并在实 验中取得很好的效果。 ·396· 智 能 系 统 学 报 第 13 卷

第3期 栾寻，等：优化AUC两遍学习算法 ·397· 2实验验证 2)OAMseq:优化AUC的在线学习算法 3)OAMgra:优化AUC的在线学习算法。 本文将在标准真实数据集和高维数据集实验验 4)Online Uni--Exp:优化加权单变量指数损失函 证所提方法的有效性，其中8个标准数据集分别为 数2 diabetes、fourclass、german、splice、usps、letter、ma- 5)Online Uni-.Squ:优化加权单变量平方损失函 gic04、a9a。数据集中样本数量从768~32561不 数 等，样本维度的范围从8~256。所有数据集的特征 实验结果如表1所示，不难发现，本文提出的 都被规范到[-1,1]，多分类问题被转变为两分类问 优化AUC两遍学习方法TPAUC性能与OPAUC 题，随机将类别划分成两类。 相当，但明显优于OAMseq、OAMgra、Online Uni- TPAUC算法的学习率参数n和正则化参数A范 Exp以及Online Uni-Squo 围都为2-10,2-9,2-8，…，2.41。首先将数据集划分为 本文选用8个高维稀疏数据集，分别为real- 训练集和测试集，参数的选择通过在训练集上进行 sim、rcv、revlv2、sector、sector..lvr、news20、ecml20l2、 五折交叉验证来确定。选定参数后，再在测试集上 news20.b。数据集中样本数量从9619~456886不 进行5遍五折交叉验证，将这25次的结果取平均值 等。特征维度的范围为20985~1355191。实验设 作为最终的测试结果。 置与标准数据集相似，实验结果如表2所示。可以 本文比较了如下5种算法： 发现，TPAUC算法在高维稀疏数据上与其他算法 1)OPAUC:优化AUC单遍学习算法 的效果具有可比性或性能更优。 表1 TPAUC在低维数据集上性能比较 Table 1 Comparisons of TPAUC on low-dim.datasets 数据集 diabetes fourlcass german splice usps letter magic04 a9a TPAUC 0.8411 0.8309 0.7981 0.9151 0.9713 0.8115 0.8319 0.9005 OPAUC 0.8309 0.8310 0.7978 0.9231 0.9620 0.8114 0.8383 0.9002 OAMseq 0.8254 0.8306 0.7747 0.8594 0.9310 0.7549 0.8238 0.8420 OAMgra 0.8295 0.8295 0.7723 0.8864 0.9348 0.7603 0.8259 0.8571 Online Uni-Exp 0.8215 0.8281 0.7908 0.8931 0.9538 0.8113 0.8353 0.9005 Online Uni-Squ 0.8258 0.8292 0.7899 0.9153 0.9563 0.8053 0.8344 0.8949 表2 TPAUC在高维数据集上性能比较 Table 2 Comparisons of TPAUC on high-dim.datasets 数据集 real-sim rev rev1v2 sector.lvr sector news20 ecml2012 news20.b TPAUC 0.9753 0.9903 0.9765 0.9966 0.9237 0.8910 0.9620 0.6401 OPAUC 0.9745 0.9802 0.9633 0.9965 0.9296 0.8840 0.9630 0.6406 OAMseq 0.9840 0.9885 0.9686 0.9965 0.9163 0.8543 0.9200 0.6314 OAMgra 0.9762 0.9852 0.9604 0.9955 0.9043 0.8346 0.9657 0.6351 Online Uni-Exp 0.9914 0.9907 0.9822 0.9969 0.9215 0.8880 0.9820 0.6347 Online Uni-Squ 0.9920 0.9918 0.9818 0.9669 0.9203 0.8878 0.9530 0.6237 3结束语 AUC两遍学习算法TPAUC。新提出的算法只需计 算与存储一阶统计量，而不需要存储二阶统计量， ROC曲线下的面积（简称AUC)是机器学习中 从而有效地提高效率，最后本文通过实验验证了该 一种重要的性能评价准则，由于AUC定义于正负 算法的有效性。 样本之间，传统方法需存储整个数据而不能适用于 大数据。为此Gao等提出优化AUC的单遍学习算 参考文献： 法，该算法仅需遍历数据一次，通过存储一阶与二 [1]HSIEH F,TURNBULL B W.Nonparametric and semipara- 阶统计量来进行优化AUC学习。本文致力于减少 metric estimation of the receiver operating characteristic 二阶统计量的计算与存储开销，提出一种新的优化 curve[J].The annals of statistics,1996,24(1):25-40

2 实验验证 本文将在标准真实数据集和高维数据集实验验 证所提方法的有效性，其中 8 个标准数据集分别为 diabetes、fourclass、german、splice、usps、letter、ma￾gic04、a9a。数据集中样本数量从 768~32 561 不 等，样本维度的范围从 8~256。所有数据集的特征 都被规范到[-1, 1]，多分类问题被转变为两分类问 题，随机将类别划分成两类。 η λ {2 −10 ,2 −9 ,2 −8 ,··· ,2,4} TPAUC 算法的学习率参数 和正则化参数 范 围都为 。首先将数据集划分为 训练集和测试集，参数的选择通过在训练集上进行 五折交叉验证来确定。选定参数后，再在测试集上 进行 5 遍五折交叉验证，将这 25 次的结果取平均值 作为最终的测试结果。 本文比较了如下 5 种算法： 1) OPAUC：优化 AUC 单遍学习算法[3]。 2) OAMseq：优化 AUC 的在线学习算法[14]。 3) OAMgra：优化 AUC 的在线学习算法[14]。 4) Online Uni-Exp：优化加权单变量指数损失函 数 [20]。 5) Online Uni-Squ：优化加权单变量平方损失函 数 [20]。 实验结果如表 1 所示，不难发现，本文提出的 优化 AUC 两遍学习方法 TPAUC 性能与 OPAUC 相当， 但明显优于 OAMseq、OAMgra、Online Uni￾Exp 以及 Online Uni-Squ。 本文选用 8 个高维稀疏数据集，分别为 real￾sim、rcv、rcv1v2、sector、sector.lvr、news20、ecml2012、 news20.b。数据集中样本数量从 9 619~456 886 不 等。特征维度的范围为 20 985~1 355 191。实验设 置与标准数据集相似， 实验结果如表 2 所示。可以 发现，TPAUC 算法在高维稀疏数据上与其他算法 的效果具有可比性或性能更优。 3 结束语 ROC 曲线下的面积 (简称 AUC) 是机器学习中 一种重要的性能评价准则，由于 AUC 定义于正负 样本之间，传统方法需存储整个数据而不能适用于 大数据。为此 Gao 等提出优化 AUC 的单遍学习算 法，该算法仅需遍历数据一次，通过存储一阶与二 阶统计量来进行优化 AUC 学习。本文致力于减少 二阶统计量的计算与存储开销，提出一种新的优化 AUC 两遍学习算法 TPAUC。新提出的算法只需计 算与存储一阶统计量，而不需要存储二阶统计量， 从而有效地提高效率，最后本文通过实验验证了该 算法的有效性。 参考文献： HSIEH F, TURNBULL B W. Nonparametric and semipara￾metric estimation of the receiver operating characteristic curve[J]. The annals of statistics, 1996, 24(1): 25–40. [1] 表 1 TPAUC 在低维数据集上性能比较 Table 1 Comparisons of TPAUC on low-dim. datasets 数据集 diabetes fourlcass german splice usps letter magic04 a9a TPAUC 0.841 1 0.830 9 0.798 1 0.915 1 0.971 3 0.811 5 0.831 9 0.900 5 OPAUC 0.830 9 0.831 0 0.797 8 0.923 1 0.962 0 0.811 4 0.838 3 0.900 2 OAMseq 0.825 4 0.830 6 0.774 7 0.859 4 0.931 0 0.754 9 0.823 8 0.842 0 OAMgra 0.829 5 0.829 5 0.772 3 0.886 4 0.934 8 0.760 3 0.825 9 0.857 1 Online Uni-Exp 0.821 5 0.828 1 0.790 8 0.893 1 0.953 8 0.811 3 0.835 3 0.900 5 Online Uni-Squ 0.825 8 0.829 2 0.789 9 0.915 3 0.956 3 0.805 3 0.834 4 0.894 9 表 2 TPAUC 在高维数据集上性能比较 Table 2 Comparisons of TPAUC on high-dim. datasets 数据集 real-sim rcv rcv1v2 sector.lvr sector news20 ecml2012 news20.b TPAUC 0.975 3 0.990 3 0.976 5 0.996 6 0.923 7 0.891 0 0.962 0 0.640 1 OPAUC 0.974 5 0.980 2 0.963 3 0.996 5 0.929 6 0.884 0 0.963 0 0.640 6 OAMseq 0.984 0 0.988 5 0.968 6 0.996 5 0.916 3 0.854 3 0.920 0 0.631 4 OAMgra 0.976 2 0.985 2 0.960 4 0.995 5 0.904 3 0.834 6 0.965 7 0.635 1 Online Uni-Exp 0.991 4 0.990 7 0.982 2 0.996 9 0.921 5 0.888 0 0.982 0 0.634 7 Online Uni-Squ 0.992 0 0.991 8 0.981 8 0.966 9 0.920 3 0.887 8 0.953 0 0.623 7 第 3 期 栾寻，等：优化 AUC 两遍学习算法 ·397·

·398· 智能系统学报 第13卷 [2]ELKAN C.The foundations of cost-sensitive learning[C]// functions[Cl//Proceedings of the 18th Annual Conference Proceedings of the 17th International Joint Conference on on Learning Theory.Bertinoro,Italy,2005:16-31 Artificial Intelligence.Seattle,WA,2001:973-978. [13]GAO Wei,ZHOU Zhihua.Uniform convergence,stability [3]GAO Wei,JIN Rong,ZHU Shenghuo,et al.One-pass AUC and learnability for ranking problems[C//Proceedings of optimization[C]//Proceedings of the 30th International Con- the 23rd International Joint Conference on Artificial Intelli- ference on Machine Learning.Atlanta,GA,2013:906-914. gence.Beijing,China,2013:1337-1343. [4]HAND D J.Measuring classifier performance:a coherent [14]ZHAO Peilin,HOI S C H,JIN Rong,et al.Online AUC alternative to the area under the ROC curve[J].Machine maximization[C]//Proceedings of the 28th International learning.2009,77(1):103-123. Conference on Machine Learning.Bellevue,WA,2011: [5]EGAN J P.Signal detection theory and ROC analysis,series 233-240. in cognition and perception[M].New York:Academic [15]GAO Wei,WANG Lu,JIN Rong,et al.One-pass AUC op- Press.1975. timization[J].Artificial intelligence,2016,236:1-29. [6]WU Jianxin,BRUBAKER S C,MULLIN M D,et al.Fast [16]SHALEV-SHWARTZ S,SINGER Y,SREBRO N,et al. asymmetric learning for cascade face detection[J].IEEE Pegasos:primal estimated sub-gradient solver for SVM[J]. transactions on pattern analysis and machine intelligence, Mathematical programming,2011,127(1):3-30. 2008.30(3):369-382. [17]CESA-BIANCHI N,LUGOSI G.Prediction,learning,and [7]BREFELD U,SCHEFFER T.AUC maximizing support games[M].New York:Cambridge University Press,2006. vector learning[C]//Proceedings of ICML 2005 Workshop [18]HAZAN E,KALAIA,KALE S,et al.Logarithmic regret on ROC Analysis in Machine Learning.Bonn,Germany, algorithms for online convex optimization[C]//Proceedings of the 19th Annual Conference on Learning Theory.Pitts- 2005. burgh,PA,2006:499-513. [8]JOACHIMS T.A support vector method for multivariate [19]DEVROYE L,GYORFI L,LUGOSI G.A probabilistic performance measures[C]//Proceedings of the 22nd Interna- theory of pattern recognition[M].New York:Springer, tional Conference on Machine Learning.Bonn,Germany, 1996 2005:377-384. [20]KOTLOWSKI W,DEMBCZYNSKI K,HULLERMEIER 9]FREUND Y,IYER R,SCHAPIRE R,et al.An efficient E.Bipartite ranking through minimization of univariate boosting algorithm for combining preferences[J].Journal of loss[C]//Proceedings of the 28th International Conference machine learning research,2003,4:933-969. on Machine Learning.Bellevue,WA,2011:1113-1120. [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 栾寻，男，1994年生，硕士研究 生，主要研究方向为大规模机器学习、 [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

ELKAN C. The foundations of cost-sensitive learning[C]// Proceedings of the 17th International Joint Conference on Artificial Intelligence. Seattle, WA, 2001: 973–978. [2] GAO Wei, JIN Rong, ZHU Shenghuo, et al. One-pass AUC optimization[C]//Proceedings of the 30th International Con￾ference on Machine Learning. Atlanta, GA, 2013: 906–914. [3] HAND D J. Measuring classifier performance: a coherent alternative to the area under the ROC curve[J]. Machine learning, 2009, 77(1): 103–123. [4] EGAN J P. Signal detection theory and ROC analysis, series in cognition and perception[M]. New York: Academic Press, 1975. [5] 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. [6] BREFELD U, SCHEFFER T. AUC maximizing support vector learning[C]//Proceedings of ICML 2005 Workshop on ROC Analysis in Machine Learning. Bonn, Germany, 2005. [7] JOACHIMS T. A support vector method for multivariate performance measures[C]//Proceedings of the 22nd Interna￾tional Conference on Machine Learning. Bonn, Germany, 2005: 377–384. [8] 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. [9] 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. [10] 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. [11] [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. GAO Wei, ZHOU Zhihua. Uniform convergence, stability and learnability for ranking problems[C]//Proceedings of the 23rd International Joint Conference on Artificial Intelli￾gence. Beijing, China, 2013: 1337–1343. [13] 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. [14] GAO Wei, WANG Lu, JIN Rong, et al. One-pass AUC op￾timization[J]. Artificial intelligence, 2016, 236: 1–29. [15] 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. [16] CESA-BIANCHI N, LUGOSI G. Prediction, learning, and games[M]. New York: Cambridge University Press, 2006. [17] 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. Pitts￾burgh, PA, 2006: 499–513. [18] DEVROYE L, GYÖRFI L, LUGOSI G. A probabilistic theory of pattern recognition[M]. New York: Springer, 1996. [19] 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. [20] 作者简介： 栾寻，男，1994 年生，硕士研究 生，主要研究方向为大规模机器学习、 推荐系统。 ·398· 智 能 系 统 学 报 第 13 卷