Chow–Liu Tree¶
Approximate a discrete joint distribution by the tree-factorized model whose edges maximize total pairwise mutual information.
Core Idea¶
A Chow–Liu tree approximates a discrete joint distribution with a tree-shaped probability model. Treat each variable as a vertex, give each possible edge the mutual information of its two variables, and choose a spanning tree with maximum total edge weight. Rooting that tree lets the approximation be written as one root marginal times the conditional distribution of every other variable given its single tree parent.[ref-fa13d5356421][ref-83bc14ea2373]
When the target distribution \(P\) is known, Chow and Liu show that this tree minimizes \(D_{\mathrm{KL}}(P\Vert Q_T)\) among their first-order dependence-tree approximations. When only a finite sample is available, empirical mutual information gives a plug-in fitted tree, not a guarantee that the unknown population-optimal tree was recovered. Tied edge weights may also produce several equally optimal trees.[ref-fa13d5356421][ref-275a41114401]
Scope of Application¶
The original paper works through a four-variable binary distribution: known joint probabilities yield pairwise information weights, then several tied maximum-weight trees provide low-order approximations. This is a literal instance of the known-distribution theorem.[^ref-fa13d5356421]
Pavlichin, Ingber and Weissman describe a tabular-data compression baseline that treats discrete columns as variables and uses a tree built from empirical mutual information. Their later MDL-like modification also prices the cost of describing the model; that variant is not the unmodified Chow–Liu objective. Their original manuscript was available here only through indexed text, leaving direct full-text reference clearance pending.[^ref-e5ba4ee86cfb]
Tree-Augmented Naive Bayes is another derived variant: it uses feature-pair mutual information conditional on class and gives each feature the class as a parent. It should not be silently presented as an ordinary joint Chow–Liu tree.[^ref-83bc14ea2373]
Clarity¶
Say whether the weights come from a known target law or estimated data. “Optimal” means minimum true-\(P\) KL loss in the first case and maximum empirical score for the observed sample in the second. Neither means the tree captures every higher-order dependence in an unrestricted source distribution. The graph is a dependency model, not a causal discovery claim.[ref-fa13d5356421][ref-275a41114401]
Manages Complexity¶
The construction replaces a large joint table with a root marginal and parent-child conditionals. The maximum spanning-tree step finds the best edge set within that restricted family without exhaustive search over every tree. This can make storage and inference within the fitted tree model easier, while leaving approximation and estimation error explicit.[ref-fa13d5356421][ref-83bc14ea2373]
Abstract Reasoning¶
For known \(P\), compare candidate trees by summing pairwise mutual information on their edges: a larger sum gives no worse KL projection within the original family. For sampled data, inspect the estimated weights and possible ties before treating an edge as stable. If an application changes the weights to include coding metadata or class conditioning, state that changed objective instead of borrowing the original theorem unchanged.[ref-fa13d5356421][ref-83bc14ea2373][^ref-e5ba4ee86cfb]
Knowledge Transfer¶
The literal pipeline—discrete variables, pairwise information, maximum tree, conditional factorization—transfers from Chow and Liu's probability table to tabular columns. What changes is the evidence regime: a supplied law yields the population KL theorem, while rows yield a finite-data estimator. Live Probabilistic Graphical Model is the proposed strict DAG parent. A generic spanning tree chosen by unrelated weights, a dynamic network, and a plane-graph Good Spanning Tree do not instantiate this specific method.[ref-fa13d5356421][ref-e5ba4ee86cfb][ref-23865c39f73c][ref-23865c39f73c-4]
[^ref-fa13d5356421]: C. K. Chow and C. N. Liu, “Approximating Discrete Probability Distributions with Dependence Trees”, IEEE Transactions on Information Theory IT-14(3) (1968), 462–467, university-hosted original scan text inspected 2026-10-01; binary/screenshot retrieval failed. [^ref-275a41114401]: Tsachy Weissman, “Information Theory, Graphical Models, and Decision Trees”, Stanford EE376A original lecture notes, PDF pp.8–13, inspected 2026-10-01. [^ref-83bc14ea2373]: Nir Friedman, Dan Geiger and Moises Goldszmidt, “Bayesian Network Classifiers”, Machine Learning 29 (1997), §4.1, full PDF inspected 2026-10-01. [^ref-e5ba4ee86cfb]: Dmitri S. Pavlichin, Amir Ingber and Tsachy Weissman, “Compressing Tabular Data via Pairwise Dependencies”, Data Compression Conference (2017), original author manuscript indexed opening text inspected 2026-10-01; direct PMC opening returned reCAPTCHA. [^ref-23865c39f73c]: Encyclopedia of Abstractions, live domain-specific Probabilistic Graphical Model, inspected 2026-10-01. [^ref-23865c39f73c-4]: Encyclopedia of Abstractions, live domain-specific Good Spanning Tree, inspected 2026-10-01.
Relationships to Other Abstractions¶
Current abstraction Chow–Liu Tree Domain-specific
Parents (1) — more general patterns this builds on
-
Chow–Liu Tree is a kind of Probabilistic Graphical Model Domain-specific
A Chow–Liu dependence tree is a PGM specialized to a maximum-mutual-information tree factorization.
Hierarchy paths (6) — routes to 4 parentless roots
- Chow–Liu Tree → Probabilistic Graphical Model → Statistical Model → Representation → Abstraction
- Chow–Liu Tree → Probabilistic Graphical Model → Statistical Model → Probability Distribution → Random Variable → Function (Mapping)
- Chow–Liu Tree → Probabilistic Graphical Model → Statistical Model → Probability Distribution → Probability → Measure → Set and Membership
- Chow–Liu Tree → Probabilistic Graphical Model → Statistical Model → Probability Distribution → Probability → Measure → Aggregation → Micro Macro Linkage
- Chow–Liu Tree → Probabilistic Graphical Model → Statistical Model → Probability Distribution → Random Variable → Probability → Measure → Set and Membership
- Chow–Liu Tree → Probabilistic Graphical Model → Statistical Model → Probability Distribution → Random Variable → Probability → Measure → Aggregation → Micro Macro Linkage
Neighborhood in Abstraction Space¶
Chow–Liu Tree sits in a sparse region of the domain-specific corpus (73rd percentile for distinctiveness): few abstractions share its structure, so a faithful description tends to retrieve it precisely.
Family — Scaling Laws & Growth Patterns (12 abstractions)
Nearest neighbors
- Factored Language Model — 0.84
- Hadwiger number — 0.83
- Brownian Skorokhod Embedding — 0.83
- Bayesian Network — 0.83
- Infomax — 0.83
Computed from structural-signature embeddings · 2026-10-08