On MAP Inference by MWSS on Perfect Graphs
This work addresses the computational challenge of MAP inference in MRFs for researchers and practitioners in machine learning and optimization, offering incremental improvements by extending existing methods to broader classes of models.
The paper tackles the NP-hard problem of finding the most likely configuration in Markov random fields (MRFs) by reducing it to maximum weight stable set (MWSS) on perfect graphs, which allows polynomial-time inference; it presents new results including a general decomposition theorem, extensions to higher-order models, and an exact characterization for binary pairwise MRFs, expanding the range of tractable models.
Finding the most likely (MAP) configuration of a Markov random field (MRF) is NP-hard in general. A promising, recent technique is to reduce the problem to finding a maximum weight stable set (MWSS) on a derived weighted graph, which if perfect, allows inference in polynomial time. We derive new results for this approach, including a general decomposition theorem for MRFs of any order and number of labels, extensions of results for binary pairwise models with submodular cost functions to higher order, and an exact characterization of which binary pairwise MRFs can be efficiently solved with this method. This defines the power of the approach on this class of models, improves our toolbox and expands the range of tractable models.