Skip to yearly menu bar Skip to main content


Poster

Efficient Exact Inference in Planar Ising Models

Nicol Schraudolph · Dmitry Kamenetsky


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.

Live content is unavailable. Log in and register to view live content