Junction Tree Algorithm

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

• AKA: Clique Tree Algorithm, Junction Tree Inference Algorithm.
• Example(s):
  • junctiontree 0.2.4 - a python implementation by Darryl Reeves & Jaakko Luttinen (2021).
  • Hugin Algorithm,
  • McAuley-Caetano Junction Tree Algorithm (McAuley, Caetano & Buntine, 2017),
  • Shafer-Shenoy Algorithm,
  • …
• Counter-Example(s):
  • a Conditioning Algorithm,
  • a Decision Tree Algorithm,
  • a Maximum Spanning Tree Algorithm,
  • a Regression Tree Algorithm.
• See: 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.

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.

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

• (Paskin, 2015) ⇒ Mark Paskin (2015)."A Short Course on Graphical Models:3. The Junction Tree Algorithms".
  • QUOTE: The junction tree algorithms take as input a decomposable density and its junction tree. They have the same distributed structure:
    • Each cluster starts out knowing only its local potential and its neighbors.
    • Each cluster sends one message (potential function) to each neighbor.
    • By combining its local potential with the messages it receives, each cluster is able to compute the marginal density of its variables.

---