Junction Tree Algorithm

From GM-RKB
(Redirected from Junction tree algorithm)
Jump to navigation Jump to search

A Junction Tree Algorithm is a Machine Learning Algorithm that is an Inference Algorithm that extracts marginal distributions from a graph.



References

2018

2017

Algorithm 3 The sum-product algorithm
Input: an undirected, tree-structured graphical model [math]\displaystyle{ \mathcal{X} }[/math] with cliques [math]\displaystyle{ \mathcal{C} }[/math] [math]\displaystyle{ \{ }[/math]the cliques are simply edges in this case[math]\displaystyle{ \} }[/math]

1: define [math]\displaystyle{ m_{A\to B}\left(\mathcal{x}_{A\cap B}\right) }[/math] to be the “message” from an edge [math]\displaystyle{ A }[/math] to an adjacent edge [math]\displaystyle{ B }[/math] {for example if [math]\displaystyle{ A=(a,b) }[/math] and [math]\displaystyle{ B=(b,c) }[/math] then we have [math]\displaystyle{ m_{(a,b) \to (b,c)}(\mathcal{x}_b) }[/math]}

2: while there exist adjacent edges [math]\displaystyle{ A,B \in \mathcal{C} }[/math] for which [math]\displaystyle{ m_{A\to B} }[/math] has not been computed do

3: find some [math]\displaystyle{ A\in \mathcal{C} }[/math] such that [math]\displaystyle{ m_{C \to B} }[/math] has been computed for every neighbor [math]\displaystyle{ C \in \Gamma(A) }[/math] except [math]\displaystyle{ B\; \{\Gamma(A) }[/math] returns the edges neighboring [math]\displaystyle{ A }[/math]; initially the condition is satisfied by all leaf-edges[math]\displaystyle{ \} }[/math]

4: [math]\displaystyle{ m_{A\to B}\left(\mathcal{x}_{A \cap B}\right):=\sum_{\mathcal{x}_{A / B}}\{\Psi_A(\mathcal{x}_A)\prod_{C\in A \Gamma (A) / B}m_{C \to A} \left(\mathcal{x}_{A\cap B} \right)\} }[/math]

5: end while

6: for [math]\displaystyle{ A \in \mathcal{C}' }[/math] do [math]\displaystyle{ }[/math]

7: [math]\displaystyle{ marginal_A(\mathcal{x_A}):=\Psi_A(\mathcal{x}_A)\prod_{C\in \Gamma(A)}m_{C \to A} \left(\mathcal{x}_{A\cap C}\right) }[/math]

8: end for

2015