Object

org.graphframes.examples

BeliefPropagation

Related Doc: package examples

Permalink

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 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:

Linear Supertypes
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

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

    Permalink

Value Members

  1. final def !=(arg0: Any): Boolean

    Permalink
    Definition Classes
    AnyRef → Any
  2. final def ##(): Int

    Permalink
    Definition Classes
    AnyRef → Any
  3. final def ==(arg0: Any): Boolean

    Permalink
    Definition Classes
    AnyRef → Any
  4. final def asInstanceOf[T0]: T0

    Permalink
    Definition Classes
    Any
  5. def clone(): AnyRef

    Permalink
    Attributes
    protected[java.lang]
    Definition Classes
    AnyRef
    Annotations
    @throws( ... )
  6. final def eq(arg0: AnyRef): Boolean

    Permalink
    Definition Classes
    AnyRef
  7. def equals(arg0: Any): Boolean

    Permalink
    Definition Classes
    AnyRef → Any
  8. def finalize(): Unit

    Permalink
    Attributes
    protected[java.lang]
    Definition Classes
    AnyRef
    Annotations
    @throws( classOf[java.lang.Throwable] )
  9. final def getClass(): Class[_]

    Permalink
    Definition Classes
    AnyRef → Any
  10. def hashCode(): Int

    Permalink
    Definition Classes
    AnyRef → Any
  11. final def isInstanceOf[T0]: Boolean

    Permalink
    Definition Classes
    Any
  12. def main(args: Array[String]): Unit

    Permalink
  13. final def ne(arg0: AnyRef): Boolean

    Permalink
    Definition Classes
    AnyRef
  14. final def notify(): Unit

    Permalink
    Definition Classes
    AnyRef
  15. final def notifyAll(): Unit

    Permalink
    Definition Classes
    AnyRef
  16. def runBPwithGraphFrames(g: GraphFrame, numIter: Int): GraphFrame

    Permalink

    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

    Permalink

    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

    Permalink
    Definition Classes
    AnyRef
  19. def toString(): String

    Permalink
    Definition Classes
    AnyRef → Any
  20. final def wait(): Unit

    Permalink
    Definition Classes
    AnyRef
    Annotations
    @throws( ... )
  21. final def wait(arg0: Long, arg1: Int): Unit

    Permalink
    Definition Classes
    AnyRef
    Annotations
    @throws( ... )
  22. final def wait(arg0: Long): Unit

    Permalink
    Definition Classes
    AnyRef
    Annotations
    @throws( ... )

Inherited from AnyRef

Inherited from Any

Ungrouped