Efficient Exact Inference in Planar Ising Models

N. N. Schraudolph and D. Kamenetsky. Efficient Exact Inference in Planar Ising Models. In Advances in Neural Information Processing Systems (NIPS), pp. 1417–1424, Curran Associates, Inc., 2009.
Long version

Download

775.8kB	125.5kB	757.1kB

Abstract

We give polynomial-time algorithms for the exact computation of lowest-energy states, worst margin violators, partition functions, and marginals 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 in an expanded dual graph. Maximum-margin parameter estimation for a boundary detection task shows our approach to be efficient and effective. A C++ implementation is available from http://nic.schraudolph.org/isinf/.

BibTeX Entry

@inproceedings{SchKam09,
     author = {Nicol N. Schraudolph and Dmitry Kamenetsky},
      title = {\href{http://nic.schraudolph.org/pubs/SchKam09.pdf}{
               Efficient Exact Inference in Planar {I}sing Models}},
      pages = {1417--1424},
     editor = {Daphne Koller and Yoshua Bengio and Dale Schuurmans
               and L\'eon Bottou and Aron Culotta},
  booktitle =  nips,
     volume =  21,
  publisher = {Curran Associates, Inc.},
       year =  2009,
   b2h_type = {Top Conferences},
  b2h_topic = {Ising Models},
   b2h_note = {<a href="b2hd-SchKam08.html">Long version</a>},
   abstract = {
    We give polynomial-time algorithms for the exact computation
    of lowest-energy states, worst margin violators, partition
    functions, and marginals 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 in an expanded
    dual graph. Maximum-margin parameter estimation for a boundary
    detection task shows our approach to be efficient and effective.
    A C++ implementation is available from
    {\small\url{http://nic.schraudolph.org/isinf/}}.
}}