Inference Techniques in Graphical Models

Exact Inference

Loopy Belief Propagation


Yedidia, Freeman and Weiss have several excellent papers on the relationship between loopy belief propagation and the Bethe free energy and extending belief propagation to use Kichuchi free energy approximations instead. Only some are included below.

"Understanding Belief Propagation and is Generalizations", Yedidia, Freeman, Weiss, IJCAI 2001.

"Constructing Free Energy Approximations and Generalized Belief Propagation Algorithms"

"Generalized Belief Propagation", Yedidia, Freeman, Weiss, NIPS December 2000, Vol 13 689-695.

Belief Propagation On Partially Ordered Sets, Mceliece and Yildirim.

"Stable fixed points of loopy belief propagation are minima of the Bethe free energy", Heskes, NIPS '02 pre-proc.

"Fractional Belief Propagation", Wiegerinck, Heskes, NIPS '02 pre-proc.

"Approximate Inference in Boltzmann Machines", Welling, Teh.


"Loopy Belief Propagation for Approximate Inference: An Empirical Study", Murphy, Weiss, Jordan. UAI '99.

"Approximate Inference in Boltzmann Machines", also has empirical results.

"Original papers"

Everybody cites the papers by Bethe and Kichuchi. They are available online. I didn't find them very useful for machine learning. If you're going to read one, I found it easiest to relate to the Kichuchi paper. Both have very detailed derivations of the partition function or free energy of some lattice-based systems.

"Statistical Theory of Superlattices", Bethe, Proceeding of the Royal Society of London. Series A, Volume 150, Issue 871 1935 552-575.

"A Theory of Cooperative Phenomena", Kikuchi, Physical Review, 1951 Vol 81, Number 6. 988-1003

Expectation Propagation

See Thomas Minka's page.

Also see slides from Erik Sudderth, MIT.:EP slides and EP summary.