package examples

  1. Public
  2. All

Type Members

  1. class Graphs extends AnyRef


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 xi. Each binary variable xi corresponds to one vertex, and it may take values -1 or +1. The probability distribution P(X) (over all xi) is parameterized by vertex factors ai and edge factors bij:

    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 xi, i.e., P(xi) 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