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

N. N. Schraudolph. Polynomial-Time Exact Inference in NP-Hard Binary MRFs via Reweighted Perfect Matching. In 13th Intl. Conf. Artificial Intelligence and Statistics (AIstats), pp. 717–724, Journal of Machine Learning Research, Chia Laguna, Italy, 2010.

 484.6kB 567.3kB 1013.9kB

### Abstract

We develop a new form of reweighting (Wainwright et al., 2005) 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.

### BibTeX Entry

@inproceedings{Schraudolph10,
author = {Nicol N. Schraudolph},
title = {\href{http://nic.schraudolph.org/pubs/Schraudolph10.pdf}{
Polynomial-Time Exact Inference in {NP}-Hard
Binary {MRF}s via Reweighted Perfect Matching}},
pages = {717--724},
editor = {Yee Whye Teh and Mike Titterington},
booktitle = {13$^{th}$ Intl.\ Conf.\ Artificial
Intelligence and Statistics (AIstats)},
volume =  9,
series = {Workshop and Conference Proceedings},
publisher =  jmlr,
year =  2010,
b2h_type = {Top Conferences},
b2h_topic = {Ising Models},
abstract = {
We develop a new form of reweighting (Wainwright et al., 2005)
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.
}}


Generated by bib2html.pl (written by Patrick Riley) on Thu Sep 25, 2014 12:00:33