Interactive demo · Probabilistic Machine Learning: Advanced Topics · Chapter 9

Loopy belief propagation on an Ising grid

Each square is a binary spin with a random field and random couplings (strength set by the slider). The left grid shows the beliefs that loopy BP has reached, the right grid the exact marginals (computed by a column transfer matrix, or by two-pass BP on the spanning tree). Strong couplings make undamped synchronous updates oscillate; damping and asynchronous updates help; on a tree BP is exact after as many sweeps as the diameter. Click a square to follow it in the plot.

Grid

Message updates

Try these

Damping lambda mixes the new message with the old one, (9.77); lambda = 1 is plain BP. A sweep updates every directed message once: all at the same time (synchronous, as in (9.78)) or one after another with the newest values (asynchronous, as in (9.79)). A message counts as converged when it moved by less than 0.001. The 11 × 11 grid with coupling 1.7 is the setting of Figure 9.13.

In the lecture notes