Efficient Exact Inference in Planar Ising Models
Abstract
We give polynomialtime algorithms for the exact computation of lowestenergy (ground) states, worst margin violators, log partition functions, and marginal edge probabilities in certain binary undirected graphical models. Our approach provides an interesting alternative to the wellknown graph cut paradigm in that it does not impose any submodularity constraints; instead we require planarity to establish a correspondence with perfect matchings (dimer coverings) in an expanded dual graph. We implement a unified framework while delegating complex but wellunderstood subproblems (planar embedding, maximumweight perfect matching) to established algorithms for which efficient implementations are freely available. Unlike graph cut methods, we can perform penalized maximumlikelihood as well as maximummargin parameter estimation in the associated conditional random fields (CRFs), and employ marginal posterior probabilities as well as maximum a posteriori (MAP) states for prediction. Maximummargin CRF parameter estimation on image denoising and segmentation problems shows our approach to be efficient and effective. A C++ implementation is available from http://nic.schraudolph.org/isinf/
 Publication:

arXiv eprints
 Pub Date:
 October 2008
 arXiv:
 arXiv:0810.4401
 Bibcode:
 2008arXiv0810.4401S
 Keywords:

 Computer Science  Machine Learning;
 Computer Science  Computer Vision and Pattern Recognition;
 Statistics  Machine Learning
 EPrint:
 Fixed a number of bugs in v1