TY - GEN
T1 - Train and test tightness of lp relaxations in structured prediction
AU - Meshi, Ofer
AU - Mahdavi, Mehrdad
AU - Weiler, Adrian
AU - Sontag, David
N1 - Publisher Copyright:
© 2016 by the author(s).
PY - 2016
Y1 - 2016
N2 - 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.
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.
UR - http://www.scopus.com/inward/record.url?scp=84998953774&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84998953774&partnerID=8YFLogxK
M3 - Conference contribution
AN - SCOPUS:84998953774
T3 - 33rd International Conference on Machine Learning, ICML 2016
SP - 2652
EP - 2664
BT - 33rd International Conference on Machine Learning, ICML 2016
A2 - Weinberger, Kilian Q.
A2 - Balcan, Maria Florina
PB - International Machine Learning Society (IMLS)
T2 - 33rd International Conference on Machine Learning, ICML 2016
Y2 - 19 June 2016 through 24 June 2016
ER -