Junction tree algorithm

From Wikipedia, the free encyclopedia
Jump to: navigation, search

The junction tree algorithm (also known as 'Clique Tree') is a method used in machine learning to extract marginalization in general graphs. In essence, it entails performing belief propagation on a modified graph called a junction tree. The basic premise is to eliminate cycles by clustering them into single nodes.

Junction tree algorithm[edit]

Hugin algorithm[edit]

  • If the graph is directed then moralize it to make it undirected
  • Introduce the evidence
  • Triangulate the graph to make it chordal
  • Construct a junction tree from the triangulated graph (we will call the vertices of the junction tree "supernodes")
  • Propagate the probabilities along the junction tree (via belief propagation)

Note that this last step is inefficient for graphs of large treewidth. Computing the messages to pass between supernodes involves doing exact marginalization over the variables in both supernodes. Performing this algorithm for a graph with treewidth k will thus have at least one computation which takes time exponential in k.

Shafer-Shenoy algorithm[edit]