Fast and Scalable Structural SVM with Slack Rescaling

Heejin Choi, Ofer Meshi, Nathan Srebro
Proceedings of the 19th International Conference on Artificial Intelligence and Statistics, PMLR 51:667-675, 2016.

Abstract

We present an efficient method for training slack-rescaled structural SVM. Although finding the most violating label in a margin-rescaled formulation is often easy since the target function decomposes with respect to the structure, this is not the case for a slack-rescaled formulation, and finding the most violated label might be very difficult. Our core contribution is an efficient method for finding the most-violating-label in a slack-rescaled formulation, given an oracle that returns the most-violating-label in a (slightly modified) margin-rescaled formulation. We show that our method enables accurate and scalable training for slack-rescaled SVMs, reducing runtime by an order of magnitude compared to previous approaches to slack-rescaled SVMs.

Cite this Paper

BibTeX
@InProceedings{pmlr-v51-choi16, title = {Fast and Scalable Structural SVM with Slack Rescaling}, author = {Choi, Heejin and Meshi, Ofer and Srebro, Nathan}, booktitle = {Proceedings of the 19th International Conference on Artificial Intelligence and Statistics}, pages = {667--675}, year = {2016}, editor = {Gretton, Arthur and Robert, Christian C.}, volume = {51}, series = {Proceedings of Machine Learning Research}, address = {Cadiz, Spain}, month = {09--11 May}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v51/choi16.pdf}, url = {https://proceedings.mlr.press/v51/choi16.html}, abstract = {We present an efficient method for training slack-rescaled structural SVM. Although finding the most violating label in a margin-rescaled formulation is often easy since the target function decomposes with respect to the structure, this is not the case for a slack-rescaled formulation, and finding the most violated label might be very difficult. Our core contribution is an efficient method for finding the most-violating-label in a slack-rescaled formulation, given an oracle that returns the most-violating-label in a (slightly modified) margin-rescaled formulation. We show that our method enables accurate and scalable training for slack-rescaled SVMs, reducing runtime by an order of magnitude compared to previous approaches to slack-rescaled SVMs.} }
Endnote
%0 Conference Paper %T Fast and Scalable Structural SVM with Slack Rescaling %A Heejin Choi %A Ofer Meshi %A Nathan Srebro %B Proceedings of the 19th International Conference on Artificial Intelligence and Statistics %C Proceedings of Machine Learning Research %D 2016 %E Arthur Gretton %E Christian C. Robert %F pmlr-v51-choi16 %I PMLR %P 667--675 %U https://proceedings.mlr.press/v51/choi16.html %V 51 %X We present an efficient method for training slack-rescaled structural SVM. Although finding the most violating label in a margin-rescaled formulation is often easy since the target function decomposes with respect to the structure, this is not the case for a slack-rescaled formulation, and finding the most violated label might be very difficult. Our core contribution is an efficient method for finding the most-violating-label in a slack-rescaled formulation, given an oracle that returns the most-violating-label in a (slightly modified) margin-rescaled formulation. We show that our method enables accurate and scalable training for slack-rescaled SVMs, reducing runtime by an order of magnitude compared to previous approaches to slack-rescaled SVMs.
RIS
TY - CPAPER TI - Fast and Scalable Structural SVM with Slack Rescaling AU - Heejin Choi AU - Ofer Meshi AU - Nathan Srebro BT - Proceedings of the 19th International Conference on Artificial Intelligence and Statistics DA - 2016/05/02 ED - Arthur Gretton ED - Christian C. Robert ID - pmlr-v51-choi16 PB - PMLR DP - Proceedings of Machine Learning Research VL - 51 SP - 667 EP - 675 L1 - http://proceedings.mlr.press/v51/choi16.pdf UR - https://proceedings.mlr.press/v51/choi16.html AB - We present an efficient method for training slack-rescaled structural SVM. Although finding the most violating label in a margin-rescaled formulation is often easy since the target function decomposes with respect to the structure, this is not the case for a slack-rescaled formulation, and finding the most violated label might be very difficult. Our core contribution is an efficient method for finding the most-violating-label in a slack-rescaled formulation, given an oracle that returns the most-violating-label in a (slightly modified) margin-rescaled formulation. We show that our method enables accurate and scalable training for slack-rescaled SVMs, reducing runtime by an order of magnitude compared to previous approaches to slack-rescaled SVMs. ER -
APA
Choi, H., Meshi, O. & Srebro, N.. (2016). Fast and Scalable Structural SVM with Slack Rescaling. Proceedings of the 19th International Conference on Artificial Intelligence and Statistics, in Proceedings of Machine Learning Research 51:667-675 Available from https://proceedings.mlr.press/v51/choi16.html.

Related Material