Efficient Exact Inference in Planar Ising Models

Nicol N. Schraudolph and Dmitry Kamenetsky. Efficient Exact Inference in Planar Ising Models. In Advances in Neural Information Processing Systems (NIPS), MIT Press, Cambridge, MA, to appear 2009.
Long version

Download

775.0kB	125.0kB	757.0kB

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{SchKam09b,
     author = {Nicol N. Schraudolph and Dmitry Kamenetsky},
      title = {\href{http://nic.schraudolph.org/pubs/SchKam09b.pdf}{
               Efficient Exact Inference in Planar {I}sing Models}},
  booktitle =  nips,
     volume =  21,
  publisher = {MIT Press},
    address = {Cambridge, MA},
      month = {to appear},
       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/}}.
}}