University of Cambridge > Talks.cam > Machine Learning Reading Group @ CUED > The War on Loops

Log in

University Account

External (via Google)

Information on

Subscribing to talks details

Finding a talk details

Adding a talk details

Disseminating talks details

Help and Documentation details

The War on Loops

Download to your calendar using vCal

Frederik Eaton (CUED)
Thursday 11 September 2008, 14:00-15:30
Engineering Department, CBL Room 438.

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.