The War on Loops

Add to your list(s) 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.

This talk is included in these lists:

• All Talks (aka the CURE list)
• Cambridge Centre for Data-Driven Discovery (C2D3)
• Cambridge Forum of Science and Humanities
• Cambridge Language Sciences
• Cambridge University Engineering Department Talks
• Cambridge talks
• Centre for Smart Infrastructure & Construction
• Chris Davis' list
• Computational Continuum Mechanics Group Seminars
• Engineering Department, CBL Room 438
• Featured lists
• Guy Emerson's list
• Hanchen DaDaDash
• Inference Group Journal Clubs
• Inference Group Summary
• Information Engineering Division seminar list
• Interested Talks
• ML
• Machine Learning Reading Group
• Machine Learning Reading Group @ CUED
• Machine Learning Summary
• Quantum Matter Journal Club
• Required lists for MLG
• School of Technology
• Simon Baker's List
• TQS Journal Clubs
• Trust & Technology Initiative - interesting events
• bld31
• custom
• ndk22's list
• ob366-ai4er
• rp587
• yk373's list

Note that ex-directory lists are not shown.