Junction tree algorithm

In machine learning, one method of exact marginalization in general graphs is called the junction tree algorithm, which is simply belief propagation on a modified graph guaranteed to be a tree. The basic premise is to eliminate cycles by clustering them into single nodes.

Junction Trees

A clique tree has the junction tree property if for all cliques A and B, for all cliques C on the unique path between A and B, we have $C\supseteq (A\cap B)$

Junction Tree Algorithm

Hugin algorithm

• Moralize the graph
• Introduce the evidence
• Triangulate the graph
• Construct a junction tree from this (form a maximal spanning tree)
• Propagate the probabilities (via belief propagation)

References

• ( PDF ) A Short Course on Graphical Models: 3. The Junction Tree Algorithms
• Michael I. Jordan, "An Introduction to Probabilistic Graphical Models" (draft copy)