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. For this purpose, we take a different perspective on belief propagation and realize that the fixed points define a set of polynomial equations – albeit a large one. Solving polynomial equations of this size is problematic; nonetheless, we present the numerical polynomial homotopy continuation method that is capable of solving the fixed point equations, the solutions of which are the fixed points of belief propagation.

The solutions to the fixed point equations give us knowledge of the whole solution space and serve as a stepping stone for analyzing belief propagation’s properties. In particular, we observe a large variety of marginal accuracy across all fixed points. This, to some degree, explains the large discrepancy in the performance of belief propagation. Another important aspect of belief propagation’s fixed points is their stability, that is if belief propagation can – at least in principle – converge to a given fixed point. Existing stability analyses were limited to models without local potentials for the lack of knowing the solution space. The capability to solve the fixed point equations thus allows us to extend the stability analysis to a wide range of models. In doing so, we obtain novel insights into how the model parameters and the model size affect the stability. In particular, we find that strong pairwise potentials degrade the performance, whereas strong local potentials enhance the performance.

Moreover, our theoretical findings inspire a simple, yet powerful, modification of belief propagation. We present self-guided belief propagation that starts from a simple model (for which belief propagation obtains the exact solutions) and iteratively adapts it to the desired model. As the model is modified, self-guided belief propagation keeps track of the solution; this way, it improves upon standard belief propagation and it obtains the best possible solution for attractive models with unidirectional local potentials. For more general models, we empirically show that self-guided belief propagation maintains its favorable properties, converges more often, and is superior in terms of marginal accuracy.

Finally, we question whether the global minimum of the Bethe free energy provides the most accurate marginals. This is a common conjecture that inspired a range of methods that aim to minimize the Bethe free energy. In the past, the studied models were either too simplistic or too complex as to the true nature of this relationship. Therefore, we must first introduce a novel class of models – termed patch potential models – which are simple enough so that we can compute all fixed points. Yet, patch potential models are complex enough to possess a rich and non-trivial solution space. A study of this solution space proves this conjecture wrong and, additionally, explains the nature of the difference between accurate marginals and good approximations of the free energy.

The full text of the thesis can be downloaded here.