Chow–Liu tree

In probability theory and statistics Chow–Liu tree is an efficient method for constructing a second-order product approximation of a joint probability distribution, first described in a paper by Chow & Liu (1968).

The goals of such a decomposition, as with such Bayesian networks in general, may be either data compression or inference.

The Chow–Liu method describes a joint probability distribution

as a product of second-order conditional and marginal distributions.

might be approximated as where each new term in the product introduces just one new variable, and the product can be represented as a first-order dependency tree, as shown in the figure.

The Chow–Liu algorithm (below) determines which conditional probabilities are to be used in the product approximation.

Pearl (1988) provides a modern analysis of the Chow–Liu tree as a Bayesian network.

, and is thus the closest approximation in the classical information-theoretic sense.

The Kullback–Leibler divergence between a second-order product approximation and the actual distribution is shown to be where

are independent of the dependency ordering in the tree, only the sum of the pairwise mutual informations,

The equation above also highlights the role of the dependencies in the approximation: When no dependencies exist, and the first term in the equation is absent, we have only an approximation based on first-order marginals, and the distance between the approximation and the true distribution is due to the redundancies that are not accounted for when the variables are treated as independent.

As we specify second-order dependencies, we begin to capture some of that structure and reduce the distance between the two distributions.

Chow and Liu provide a simple algorithm for constructing the optimal tree; at each stage of the procedure the algorithm simply adds the maximum mutual information pair to the tree.

See the original paper, Chow & Liu (1968), for full details.

A more efficient tree construction algorithm for the common case of sparse data was outlined in Meilă (1999).

Chow and Wagner proved in a later paper Chow & Wagner (1973) that the learning of the Chow–Liu tree is consistent given samples (or observations) drawn i.i.d.

In other words, the probability of learning an incorrect tree decays to zero as the number of samples tends to infinity.

The main idea in the proof is the continuity of the mutual information in the pairwise marginal distribution.

More recently, the exponential rate of convergence of the error probability was provided.

[2] The obvious problem which occurs when the actual distribution is not in fact a second-order dependency tree can still in some cases be addressed by fusing or aggregating together densely connected subsets of variables to obtain a "large-node" Chow–Liu tree (Huang, King & Lyu 2002), or by extending the idea of greedy maximum branch weight selection to non-tree (multiple parent) structures (Williamson 2000).

(Similar techniques of variable substitution and construction are common in the Bayes network literature, e.g., for dealing with loops.

For the third order t-cherry junction tree see (Kovács & Szántai 2010), for the kth-order t-cherry junction tree see (Szántai & Kovács 2010).