TY - GEN
T1 - Efficient exact inference in planar ising models
AU - Schraudolph, Nicol N.
AU - Kamenetsky, Dmitry
PY - 2009
Y1 - 2009
N2 - 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 detection task shows our approach to be efficient and effective. A C++ implementation is available from http://nic.schraudolph.org/isinf/.
AB - 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 detection task shows our approach to be efficient and effective. A C++ implementation is available from http://nic.schraudolph.org/isinf/.
UR - http://www.scopus.com/inward/record.url?scp=80053434096&partnerID=8YFLogxK
M3 - Conference contribution
SN - 9781605609492
T3 - Advances in Neural Information Processing Systems 21 - Proceedings of the 2008 Conference
SP - 1417
EP - 1424
BT - Advances in Neural Information Processing Systems 21 - Proceedings of the 2008 Conference
PB - Neural Information Processing Systems
T2 - 22nd Annual Conference on Neural Information Processing Systems, NIPS 2008
Y2 - 8 December 2008 through 11 December 2008
ER -