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.