# Junction Tree Algorithm

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

**AKA:**Clique Tree.**See:**Cycle (Graph Theory), Machine Learning, Marginal Distribution, Graph, Belief Propagation, Junction Tree, Bayesian Network.

## References

### 2018

- (Wikipedia, 2018) ⇒ https://en.wikipedia.org/wiki/Junction_tree_algorithm Retrieved:2018-7-29.
- The
**junction tree algorithm**(also known as 'Clique Tree') is a method used in machine learning to extract 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.

- The

### 2017

- (McAuley, Caetano & Buntine, 2017) ⇒ Julian McAuley, Tibério Caetano, and Wray L. Buntine (2017)."Graphical Models". In: Sammut & Webb. (2017).
- QUOTE:
**Theorem 3***Let G be a triangulated graph and H a corresponding clique tree. If the sum of the cardinalities of the intersection sets of H is maximum, then H is a junction tree. The converse also holds*.If the nodes and edges in Algorithm 3 are replaced by the nodes (maximal cliques in G) and edges (intersecting cliques in G) of H, then we recover the junction tree algorithm.

- QUOTE:

**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**