Understanding the Behavior of Belief Propagation
It addresses the lack of performance and convergence guarantees for belief propagation in loopy graphical models, which is a foundational issue in approximate inference for machine learning.
This thesis investigates how model parameters influence the performance of belief propagation in probabilistic graphical models, focusing on fixed points, convergence, and approximation quality, but does not report specific numerical results.
Probabilistic graphical models are a powerful concept for modeling high-dimensional distributions. Besides modeling distributions, probabilistic graphical models also provide an elegant framework for performing statistical inference; because of the high-dimensional nature, however, one must often use approximate methods for this purpose. Belief propagation performs approximate inference, is efficient, and looks back on a long success-story. Yet, in most cases, belief propagation lacks any performance and convergence guarantees. Many realistic problems are presented by graphical models with loops, however, in which case belief propagation is neither guaranteed to provide accurate estimates nor that it converges at all. This thesis investigates how the model parameters influence the performance of belief propagation. We are particularly interested in their influence on (i) the number of fixed points, (ii) the convergence properties, and (iii) the approximation quality.