The joint tree algorithm is a method used in machine learning to extract marginalization in general graphs . In essence, the algorithm distributes trust on a modified graph called a joint tree . The basic premise of the algorithm is to exclude cycles by clustering them into nodes.
Content
- 1 Algorithm for the joint tree
- 1.1 the algorithm of the program "Hugin" [1]
- 1.2 Schafer-Shenoy algorithm
- 1.3 Theoretical background (for the Hugin algorithm)
- 2 notes
- 3 Literature
Articulation Tree Algorithm
Hugin Algorithm [1]
- If the graph is oriented, then we moralize it to make it non-oriented
- We form information
- Triangulate the graph to get a chordal graph
- We construct the joint tree from the triagulated graph (we will call the vertices of the joint tree “super nodes”)
- We carry out the propagation of probabilities along the joint tree (using the confidence propagation algorithm )
Note that the last step is ineffective for graphs with large wood widths . Calculation of messages transmitted between super nodes requires precise marginalization in both super nodes. Implementing an algorithm on a graph with tree width k will require computations that exponentially depend on time on the value of k.
Schafer-Shenoy Algorithm
- We triangulate the graph by throwing exceptions in an arbitrary order (if required).
- Find the maximum clicks in the chord graph.
- We find the dividing sets for each pair of maximum clicks and build a weighted click graph.
- Find the spanning tree of maximum weight on the click graph to get a joint tree.
- We determine the potentials on the joint tree.
- We calculate the sum of the works on the joint tree. This method of modifying information (message passing). This step, in fact, is known as the Schafer-Shenoy algorithm.
- We calculate the marginals.
The total running time of the algorithm where N is the number of vertices, D is the size of the largest click, - the maximum size of the alphabet in the node [2]
Note that the size of the largest clique D depends on the order of exclusion and the minimum size is equal to the wood width.
In essence, the Hugin algorithm does the same, but steps 5 and 6 are performed differently to reduce the number of multiplications [2] .
Theoretical background (for the Hugin algorithm)
The first step applies only to Bayesian networks and the procedure for turning a directed graph into an undirected one. We do this because it allows a universal application of the algorithm, regardless of direction.
The second step is to set the variables to their observable values. This is usually needed when we want to calculate conditional probabilities, so that we fix the value of random variables by which the probabilities are calculated.
In the third step, we make the graphs become chordal if they are no longer chordal. This is the first essential part of the algorithm. For this, the following theorem is used [3] :
Theorem: For an undirected graph G, the following properties are equivalent:
- Graph G is triangulated.
- The click graph of graph G has a joint tree.
- There is an exception order for graph G that does not exclude any added edge.
Thus, triangulating the graph, we make sure that the corresponding joint tree exists. Usually this is done by the order of exclusion of nodes, and then the algorithm launched. This leads to the addition of additional edges to the original graph in such a way that a chordal graph is obtained as a result. In the next step, a joint tree is built. To do this, use the graph from the previous step and form a click graph [4] . The following theorem gives a method for constructing a joint tree [3] :
Theorem: Let a triangulated graph be given, the weight of the edges of the clique graph of which | A∩B | is given by the intersection power of adjacent cliques A and B. Then the spanning tree of maximum weight of the clique graph is a joint tree.
Thus, to build a joint tree, you need to select a spanning tree of maximum weight from the click graph. This can be effectively done, for example, by modifying the Kruskal algorithm . At the last step, the algorithm for distributing trust to the resulting joint tree is applied [5] .
Notes
- ↑ About the Hugin program you can read on the Hugin page - the best program for creating panoramas
- ↑ 1 2 Recitation 8, 2014 .
- ↑ 1 2 Wainwright .
- ↑ Clique Graph .
- ↑ Barber, 2014 .
Literature
- Martin Wainwright. Graphical models, message-passing algorithms, and variational methods: Part I . Berkeley EECS (March 31, 2008). Date of treatment November 16, 2016.
- Clique Graph . Date of treatment November 16, 2016.
- David Barber Probabilistic Modeling and Reasoning, The Junction Tree Algorithm . University of Helsinki (2014). Date of treatment November 16, 2016.
- Steffen L. Lauritzen, David J. Spiegelhalter. Local Computations with Probabilities on Graphical Structures and their Application to Expert Systems // Journal of the Royal Statistical Society . Series B (Methodological). - Blackwell Publishing, 1988 .-- T. 50 , no. 2 . - S. 157–224 .
- Dawid AP Applications of a general propagation algorithm for probabilistic expert systems // Statistics and Computing. - Springer, 1992.- T. 2 , no. 1 . - S. 25–26 . - DOI : 10.1007 / BF01890546 .
- Cecil Huang, Adnan Darwiche. Inference in Belief Networks: A Procedural Guide // International Journal of Approximate Reasoning. - Elsevier, 1996 .-- T. 15 , no. 3 . - S. 225–263 . - DOI : 10.1016 / S0888-613X (96) 00069-2 .
- Mark A. Paskin. A Short Course on Graphical Models: 3. The Junction Tree Algorithms . Archived on March 19, 2015.
- Algorithms For Inference . Massachusetts Institute of Technology (2014). Date of appeal September 25, 2017.