  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.
