The cabinet of sixteen drawers

Imagine four switches in a sealed cabinet: rain, a delayed train, a damp platform and a late arrival. Each switch is either off or on. A complete joint distribution needs a probability for every one of the sixteen possible patterns. Add a fifth switch and the cabinet needs thirty-two drawers. At twenty switches, it needs more than a million.

The number is only the first difficulty. Every drawer needs evidence. If a combination is rare, a finite sample may never visit it. The table can be formally complete yet statistically brittle. It also hides structure. Perhaps rain predicts a damp platform, the platform predicts delay, and delay predicts a late arrival. A list of sixteen numbers does not announce that organisation.

Chow and Liu’s problem begins here. They are given a discrete joint distribution, rather than asked to discover reality from nothing. They want a simpler distribution made from first- and second-order pieces. Those pieces must form a dependence tree: every variable is a vertex, every retained pair is an edge, all vertices are connected, and no route closes into a cycle.

A tree on n variables has exactly n − 1 edges. That is the compression bargain. The complete graph offers n(n − 1)/2 candidate pairs; the approximation keeps only enough to connect the variables. The hard question is not whether to keep fewer pairs. It is which pairs retain the most consequential dependence.

There are two kinds of economy here, and they should not be merged. Structural economy limits how many variables can appear together in a factor. Statistical economy limits how many independent numbers must be estimated. Computational economy lets marginal or conditional questions be answered by passing information along a tree instead of summing an unrestricted table. A small factorisation can deliver all three, but only if its omitted interactions are acceptable for the question being asked.

Suppose every variable has m possible values. The unrestricted table has mⁿ cells and mⁿ−1 free parameters. A rooted tree with the same alphabet size has m−1 root parameters and n−1 conditional tables, each with m(m−1) free parameters. Its total grows as (m−1)+(n−1)m(m−1). The exponential dependence on variable count has become linear. Large alphabets can still be expensive, so “tractable” is relative to the discarded exponential, not a claim that every instance is small.

The representation also changes what can be checked. In a full table, consistency is only the global requirement that probabilities are non-negative and sum to one. In a tree, every edge factor can be inspected as a contingency table, and the whole joint follows from how those tables share marginals. A reader can ask whether a connection earns its place. That interpretability is structural and limited: a visible edge shows retained association, while absence can mean weak association or sacrifice to preserve acyclicity.

What makes a pair worth keeping?

Correlation is not general enough for arbitrary discrete variables. Chow and Liu inherit a sharper quantity from information theory. Mutual information asks how much observing one variable reduces uncertainty about another. For variables X and Y with joint probability p(x,y), it is

If the joint equals the product of marginals in every cell, the logarithm is zero and I(X;Y)=0. If knowing X narrows the possibilities for Y, the value is positive. The quantity is symmetric. I(X;Y) equals I(Y;X), an algebraic fact that will later block any causal reading of the learned arrow.

The paper also needs a measure for entire distributions. Given the target P and an approximation Q, Kullback information is

It is non-negative and becomes zero only when P and Q agree wherever P places mass. It is not a geometric distance: reversing P and Q can change the value. Chow and Liu use the P-to-Q direction. That choice asks how much descriptive information is lost when data distributed as P are encoded or represented through Q.

The support condition deserves attention. If P assigns positive probability to a state for which Q assigns zero, the logarithmic penalty is infinite. The tree built from P’s own marginals avoids casually inventing such holes along retained factors, although zeros in empirical tables still need careful handling. Conversely, Q may assign mass to a state absent under P without receiving an infinite forward penalty, because that state carries zero P-weight. The direction therefore expresses a definite tolerance pattern.

Neither non-negativity nor asymmetry makes divergence a moral ranking of models. It is an expected logarithmic scoring difference under one target. A model with slightly larger D(P||Q) could be preferable for a task that values a rare state differently, requires causal interpretability, or measures classification error. The 1968 result is strong because its objective is explicit, not because that objective silently subsumes every use of a probability model.

One root, one parent per remaining variable

Take a tree and choose any vertex as its root. Direct every edge away from that root. Each non-root variable now has exactly one parent. The associated distribution can be written as a root marginal multiplied by one conditional factor for every other variable:

Using factors taken from P is crucial. It means Q reproduces every one-variable marginal and every pair marginal on a selected tree edge. What it relinquishes is the freedom to specify arbitrary interactions around cycles or among larger groups.

The same distribution also has an undirected product form. Multiply the pair marginal on every edge, then divide by each node marginal enough times to correct for its degree. A leaf appears in one pair and needs no correction. A vertex of degree three appears in three pair factors, so its marginal must be divided out twice. This form makes the absence of a privileged root visible and explains why all edge marginals can match P simultaneously.

Normalisation follows from leaf elimination. Choose a leaf, sum over its value, and its pair factor collapses to the marginal of its neighbour. The matching denominator cancels. Repeat until only one variable remains, whose marginal sums to one. This check matters because multiplying locally plausible tables does not ordinarily guarantee a coherent joint. The tree’s acyclic organisation supplies the guarantee.

The divergence sheds its difficult part

The decisive move is to substitute the tree factorisation into D(P||Q). The term ΣP log P depends only on the target distribution. It cannot distinguish candidate trees. The expected log of the tree distribution separates into a root entropy and conditional entropies:

Now use H(X|Y)=H(X)−I(X;Y). The root entropy plus all child marginal entropies becomes ΣᵢH(Xᵢ), the same for every tree. The only tree-dependent terms are the subtracted mutual informations:

The bracket is fixed. Minimising divergence is therefore exactly the same problem as maximising the sum of retained edge weights. A statistical approximation problem has become a graph optimisation problem. This is the paper’s load-bearing reduction.

It is worth tracing one term rather than accepting the cancellation as magic. If B is the parent of C, the contribution −Eₚ log P(C|B) is H(C|B). Replacing it by H(C)−I(B;C) says that an unconditional description of C costs H(C), while access to B saves I(B;C). Across a tree, every node pays its unconditional entropy once and every retained edge earns one information saving. Structure selection is therefore a contest among savings against a common bill.

This account also explains why mutual information, rather than raw agreement, is the proper weight. Two variables that are almost always zero may agree often even when independent. Their marginal entropies are already part of the common bill. The edge earns credit only for the extra predictability left after those marginals are accounted for. The logarithmic ratio in mutual information performs that correction cell by cell.

The derivation separates parameter fitting from structure fitting. For a fixed tree, choose the factors that match P’s relevant marginals. Then compare structures by their edge-information sum. If one instead chose arbitrary conditional tables for every candidate tree, poor parameter choices could obscure structural quality. Chow and Liu’s projection fits each tree as well as possible before the trees compete.

Choose strong edges, refuse every cycle

Construct the complete graph on the variables. Give edge (i,j) the weight I(Xᵢ;Xⱼ). Then find a spanning tree with the largest total weight. One transparent procedure sorts edges from strongest to weakest and adds an edge unless doing so would close a cycle. It stops after n−1 edges.

Why can a greedy procedure be trusted? Suppose a candidate tree omits a heavier edge e. Adding e creates exactly one cycle. Somewhere on that cycle lies an edge f no heavier than e. Remove f. Connectivity returns, the graph is again a tree, and total weight does not decrease. Repeating this exchange transforms an optimum into one consistent with the greedy choices. The algorithm exploits a property of trees, not a vague hope that strong local choices usually work.

The cycle test can be implemented with connected-component labels. At the start every vertex is its own component. An edge whose endpoints have different labels joins two components and is accepted; their labels merge. An edge whose endpoints already share a label would close a cycle and is rejected. After n−1 acceptances, one component contains every variable. The laboratory below uses a disjoint-set structure for exactly this check.

Ties do not threaten optimality, but they can destroy uniqueness. If two candidate edges have equal weights and each can complete the same cut, more than one maximum tree may exist. A program’s tie-breaking rule will return one of them. Reporting that single drawing without its tied alternatives can suggest structural certainty that the objective never supplied. The distributional projections may even differ while sharing the same divergence.

The exchange proof has a useful negative lesson. Taking each node’s strongest neighbour independently is not enough. Those choices can create a cycle in one region and leave another vertex disconnected. Likewise, choosing the n−1 strongest pairs without a cycle check need not produce a tree. Global optimality is possible because the greedy procedure respects the independence rule for forests at every step.

For n variables the complete graph has O(n²) pair weights. Estimating each weight also depends on the variables’ alphabet sizes and the amount of data. Once weights exist, standard spanning-tree algorithms are polynomial. The striking contrast is with learning an unrestricted network structure, where the search space grows much more severely. Tractability arrives because the model family is narrow enough to possess an exchange structure.

Exact recovery, then the triangle tax

If P itself factorises on a tree and the relevant edge dependencies are identifiable, the construction can recover a zero-divergence representation. The pair marginals along its edges contain exactly what the product needs. The situation changes when P contains an irreducible loop.

Consider three variables with substantial dependence on every pair. A tree has room for two edges. One association must be represented only indirectly through the path formed by the others. The selected tree is still optimal inside its family, but “optimal” does not mean “lossless”. It names the least expensive omission under the chosen information criterion.

The XOR example does not refute the theorem. It clarifies its price. The algorithm correctly finds the best tree under its objective; the best tree happens to be unable to represent the decisive interaction. The distinction between optimisation error and model-class error is essential. Chow and Liu solve the former exactly. They do not abolish the latter.

Several familiar graph intuitions need repair at this point. A missing edge in the fitted tree does not assert marginal independence in P. A and C can be strongly associated yet connected only through B because the tree spends its direct edges where the total information saving is greatest. Nor does a path certify that B explains the association. It states how Q factorises. Conditional independences belong to Q’s model structure; whether they are adequate descriptions of P is measured only indirectly by the remaining divergence.

Forward divergence also aggregates loss. Two targets can have the same minimum divergence while failing in different regions. One tree may miss a modest interaction spread across common states; another may badly distort a rare configuration. The single number ranks expected log loss but does not replace a residual analysis. Pairwise tables for omitted edges, higher-order contingency checks and task-specific errors can reveal what the aggregate conceals.

There is a further distinction between an exact tree distribution and an identifiable tree structure. If an edge has zero mutual information, cutting it does not change the represented distribution, and several trees can encode the same independent factors. If weights tie, multiple structures can be equally good. Exact density recovery can therefore coexist with uncertainty about which graph deserves to be called “the” tree.

When edge weights come from a finite sample

The formal problem begins with a distribution. In practice, probabilities often come from counts. Replace p(x,y) with empirical frequencies and the same calculation yields empirical mutual information. This makes the algorithm usable, but it introduces sampling variation. A rare coincidence can inflate an edge; an unobserved cell can make an estimate brittle; two nearly equal edges may swap order between samples.

For a pair of binary variables, the estimate comes from four counts. For variables with twenty categories each, it comes from four hundred cells, many of which may be sparsely occupied. The tree still uses only pairwise tables, but those tables are not equally easy to estimate. Alphabet size, sample size and marginal imbalance all shape uncertainty before graph optimisation begins.

An empirical mutual information is non-negative on the observed table and is biased upward in small samples: random fluctuations create apparent departures from independence. This does not automatically invalidate the ranking, because edges are compared under similar calculations, but unequal alphabet sizes can make biases unequal. Penalised scores, Bayesian estimates or held-out likelihood can answer that concern. Each changes the estimation problem and must be stated rather than smuggled into the 1968 theorem.

Resampling offers a descriptive check. Draw bootstrap samples, rebuild the tree and count how often each edge appears. A ninety-per-cent edge frequency means the fitted procedure repeatedly selects that edge under resampled empirical variation. It is not a posterior probability that the edge is true, and it cannot expose an interaction absent from the tree family. Stability measures sensitivity; it does not confer causal status or model adequacy.

Later consistency work asks whether the estimated tree converges to the generating tree as observations accumulate. The relevant promise needs conditions: the data must arise from an identifiable tree distribution, and edge comparisons must be separated enough for sampling noise eventually to stop reversing them. A finite data set does not inherit asymptotic certainty merely because the structure search is exact.

Smoothing can prevent zero probabilities, but it also changes the estimate. Resampling can show how often an edge survives, but it does not make the chosen family richer. Mixtures of trees address a different limitation by averaging multiple tree structures. Higher-treewidth models retain more interactions but spend more computation and parameters. Each remedy targets a separate weakness.

A responsible empirical workflow therefore keeps three ledgers. The probability ledger records counts, smoothing and held-out evaluation. The structure ledger records edge weights, ties, cycle rejections and alternative maximum trees. The adequacy ledger records residual dependencies and task errors after fitting. Collapsing them into one attractive diagram makes it impossible to tell whether a surprising edge arose from the data, the estimator, the tree constraint or the downstream use.

Executable Chow–Liu laboratory

The laboratory below computes pairwise mutual informations from an exact synthetic five-bit distribution, orders all candidate edges, and builds the maximum spanning tree with a cycle veto. The preset controls the generating mechanism; the step control truncates the edge scan so rejection and acceptance can be inspected.

Choose a preset, then build the tree.

What it demonstrates. Pairwise tables are enough to score edges; descending scores plus a cycle check are enough to find the best tree. Assumptions. Variables are discrete, the displayed distribution is exact, logarithms use base two, and no causal meaning is assigned. How to inspect it. Move “edges inspected” down to reveal the greedy trace. Positive result. Four accepted edges connect all five vertices and maximise their total weight. Negative result. Failure to connect means the scan was stopped early, not that the theorem failed. The artefact cannot establish a population model from finite observations or recover higher-order XOR dependence from zero pairwise weights.

From one tree to richer tractable families

Chow and Wagner later examined consistency of estimating a tree-dependent distribution. That successor moves from a known target distribution to the conditions under which sample estimates recover structure. It strengthens the statistical route without changing the original projection theorem.

Tree-augmented naïve Bayes places a class variable above features and permits a tree of additional feature dependencies. The restriction remains deliberate: it gains interactions beyond conditional independence while preserving efficient learning and inference. The objective is classification-oriented, so its success should not be confused with universal density accuracy.

Meilă and Jordan’s mixtures of trees answer a different objection. One tree must choose a single skeleton. A mixture can express several regimes, each with its own tree, and combine them probabilistically. The price is latent mixture structure and a more involved learning problem. Conditional Chow–Liu forests extend the scoring idea to conditional distributions and time-series settings.

These branches preserve the paper’s durable lesson: choose a representation class whose statistical score decomposes into locally computable pieces and whose global consistency can still be optimised exactly. The particular miracle is not that every distribution is a tree. It is that the best tree can be found without enumerating all labelled trees or all joint tables.

That lesson is easy to misapply. A decomposable score is useful only when its pieces recombine into the intended global objective. Pairwise association scores cannot simply be attached to an arbitrary cyclic graph and expected to preserve the same proof. The spanning-tree constraint prevents incompatible local choices and gives the exchange argument somewhere to operate. When a later model adds cliques, latent regimes or conditional targets, it needs a new account of fitting, normalisation and optimisation.

The paper also separates explanation from prediction in a productive way. Its tree can make probabilistic calculations transparent because each retained factor has a local interpretation. Yet a transparent projection can still be wrong where P contains looped or higher-order structure. Conversely, a richer model can predict better while becoming harder to inspect. Chow and Liu do not settle that trade-off. They provide a rare calibrated point on it: a simple family, an explicit loss, an exact structural optimum and visible failure boundaries.

For contemporary readers, the most transferable test is threefold. Ask what family is being searched, what loss defines “best”, and whether the optimisation is exact for that pairing. Then ask a separate question about estimation: how reliably were the local scores obtained? Finally inspect residuals that the family cannot represent. These questions prevent an elegant graph from borrowing certainty from a theorem whose assumptions it no longer satisfies.

Memory studio

Next three papers to read

1. Canon 0016, Hastings (1970). Continue the probability module by seeing how a target distribution is preserved by an asymmetric Markov-chain proposal.
2. Chow and Wagner (1973). Move from an exact target distribution to the statistical consistency of an estimated dependence tree.
3. Meilă and Jordan (2000). Test the single-tree boundary by learning a mixture whose components carry different tree structures.

The achievement is the reduction, not the tree myth

Chow and Liu made a large approximation problem newly tractable by aligning three structures. Kullback information provides the loss. Mutual information provides local pair scores. The acyclic connectivity constraint provides a graph family with an exact global optimiser. None of the three can be removed casually: change the loss, the factor family or the connectivity rule, and the reduction may disappear.

The tree is valuable precisely because it is a disciplined compromise. It stores and estimates far less than a full joint table. It preserves selected pair marginals and supports efficient probability calculations. It also announces its omissions: no cycles, one structural route between any two variables, and no direct representation for a pure higher-order constraint.

The right reading is therefore neither “all dependence is a tree” nor “trees are too simple to matter”. The paper shows how a restricted family can earn an exact optimisation theorem. It also teaches a durable research habit: distinguish the certainty of an optimiser from the adequacy of its model class and the uncertainty of the quantities it optimises.