MAP estimation via agreement on (hyper)trees: Message-passing and linear programming

Martin J. Wainwright, Tommi S. Jaakkola, Alan S. Willsky

We develop and analyze methods for computing provably optimal {\em maximum a posteriori} (MAP) configurations for a subclass of Markov random fields defined on graphs with cycles.…