Part of Advances in Neural Information Processing Systems 17 (NIPS 2004)
Alexander Ihler, John Fisher, Alan Willsky
Belief propagation (BP) is an increasingly popular method of perform- ing approximate inference on arbitrary graphical models. At times, even further approximations are required, whether from quantization or other simplified message representations or from stochastic approxima- tion methods. Introducing such errors into the BP message computations has the potential to adversely affect the solution obtained. We analyze this effect with respect to a particular measure of message error, and show bounds on the accumulation of errors in the system. This leads both to convergence conditions and error bounds in traditional and approximate BP message passing.