Maximum Margin Multi-Label Structured Prediction
Christoph H. Lampert · 2011
We study multi-label prediction for structured output sets, a problem that occurs, for example, in object detection in images, secondary structure prediction in com-putational biology, and graph matching with symmetries. Conventional multi-label classification techniques are typically not applicable in this situation, be-cause they require explicit enumeration of the label set, which is infeasible in case of structured outputs. Relying on techniques originally designed for single-label structured prediction, in particular structured support vector machines, results in reduced prediction accuracy, or leads to infeasible optimization problems. In this work we derive a maximum-margin training formulation for multi-label structured prediction that remains computationally tractable while achieving high prediction accuracy. It also shares most beneficial properties with single-label maximum-margin approaches, in particular formulation as a convex optimization problem, efficient working set training, and PAC-Bayesian generalization bounds. 1