Polynomial-Time Exact Inference in NP-Hard Binary MRFs via Reweighted Perfect Matching
Abstract
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 \times 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^3)$ even though this problem is NP-hard and non-approximable in polynomial time. We discuss limitations of our current implementation and propose ways to overcome them.
Cite
Text
Schraudolph. "Polynomial-Time Exact Inference in NP-Hard Binary MRFs via Reweighted Perfect Matching." Proceedings of the Thirteenth International Conference on Artificial Intelligence and Statistics, 2010.Markdown
[Schraudolph. "Polynomial-Time Exact Inference in NP-Hard Binary MRFs via Reweighted Perfect Matching." Proceedings of the Thirteenth International Conference on Artificial Intelligence and Statistics, 2010.](https://mlanthology.org/aistats/2010/schraudolph2010aistats-polynomialtime/)BibTeX
@inproceedings{schraudolph2010aistats-polynomialtime,
title = {{Polynomial-Time Exact Inference in NP-Hard Binary MRFs via Reweighted Perfect Matching}},
author = {Schraudolph, Nic},
booktitle = {Proceedings of the Thirteenth International Conference on Artificial Intelligence and Statistics},
year = {2010},
pages = {717-724},
volume = {9},
url = {https://mlanthology.org/aistats/2010/schraudolph2010aistats-polynomialtime/}
}