Repository logo
 

Train and test tightness of LP relaxations in structured prediction

Accepted version
Peer-reviewed

Type

Article

Change log

Authors

Meshi, O 
London, B 
Sontag, D 

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.

Description

This is the author accepted manuscript. The final version is available from Microtome Publishing via http://www.jmlr.org/proceedings/papers/v48/meshi16.html

Keywords

Journal Title

Journal of Machine Learning Research

Conference Name

Journal ISSN

1532-4435
1533-7928

Volume Title

48

Publisher

Microtome Publishing

Publisher DOI

Publisher URL