Train and Test Tightness of LP Relaxations in Structured Prediction

Ofer Meshi, Mehrdad Mahdavi, Adrian Weller, David Sontag
Proceedings of The 33rd International Conference on Machine Learning, PMLR 48:1776-1785, 2016.

Abstract

Structured prediction is used in areas such as computer vision and natural language processing to predict structured outputs such as segmentations or parse trees. In these settings, prediction is performed by MAP inference or, equivalently, by solving an integer linear program. Because of the complex scoring functions required to obtain accurate predictions, both learning and inference typically require the use of approximate solvers. We propose a theoretical explanation to the striking observation that approximations based on linear programming (LP) relaxations are often tight on real-world instances. In particular, we show that learning with LP relaxed inference encourages integrality of training instances, and that tightness generalizes from train to test data.

Cite this Paper

BibTeX
@InProceedings{pmlr-v48-meshi16, title = {Train and Test Tightness of LP Relaxations in Structured Prediction}, author = {Meshi, Ofer and Mahdavi, Mehrdad and Weller, Adrian and Sontag, David}, booktitle = {Proceedings of The 33rd International Conference on Machine Learning}, pages = {1776--1785}, year = {2016}, editor = {Balcan, Maria Florina and Weinberger, Kilian Q.}, volume = {48}, series = {Proceedings of Machine Learning Research}, address = {New York, New York, USA}, month = {20--22 Jun}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v48/meshi16.pdf}, url = {https://proceedings.mlr.press/v48/meshi16.html}, abstract = {Structured prediction is used in areas such as computer vision and natural language processing to predict structured outputs such as segmentations or parse trees. In these settings, prediction is performed by MAP inference or, equivalently, by solving an integer linear program. Because of the complex scoring functions required to obtain accurate predictions, both learning and inference typically require the use of approximate solvers. We propose a theoretical explanation to the striking observation that approximations based on linear programming (LP) relaxations are often tight on real-world instances. In particular, we show that learning with LP relaxed inference encourages integrality of training instances, and that tightness generalizes from train to test data.} }
Endnote
%0 Conference Paper %T Train and Test Tightness of LP Relaxations in Structured Prediction %A Ofer Meshi %A Mehrdad Mahdavi %A Adrian Weller %A David Sontag %B Proceedings of The 33rd International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2016 %E Maria Florina Balcan %E Kilian Q. Weinberger %F pmlr-v48-meshi16 %I PMLR %P 1776--1785 %U https://proceedings.mlr.press/v48/meshi16.html %V 48 %X Structured prediction is used in areas such as computer vision and natural language processing to predict structured outputs such as segmentations or parse trees. In these settings, prediction is performed by MAP inference or, equivalently, by solving an integer linear program. Because of the complex scoring functions required to obtain accurate predictions, both learning and inference typically require the use of approximate solvers. We propose a theoretical explanation to the striking observation that approximations based on linear programming (LP) relaxations are often tight on real-world instances. In particular, we show that learning with LP relaxed inference encourages integrality of training instances, and that tightness generalizes from train to test data.
RIS
TY - CPAPER TI - Train and Test Tightness of LP Relaxations in Structured Prediction AU - Ofer Meshi AU - Mehrdad Mahdavi AU - Adrian Weller AU - David Sontag BT - Proceedings of The 33rd International Conference on Machine Learning DA - 2016/06/11 ED - Maria Florina Balcan ED - Kilian Q. Weinberger ID - pmlr-v48-meshi16 PB - PMLR DP - Proceedings of Machine Learning Research VL - 48 SP - 1776 EP - 1785 L1 - http://proceedings.mlr.press/v48/meshi16.pdf UR - https://proceedings.mlr.press/v48/meshi16.html AB - Structured prediction is used in areas such as computer vision and natural language processing to predict structured outputs such as segmentations or parse trees. In these settings, prediction is performed by MAP inference or, equivalently, by solving an integer linear program. Because of the complex scoring functions required to obtain accurate predictions, both learning and inference typically require the use of approximate solvers. We propose a theoretical explanation to the striking observation that approximations based on linear programming (LP) relaxations are often tight on real-world instances. In particular, we show that learning with LP relaxed inference encourages integrality of training instances, and that tightness generalizes from train to test data. ER -
APA
Meshi, O., Mahdavi, M., Weller, A. & Sontag, D.. (2016). Train and Test Tightness of LP Relaxations in Structured Prediction. Proceedings of The 33rd International Conference on Machine Learning, in Proceedings of Machine Learning Research 48:1776-1785 Available from https://proceedings.mlr.press/v48/meshi16.html.

Related Material