Chow–Liu Dependence Tree
Approximate a joint distribution with the best pairwise dependence tree and expose XOR’s missing interaction.
Free theory articleApproximate a joint distribution with the best pairwise dependence tree and expose XOR’s missing interaction.
Concept & interpretation
The Chow–Liu algorithm finds a maximum mutual-information spanning tree over variables to approximate a full joint distribution. It highlights strongest pairwise dependencies and reveals when pairwise factors cannot capture higher-order relationships.
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:
- 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.
- 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.