ISSN 1000-1239 CN 11-1777/TP

计算机研究与发展 ›› 2018, Vol. 55 ›› Issue (12): 2725-2733.doi: 10.7544/issn1000-1239.2018.20170357

• 人工智能 • 上一篇    下一篇

一种线性的在线AUC优化方法

朱真峰,翟艳祥,叶阳东   

  1. (郑州大学信息工程学院 郑州 450052) (iezfzhu@zzu.edu.cn)
  • 出版日期: 2018-12-01
  • 基金资助: 
    国家自然科学基金委员会-河南省人民政府人才培养联合基金项目(U1204610);国家自然科学基金项目(61772475,61502434);国家重点研发计划基金项目(2018YFB1201403);河南省科技攻关项目(172102210011);河南省高等学校青年骨干教师培养计划基金项目

A Linear Method for Online AUC Maximization

Zhu Zhenfeng, Zhai Yanxiang, Ye Yangdong   

  1. (School of Information Engineering, Zhengzhou University, Zhengzhou 450052)
  • Online: 2018-12-01

摘要: AUC(area under the ROC curve)优化问题的损失函数由来自不同类别的样本对构成,这使得依赖于损失函数之和的目标函数与训练样本数二次相关,不能直接使用传统在线学习方法求解.当前的在线AUC优化算法聚焦于在求解过程中避免直接计算所有的损失函数,以减小问题的规模,实现在线AUC优化.针对以上问题提出了一种AUC优化的新目标函数,该目标函数仅与训练样本数线性相关;理论分析表明:最小化该目标函数等价于最小化由L2正则化项和最小二乘损失函数组成的AUC优化的目标函数.基于新的目标函数,提出了在线AUC优化的线性方法(linear online AUC maximization, LOAM);根据不同的分类器更新策略,给出2种算法LOAM\-{ILSC}和LOAM\-{Ada}.实验表明:与原有方法相比,LOAM\-{ILSC}算法获得了更优的AUC性能,而对于实时或高维学习任务,LOAM\-{Ada}算法更加高效.

关键词: 分类, AUC优化, 在线学习, 线性方法, 最小二乘损失

Abstract: The loss function of AUC optimization involves pair-wise instances coming from different classes, so the objective functions of AUC methods, depending on the sum of pair-wise losses, are quadratic in the number of training examples. As a result, the objective functions of this type can not be directly solved through conventional online learning methods. The existing online AUC maximization methods focus on avoiding the direct calculation of all pair-wise loss functions, in order to reduce the problem sizes and achieve the online AUC optimization. To further solve the AUC optimization problems described above, we propose a novel AUC objective function that is only linear in the number of training examples. Theoretical analysis shows the minimization of the proposed objective function is equivalent to that of the objective function for AUC optimization by the combination of L2 regularization and least square surrogate loss. Based on this new objective function, we obtain the method named linear online AUC maximization (LOAM). According to different updating strategies for classifiers, we develop two algorithms for LOAM method: LOAM\-{ILSC} and LOAM\-{Ada}. Experimental results show that, compared with the rival methods, LOAM\-{ILSC} can achieve better AUC performance, and LOAM\-{Ada} is more effective and efficient to handle real-time or high dimensional learning tasks.

Key words: classification, AUC optimization, online learning, linear method, least square loss

中图分类号: