Skip navigation
Skip navigation

Efficient exact inference in planar Ising models

Schraudolph, Nicol; Kamenetsky, Dmitry


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...[Show more]

CollectionsANU Research Publications
Date published: 2008
Type: Conference paper
Source: Advances in Neural Information Processing Systems 21


File Description SizeFormat Image
01_Schraudolph_Efficient_exact_inference_in_2008.pdf15.6 kBAdobe PDF    Request a copy
02_Schraudolph_Efficient_exact_inference_in_2008.pdf774.22 kBAdobe PDF    Request a copy
03_Schraudolph_Efficient_exact_inference_in_2008.pdf433.46 kBAdobe PDF    Request a copy
04_Schraudolph_Efficient_exact_inference_in_2008.pdf317.61 kBAdobe PDF    Request a copy

Items in Open Research are protected by copyright, with all rights reserved, unless otherwise indicated.

Updated:  19 May 2020/ Responsible Officer:  University Librarian/ Page Contact:  Library Systems & Web Coordinator