The LCFI website uses cookies only for anonymised website statistics and for ensuring our security, never for tracking or identifying you individually. To find out more, and to find out how we protect your personal information, please read our privacy policy.

Train and Test Tightness of LP Relaxations in Structured Prediction

Academic Journal article by Ofer Meshi, Mehrdad Mahdavi, Adrian Weller, David Sontag

Train and Test Tightness of LP Relaxations in Structured Prediction, Journal of Machine Learning Research (2019)

Structured prediction is used in areas such as computer vision and natural language processing to predict structured outputs such as seg- mentations or parse trees. In these settings, prediction is performed by MAP inference or, equivalently, by solving an integer linear pro- gram. 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 program- ming (LP) relaxations are often tight on real-world instances. In par- ticular, we show that learning with LP relaxed inference encourages integrality of training instances, and that tightness generalizes from train to test data.

Download Academic Journal article