Understanding the ratio of the partition sum to its Bethe approximation via double covers
Preprint
Abstract
For various classes of graphical models it has been observed that the ratio of the partition sum to its Bethe approximation is often close to being the square of the ratio of the partition sum to its degree-2 Bethe approximation. This is of relevance because the latter ratio can often better be analyzed and/or quantified than the former ratio. In this paper, we give some justifications for the observed relationship between these two ratios and then analyze these ratios for two classes of log-supermodular graphical models.Keywords
All Related Versions
This publication has 8 references indexed in Scilit:
- Markov Random Fields, Homomorphism Counting, and Sidorenko’s ConjectureIEEE Transactions on Information Theory, 2022
- Belief Propagation, Bethe Approximation and PolynomialsIEEE Transactions on Information Theory, 2019
- Counting in Graph Covers: A Combinatorial Characterization of the Bethe Entropy FunctionIEEE Transactions on Information Theory, 2013
- Modern Coding Theory2008
- Loop series for discrete statistical models on graphsJournal of Statistical Mechanics: Theory and Experiment, 2006
- Constructing Free-Energy Approximations and Generalized Belief Propagation AlgorithmsIEEE Transactions on Information Theory, 2005
- Codes on graphs: normal realizationsIEEE Transactions on Information Theory, 2001
- Factor graphs and the sum-product algorithmIEEE Transactions on Information Theory, 2001