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.

本文介绍了结构预测在计算机视觉和自然语言处理等领域中的应用，主要是通过最大后验推断或整数线性规划来进行预测，但由于需要复杂的打分函数来获得准确的预测结果，因此学习和推断通常需要使用近似求解器。我们提出了一个理论解释，解释了基于线性规划松弛的近似算法在真实场景中的紧密性，并表明使用 LP 松弛推断进行学习有助于保证训练示例的整整性。