Structured Learning with Approximate Inference

Abstract In many structured prediction problems, the highest-scoring labeling is hard tocompute exactly, leading to the use of approximate inference methods. However, when inference is used in a learning algorithm, a good approximation of the scoremay not be sufficient. We show in particular that learning can fail even with an approximate inference method with rigorous approximation guarantees. There aretwo reasons for this. First, approximate methods can effectively reduce the expressivity of an underlying model by making it impossible to choose parameters thatreliably give good predictions. Second, approximations can respond to parameter changes in such a way that standard learning algorithms are misled. In contrast, wegive two positive results in the form of learning bounds for the use of LP-relaxed inference in structured perceptron and empirical risk minimization settings. Weargue that without understanding combinations of inference and learning, such as these, that are appropriately compatible, learning performance under approximateinference cannot be guaranteed.