Efficient Exact Inference in Planar Ising Models
  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/
