The Bethe Partition Function of Log-supermodular Graphical Models
From MaRDI portal
Publication:6231292
arXiv1202.6035MaRDI QIDQ6231292FDOQ6231292
Authors: Nicholas Ruozzi 
Publication date: 27 February 2012
Abstract: Sudderth, Wainwright, and Willsky have conjectured that the Bethe approximation corresponding to any fixed point of the belief propagation algorithm over an attractive, pairwise binary graphical model provides a lower bound on the true partition function. In this work, we resolve this conjecture in the affirmative by demonstrating that, for any graphical model with binary variables whose potential functions (not necessarily pairwise) are all log-supermodular, the Bethe partition function always lower bounds the true partition function. The proof of this result follows from a new variant of the "four functions" theorem that may be of independent interest.
This page was built for publication: The Bethe Partition Function of Log-supermodular Graphical Models
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6231292)
