Junction tree algorithm
From Wikipedia, the free encyclopedia
The junction tree algorithm is a method used in machine learning for exact 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.
Contents |
[edit] Junction tree algorithm
[edit] 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)
[edit] Shafer-Shenoy algorithm
[edit] References
- Lauritzen, Steffen L.; Spiegelhalter, David J. (1988). "Local Computations with Probabilities on Graphical Structures and their Application to Expert Systems". Journal of the Royal Statistical Society, Series B 50: 157–224. Blackwell Publishing.
- Dawid, A. P. (1992). "Applications of a general propagation algorithm for probabilistic expert systems". Statistics and Computing 2 (1): 25–26. Springer. doi: .
- Huang, Cecil; Darwiche, Adnan (1996). "Inference in Belief Networks: A Procedural Guide". International Journal of Approximate Reasoning 15 (3): 225–263. Elsevier. doi: .
- Paskin, Mark A., “A Short Course on Graphical Models : 3. The Junction Tree Algorithms”