Polynomial-Time Exact MAP Inference on Discrete Models with Global Dependencies

Considering the worst-case scenario, junction tree algorithm remains the most general solution for exact MAP inference with polynomial run-time guarantees. Unfortunately, its main tractability assumption requires the treewidth of a corresponding MRF to be bounded strongly limiting the range of admissible applications. In fact, many practical problems in the area of structured prediction require modelling of global dependencies by either directly introducing global factors or enforcing global constraints on the prediction variables. That, however, always results in a fully-connected graph making exact inference by means of this algorithm intractable. Previous work [1]-[4] focusing on the problem of loss-augmented inference has demonstrated how efficient inference can be performed on models with specific global factors representing non-decomposable loss functions within the training regime of SSVMs. In this paper, we provide a more general framework for an efficient exact inference and extend the set of handleable problem instances by allowing much finer interactions between the energy of the core model and the sufficient statistics of the global terms. We demonstrate the usefulness of our method in several use cases, including one that cannot be handled by any of the previous approaches.