Chow–Liu Dependence Tree

Theory

Given a joint probability distribution p(x_1, x_2, …, x_n), finding a simpler tree-structured distribution q that best approximates p (in the sense of minimizing the Kullback-Leibler divergence D_(KL)(p || q)) is equivalent to maximizing the sum of mutual information across the edges of the tree.

For three binary variables A, B, and C, the maximum weight spanning tree has exactly two edges. By computing the mutual information (MI) between each pair and selecting the edges that form a maximum weight spanning tree, we can construct the optimal q. The direction of the edges (the root choice) in the spanning tree is simply a factorization convention. For instance, the edges A-B and A-C can be factored as q(A)q(B|A)q(C|A).

Experiment

Observe the difference between the true joint distribution p and the tree-structured approximation q for different joint laws in the interactive Chow–Liu Dependence Tree module:

1. Set the Joint law to Markov chain. Notice how q perfectly matches p, and the KL divergence is exactly zero. The variables follow a strict sequential dependence that the tree captures completely.
2. Change the Joint law to XOR. Observe that all pairwise mutual information values are zero. The maximum spanning tree chooses edges arbitrarily (by tie-breaking). However, the KL divergence to the tree approximation is ln 2 ≈ 0.693, exposing the hidden higher-order dependence that a pairwise tree cannot capture.

Worked Example

Let's run a calculation based on the specified model logic to find out the tree probability of the state '000'.

Consider the Markov chain joint law, where A is fair (0.5), B is formed by flipping A with probability 1/4 (B = A XOR Bern(1/4)), and C is formed by flipping B with probability 1/4. We wish to calculate the true joint probability of the state "000" and the tree probe probability.

1. Calculate the marginal for A: P(A=0) = 0.5.
2. Calculate the conditional for B: P(B=0|A=0) = 0.75.
3. Calculate the conditional for C: P(C=0|B=0) = 0.75.
4. The true joint probability is 0.5 × 0.75 × 0.75 = 0.28125.
5. For the maximum spanning tree, the mutual information is highest for the A-B edge (approx 0.1308) and the B-C edge (approx 0.1308), so the edges are A-B and B-C.
6. Using the tree factorization q(A)q(B|A)q(C|B), the tree probability for "000" is also 0.5 × 0.75 × 0.75 = 0.28125.

Limitations

The Chow-Liu tree specifically approximates distributions using only pairwise relationships. It intrinsically fails to represent situations where variables are pairwise independent but jointly dependent, such as the XOR relationship. Furthermore, the tree edges do not inherently represent causal direction.

References

C. K. Chow and C. N. Liu, "Approximating discrete probability distributions with dependence trees", IEEE Transactions on Information Theory, vol. 14, no. 3, pp. 462-467, May 1968.
Original Paper
Experiment available at https://riano.app/module/chow-liu-dependence-tree