Submodular relaxation for inference in Markov random fields
This addresses a fundamental inference problem in computer vision and machine learning, offering a novel relaxation method that could improve approximate solutions for MRF-based applications.
The paper tackles the NP-hard problem of finding the most probable state in discrete Markov random fields (MRF energy minimization) by proposing a submodular relaxation approach (SMR) that constructs a submodular energy within a Lagrangian relaxation, applicable to pairwise and high-order MRFs with certain global potentials.
In this paper we address the problem of finding the most probable state of a discrete Markov random field (MRF), also known as the MRF energy minimization problem. The task is known to be NP-hard in general and its practical importance motivates numerous approximate algorithms. We propose a submodular relaxation approach (SMR) based on a Lagrangian relaxation of the initial problem. Unlike the dual decomposition approach of Komodakis et al., 2011 SMR does not decompose the graph structure of the initial problem but constructs a submodular energy that is minimized within the Lagrangian relaxation. Our approach is applicable to both pairwise and high-order MRFs and allows to take into account global potentials of certain types. We study theoretical properties of the proposed approach and evaluate it experimentally.