Optimizing the Multiclass F-Measure via Biconcave Programming
Optimizing the Multiclass F-Measure via Biconcave Programming
复制标题
通过双凹规划优化多类 F 测量
DOI：
--
复制
发表时间：
2016
期刊：
影响因子：
--
通讯作者：
H. G. Ramaswamy
中科院分区：
文献类型：
--
作者：
H. Narasimhan;Weiwei Pan;Purushottam Kar;P. Protopapas;H. G. Ramaswamy
F度量及其变体是在存在严重类别不平衡的情况下评估分类和检索任务的首选性能度量。因此，非常希望能够在大规模数据上直接优化这些性能度量。最近的进展表明，这是可能的，在简单的二元分类设置。然而，在班级众多的多班级环境中，进展甚微，而且班级不平衡更为严重。缺乏进展是特别明显的宏观平均F-措施，这是广泛首选的F-措施变量在多类设置，由于其同等重视罕见的类。已知的优化方法对于宏F测量的缩放性差，通常需要类的数量呈指数的运行时间。我们开发BEAM-F，第一个有效的方法直接优化的宏观F-措施在多类设置。这里的挑战是优化混淆矩阵空间上的分数线性函数之和的棘手性。我们克服了这个困难，制定了一个双凹最大化程序的问题，并解决它使用一个有效的交替最大化的方法，涉及一个弗兰克-沃尔夫迭代求解器。我们的方法提供了保证收敛到一个固定的点和实验表明，对于一个范围内的合成数据集和现实世界的应用程序，我们的方法提供了上级性能表现出大类不平衡的问题。
The F-measure and its variants are performance measures of choice for evaluating classification and retrieval tasks in the presence of severe class imbalance. It is thus highly desirable to be able to directly optimize these performance measures on large-scale data. Recent advances have shown that this is possible in the simple binary classification setting. However, scant progress exists in multiclass settings with a large number of classes where, in addition, class-imbalance is much more severe. The lack of progress is especially conspicuous for the macro-averaged F-measure, which is the widely preferred F-measure variant in multiclass settings due to its equal emphasis on rare classes. Known methods of optimization scale poorly for macro F-measure, often requiring run times that are exponential in the number of classes. We develop BEAM-F, the first efficient method for directly optimizing the macro F-measure in multiclass settings. The challenge here is the intractability of optimizing a sum of fractional-linear functions over the space of confusion matrices. We overcome this difficulty by formulating the problem as a biconcave maximization program and solve it using an efficient alternating maximization approach that involves a Frank-Wolfe based iterative solver. Our approach offers guaranteed convergence to a stationary point and experiments show that, for a range synthetic data sets and real-world applications, our method offers superior performance on problems exhibiting large class imbalance.