Packages

•  package root

  Definition Classes

  root

•  package org

  Definition Classes

  root

•  package graphframes

  Definition Classes

  org

•  package examples

  Definition Classes

  graphframes

•  object BeliefPropagation

  Example code for Belief Propagation (BP)

  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.

  Definition Classes

  examples

• EdgeAttr
• VertexAttr

org.graphframes.examples.BeliefPropagation

EdgeAttr 