# The War on Loops

Add to your list(s)
Download to your calendar using vCal

If you have a question about this talk, please contact Shakir Mohamed.

It is well known that belief propagation is exact on trees, i.e. graphs without loops, although it often gives accurate results even on graphs with loops. In this week’s RCC I will discuss two approaches to improving the accuracy of BP on loopy graphs. The relevant papers are:

JM Mooij, B Wemmenhove, HJ Kappen, T Rizzo, Loop Corrected Belief Propagation

M Chertkov, VY Chernyak, Loop Calculus in Statistical Physics and Information Science

The first paper describes an algorithm for propagating cavity distributions which is exact in graphs with 1 loop. The second paper is a purely theoretical contribution which gives an expression for the partition function of a factor graph with binary nodes in terms of a finite sum over “generalised loops” in a graphical representation called the “vertex model” (but doesn’t describe an algorithm).

For further reading, both papers have extended versions:

J Mooij, B Kappen, Loop corrections for approximate inference

M Chertkov, VY Chernyak, Loop series for discrete statistical models on graphs

This talk is part of the Machine Learning Reading Group @ CUED series.

## This talk is included in these lists:

Note that ex-directory lists are not shown.