A maximum weight spanning tree selects a tree topology whose total edge weight is greatest among the available spanning trees. In structure learning, pairwise mutual information supplies the edge weights, so the selected topology favors strongly dependent variables while remaining a tree. section 9.3.1
For the Chow–Liu algorithm, tree decomposition converts the likelihood objective into a sum involving pairwise mutual information. The likelihood-maximizing topology is therefore obtained by finding a maximum weight spanning tree with weights I(xs, xt | θ). section 9.3.1
The computational procedure is:
- Estimate node marginals and pairwise edge marginals from the observed state counts. section 9.3.1
- Compute pairwise mutual information for candidate edges and use each value as its edge weight. section 9.3.1
- Run Prim’s or Kruskal’s algorithm to select the maximum spanning tree; the stated time complexity is O(E log V). section 9.3.1
Three-node tree
For a three-node V-shaped undirected tree, node marginals and edge marginals define the likelihood terms. Comparing pairwise mutual-information weights determines which two edges form the maximum-weight topology. section 9.3.1
