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

Nic Schraudolph; JMLR W&CP 9:717-724, 2010.

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 by 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 non-approximable in polynomial time. We discuss limitations of our current implementation and propose ways to overcome them.



Home Page

Papers

Submissions

News

Scope

Editorial Board

Announcements

Proceedings

Open Source Software

Search

Login



RSS Feed

Page last modified on Wed Mar 24 15:36 GMT 2010.

Copyright @ JMLR 2000. All rights reserved.