Polynomial-Time Exact Inference in NP-Hard Binary MRFs via Reweighted Perfect Matching
Nic Schraudolph · 2010
We develop a new form of reweighting (Wainwright et al., 2005b) to leverage the relationship between Ising spin glasses and perfect matchings into a novel technique for the exact computation of MAP states in hitherto intractable binary Markov random fields. Our method solves an n× n lattice with external field and random couplings much faster, and for larger n, than the best competing algorithms. It empirically scales as O(n) even though this problem is NP-hard and nonapproximable in polynomial time. We discuss limitations of our current implementation and propose ways to overcome them.