Schraudolph, NicolKamenetsky, Dmitry2015-12-10December 8http://hdl.handle.net/1885/54287We 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/.Keywords: Boundary detection; Dual graphs; Exact computations; Exact inference; Graph cut; GraphicaL model; Marginals; Partition functions; Perfect matchings; Planarity; Polynomial-time algorithms; Submodularity; Graphic methods; Inference engines; Ising model; Par20082016-02-24