Mutual Information

How much one random variable tells about another, with the general theory beneath the site's uses of it. Mutual information defined as the divergence of a joint distribution from independence, its three equivalent forms and its bounds proved, conditional mutual information and the chain rule, and the data processing inequality proved two ways with its case of equality. Worked on Reuters term and class tables (why the scores of two terms do not add, and what counting occurrences adds to noting presence), on clusterings, and on the characters of the Tiny Shakespeare text, where an experiment measures the bias of the estimate from counts. Worked problems on Shannon's noisy binary channel, the exclusive-or example, term counts, merged clusters and the likelihood ratio statistic.

In the Reuters-21578 training set, 433 of 7,769 stories are about grain, and the term wheat occurs in 243 stories, 227 of them about grain. Feature selection scores the term by its mutual information with the class, 0.124 bits, and shows that no term can score more than 0.310 bits for this class. What is that score a measure of, in general, and what can raise or lower it? It is the divergence between the joint distribution of two variables and the distribution they would have if they were independent. It equals the amount by which knowing one variable lowers the entropy of the other. And no processing of one variable, however clever, can raise it.

The mutual information of two random variables $X$ and $Y$ with joint mass function $p(x, y)$ and marginals $p(x)$ and $p(y)$ is

$$I(X; Y) = \sum_{x, y} p(x, y)\log\frac{p(x, y)}{p(x)\,p(y)}.$$

First we read the definition as a divergence and prove its equivalent forms and its bounds. Then we define conditional mutual information and prove the chain rule, which explains why the scores of two features do not add. Next we prove the data processing inequality and find when it holds with equality. Then we collect what these results say about the pages of this site that use mutual information. Finally an experiment measures how far the value computed from counts can be trusted. The article assumes Entropy and Cross-Entropy and Kullback–Leibler Divergence, and keeps their notation.

Two pages of the information retrieval course already compute mutual information and prove what they need about it for their tables: feature selection for a term and a class, and evaluating clusterings for clusters and classes. This article does not repeat their computations. It gives the general statements those pages are instances of, and the results they did not need.

Notation

$X$, $Y$ and $Z$ are random variables on finite alphabets, with joint mass function $p(x, y, z)$. As in Entropy, the argument names the function: $p(x)$, $p(y \mid x)$, $p(x, y)$ are the marginal, conditional and joint mass functions. The semicolon in $I(X; Y)$ separates the two sides. A comma joins variables into one, so $I(X; Y, Z)$ is the mutual information between $X$ and the pair $(Y, Z)$. Sums run over the outcomes of positive probability. Numbers about term and class tables are in bits, to agree with feature selection; numbers about clusterings are in nats, to agree with evaluating clusterings.

The symbol $I(\theta)$ with a single argument is the Fisher information of another unit and is unrelated.

A divergence from independence

Here is the idea. If $X$ and $Y$ were independent, the probability of the pair $(x, y)$ would be the product $p(x)\,p(y)$. Mutual information measures how far the true joint distribution is from that product, with the measuring stick of the last article:

$$I(X; Y) = D\big(p(x, y) \,\big\|\, p(x)\,p(y)\big).$$

The product $q(x, y) = p(x)\,p(y)$ is a mass function on pairs, and it is positive wherever $p(x, y)$ is, because $p(x) \ge p(x, y)$ and $p(y) \ge p(x, y)$. So the divergence is finite, and the definition involves no division by zero.

The quantity inside the sum, $\log\frac{p(x, y)}{p(x)\,p(y)}$, is the pointwise mutual information of the pair $(x, y)$. It is positive when the pair occurs more often than independence predicts and negative when it occurs less often. Mutual information is its expected value. For wheat and grain, the cell of stories that contain the term and are about grain holds 227 stories where independence predicts $243 \times 433/7{,}769 = 13.5$, a ratio of 16.8 and a pointwise value of 4.07 bits. The other three cells have pointwise values of $-3.84$, $-1.03$ and $0.04$ bits, and the average of the four, weighted by the cells' shares of the stories, is the 0.124 bits. Feature selection works that sum cell by cell. The pointwise quantity on its own, for pairs of words, is the basis of the coherence scores in Evaluating Topic Models.

Example (negative cells do not mean negative information). Two of the four pointwise values in the wheat table are negative, and a term can be less common in a class than outside it. The mutual information is still positive, because it is a divergence. The term lt in feature selection occurs in only 2 of the 433 grain stories and scores 0.066 bits, which that page reports as the fourth highest score of any term for the class. Mutual information measures dependence of any kind, not agreement.

Three forms and two bounds

Theorem (properties of mutual information). For random variables $X$ and $Y$ on finite alphabets:

  1. $I(X; Y) \ge 0$, with equality exactly when $X$ and $Y$ are independent.
  2. $I(X; Y) = I(Y; X)$.
  3. $I(X; Y) = H(X) - H(X \mid Y) = H(Y) - H(Y \mid X) = H(X) + H(Y) - H(X, Y)$.
  4. $I(X; X) = H(X)$.
  5. $I(X; Y) \le \min\{H(X), H(Y)\}$, and $I(X; Y) = H(X)$ exactly when $X$ is a function of $Y$.

Proof. (1) $I(X; Y)$ is the divergence $D(p \,\|\, q)$ between the mass functions $p(x, y)$ and $q(x, y) = p(x)\,p(y)$. By Gibbs' inequality it is at least 0, and it is 0 exactly when $p(x, y) = p(x)\,p(y)$ for all pairs, which is the definition of independence.

(2) The defining sum is unchanged when the roles of $x$ and $y$ are exchanged.

(3) Split the logarithm as $\log\frac{p(x, y)}{p(x)\,p(y)} = \log p(y \mid x) - \log p(y)$, using $p(x, y) = p(x)\,p(y \mid x)$. Then

$$I(X; Y) = \sum_{x, y} p(x, y)\log p(y \mid x) - \sum_{x, y} p(x, y)\log p(y) = -H(Y \mid X) + H(Y),$$

where the second sum reduces to $\sum_y p(y)\log p(y)$ because $\sum_x p(x, y) = p(y)$. By (2) the same holds with the variables exchanged, $I(X; Y) = H(X) - H(X \mid Y)$. For the last form, substitute the chain rule $H(Y \mid X) = H(X, Y) - H(X)$ from Entropy.

(4) By (3), $I(X; X) = H(X) - H(X \mid X)$, and $H(X \mid X) = 0$ because $X$ is a function of itself.

(5) By (3), $I(X; Y) = H(X) - H(X \mid Y) \le H(X)$, since a conditional entropy is not negative. Equality holds exactly when $H(X \mid Y) = 0$, which Entropy shows is the case exactly when $X$ is a function of $Y$. The same argument with the variables exchanged gives $I(X; Y) \le H(Y)$. $\square$

Part 3 is the reading that gives the quantity its name. $H(X)$ is the uncertainty about $X$, $H(X \mid Y)$ is what remains on average once $Y$ is known, and the difference is what $Y$ tells about $X$. By symmetry it is also what $X$ tells about $Y$: the information is mutual. Shannon (1948, Section 12) introduced the difference $H(x) - H_y(x)$ as the rate at which information passes through a noisy channel, and called the conditional entropy the equivocation. Problem 1 works his example. He gives the same three forms as part 3. Of the last he says that it "is the sum of the two amounts less the joint entropy and therefore in a sense is the number of bits per second common to the two". Part 1 restates the theorem of Entropy that conditioning lowers entropy on average.

The entropies of a pair divide into three parts that add up:

$$H(X, Y) = H(X \mid Y) + I(X; Y) + H(Y \mid X).$$

This follows from part 3 and the chain rule: $H(X, Y) = H(X) + H(Y \mid X)$ and $H(X) = H(X \mid Y) + I(X; Y)$. MacKay (2003, Figure 8.1) draws the three parts as adjoining bars.

On the running examples. For two adjacent characters of the Tiny Shakespeare text, Entropy found $H(X_1) = 4.7794$, $H(X_2) = 4.7793$ and $H(X_1, X_2) = 8.3177$ bits. So $I(X_1; X_2) = 4.7794 + 4.7793 - 8.3177 = 1.2410$ bits. A character removes about a quarter (0.26) of the uncertainty about its neighbor. The joint entropy divides as $3.5383 + 1.2410 + 3.5383$ bits.

For wheat and grain, the term's presence $U$ has entropy $H(U) = 0.2008$ bits and the class $C$ has $H(C) = 0.3103$ bits. The joint entropy is 0.3871 bits, and $H(U) + H(C) - H(U, C) = 0.1239$ bits (from unrounded values). Part 5 gives two ceilings, 0.2008 and 0.3103 bits. Feature selection proves the second for a two-by-two table and uses it to compare terms across classes. The first is lower here: a term found in only 243 stories cannot carry more than 0.2008 bits about anything.

For the seventeen documents of evaluating clusterings, with clusters $\Omega$ and classes $C$, that page finds $I(\Omega; C) = 0.3919$ nats, $H(\Omega) = 1.0951$ and $H(C) = 1.0551$ nats. Part 5 is the reason normalized mutual information, which divides $I$ by the average of the two entropies, cannot exceed 1: $I$ is at most the smaller entropy, and so at most their average.

Conditional mutual information and the chain rule

A classifier uses many terms, not one. If wheat is worth 0.124 bits about grain and corn is worth 0.065, are the two together worth 0.189? They are not, and the chain rule says what they are worth.

The conditional mutual information of $X$ and $Y$ given $Z$ is the mutual information of $X$ and $Y$ within each value of $Z$, averaged over $Z$:

$$I(X; Y \mid Z) = \sum_{z} p(z)\,I(X; Y \mid Z = z) = \sum_{x, y, z} p(x, y, z)\log\frac{p(x, y \mid z)}{p(x \mid z)\,p(y \mid z)}.$$

Here $I(X; Y \mid Z = z)$ is the mutual information computed from the conditional joint mass function $p(x, y \mid z)$. Each term is a mutual information, so by the theorem above $I(X; Y \mid Z) \ge 0$, with equality exactly when $p(x, y \mid z) = p(x \mid z)\,p(y \mid z)$ for every $z$ with $p(z) > 0$. That condition is conditional independence of $X$ and $Y$ given $Z$. Applying part 3 of the theorem within each value of $z$ and averaging,

$$I(X; Y \mid Z) = H(X \mid Z) - H(X \mid Y, Z),$$

where $H(X \mid Y, Z)$ is the conditional entropy of $X$ given the pair $(Y, Z)$.

Theorem (chain rule for mutual information). $I(X; Y, Z) = I(X; Z) + I(X; Y \mid Z)$.

In words: what the pair $(Y, Z)$ tells about $X$ is what $Z$ tells, plus what $Y$ adds once $Z$ is known.

Proof. By part 3 of the theorem applied to $X$ and the pair $(Y, Z)$, and adding and subtracting $H(X \mid Z)$,

$$I(X; Y, Z) = H(X) - H(X \mid Y, Z) = \big[H(X) - H(X \mid Z)\big] + \big[H(X \mid Z) - H(X \mid Y, Z)\big].$$

The first bracket is $I(X; Z)$ and the second is $I(X; Y \mid Z)$. $\square$

By induction, for variables $Y_1, \dots, Y_k$,

$$I(X; Y_1, \dots, Y_k) = \sum_{j=1}^{k} I(X; Y_j \mid Y_1, \dots, Y_{j-1}).$$

The step from $k - 1$ to $k$ is the theorem with $Z = (Y_1, \dots, Y_{k-1})$ and $Y = Y_k$.

Two terms. Let $W$ and $K$ record whether a story contains wheat and corn, and $C$ whether it is about grain. The four combinations of the two terms, against the class:

wheat corn About grain Not about grain
present present 60 4
present absent 167 12
absent present 81 28
absent absent 125 7,292

From this table $I(C; W, K) = 0.1700$ bits. Alone, $I(C; W) = 0.1239$ and $I(C; K) = 0.0650$ bits, which sum to 0.1890. The chain rule gives the correct accounting: $I(C; W, K) = I(C; W) + I(C; K \mid W) = 0.1239 + 0.0460$ (the sum is 0.1700 from unrounded values). Once wheat is known, corn adds 0.0460 bits, not its 0.0650. The two rows of the table with wheat present show why. Among the 243 stories that contain wheat, the share about grain is $60/64 = 0.94$ with corn and $167/179 = 0.93$ without it. Corn tells almost nothing more there; its conditional mutual information within those stories is 0.00005 bits. All of its contribution comes from the stories without wheat.

This is a general limitation of ranking features one at a time, as feature selection does. The scores $I(C; Y_j)$ are each measured against the class alone. The information in a set of features is the chain-rule sum of conditional terms, and features that say the same thing overlap. The overlap between these two terms is visible directly. Corn occurs in 64 of the 243 stories that contain wheat, 26 percent, against 109 of the 7,526 that do not, 1.4 percent. Their mutual information is $I(W; K) = 0.0222$ bits. That is a small number of bits, since neither term is common, but it is far more than independent terms would show in a collection of this size: the bias discussed at the end of this article is about 0.00009 bits for such a table.

Example (conditioning can also raise mutual information). It might seem from the two terms that knowing a third variable always lowers what $Y$ tells about $X$. It can do the opposite. Let $X$ and $Y$ be independent fair bits and let $Z$ be 1 if they differ and 0 if they agree (their exclusive or). Then $I(X; Y) = 0$. Given $Z$, though, $Y$ determines $X$: if $Z = 0$ then $X = Y$, and if $Z = 1$ then $X = 1 - Y$. So $H(X \mid Y, Z) = 0$, while $H(X \mid Z) = 1$ bit because $X$ is still a fair bit within each value of $Z$, and $I(X; Y \mid Z) = 1$ bit. Two variables that are useless alone can be decisive together. Problem 2 works the numbers. There is no general inequality between $I(X; Y \mid Z)$ and $I(X; Y)$, in contrast to entropy, where conditioning never raises the average.

The data processing inequality

Text classification does not use the stories themselves. It uses features computed from them: stems instead of words, presence instead of counts, the top 50 terms instead of all of them. Can a well-chosen computation make the features more informative about the class than the raw data were? It cannot.

Three random variables form a Markov chain in the order $X \to Y \to Z$ if $Z$ depends on $X$ only through $Y$: the joint mass function factors as

$$p(x, y, z) = p(x)\,p(y \mid x)\,p(z \mid y).$$

Dividing by $p(y)$, this says $p(x, z \mid y) = p(x \mid y)\,p(z \mid y)$ for every $y$ with $p(y) > 0$: $X$ and $Z$ are conditionally independent given $Y$, that is, $I(X; Z \mid Y) = 0$. Conversely, conditional independence gives the factorization, by multiplying $p(x, z \mid y) = p(x \mid y)\,p(z \mid y)$ by $p(y)$. The condition is symmetric in $X$ and $Z$, so $X \to Y \to Z$ is a Markov chain exactly when $Z \to Y \to X$ is.

The most common case is a function. If $Z = g(Y)$, then $p(z \mid x, y)$ is 1 when $z = g(y)$ and 0 otherwise, whatever $x$ is. It does not depend on $x$, so $X \to Y \to g(Y)$ is a Markov chain for any $X$.

Theorem (data processing inequality). If $X \to Y \to Z$ is a Markov chain, then

$$I(X; Z) \le I(X; Y),$$

with equality exactly when $I(X; Y \mid Z) = 0$, that is, when $X \to Z \to Y$ is also a Markov chain.

The plan of the proof: write what the pair $(Y, Z)$ tells about $X$ in the two orders the chain rule allows. One order contains the term $I(X; Z \mid Y)$, which the Markov property makes zero.

Proof. By the chain rule for mutual information, applied in both orders,

$$I(X; Y, Z) = I(X; Z) + I(X; Y \mid Z) = I(X; Y) + I(X; Z \mid Y).$$

The Markov property gives $I(X; Z \mid Y) = 0$. Therefore

$$I(X; Y) = I(X; Z) + I(X; Y \mid Z) \ge I(X; Z),$$

because a conditional mutual information is not negative. Equality holds exactly when $I(X; Y \mid Z) = 0$, which is conditional independence of $X$ and $Y$ given $Z$, the Markov property for the order $X \to Z \to Y$. $\square$

Corollary (functions). For any function $g$, $I(X; g(Y)) \le I(X; Y)$, with equality exactly when $X$ and $Y$ are conditionally independent given $g(Y)$.

Corollary (the other end). If $X \to Y \to Z$ is a Markov chain, then also $I(X; Z) \le I(Y; Z)$.

Proof. The first is the theorem for the chain $X \to Y \to g(Y)$. The second is the theorem for the reversed chain $Z \to Y \to X$, with the symmetry of mutual information. $\square$

The name comes from reading $Y$ as data about some state of the world $X$, and $Z$ as the result of processing the data. MacKay (2003, Section 8.3) puts the content in one sentence, "data processing can only destroy information", and adds a warning: "This theorem is as much a caution about our definition of 'information' as it is a caution about data processing!" The warning is fair. Stemming, selecting features and training a network are all processing, and all are useful, because they put the information into a form that a limited procedure can use. What the theorem rules out is that they increase the dependence between what is kept and the state of the world.

A second proof for functions. The corollary for functions also follows from a theorem of the last article: merging outcomes cannot increase a divergence. Let $p(x, y)$ be the joint mass function and $q(x, y) = p(x)\,p(y)$, so that $I(X; Y) = D(p \,\|\, q)$. Merge pairs by the map $(x, y) \mapsto (x, g(y))$. Under $p$ the merged pair $(X, g(Y))$ has its joint distribution. Under $q$ the two coordinates are independent with the marginals of $X$ and $g(Y)$, so the merged distribution is the product of those marginals. The divergence between the two merged distributions is therefore $I(X; g(Y))$, and by the merging theorem it is at most $D(p \,\|\, q) = I(X; Y)$.

Counting occurrences

Feature selection scores a term by whether it is present. The stories record more: how many times it occurs. Let $N_w$ be the number of occurrences of wheat in a story, so that the presence indicator is a function of it, $W = \mathbf{1}\{N_w \ge 1\}$. By the corollary, $I(C; W) \le I(C; N_w)$. The counts:

Occurrences of wheat About grain Not about grain
0 206 7,320
1 42 13
2 62 3
3 or more 123 0

The count ranges up to 19. From the full table of counts, $I(C; N_w) = 0.1271$ bits, against $I(C; W) = 0.1239$ for presence alone. Counting adds 0.0031 bits, about 2.5 percent. Presence carries nearly everything the count does, which is some justification for the two-by-two tables.

The table also shows the case of equality. Let $T = \min(N_w, 3)$, the count with everything from 3 upward merged, as in the last row. Then $I(C; T) = 0.1271$ bits, the same as for the full count to every digit computed. The theorem says why: equality holds exactly when $C$ and $N_w$ are conditionally independent given $T$. When $T$ is 0, 1 or 2 it determines $N_w$. When $T = 3$ every story is about grain, so the class is settled and the exact count cannot tell more. Merging outcomes loses information only if the merged outcomes differed in what they said about $X$.

Sufficiency

The case of equality has a name in statistics. Suppose $X$ is a parameter that takes finitely many values, with a prior distribution that gives each of them positive probability. Let $Y$ be a sample whose distribution depends on the parameter, and $T = g(Y)$ a statistic. Then $X \to Y \to T$ is a Markov chain and $I(X; T) \le I(X; Y)$. Equality holds exactly when $X$ and $Y$ are conditionally independent given $T$. That says the conditional distribution of the sample given the statistic is the same for every parameter value that has positive probability together with that value of the statistic. Because the prior leaves no parameter value out, this is the definition of a sufficient statistic, the subject of Sufficient Statistics. A sufficient statistic is a summary of the data that loses no information about the parameter, in exactly this sense.

The condition on the prior is needed. If the prior puts all its probability on one parameter value, then $X$ is constant, $I(X; T) = I(X; Y) = 0$ for every statistic, and equality holds for statistics that are not sufficient. Conditional independence under the joint distribution says nothing about parameter values the prior excludes. A parameter with a continuum of values, such as a normal mean, is outside the finite alphabets of this article.

What this says about the pages that use mutual information

The results above are used, mostly without their names, across the site.

Information gain in decision trees. Classification Trees chooses the split that most reduces the weighted entropy of the class. If $S$ is the variable recording which side of the split a case falls on, the weighted entropy of the children is $H(C \mid S)$, so the reduction is $H(C) - H(C \mid S) = I(C; S)$, by part 3 of the theorem. Information gain is mutual information between the class and the split. For the 23 Challenger flights of that page, the root has 0.8865 bits. The split at 64.5 °F leaves a pure node of 4 flights and a node of 19 with entropy 0.6292 bits. The weighted entropy is $\frac{19}{23} \times 0.6292 = 0.5198$ bits, and the gain is $0.8865 - 0.5198 = 0.3667$ bits. Part 1 of the theorem is the reason a split never has negative gain, and gain is zero only for a split whose two sides have the same class proportions. A split is a function of the input variable, so by the data processing inequality no split of a variable can gain more than the variable itself holds about the class.

Feature selection. The score of feature selection is $I(U; C)$ for a term's presence $U$. Its two bounds there are parts 1 and 5 of the theorem for a two-by-two table, and its Problem 3, that information gain equals mutual information, is part 3. The chain rule adds what that page's method leaves out: scores of individual terms overstate what a set of terms holds, by the overlaps among them.

Evaluating clusterings. In evaluating clusterings the two variables are a document's cluster and its class. That page observes that mutual information is largest when every document is its own cluster. The data processing inequality gives the general fact behind it. If a clustering $\Omega$ is obtained from a finer one $\Omega'$ by merging clusters, then $\Omega$ is a function of $\Omega'$, and $I(C; \Omega) \le I(C; \Omega')$. Merging clusters never raises mutual information with the classes, and splitting them never lowers it, whatever the split. This is why the raw score cannot be used to choose the number of clusters, and why it is normalized. Problem 4 merges clusters of the seventeen documents. The correction for chance is the subject of chance-adjusted clustering measures.

Loss and likelihood. By part 3, $I(X_1; X_2) = H(X_2) - H(X_2 \mid X_1)$. In the language of the last article, $H(X_2)$ is the lowest loss of a model that ignores context, and $H(X_2 \mid X_1)$ is the lowest loss of a model that sees the previous character. Both models are fitted to the text they are scored on. The mutual information of adjacent characters, 1.2410 bits or 0.8602 nats, is the most that a bigram table can gain over character frequencies on the Tiny Shakespeare text.

Measuring it from counts

Every value above was computed by putting observed shares into the definition. How far can such a value be trusted as a measure of dependence? The experiment in Entropy showed conditional entropies computed from counts falling when nothing was there to find. Mutual information computed from counts has the mirror-image fault when the variables are independent. By part 1 it is never negative, and for a sample from independent variables it is almost never exactly zero. On average, then, it is too high. This is proved here only for that case, a true value of zero.

Example (the count-based value can also be too low). The fault does not always run upward. Let $X$ be uniform on four values and $Y = X$, so that $I(X; Y) = H(X) = 2$ bits. A sample of two pairs shows either one value twice or two different values, and its count-based mutual information is 0 bits or 1 bit, never 2. Averaged over the sixteen equally likely samples it is 0.75 bits. In general a sample of $N$ pairs cannot show more than $\log_2 N$ bits, whatever the truth is.

The characters of the Tiny Shakespeare text give a measurement. Let $X_t$ and $X_{t+d}$ be the characters at two positions $d$ apart. Their mutual information, from the counts of all such pairs in the file:

Distance $d$ $I(X_t; X_{t+d})$ (bits)
1 1.2410
2 0.6199
3 0.3521
4 0.2244
8 0.0724
16 0.0114
32 0.0039
64 0.0039

The table samples a curve that the figure shows in full, for every distance from 1 to 64. The dependence falls quickly, below 0.01 bits from $d = 17$ (0.0097), to a low of 0.0032 bits at $d = 37$. Are values that small dependence between characters, or the fault just described?

For comparison, shuffle the characters of the file into a random order and compute the mutual information of adjacent characters. A shuffled text has no real dependence between neighbors beyond a trace from the fixed counts. Over 30 shuffles (seeds 0 to 29) the median is 0.0025 bits, with interquartile range 0.0025 to 0.0026, and the largest of the 30 values is 0.0026. So about 0.0025 bits of every value in the table is what this file yields when there is nothing to measure. At distance 1 that is negligible against 1.2410. At the low point, $d = 37$, it is most of the value: the experiment supports dependence there only to the extent of the remaining 0.0007 bits or so. Every distance up to 64 does stay above every one of the shuffles.

Mutual information between two characters of the text d positions apart, for d from 1 to 64, on a logarithmic scale; the band is the range of the same quantity for adjacent characters in 30 shuffles of the text. Notice that the curve comes down to 1.2 times the top of the band at d = 37 and never enters it, and that it rises again to a second, low hump between about d = 45 and d = 52.
Mutual information between two characters of the text d positions apart, for d from 1 to 64, on a logarithmic scale; the band is the range of the same quantity for adjacent characters in 30 shuffles of the text. Notice that the curve comes down to 1.2 times the top of the band at d = 37 and never enters it, and that it rises again to a second, low hump between about d = 45 and d = 52.

The figure shows something the table hides. From $d = 38$ the curve rises again, to a broad second hump of 0.0069 to 0.0071 bits between $d = 45$ and $d = 52$ (highest at $d = 51$, by a margin too small to mean anything), before returning to 0.0039 at $d = 64$. The file's layout offers an explanation. Its non-empty lines have a median length of 39 characters, and the five commonest lengths are 40 to 44. Two characters 41 to 45 positions apart are therefore often at the same place in successive lines, and line beginnings are unlike line middles: a newline, then usually a capital. A hump beginning near $d = 40$ and several positions wide is consistent with that, though this article has not tested it.

The size of the fault can be anticipated. Take a table of counts with total $N$. The mutual information of its observed shares in nats, multiplied by $2N$, is the likelihood ratio statistic for independence, $G = 2\sum O\ln\frac{O}{E}$, with observed counts $O$ and expected counts $E$. Problem 5 works the identity. Under the hypothesis, and with large expected counts, a likelihood ratio statistic has approximately a chi-squared distribution. Its degrees of freedom are the number of free parameters of the unrestricted model minus the number that remain free under the hypothesis. That is Wilks's theorem, which Likelihood Ratio, Wald and Score Tests proves for one parameter and cites for several; it is not proved here. The count for a table of $r$ rows and $c$ columns is short. The unrestricted model has a probability for each of the $rc$ cells, summing to 1, so $rc - 1$ free parameters. Independence leaves the row probabilities and the column probabilities, $(r - 1) + (c - 1)$ free parameters. The difference is $(rc - 1) - (r - 1) - (c - 1) = (r - 1)(c - 1)$. A chi-squared variable has mean equal to its degrees of freedom (The Chi-Squared and t Distributions). Taking the theorem as given, then, the mutual information of a sample from independent variables should average about

$$\frac{(r - 1)(c - 1)}{2N} \text{ nats}.$$

For the shuffled text, $r = c = 65$ and $N = 1{,}115{,}393$, which gives 0.0018 nats, or 0.0026 bits, close to the observed median of 0.0025. (Some characters are too rare for the chi-squared approximation to be good, so exact agreement is not expected.) The formula shows what governs the fault: the number of cells against the number of observations. For a two-by-two table on the 7,769 Reuters stories it is $1/15{,}538$ nats, about 0.00009 bits, small against the 0.124 bits of wheat though not against the scores of the weakest terms. For the seventeen documents in a three-by-three table it is $4/34 = 0.118$ nats, a share of 0.30 of the 0.3919 nats that table scores. Chance-adjusted clustering measures compute the exact expectation under a permutation model instead, 0.1517 nats for that table, and subtract it.

The formula above is for independent variables only. For dependent variables the usual first-order estimate works through the three entropies in $I = H(X) + H(Y) - H(X, Y)$: Paninski (2003, Section 3 and equation 4.6) gives the bias of an entropy computed from the shares of $N$ observations on $m$ cells as about $-(m - 1)/(2N)$ nats for fixed $m$ and large $N$, and calls the matching adjustment the Miller–Madow bias correction. He also notes (Section 3.3) that the count-based mutual information is not biased upward for every distribution, as the example above shows. That estimate is cited, not proved here; Differential Entropy and the Gaussian uses it on a table of strongly dependent readings.

What is proved, what is cited, what the experiment shows

Proved here: the five properties of mutual information; the formula for conditional mutual information as a difference of conditional entropies and its nonnegativity; the chain rule for two and for several variables; the equivalence of the Markov property with conditional independence; the data processing inequality with its case of equality, its corollaries, and a second proof for functions; the identification of information gain with mutual information; that merging clusters cannot raise mutual information with the classes; the equality case as sufficiency, for a prior that gives every parameter value positive probability.

Proved on linked pages: Gibbs' inequality and the merging theorem for divergences (Cross-Entropy and Kullback–Leibler Divergence); the chain rule for entropy and the fact that a conditional entropy is zero exactly for a function (Entropy).

Cited: Shannon (1948, Section 12) for the rate of transmission and the equivocation; MacKay (2003, Section 8.1 and Exercise 8.9) for the definitions and the name of the data processing theorem. The noisy channel coding theorem, which makes the largest mutual information over input distributions the capacity of a channel, is Shannon's (1948, Theorem 11); it is not proved or used here. Cover and Thomas (2006) is the standard textbook treatment. The large-sample chi-squared distribution of the likelihood ratio statistic (Wilks's theorem) is taken from the linked page; only the count of its degrees of freedom for a table is done here. The first-order bias of an entropy computed from counts, for dependent variables, is Paninski's statement (2003).

Computed: the Reuters tables, from the training stories of the Reuters-21578 collection with the text processing of feature selection, whose method follows Manning, Raghavan, and Schütze (2008, Section 13.5); the seventeen documents, which are the example of the same book (Section 16.3, Figure 16.4) as tabulated in evaluating clusterings; the Tiny Shakespeare distances and shuffles. The shuffling experiment measures the fault of the count-based value on one file at one table size, for independent variables only. The approximate formula for the size of that fault, $(r - 1)(c - 1)/(2N)$ nats, depends on Wilks's theorem, which is not proved here. The explanation offered for the second hump in the curve of distances is a conjecture from the lengths of the lines.

Worked problems

These problems are posed for this article, on exact small cases and on the unit's data. The script tools/experiments/statistics/mutual-information.py checks every number.

Problem 1 (Shannon's noisy channel). A source sends 0 and 1 with equal probability. The channel delivers each symbol correctly with probability 0.99 and flips it with probability 0.01, independently of the symbol sent. Find the mutual information between the symbol sent, $X$, and the symbol received, $Y$.

Solution. $I(X; Y) = 0.9192$ bits per symbol. The received symbol is 1 with probability $0.5 \times 0.99 + 0.5 \times 0.01 = 0.5$, so $H(Y) = 1$ bit. Given either value of $X$, the received symbol is right with probability 0.99 and wrong with probability 0.01, so $H(Y \mid X) = H_{\mathrm{b}}(0.01) = -0.01\log_2 0.01 - 0.99\log_2 0.99 = 0.0664 + 0.0144 = 0.0808$ bits. By part 3, $I(X; Y) = 1 - 0.0808 = 0.9192$ bits. By the symmetry of the channel and the source, $H(X \mid Y)$ is also 0.0808 bits. This is the example with which Shannon (1948, Section 12) introduces the idea: at 1,000 symbols per second he finds an equivocation of 81 bits per second and a rate of transmission of 919 bits per second. He notes that subtracting the 1 percent of symbols in error, to get 990, would be wrong, because the receiver does not know which symbols are the wrong ones. If the channel flipped half the symbols, $H(Y \mid X)$ would be 1 bit and the mutual information 0, although half the symbols would still arrive correct.

Problem 2 (exclusive or). Let $X$ and $Y$ be independent fair bits and $Z$ their exclusive or. Compute $I(X; Y)$, $I(X; Z)$, $I(X; Y \mid Z)$ and $I(X; Y, Z)$, and verify the chain rule in both orders.

Solution. The four equally likely outcomes $(x, y, z)$ are $(0,0,0)$, $(0,1,1)$, $(1,0,1)$ and $(1,1,0)$. Each of the three variables is a fair bit with 1 bit of entropy. Any two of them take their four combinations with probability $\tfrac14$ each, so any two are independent: $I(X; Y) = I(X; Z) = 0$. Any two determine the third, so $H(X \mid Y, Z) = 0$ and $I(X; Y, Z) = H(X) - H(X \mid Y, Z) = 1$ bit. Then $I(X; Y \mid Z) = H(X \mid Z) - H(X \mid Y, Z) = 1 - 0 = 1$ bit, where $H(X \mid Z) = H(X) = 1$ by independence. The chain rule in one order reads $I(X; Y, Z) = I(X; Z) + I(X; Y \mid Z) = 0 + 1$, and in the other $I(X; Y) + I(X; Z \mid Y) = 0 + 1$. Each variable alone says nothing about $X$, and the pair says everything. No Markov chain is involved: $X \to Y \to Z$ would require $I(X; Z \mid Y) = 0$, and it is 1 bit.

Problem 3 (what the count adds). Using the table of occurrences of wheat above, compute $I(C; N_w \mid W)$, the information the count adds to presence, and verify the chain rule $I(C; N_w) = I(C; W) + I(C; N_w \mid W)$.

Solution. Since $W$ is a function of $N_w$, the pair $(W, N_w)$ carries the same information as $N_w$, and the chain rule reads $I(C; N_w) = I(C; W, N_w) = I(C; W) + I(C; N_w \mid W)$. The conditional term is an average over the two values of $W$. Among the 7,526 stories without the term the count is always 0, a constant, and contributes no information. Among the 243 stories with it, the table of counts against class is

Occurrences About grain Not about grain
1 42 13
2 62 3
3 or more 123 0

and its mutual information is 0.0995 bits. (Merging the counts from 3 upward changes nothing, as shown above.) A story where the term occurs once is about grain 76 percent of the time; twice, 95 percent; three times or more, always. Weighted by the share of stories that contain the term,

$$I(C; N_w \mid W) = \frac{243}{7{,}769} \times 0.0995 = 0.0031 \text{ bits},$$

and $0.1239 + 0.0031 = 0.1271$ bits (from unrounded values), which is $I(C; N_w)$. Within the stories that contain the term the count is worth a tenth of a bit. It is worth little overall because those stories are 3 percent of the collection.

Problem 4 (merging clusters). The seventeen documents of evaluating clusterings fall in three clusters holding, by class (x, o, ◇), $(5, 1, 0)$, $(1, 4, 1)$ and $(2, 0, 3)$ documents. Their mutual information with the classes is 0.3919 nats. Compute it after merging each pair of clusters, and compare the normalized values.

Solution. Each merged clustering is a function of the original, so each mutual information must be at most 0.3919 nats by the data processing inequality. Merging clusters 1 and 2 gives rows $(6, 5, 1)$ and $(2, 0, 3)$, with $I = 0.2089$ nats. Merging 1 and 3 gives $(7, 1, 3)$ and $(1, 4, 1)$, with $I = 0.1925$. Merging 2 and 3 gives $(5, 1, 0)$ and $(3, 4, 4)$, with $I = 0.1907$. All three are below 0.3919, as required, and all lose about half: each of the original clusters has a different majority class, so every merge mixes two majorities. Normalized mutual information divides by the average of the cluster and class entropies. The class entropy is 1.0551 nats throughout. The cluster entropy falls from 1.0951 nats to 0.6058, 0.6492 and 0.6492, so the divisor shrinks too, but by less than the numerator: NMI goes from 0.365 to 0.251, 0.226 and 0.224. Normalizing changes the scale of the comparison and here leaves its direction alone.

Problem 5 (mutual information and the likelihood ratio statistic). Show that for a table of counts with total $N$, $2N$ times the mutual information of the observed shares, in nats, equals $G = 2\sum O\ln(O/E)$. Evaluate it for the terms wheat and from with the class grain, and compare with the chi-square values 3,677.9 and 19.3 of feature selection.

Solution. Let $O_{ij}$ be the count in cell $(i, j)$, with row totals $R_i$ and column totals $C_j$. The observed shares are $O_{ij}/N$, $R_i/N$ and $C_j/N$, and the expected count under independence is $E_{ij} = R_i C_j/N$. Then

$$\frac{p(i, j)}{p(i)\,p(j)} = \frac{O_{ij}/N}{(R_i/N)(C_j/N)} = \frac{O_{ij}}{E_{ij}}, \qquad I = \sum_{i,j}\frac{O_{ij}}{N}\ln\frac{O_{ij}}{E_{ij}} = \frac{G}{2N}.$$

For wheat, $I = 0.12395$ bits is 0.08591 nats, and $G = 2 \times 7{,}769 \times 0.08591 = 1{,}334.9$. For from, $I = 0.00175$ bits is 0.001214 nats, and $G = 18.9$. For from the two statistics nearly agree, 18.9 against 19.3. That is the theorem of the last article on small differences. When every cell is close to its expected count, the divergence is close to half of $\chi^2(p, q)$, so $G = 2N\,D$ is close to Pearson's statistic $N\chi^2(p, q)$. For wheat the table is nowhere near independence: one cell holds 16.8 times its expected count. The condition of that theorem fails, and the statistics differ by a factor of 2.8. The unconditional bound of the same theorem, $D \le \chi^2(p, q)$, gives $G \le 2 \times 3{,}677.9$, which holds. Both statistics test the same hypothesis, and they agree where a test is in doubt, near independence.

What we have learned

Mutual information is the divergence of a joint distribution from the product of its marginals. It is zero exactly under independence, symmetric, equal to the drop in the entropy of either variable when the other is known, and at most the smaller of the two entropies. The chain rule splits the information in several variables into conditional terms. That is why the scores of features measured one at a time overstate what they hold together: on Reuters, corn adds 0.0460 bits to wheat, not its own 0.0650. The data processing inequality says that along a Markov chain, and so under any function, mutual information can only stay the same or fall. It stays the same exactly when what was discarded said nothing more, as with a sufficient statistic or the counts of wheat above 3. For independent variables, values computed from counts are biased upward, by about $(r - 1)(c - 1)/(2N)$ nats for a table of $r$ rows and $c$ columns with $N$ observations. An experiment on shuffled text put it at 0.0025 bits for that file. For strongly dependent variables and small samples the bias can run the other way.

The three articles so far have counted in bits and nats without saying what a bit buys. Perplexity and Source Coding gives the bit its meaning, as a unit of code length, and turns cross-entropy into the perplexity by which language models are compared.

References

  • Cover, T. M., and Thomas, J. A. (2006). Elements of Information Theory, 2nd edition. Wiley. record · 8 pages
  • MacKay, D. J. C. (2003). Information Theory, Inference, and Learning Algorithms. Cambridge University Press. Section 8.1, "More about entropy" (Figure 8.1), and Section 8.3, Exercise 8.9 (the data-processing theorem). record · 5 pages
  • Manning, C. D., Raghavan, P., and Schütze, H. (2008). Introduction to Information Retrieval. Cambridge University Press. Section 13.5, "Feature selection" (mutual information in Section 13.5.1), and Section 16.3, "Evaluation of clustering" (Figure 16.4). record · 102 pages
  • Paninski, L. (2003). Estimation of entropy and mutual information. Neural Computation, 15(6), 1191–1253. Section 3, "Previous Work" (the Miller–Madow bias correction; Section 3.3 on the direction of the bias), and equation 4.6. record · 2 pages
  • Shannon, C. E. (1948). A mathematical theory of communication. Bell System Technical Journal, 27(3), 379–423, and 27(4), 623–656. Section 12, "Equivocation and channel capacity", and Theorem 11. record · 6 pages