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