We consider sequential maximization of performance metrics that are general functions of a confusion matrix of a classifier (such as precision, F-measure, or G-mean). Such metrics are, in general, non-decomposable over individual instances, making their optimization very challenging. While they have been extensively studied under different frameworks in the batch setting, their analysis in the online learning regime is very limited, with only a few distinguished exceptions. In this paper, we introduce and analyze a general online algorithm that can be used in a straightforward way with a variety of complex performance metrics in binary, multi-class, and multi-label classification problems. The algorithm's update and prediction rules are appealingly simple and computationally efficient without the need to store any past data. We show the algorithm attains $\mathcal{O}(\frac{\ln n}{n})$ regret for concave and smooth metrics and verify the efficiency of the proposed algorithm in empirical studies.

我们介绍和分析了一种通用的在线算法，适用于二元、多类和多标签分类问题中的各种复杂性能指标，该算法的更新和预测规则简单且计算效率高，无需存储任何过去的数据，而且对于凹函数和平滑度函数达到了O(ln n/n)的遗憾，并通过实证研究验证了所提算法的效率。

优化复杂绩效指标的通用在线算法