Junction Tree Algorithm

Jump to: navigation, search

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




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

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

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

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

4: [math]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]A \in \mathcal{C}'[/math] do [math][/math]

7: [math]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