21. December 2016 - 13:48 — Elmar Messner
# Result of the Month

Belief propagation is an iterative method to perform approximate inference on arbitrary graphical models. Whether it converges and if the solution is a unique fixed point depends on both, the structure and the parametrization of the model. To understand this dependence it is interesting to find all fixed points.

We formulate a set of polynomial equations, the solutions of which correspond to BP fixed points. Experiments on binary Ising models show how our method is capable of obtaining all fixed points.

Contact: Christian Knoll

The figure on the upper-left-hand-side shows the number of iterations until belief propagation converged -- for red it did not converge at all. The upper-right-hand-figure shows the number of fixed points (yellow: unique fixed point, red: three fixed points). Phase transitions separate the parameter space into three distinct regions. In the lower figure the number of real solutions is depicted: at the onset of phase transitions a sudden increase in the number of real solutions can be seen.

For more information, see our recent NIPS (workshop) paper.

1. January 2017 - 31. January 2017