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]
Items in Open Research are protected by copyright, with all rights reserved, unless otherwise indicated.