## 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

### Download

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/}}. }}