Efficient Training of Structured SVMs via Soft Constraints
Ofer Meshi, Nathan Srebro, Tamir Hazan · 2015
Structured output prediction is a powerful framework for jointly predicting interdepen-dent output labels. Learning the parame-ters of structured predictors is a central task in machine learning applications. However, training the model from data often becomes computationally expensive. Several meth-ods have been proposed to exploit the model structure, or decomposition, in order to ob-tain efficient training algorithms. In particu-lar, methods based on linear programming re-laxation, or dual decomposition, decompose the prediction task into multiple simpler pre-diction tasks and enforce agreement between overlapping predictions. In this work we observe that relaxing these agreement con-straints and replacing them with soft con-straints yields a much easier optimization problem. Based on this insight we propose an alternative training objective, analyze its the-oretical properties, and derive an algorithm for its optimization. Our method, based on the Frank-Wolfe algorithm, achieves sig-nificant speedups over existing state-of-the-art methods without hurting prediction ac-curacy. 1