Semidefinite and Spectral Relaxations for Multi-Label Classification
This work addresses multi-label classification, an incremental improvement for machine learning applications.
The paper tackles multi-label classification by learning a quadratic prior over labels to encode attractive and repulsive relations, optimizing for accuracy or F1-score, and shows performance improvements on standard datasets.
In this paper, we address the problem of multi-label classification. We consider linear classifiers and propose to learn a prior over the space of labels to directly leverage the performance of such methods. This prior takes the form of a quadratic function of the labels and permits to encode both attractive and repulsive relations between labels. We cast this problem as a structured prediction one aiming at optimizing either the accuracies of the predictors or the F 1-score. This leads to an optimization problem closely related to the max-cut problem, which naturally leads to semidefinite and spectral relaxations. We show on standard datasets how such a general prior can improve the performances of multi-label techniques.