This week I read two papers: Parallel Splash Belief Propagation by J. Gonzalez et al. and Understanding Belief Propagation and its Generalizations by J. S. Yedidia et al. The second was written eight years before the first one and I found that it is a very good introduction to the topic and a very well written paper (I appreciate a lot when a paper is easy to read).

Before starting with Belief Propagation, we need to understand the concept of inference and review graphical models (Bayesian Networks, Pairwise Markov Random Fields, Factor Graphs, etc.). I would recommend taking a look at Chapter 8 of Christopher M. Bishop’s book “Pattern Recognition and Machine Learning” (which can be downloaded for free from his website).

Back to the first paper, I highlight two basic concepts:

- The Belief Propagation (BP) algorithm is
**a way to approximately solve inference problems** -whose goal is to calculate probability distributions- based on statistical models represented using graphs. Many scientific domains have separately addressed different real-world problems that can be solved using inference algorithms such as BP.
- Parallelisation is a programming technique consisting in
**performing more than one operation at the same time** using the hardware resources available. As in everyday life, if independent tasks (operations) are divided among different people (processing units), the overall work is finished much quicker. Problems arise when tasks are not completely independent; some process may need to wait for another to finish or two operations may try modify the same object (data in memory) simultaneously. To deal with this, lots of scheduling algorithms exist.

As many other computationally heavy tasks, **Belief Propagation can use parallelisation**. This is useful to improve the overall performance of a machine learning system that uses an inference procedure. **Parallel Splash Belief Propagation** is an algorithm for approximate inference using high performance shared (multi-core) and distributed (cluster) memory systems. The proposed algorithm generalises the forward-backward scheduling to arbitrary cyclic graphical models and outperforms other techniques (in terms in running time before convergence and in total number of message computations).

Continue reading “PARALLEL (DISTRIBUTED) SPLASH BELIEF PROPAGATION” →