imported>Citation bot: Add: isbn, pages. | Use this bot. Report bugs. | Suggested by Dominic3203 | Category:Graph algorithms | #UCB_Category 17/132

2024-10-25T14:22:38Z

Add: isbn, pages. | Use this bot. Report bugs. | Suggested by Dominic3203 | Category:Graph algorithms | #UCB_Category 17/132

New page

[[File:Junction-tree-example.gif|300px|thumb|Example of a junction tree]]
The '''junction tree algorithm''' (also known as 'Clique Tree') is a method used in [[machine learning]] to extract [[marginal distribution|marginalization]] in general [[Graph (discrete mathematics)|graph]]s. In essence, it entails performing [[belief propagation]] on a modified graph called a [[junction tree]]. The graph is called a tree because it branches into different sections of data; [[Vertex (graph theory)|nodes]] of variables are the branches.<ref name=":1">{{Cite web|url=https://ai.stanford.edu/~paskin/gm-short-course/lec3.pdf|title=A Short Course on Graphical Models|last=Paskin|first=Mark|website=Stanford}}</ref> The basic premise is to eliminate [[cycle (graph theory)|cycle]]s by clustering them into single nodes. Multiple extensive classes of queries can be compiled at the same time into larger structures of data.<ref name=":1" /> There are different [[algorithm]]s to meet specific needs and for what needs to be calculated. [[Inference network|Inference algorithms]] gather new developments in the data and calculate it based on the new information provided.<ref>{{Cite web|url=http://www.dfki.de/~neumann/publications/diss/node58.html|title=The Inference Algorithm|website=www.dfki.de|access-date=2018-10-25}}</ref>

==Junction tree algorithm==

===Hugin algorithm===

* If the graph is directed then [[Moral graph|moralize]] it to make it un-directed.
*Introduce the evidence.
*[[Chordal graph|Triangulate]] the graph to make it chordal.
*Construct a [[junction tree]] from the triangulated graph (we will call the vertices of the junction tree "[[Supernode (circuit)|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. It is a [[belief propagation|message passing]] algorithm.<ref name=":2">{{Cite web|url=http://www.gatsby.ucl.ac.uk/teaching/courses/ml1-2007/lect5-handout.pdf|title=Recap on Graphical Models}}</ref> The Hugin algorithm takes fewer [[computation]]s to find a solution compared to Shafer-Shenoy.

===Shafer-Shenoy algorithm===

* Computed recursively<ref name=":2" />
* Multiple recursions of the Shafer-Shenoy algorithm results in Hugin algorithm<ref name=":3">{{Cite web|url=https://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-438-algorithms-for-inference-fall-2014/lecture-notes/MIT6_438F14_Lec14.pdf|title=Algorithms|date=2014|website=Massachusetts Institute of Technology}}</ref>
* Found by the [[Message passing in computer clusters|message passing]] equation<ref name=":3" />
*[[Vertex separator|Separator]] potentials are not stored<ref>{{Cite web|url=https://cs.nyu.edu/~roweis/csc412-2004/notes/lec20x.pdf|title=Hugin Inference Algorithm|last=Roweis|first=Sam|date=2004|website=NYU}}</ref>

The Shafer-Shenoy [[algorithm]] is the [[Sum-product algorithm|sum product]] of a junction tree.<ref>{{Cite web|url=https://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-438-algorithms-for-inference-fall-2014/recitations/MIT6_438F14_rec8.pdf|title=Algorithms for Inference|date=2014|website=Massachusetts Institute of Technology}}</ref> It is used because it runs programs and queries more efficiently than the Hugin algorithm. The algorithm makes calculations for conditionals for [[belief functions]] possible.<ref name=":02">{{cite arXiv|last=Kłopotek|first=Mieczysław A.|date=2018-06-06|title=Dempsterian-Shaferian Belief Network From Data|eprint=1806.02373|class=cs.AI}}</ref> [[Joint distributions]] are needed to make local computations happen.<ref name=":02" />

===Underlying theory===
[[File:Hmm temporal bayesian net.svg|thumb|Example of a Dynamic Bayesian network]]
The first step concerns only [[Bayesian networks]], and is a procedure to turn a directed graph into an [[undirected]] one. We do this because it allows for the universal applicability of the algorithm, regardless of direction.

The second step is setting variables to their observed value. This is usually needed when we want to calculate conditional probabilities, so we fix the value of the [[random variable]]s we condition on. Those variables are also said to be clamped to their particular value.
[[File:Chordal-graph.svg|thumb|Example of a chordal graph]]
The third step is to ensure that graphs are made [[Chordal graph|chordal]] if they aren't already chordal. This is the first essential step of the algorithm. It makes use of the following theorem:<ref name=":0">{{cite web |url=https://people.eecs.berkeley.edu/~wainwrig/Talks/Wainwright_PartI.pdf |title= Graphical models, message-passing algorithms, and variational methods: Part I|last= Wainwright|first=Martin |date= 31 March 2008|website=Berkeley EECS |access-date=16 November 2016}}</ref>

'''Theorem:''' For an [[Graph (discrete mathematics)|undirected]] graph, G, the following properties are equivalent:

* Graph G is triangulated.
* The clique graph of G has a junction tree.
* There is an elimination ordering for G that does not lead to any added edges.

Thus, by [[Triangulation (geometry)|triangulating]] a graph, we make sure that the corresponding junction tree exists. A usual way to do this, is to decide an elimination order for its nodes, and then run the [[Variable elimination]] algorithm. The [[variable elimination]] algorithm states that the algorithm must be run each time there is a different query.<ref name=":1" /> This will result to adding more edges to the initial graph, in such a way that the output will be a [[chordal graph]].
All chordal graphs have a junction tree.<ref name=":3" /> The next step is to construct the [[junction tree]]. To do so, we use the graph from the previous step, and form its corresponding [[clique graph]].<ref>{{cite web |url=http://mathworld.wolfram.com/CliqueGraph.html |title=Clique Graph|access-date=16 November 2016}}</ref> Now the next theorem gives us a way to find a junction tree:<ref name=":0" />

'''Theorem:''' Given a triangulated graph, weight the edges of the clique graph by their cardinality, |A∩B|, of the intersection of the adjacent cliques A and B. Then any maximum-weight spanning tree of the clique graph is a junction tree.

So, to construct a junction tree we just have to extract a maximum weight spanning tree out of the clique graph. This can be efficiently done by, for example, modifying [[Kruskal's algorithm]].
The last step is to apply [[belief propagation]] to the obtained junction tree.<ref>{{cite web |url=https://www.cs.helsinki.fi/u/bmmalone/probabilistic-models-spring-2014/JunctionTreeBarber.pdf |title= Probabilistic Modelling and Reasoning, The Junction Tree Algorithm |last= Barber|first=David |date= 28 January 2014|website= University of Helsinki |access-date=16 November 2016}}</ref>

'''Usage:''' A junction tree graph is used to visualize the probabilities of the problem. The tree can become a binary tree to form the actual building of the tree.<ref>{{cite conference
| last1 = Ramirez | first1 = Julio C.
| last2 = Munoz | first2 = Guillermina
| last3 = Gutierrez | first3 = Ludivina
| contribution = Fault Diagnosis in an Industrial Process Using Bayesian Networks: Application of the Junction Tree Algorithm
| date = September 2009
| doi = 10.1109/cerma.2009.28
| publisher = IEEE
| title = 2009 Electronics, Robotics and Automotive Mechanics Conference (CERMA)| pages = 301–306
| isbn = 978-0-7695-3799-3
}}</ref> A specific use could be found in [[Autoencoder|auto encoders]], which combine the graph and a passing network on a large scale automatically.<ref>{{Cite journal|last=Jin|first=Wengong|date=Feb 2018|title=Junction Tree Variational Autoencoder for Molecular Graph Generation|journal=Cornell University|arxiv=1802.04364|bibcode=2018arXiv180204364J}}</ref>

=== Inference Algorithms ===
[[File:Cutset-4.svg|thumb|Cutset conditioning]]
'''Loopy belief propagation:''' A different method of interpreting complex graphs. The [[loopy belief propagation]] is used when an approximate solution is needed instead of the [[Exact solutions|exact solution]].<ref>{{Cite book|title=CERMA 2009 : proceedings : 2009 Electronics, Robotics and Automotive Mechanics Conference : 22-25 September 2009 : Cuernavaca, Morelos, Mexico|date=2009|publisher=IEEE Computer Society|others=Institute of Electrical and Electronics Engineers.|isbn=9780769537993|location=Los Alamitos, Calif.|oclc=613519385}}</ref> It is an [[approximate inference]].<ref name=":2" />

'''Cutset conditioning:''' Used with smaller sets of variables. [[Cutset]] conditioning allows for simpler graphs that are easier to read but are not [[Exact solutions|exact]].<ref name=":2" />

==References==
{{reflist}}

==Further reading==
* {{cite journal
| last = Lauritzen
| first = Steffen L.
|author2=Spiegelhalter, David J. |author-link2=David Spiegelhalter
| title = Local Computations with Probabilities on Graphical Structures and their Application to Expert Systems
| journal = Journal of the Royal Statistical Society. Series B (Methodological)
| volume = 50 |issue=2
| pages = 157–224
| date = 1988
| mr = 0964177
| jstor = 2345762 | doi = 10.1111/j.2517-6161.1988.tb01721.x
}}
* {{cite journal
| last = Dawid
| first = A. P.
| author-link = Philip Dawid
| title = Applications of a general propagation algorithm for probabilistic expert systems
| journal = Statistics and Computing
| volume = 2
| issue = 1
| pages = 25–26
| date = 1992
| doi = 10.1007/BF01890546| s2cid = 61247712
}}
* {{cite journal
| last = Huang
| first = Cecil
|author2=Darwiche, Adnan
| title = Inference in Belief Networks: A Procedural Guide
| journal = International Journal of Approximate Reasoning
| volume = 15
| issue = 3
| pages = 225–263
| date = 1996
| url = http://citeseer.ist.psu.edu/huang94inference.html
| doi = 10.1016/S0888-613X(96)00069-2| citeseerx = 10.1.1.47.3279
}}
*Lepar, V., Shenoy, P. (1998). "A Comparison of Lauritzen-Spiegelhalter, Hugin, and Shenoy-Shafer Architectures for Computing Marginals of Probability Distributions." https://arxiv.org/ftp/arxiv/papers/1301/1301.7394.pdf

{{DEFAULTSORT:Junction Tree Algorithm}}
[[Category:Bayesian networks]]
[[Category:Graph algorithms]]

Junction tree algorithm - Revision history

imported>Citation bot: Add: isbn, pages. | Use this bot. Report bugs. | Suggested by Dominic3203 | Category:Graph algorithms | #UCB_Category 17/132