Timezone: »

 
Poster
Loop Series and Bethe Variational Bounds in Attractive Graphical Models
Erik Sudderth · Martin J Wainwright · Alan S Willsky

Mon Dec 03 10:30 AM -- 10:40 AM (PST) @
in Poster Session »

Variational methods are frequently used to approximate or bound the partition or likelihood function of a Markov random field. Methods based on mean field theory are guaranteed to provide lower bounds, whereas certain types of convex relaxations provide upper bounds. In general, loopy belief propagation (BP) provides (often accurate) approximations, but not bounds. We prove that for a class of attractive binary models, the value specified by any fixed point of loopy BP always provides a lower bound on the true likelihood. Empirically, this bound is much better than the naive mean field bound, and requires no further work than running BP. We establish these lower bounds using a loop series expansion due to Chertkov and Chernyak, which we show can be derived as a consequence of the tree reparameterization characterization of BP fixed points.

[ PDF] 

Author Information

Erik Sudderth (University of California, Irvine)
Martin J Wainwright (UC Berkeley)
Alan S Willsky (Massachusetts Institute of Technology)

More from the Same Authors