## Efficient Exact Inference in Planar Ising Models

N. N. Schraudolph and D. Kamenetsky. Efficient Exact Inference in Planar Ising Models. Technical Report 0810.4401, arXiv, 2008.
Short version

 981.4kB 669.7kB 1.5MB

### Abstract

We give polynomial-time algorithms for the exact computation of lowest-energy (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 well-known 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 well-understood subproblems (planar embedding, maximum-weight perfect matching) to established algorithms for which efficient implementations are freely available. Unlike graph cut methods, we can perform penalized maximum-likelihood as well as maximum-margin parameter estimation in the associated conditional random fields (CRFs), and employ marginal posterior probabilities as well as maximum a posteriori (MAP) states for prediction. Maximum-margin 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/.

### BibTeX Entry

@techreport{SchKam08,
author = {Nicol N. Schraudolph and Dmitry Kamenetsky},
title = {\href{http://nic.schraudolph.org/pubs/SchKam08.pdf}{
Efficient Exact Inference in Planar {I}sing Models}},
number = {\href{http://arxiv.org/abs/0810.4401}{0810.4401}},
institution = {\href{http://arxiv.org/}{arXiv}},
year =  2008,
b2h_type = {Other},
b2h_topic = {Ising Models},
b2h_note = {<a href="b2hd-SchKam09.html">Short version</a>},
abstract = {
We give polynomial-time algorithms for the exact computation
of lowest-energy (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 well-known 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
well-understood subproblems (planar embedding, maximum-weight
perfect matching) to established algorithms for which efficient
implementations are freely available.  Unlike graph cut methods,
we can perform penalized maximum-likelihood as well as
maximum-margin parameter estimation in the associated conditional
random fields (CRFs), and employ marginal posterior probabilities
as well as \emph{maximum a posteriori} (MAP) states for prediction.
Maximum-margin CRF parameter estimation on image denoising and
segmentation problems shows our approach to be efficient and
effective.  A C++ implementation is available from
{\small\url{http://nic.schraudolph.org/isinf/}}.
}}


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