Value Members

1.  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.
2.  object Graphs extends Graphs

   Example GraphFrames for testing the API