提出高效线搜索算法，让梯度下降优化AUC更准更快。
Efficient line search for optimizing Area Under the ROC Curve in gradient descent
- 基于AUM的分段线性特性，设计路径跟踪线搜索法。
- 计算量仅比固定步长梯度下降多对数因子，但精度接近网格搜索。
- 适合需要精确优化AUC的二分类与变点检测任务。
ROC曲线在二分类和变点检测中具有重要价值，但因其曲线下面积（AUC）几乎处处为常数，难以直接用于学习。近期提出的误报率与漏报率最小值下的曲线下面积（AUM）可微，作为AUC的替代目标。本文研究AUM/AUC的分段线性/常数性质，提出新的高效路径跟踪线搜索算法，用于在线性模型梯度下降中每一步自动选择最优学习率。该算法在渐近时间复杂度上仅比固定步长梯度下降多一个对数因子，却能完整刻画AUM/AUC随步长变化的全貌。在二分类实验中验证其快速且精确；在变点检测任务中，性能与网格搜索相当，但速度显著提升。
原文摘要 · Abstract (English)
Receiver Operating Characteristic (ROC) curves are useful for evaluation in binary classification and changepoint detection, but difficult to use for learning since the Area Under the Curve (AUC) is piecewise constant (gradient zero almost everywhere). Recently the Area Under Min (AUM) of false positive and false negative rates has been proposed as a differentiable surrogate for AUC. In this paper we study the piecewise linear/constant nature of the AUM/AUC, and propose new efficient path-following algorithms for choosing the learning rate which is optimal for each step of gradient descent (line search), when optimizing a linear model. Remarkably, our proposed line search algorithm has the same log-linear asymptotic time complexity as gradient descent with constant step size, but it computes a complete representation of the AUM/AUC as a function of step size. In our empirical study of binary classification problems, we verify that our proposed algorithm is fast and exact; in changepoint detection problems we show that the proposed algorithm is just as accurate as grid search, but faster.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。