Analysis of Message Scheduling for Belief Propagation
The influence of different message update schemes on belief propagation (BP) highlights the need of designing an appropriate message scheduling. Yet, Residual belief propagation (RBP) is the only established method utilizing this observation and consequently increasing the convergence rate. We observed that RBP fails to converge if local oscillations occur and the same messages are repeatedly updated. We propose two novel methods to prevent and correct such oscillations. First we show how noise injection belief propagation (NIBP) detects oscillating messages and adds random noise to improves the convergence rate. The second method, weight decay belief propagation (WDP), applies a damping on the residual to gradually reduce the relevance of these messages and consequently forces convergence. Additionally, in contrast to previous work, we consider the correctness of the obtained marginals and present the remarkable performance increase on a variety of synthetic problems.
The figure shows the rate of convergence on graphs of varying size and difficulty. We compare our WDBP and NIBP to residual (RBP) and asynchronous (AB) belief propagation. Looking at the overall performance we can see that NIBP has the highest convergence rate. Still WDBP outperforms RBP on all graphs, altough the harder the problem the slower the convergence.