A Linear Method for Online AUC Maximization
-
摘要: 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}算法更加高效.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.
-
Keywords:
- classification /
- AUC optimization /
- online learning /
- linear method /
- least square loss
-
计量
- 文章访问数: 1753
- HTML全文浏览量: 1
- PDF下载量: 501
下载:
