Semidefinite and Spectral Relaxations for Multi-Label Classification
  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.
