Chow-Liu Tree

A Chow-Liu tree is the "best possible" tree-shaped belief network approximation to a probability distribution such that all edges are directed away from the root. The quality of the approximation is measured using the Kullback-Leibler distance between the true distribution and the distribution defined by the Chow-Liu tree. When we learn from data, the "true" distribution is defined by the frequencies of the observations.

Chow and Liu (1968) show that the optimum tree can be found as the maximum-weight spanning tree over all variables, where the weight of each edge is given as the mutual information between the variables connected by the edge.

A Chow-Liu tree can be constructed as follows:

• Calculate the mutual information MI(X_i, X_j) for each pair (X_i, X_j).
• Consider the complete MI-weighted graph: the complete undirected graph over {X,...,X_n}, where the links (X_i, X_j) have the weight MI(X_i, X_j).
• Build a maximal-weight spanning tree for the complete MI-weighted graph.
• Direct the resulting tree by choosing any variable as a root and setting the directions of the links to be outward from it.

References

• C. K. Chow, C. N. Liu (1968). Approximating Discrete Probability Distributions with Dependence Trees.