Mutual information

How much does one fact tell you about another? Return to the 100 emails from the last section. Before you read the subject, your uncertainty about spam is one bit. After you learn whether the subject says free, 0.722 bits remain on average.

The word therefore removes 0.278 bits of uncertainty, which is the mutual information between the two facts and the answer to the question. !Two circles of area 1 bit each, overlapping by 0.278 bits. The overlap is the mutual information: the part of each variable's uncertainty that the other shares. The two crescents are what remains, 0.722 bits each, and the union is the joint entropy, 1.722 bits. When the circles separate the overlap is zero and the variables are independent; when they coincide the overlap is a whole circle and one variable determines the other. Status: synthetic.

What one variable tells you. Write A for the spam label and B for the free flag, and H(A) for the entropy of A. The mutual information I(A;B) is the reduction in uncertainty about one variable when another is learned. The semicolon separates the two variables; a comma inside the brackets, as in $H(A,B)$, would mean the pair. In symbols:

$$I(A;B)=H(A)-H(A\mid B)$$

The equation says that you take the uncertainty before and subtract what is left after. The same number also equals $H(B)-H(B\mid A)$, because the joint entropy does not depend on the order of the two variables [S:36:151]. Mutual information is symmetric as a result: $I(A;B)=I(B;A)$ [S:36:151]. Some writers call it the information gain, because it measures what observing B adds to what you already know about A.

The shared part. A useful rewrite uses only the three entropies: $I(A;B)=H(A)+H(B)-H(A,B)$. The sum of the two marginal entropies counts the shared part twice, so subtracting the joint removes the double count. What remains is the part of the uncertainty that the two variables have in common. This is also why mutual information can never exceed either marginal entropy.

The range follows from the definition. The value cannot be negative, and it cannot exceed the smaller of $H(A)$ and $H(B)$. Zero means the variables are independent, so learning one leaves the probability of the other unchanged. The maximum means that one variable determines the other. A value in between means that the second variable carries part of the first.

Worked example. In the email table, each fact alone is a fair coin, so both marginal entropies are 1 bit. The joint entropy is 1.722 bits.

The three-entropy formula gives $1+1-1.722=0.278$ bits. The direct formula gives $1-0.722=0.278$ bits. The two routes agree, as they must.

The shared part has another reading. If you pretended the two facts were independent, you would use the product of the two marginal distributions as your model. The KL divergence between the true joint table and that product measures the extra bits that mistake costs, and it is 0.278 bits. Mutual information is the cost of that pretence [S:60:173]. Independence is the model that assumes there is nothing to learn, and the divergence measures how wrong that assumption is.

The identity is exact, not an approximation. The product model assigns probability $p(a)p(b)$ to each cell. The log ratio inside the divergence becomes $\log [p(a,b)/(p(a)p(b))]$, and its average over the table is the mutual information. The divergence and the entropy formulas are two views of one quantity.

The measure does not assume a straight-line relation. A curved dependence still registers, and so does a dependence that appears in only part of the table. That generality is why the measure suits a table of words and labels, where the relation is rarely a line.

Zero and one. Two extreme cases fix the scale. If B is a copy of A, then learning B removes all uncertainty about A, so the mutual information equals the entropy of A. If B is a fair coin flipped separately, learning B changes nothing, so the mutual information is zero. A word with a value of zero tells the filter nothing, and a word whose mutual information approaches one bit tells it almost everything.

The units are bits per email. If the filter reads one email, the mutual information says how many bits that email's subject saves about the label on average. It is an average over emails, not a promise about the next one. A single subject line can be more informative or less.

Mutual information also measures what a channel carries. A channel is a link that carries a bit from a sender to a receiver. If A is the bit you send and B is the bit you receive, the value is the number of bits the receiver gains per use of the channel. The last section of this chapter turns that sentence into the definition of capacity.

The measure has limits. It notices any dependence, straight or curved, but it does not say which variable drives which. A common cause can make two variables informative about each other with no arrow between them. It also needs the joint distribution, so the table problem from the last section returns. The number is exact only when the table is exact.

The formal statement. Take two variables on finite alphabets:

$$I(A;B)=\sum _{a,b}p(a,b){\log }_2\frac{p(a,b)}{p(a)p(b)}.$$

The equation says that each cell contributes its probability times the log ratio of its true probability to the probability it would have if the two variables were independent. That ratio is the whole idea: mutual information measures how far the joint table sits from the product of its marginal distributions [S:36:151].

The derivation. Expand the log ratio into three terms. The first two are the information contents of A and B, and the third subtracts the information content of the pair. Averaging over the joint table gives

$$I(A;B)=H(A)+H(B)-H(A,B).$$

The equation says that the two marginal entropies count the shared part twice, so subtracting the joint removes the double count. Rearranging the chain rule gives the form L1 used, $I=H(A)-H(A\mid B)$. Symmetry is visible in the first definition, because swapping A and B leaves the ratio unchanged. Non-negativity follows from Gibbs' inequality applied to the joint and the product.

The edge case. The identity is exact for the true joint table and misleading for an estimated one. A plug-in estimate from a finite sample has a positive bias that grows with the number of cells, so a large table can show dependence that is not there [S:34:163]. The population quantity is never negative, but its estimate is not the quantity. This matters in the email example: a hundred emails fill four cells comfortably, while a table of word pairs has far more cells than samples and is mostly zeros.

A second edge case is invariance. Mutual information and discrete entropy are both invariant under an invertible relabelling of either variable, because a bijection only permutes the probabilities. Entropy is unchanged by any non-singular map and can only fall under a non-invertible one [S:156:15]. It is differential entropy that changes under a smooth reparameterisation, by the log of the Jacobian determinant, and that is why only the divergence is reparameterisation-invariant [S:62:270]. L1's phrase "bits per observation" therefore describes a quantity tied to the table, not to the names of its rows.

What L1 hid, and why that was safe. L1 computed the number from the four cells and read it as information gained. The definition also requires the marginal distributions, and the estimate of those marginals is where the bias enters. L1 could ignore this because its table was given exactly and was small. The section asked what one variable tells you, not how to measure that from a sample.

Where the analogy breaks. The Venn diagram of two overlapping circles suggests that mutual information is the literal intersection of two sets of bits. For two variables the picture is a useful bookkeeping device. For three variables the diagram fails: the three-way mutual information $I(X;Y;Z)=H(Z)-H(Z\mid X)-H(Z\mid Y)+H(Z\mid X,Y)$ can be negative (for independent bits X and Y and $Z=X\oplus Y$ it equals $-1$), so no non-negative area can represent it [S:62:278]. MacKay's version of the warning is that expressions such as $I(X;Y;Z)$ are illegal and that the Venn diagram is a misleading representation [S:36:151] [S:36:153]. The diagram is a mnemonic, not a model of information as a substance.

Original sources. Shannon calls the conditional entropy of the sent signal given the received one the equivocation, and writes the rate as the source entropy minus that term [S:156:20]. MacKay states the modern definition as a reduction in uncertainty and proves symmetry and non-negativity [S:36:151]. Murphy defines it as the divergence between the joint and the product of the marginal distributions, which is the form this layer uses [S:62:272].

An open question. How do you estimate mutual information in high dimensions? The joint distribution is intractable, so the field replaces it with variational bounds [S:62:278]. The InfoNCE bound is a lower bound that cannot exceed the logarithm of the batch size, so a large batch is needed when the true value is large [S:62:280]. An estimator with a tight bound at a fixed sample size, checked against a problem with a known value, would settle which bound to use for a given budget.

A frontier result. Contrastive learning trains a representation with InfoNCE, which asks a model to tell a jointly sampled pair from independently sampled pairs [S:62:279]. The loss is a lower bound on mutual information, so the training objective has a reading in the units of this chapter. That reading also explains its limit: the bound saturates at the log of the batch size. The estimate is therefore a diagnostic of the representation, not a certificate of its content.

A consequence you will use. The data-processing inequality says that no function of the received data carries more information about the source than the data itself [S:62:273]. That statement rules out a cleaning step that creates information, and it explains why post-processing alone cannot improve a representation.

What to read next. Read MacKay 8.1 and 8.2 for the definitions and the diagram warning [S:36:151]. Read Murphy 5.3 for the divergence form and the variational bounds [S:62:272]. Read Polyanskiy Chapter 30 for a different use of the same quantity: mutual information as a tool for proving lower bounds on estimation error [S:34:610]. The three together separate the definition, the estimator and the proof technique.