Efficient Exact Inference in Planar Ising Models

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/

Fixed a number of bugs in v1; added 10 pages of additional figures, explanations, proofs, and experiments

References in corpus (2)

• Matching Kasteleyn Cities for Spin Glass Ground States
• Exact Ground States of Large Two-Dimensional Planar Ising Spin Glasses

Cited by in corpus (13)

• Large-scale Log-determinant Computation through Stochastic Chebyshev Expansions
• Generalized Fast Approximate Energy Minimization via Graph Cuts: Alpha-Expansion Beta-Shrink Moves
• Approximate inference on planar graphs using Loop Calculus and Belief Propagation
• Investigation of Finite-size 2D Ising Model with a Noisy Matrix of Spin-Spin Interactions
• Spectral Bounds for the Ising Ferromagnet on an Arbitrary Given Graph
• A class of random fields on complete graphs with tractable partition function
• ESSP: An Efficient Approach to Minimizing Dense and Nonsubmodular Energy Functions
• Tractable Minor-free Generalization of Planar Zero-field Ising Models
• A New Family of Tractable Ising Models
• Inference and Sampling of $K_{33}$-free Ising Models
• Classical algorithms for Forrelation
• Fairness constraints can help exact inference in structured prediction
• A Thorough View of Exact Inference in Graphs from the Degree-4 Sum-of-Squares Hierarchy