Understanding and improving belief propagation

Abstract

The research reported in this thesis focuses on approximation techniques for inference in graphical models. Approximate inference can be dTefined as the task of calculating approximations for certain probabilities in large, complexprobabilistic models, such as Bayesian networks, Markov random fields or Ising spin systems (which are all special cases of graphical models). We have focussed on graphical models with variables that have a finite number of possible values. Calculating these probabilities is simple in principle, but computationally hard in practice, because it requires a summation over an exponential number of terms. However, the practical relevance is enormous: application areas include genetic linkage analysis, medical diagnosis, expert systems, error correcting codes, speech recognition, computer vision and many more. Because the probabilities that one is interested in cannot always be calculated exactly (given a limited amount of computation time), one often uses approximate methods, which use less computation time but only give an approximation of the quantities of interest. In this thesis, we have tried to better understand and improve upon Belief Propagation (BP), a popular approximate inference method that performs surprisingly well on many problems. It is also known as 'Loopy Belief Propagation', the 'Sum-Product Algorithm' and the 'Bethe-Peierls approximation'. BP yields exact results if the underlying graphical model has no loops. In general, the BP results are approximate but can be surprisingly accurate. However, if variables become highly dependent, the error made by BP can become significant. In some cases, BP does not even converge anymore. Our results have contributed to a better understanding of these issues. In addition, we introduced a method that improves the accuracy of BP by taking into account the influence of loops in the graphical model. Finally, we proposed a method to calculate exact bounds on marginal probabilities, which was inspired by BP