Polynomial-Time Exact Inference in NP-Hard Binary MRFs via Reweighted Perfect Matching

Nic Schraudolph
Proceedings of the Thirteenth International Conference on Artificial Intelligence and Statistics, PMLR 9:717-724, 2010.

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 this Paper

BibTeX
@InProceedings{pmlr-v9-schraudolph10a, 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}, pages = {717--724}, year = {2010}, editor = {Teh, Yee Whye and Titterington, Mike}, volume = {9}, series = {Proceedings of Machine Learning Research}, address = {Chia Laguna Resort, Sardinia, Italy}, month = {13--15 May}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v9/schraudolph10a/schraudolph10a.pdf}, url = {https://proceedings.mlr.press/v9/schraudolph10a.html}, 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.} }
Endnote
%0 Conference Paper %T Polynomial-Time Exact Inference in NP-Hard Binary MRFs via Reweighted Perfect Matching %A Nic Schraudolph %B Proceedings of the Thirteenth International Conference on Artificial Intelligence and Statistics %C Proceedings of Machine Learning Research %D 2010 %E Yee Whye Teh %E Mike Titterington %F pmlr-v9-schraudolph10a %I PMLR %P 717--724 %U https://proceedings.mlr.press/v9/schraudolph10a.html %V 9 %X 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.
RIS
TY - CPAPER TI - Polynomial-Time Exact Inference in NP-Hard Binary MRFs via Reweighted Perfect Matching AU - Nic Schraudolph BT - Proceedings of the Thirteenth International Conference on Artificial Intelligence and Statistics DA - 2010/03/31 ED - Yee Whye Teh ED - Mike Titterington ID - pmlr-v9-schraudolph10a PB - PMLR DP - Proceedings of Machine Learning Research VL - 9 SP - 717 EP - 724 L1 - http://proceedings.mlr.press/v9/schraudolph10a/schraudolph10a.pdf UR - https://proceedings.mlr.press/v9/schraudolph10a.html AB - 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. ER -
APA
Schraudolph, N.. (2010). Polynomial-Time Exact Inference in NP-Hard Binary MRFs via Reweighted Perfect Matching. Proceedings of the Thirteenth International Conference on Artificial Intelligence and Statistics, in Proceedings of Machine Learning Research 9:717-724 Available from https://proceedings.mlr.press/v9/schraudolph10a.html.

Related Material