An Exact Algorithm for F-Measure Maximization

Part of Advances in Neural Information Processing Systems 24 (NIPS 2011)

Bibtex Metadata Paper


Krzysztof Dembczynski, Willem Waegeman, Weiwei Cheng, Eyke Hüllermeier


The F-measure, originally introduced in information retrieval, is nowadays routinely used as a performance metric for problems such as binary classification, multi-label classification, and structured output prediction. Optimizing this measure remains a statistically and computationally challenging problem, since no closed-form maximizer exists. Current algorithms are approximate and typically rely on additional assumptions regarding the statistical distribution of the binary response variables. In this paper, we present an algorithm which is not only computationally efficient but also exact, regardless of the underlying distribution. The algorithm requires only a quadratic number of parameters of the joint distribution (with respect to the number of binary responses). We illustrate its practical performance by means of experimental results for multi-label classification.