# Belief propagation with loops

Bethe approximation, Kikuchi approximations, loop calculus

September 18, 2020 — October 24, 2023

algebra

graphical models

how do science

machine learning

networks

neural nets

probability

statistics

Local versus global information flows in inference.

## 1 Bethe approximation

## 2 Regional approximations

## 3 Loop calculus

## 4 References

Blei, Kucukelbir, and McAuliffe. 2017. “Variational Inference: A Review for Statisticians.”

*Journal of the American Statistical Association*.
Chertkov, and Chernyak. 2006a. “Loop Series for Discrete Statistical Models on Graphs.”

*Journal of Statistical Mechanics: Theory and Experiment*.
———. 2006b. “Loop Calculus in Statistical Physics and Information Science.”

*Physical Review E*.
Dauwels. 2007. “On Variational Message Passing on Factor Graphs.” In

*2007 IEEE International Symposium on Information Theory*.
Gómez, Mooij, and Kappen. 2007. “Truncating the Loop Series Expansion for Belief Propagation.”

*The Journal of Machine Learning Research*.
Kirkley, Cantwell, and Newman. 2021. “Belief Propagation for Networks with Loops.”

*Science Advances*.
Kroc, and Chertkov. 2008. “Loop Calculus for Satisfiability.” In

*Proceedings of the 23rd National Conference on Artificial Intelligence - Volume 3*. AAAI’08.
Noorshams, and Wainwright. 2013. “Belief Propagation for Continuous State Spaces: Stochastic Message-Passing with Quantitative Guarantees.”

*The Journal of Machine Learning Research*.
Wainwright, Martin, and Jordan. 2005. “A Variational Principle for Graphical Models.” In

*New Directions in Statistical Signal Processing*.
Wainwright, Martin J., and Jordan. 2008.

*Graphical Models, Exponential Families, and Variational Inference*. Foundations and Trends® in Machine Learning.
Watanabe, and Chertkov. 2010. “Belief Propagation and Loop Calculus for the Permanent of a Non-Negative Matrix.”

*Journal of Physics A: Mathematical and Theoretical*.
Wiegerinck, and Heskes. 2002. “Fractional Belief Propagation.” In

*Advances in Neural Information Processing Systems*.
Winn, John M. 2004. “Variational Message Passing and Its Applications.”

Winn, John M., and Bishop. 2005. “Variational Message Passing.” In

*Journal of Machine Learning Research*.
Yedidia, Jonathan S., Freeman, and Weiss. 2000. “Generalized Belief Propagation.” In

*Proceedings of the 13th International Conference on Neural Information Processing Systems*. NIPS’00.
Yedidia, J.S., Freeman, and Weiss. 2003. “Understanding Belief Propagation and Its Generalizations.” In

*Exploring Artificial Intelligence in the New Millennium*.
———. 2005. “Constructing Free-Energy Approximations and Generalized Belief Propagation Algorithms.”

*IEEE Transactions on Information Theory*.