Computer Science – Learning
Scientific paper
2008-10-24
Computer Science
Learning
Fixed a number of bugs in v1; added 10 pages of additional figures, explanations, proofs, and experiments
Scientific paper
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/
Kamenetsky Dmitry
Schraudolph Nicol N.
No associations
LandOfFree
Efficient Exact Inference in Planar Ising Models does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Efficient Exact Inference in Planar Ising Models, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Efficient Exact Inference in Planar Ising Models will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-698048