Efficient Exact Inference in Planar Ising Models
Abstract
We present polynomial-time algorithms for the exact computation of lowest- energy states, worst margin violators, partition functions, and marginals in 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 in an expanded dual graph. Maximum-margin parameter estimation for a boundary detection task shows our approach to be efficient and effective.
Cite
Text
Schraudolph and Kamenetsky. "Efficient Exact Inference in Planar Ising Models." Neural Information Processing Systems, 2008.Markdown
[Schraudolph and Kamenetsky. "Efficient Exact Inference in Planar Ising Models." Neural Information Processing Systems, 2008.](https://mlanthology.org/neurips/2008/schraudolph2008neurips-efficient/)BibTeX
@inproceedings{schraudolph2008neurips-efficient,
title = {{Efficient Exact Inference in Planar Ising Models}},
author = {Schraudolph, Nicol N. and Kamenetsky, Dmitry},
booktitle = {Neural Information Processing Systems},
year = {2008},
pages = {1417-1424},
url = {https://mlanthology.org/neurips/2008/schraudolph2008neurips-efficient/}
}