Example code for Belief Propagation (BP)

This provides a template for building customized BP algorithms for different types of graphical models.

This example:

• Ising model on a grid
• Parallel Belief Propagation using colored fields

Ising models are probabilistic graphical models over binary variables x_i. Each binary variable x_i corresponds to one vertex, and it may take values -1 or +1. The probability distribution P(X) (over all x_i) is parameterized by vertex factors a_i and edge factors b_ij:

P(X) = (1/Z) * exp[ \sum_i a_i x_i + \sum_{ij} b_{ij} x_i x_j ]

where Z is the normalization constant (partition function). See Wikipedia for more information on Ising models.

Belief Propagation (BP) provides marginal probabilities of the values of the variables x_i, i.e., P(x_i) for each i. This allows a user to understand likely values of variables. See Wikipedia for more information on BP.

We use a batch synchronous BP algorithm, where batches of vertices are updated synchronously. We follow the mean field update algorithm in Slide 13 of the talk slides from: Wainwright. "Graphical models, message-passing algorithms, and convex optimization."

The batches are chosen according to a coloring. For background on graph colorings for inference, see for example: Gonzalez et al. "Parallel Gibbs Sampling: From Colored Fields to Thin Junction Trees." AISTATS, 2011.

The BP algorithm works by:

• Coloring the graph by assigning a color to each vertex such that no neighboring vertices share the same color.
• In each step of BP, update all vertices of a single color. Alternate colors.