Packages

o

org.graphframes.examples

BeliefPropagation

object BeliefPropagation

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.
Linear Supertypes
AnyRef, Any
Ordering
  1. Alphabetic
  2. By Inheritance
Inherited
  1. BeliefPropagation
  2. AnyRef
  3. Any
  1. Hide All
  2. Show All
Visibility
  1. Public
  2. All

Type Members

  1. case class EdgeAttr(b: Double) extends Product with Serializable
  2. case class VertexAttr(a: Double, belief: Double, color: Int) extends Product with Serializable

Value Members

  1. final def !=(arg0: Any): Boolean
    Definition Classes
    AnyRef → Any
  2. final def ##(): Int
    Definition Classes
    AnyRef → Any
  3. final def ==(arg0: Any): Boolean
    Definition Classes
    AnyRef → Any
  4. final def asInstanceOf[T0]: T0
    Definition Classes
    Any
  5. def clone(): AnyRef
    Attributes
    protected[lang]
    Definition Classes
    AnyRef
    Annotations
    @throws( ... ) @native()
  6. final def eq(arg0: AnyRef): Boolean
    Definition Classes
    AnyRef
  7. def equals(arg0: Any): Boolean
    Definition Classes
    AnyRef → Any
  8. def finalize(): Unit
    Attributes
    protected[lang]
    Definition Classes
    AnyRef
    Annotations
    @throws( classOf[java.lang.Throwable] )
  9. final def getClass(): Class[_]
    Definition Classes
    AnyRef → Any
    Annotations
    @native()
  10. def hashCode(): Int
    Definition Classes
    AnyRef → Any
    Annotations
    @native()
  11. final def isInstanceOf[T0]: Boolean
    Definition Classes
    Any
  12. def main(args: Array[String]): Unit
  13. final def ne(arg0: AnyRef): Boolean
    Definition Classes
    AnyRef
  14. final def notify(): Unit
    Definition Classes
    AnyRef
    Annotations
    @native()
  15. final def notifyAll(): Unit
    Definition Classes
    AnyRef
    Annotations
    @native()
  16. def runBPwithGraphFrames(g: GraphFrame, numIter: Int): GraphFrame

    Run Belief Propagation.

    Run Belief Propagation.

    This implementation of BP shows how to use GraphFrame's aggregateMessages method.

    • Color GraphFrame vertices for BP scheduling.
    • Run BP using GraphFrame's aggregateMessages API.
    • Augment the original GraphFrame with the BP results (vertex beliefs).
    g

    Graphical model created by org.graphframes.examples.Graphs.gridIsingModel()

    numIter

    Number of iterations of BP to run. One iteration includes updating each vertex's belief once.

    returns

    Same graphical model, but with GraphFrame.vertices augmented with a new column "belief" containing P(xi = +1), the marginal probability of vertex i taking value +1 instead of -1.

  17. def runBPwithGraphX(g: GraphFrame, numIter: Int): GraphFrame

    Run Belief Propagation.

    Run Belief Propagation.

    This implementation of BP shows how to use GraphX's aggregateMessages method. It is simple to convert to and from GraphX format. This method does the following:

    • Color GraphFrame vertices for BP scheduling.
    • Convert GraphFrame to GraphX format.
    • Run BP using GraphX's aggregateMessages API.
    • Augment the original GraphFrame with the BP results (vertex beliefs).
    g

    Graphical model created by org.graphframes.examples.Graphs.gridIsingModel()

    numIter

    Number of iterations of BP to run. One iteration includes updating each vertex's belief once.

    returns

    Same graphical model, but with GraphFrame.vertices augmented with a new column "belief" containing P(xi = +1), the marginal probability of vertex i taking value +1 instead of -1.

  18. final def synchronized[T0](arg0: ⇒ T0): T0
    Definition Classes
    AnyRef
  19. def toString(): String
    Definition Classes
    AnyRef → Any
  20. final def wait(): Unit
    Definition Classes
    AnyRef
    Annotations
    @throws( ... )
  21. final def wait(arg0: Long, arg1: Int): Unit
    Definition Classes
    AnyRef
    Annotations
    @throws( ... )
  22. final def wait(arg0: Long): Unit
    Definition Classes
    AnyRef
    Annotations
    @throws( ... ) @native()

Inherited from AnyRef

Inherited from Any

Ungrouped