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 13^th Intl. Conf. Artificial Intelligence and Statistics (AIstats), pp. 717–724, Journal of Machine Learning Research, Chia Laguna, Italy, to appear May 2010.

Download

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)},
    address = {Chia Laguna, Italy},
     volume =  9,
     series = {Workshop and Conference Proceedings},
  publisher =  jmlr,
      month = {to appear May},
       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.
}}