Junction tree algorithm

Junction tree algorithm

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.

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)

hafer-Shenoy algorithm

References

* cite journal
last = Lauritzen
first = Steffen L.
coauthors = Spiegelhalter, David J.
title = Local Computations with Probabilities on Graphical Structures and their Application to Expert Systems
journal = Journal of the Royal Statistical Society, Series B
volume = 50
pages = 157–224
publisher = Blackwell Publishing
date = 1988
* cite journal
last = Dawid
first = A. P.
title = Applications of a general propagation algorithm for probabilistic expert systems
journal = Statistics and Computing
volume = 2
issue = 1
pages = 25–26
publisher = Springer
date = 1992
url = http://www.springerlink.com/content/k36v48vx6467303h/
doi = 10.1007/BF01890546
* cite journal
last = Huang
first = Cecil
coauthors = Darwiche, Adnan
title = Inference in Belief Networks: A Procedural Guide
journal = International Journal of Approximate Reasoning
volume = 15
issue = 3
pages = 225–263
publisher = Elsevier
date = 1996
url = http://citeseer.ist.psu.edu/huang94inference.html
doi = 10.1016/S0888-613X(96)00069-2
* citation
last = Paskin
first = Mark A.
contribution = A Short Course on Graphical Models : 3. The Junction Tree Algorithms
contribution-url = http://ai.stanford.edu/~paskin/gm-short-course/lec3.pdf


Wikimedia Foundation. 2010.

Игры ⚽ Поможем написать реферат

Look at other dictionaries:

  • Tree decomposition — A graph with eight vertices, and a tree decomposition of it onto a tree with six nodes. Each graph edge connects two vertices that are listed together at some tree node, and each graph vertex is listed at the nodes of a contiguous subtree of the… …   Wikipedia

  • Chow-Liu tree — A first order dependency tree representing the product on the left. A Chow Liu tree is an efficient method for constructing a second order product approximation of a joint distribution, first described in a paper by Chow Liu (1968). The goals of… …   Wikipedia

  • Maze solving algorithm — There are a number of different maze solving algorithms, that is, automated methods for the solving of mazes. A few important maze solving algorithms are explained below. The random mouse, wall follower, Pledge, and Trémaux algorithms are… …   Wikipedia

  • Maze generation algorithm — Maze generation algorithms are automated methods for the creation of mazes. This maze generated by modified version of Prim s algorithm, below. Contents 1 Graph theory based methods …   Wikipedia

  • Chordal graph — A cycle (black) with two chords (green). As for this part, the graph is chordal. However, removing one green edge would result in a non chordal graph. Indeed, the other green edge with three black edges would form a cycle of length four with no… …   Wikipedia

  • Belief propagation — is a message passing algorithm for performing inference on graphical models, such as Bayesian networks and Markov random fields. It calculates the marginal distribution for each unobserved node, conditional on any observed nodes. Belief… …   Wikipedia

  • List of mathematics articles (J) — NOTOC J J homomorphism J integral J invariant J. H. Wilkinson Prize for Numerical Software Jaccard index Jack function Jacket matrix Jackson integral Jackson network Jackson s dimensional theorem Jackson s inequality Jackson s theorem Jackson s… …   Wikipedia

  • Moral graph — A moral graph is a concept in graph theory, used to find the equivalent undirected form of a directed acyclic graph. It is a key step of the junction tree algorithm, used in belief propagation on graphical models. The moralized counterpart of a… …   Wikipedia

  • Message-passing method — Message passing methods are a set of algorithms in statistics/machine learning for doing inference through local computation. Belief propagation on Bayesian networks is a good example of a message passing method. Variational message passing… …   Wikipedia

  • List of graph theory topics — This is a list of graph theory topics, by Wikipedia page. See glossary of graph theory for basic terminology Contents 1 Examples and types of graphs 2 Graph coloring 3 Paths and cycles 4 …   Wikipedia

Share the article and excerpts

Direct link
… Do a right-click on the link above
and select “Copy Link”