DivMCuts: Faster Training of Structural SVMs with Diverse M-Best Cutting-Planes

Abner Guzman-Rivera, Pushmeet Kohli, Dhruv Batra
Proceedings of the Sixteenth International Conference on Artificial Intelligence and Statistics, PMLR 31:316-324, 2013.

Abstract

Training of Structural SVMs involves solving a large Quadratic Program (QP). One popular method for solving this QP is a cutting-plane approach, where the most violated constraint is iteratively added to a working-set of constraints. Unfortunately, training models with a large number of parameters remains a time consuming process. This paper shows that significant computational savings can be achieved by adding multiple diverse and highly violated constraints at every iteration of the cutting-plane algorithm. We show that generation of such diverse cutting-planes involves extracting diverse M-Best solutions from the loss-augmented score of the training instances. To find these diverse M-Best solutions, we employ a recently proposed algorithm [4]. Our experiments on image segmentation and protein side-chain prediction show that the proposed approach can lead to significant computational savings, e.g., ∼28% reduction in training time.

Cite this Paper

BibTeX
@InProceedings{pmlr-v31-guzman-rivera13a, title = {DivMCuts: Faster Training of Structural SVMs with Diverse M-Best Cutting-Planes}, author = {Guzman-Rivera, Abner and Kohli, Pushmeet and Batra, Dhruv}, booktitle = {Proceedings of the Sixteenth International Conference on Artificial Intelligence and Statistics}, pages = {316--324}, year = {2013}, editor = {Carvalho, Carlos M. and Ravikumar, Pradeep}, volume = {31}, series = {Proceedings of Machine Learning Research}, address = {Scottsdale, Arizona, USA}, month = {29 Apr--01 May}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v31/guzman-rivera13a.pdf}, url = {https://proceedings.mlr.press/v31/guzman-rivera13a.html}, abstract = {Training of Structural SVMs involves solving a large Quadratic Program (QP). One popular method for solving this QP is a cutting-plane approach, where the most violated constraint is iteratively added to a working-set of constraints. Unfortunately, training models with a large number of parameters remains a time consuming process. This paper shows that significant computational savings can be achieved by adding multiple diverse and highly violated constraints at every iteration of the cutting-plane algorithm. We show that generation of such diverse cutting-planes involves extracting diverse M-Best solutions from the loss-augmented score of the training instances. To find these diverse M-Best solutions, we employ a recently proposed algorithm [4]. Our experiments on image segmentation and protein side-chain prediction show that the proposed approach can lead to significant computational savings, e.g., ∼28% reduction in training time.} }
Endnote
%0 Conference Paper %T DivMCuts: Faster Training of Structural SVMs with Diverse M-Best Cutting-Planes %A Abner Guzman-Rivera %A Pushmeet Kohli %A Dhruv Batra %B Proceedings of the Sixteenth International Conference on Artificial Intelligence and Statistics %C Proceedings of Machine Learning Research %D 2013 %E Carlos M. Carvalho %E Pradeep Ravikumar %F pmlr-v31-guzman-rivera13a %I PMLR %P 316--324 %U https://proceedings.mlr.press/v31/guzman-rivera13a.html %V 31 %X Training of Structural SVMs involves solving a large Quadratic Program (QP). One popular method for solving this QP is a cutting-plane approach, where the most violated constraint is iteratively added to a working-set of constraints. Unfortunately, training models with a large number of parameters remains a time consuming process. This paper shows that significant computational savings can be achieved by adding multiple diverse and highly violated constraints at every iteration of the cutting-plane algorithm. We show that generation of such diverse cutting-planes involves extracting diverse M-Best solutions from the loss-augmented score of the training instances. To find these diverse M-Best solutions, we employ a recently proposed algorithm [4]. Our experiments on image segmentation and protein side-chain prediction show that the proposed approach can lead to significant computational savings, e.g., ∼28% reduction in training time.
RIS
TY - CPAPER TI - DivMCuts: Faster Training of Structural SVMs with Diverse M-Best Cutting-Planes AU - Abner Guzman-Rivera AU - Pushmeet Kohli AU - Dhruv Batra BT - Proceedings of the Sixteenth International Conference on Artificial Intelligence and Statistics DA - 2013/04/29 ED - Carlos M. Carvalho ED - Pradeep Ravikumar ID - pmlr-v31-guzman-rivera13a PB - PMLR DP - Proceedings of Machine Learning Research VL - 31 SP - 316 EP - 324 L1 - http://proceedings.mlr.press/v31/guzman-rivera13a.pdf UR - https://proceedings.mlr.press/v31/guzman-rivera13a.html AB - Training of Structural SVMs involves solving a large Quadratic Program (QP). One popular method for solving this QP is a cutting-plane approach, where the most violated constraint is iteratively added to a working-set of constraints. Unfortunately, training models with a large number of parameters remains a time consuming process. This paper shows that significant computational savings can be achieved by adding multiple diverse and highly violated constraints at every iteration of the cutting-plane algorithm. We show that generation of such diverse cutting-planes involves extracting diverse M-Best solutions from the loss-augmented score of the training instances. To find these diverse M-Best solutions, we employ a recently proposed algorithm [4]. Our experiments on image segmentation and protein side-chain prediction show that the proposed approach can lead to significant computational savings, e.g., ∼28% reduction in training time. ER -
APA
Guzman-Rivera, A., Kohli, P. & Batra, D.. (2013). DivMCuts: Faster Training of Structural SVMs with Diverse M-Best Cutting-Planes. Proceedings of the Sixteenth International Conference on Artificial Intelligence and Statistics, in Proceedings of Machine Learning Research 31:316-324 Available from https://proceedings.mlr.press/v31/guzman-rivera13a.html.

Related Material