Joint, conditional and relative entropy

A spam filter reads two facts about each of 100 emails: whether the subject contains the word free, and whether the reader marked the email as spam. Forty emails have both marks, ten contain free and are not spam, ten are spam without free, and forty have neither. The table is constructed for this section and is small enough to check by hand.

!Two ways to cut the same joint entropy. On the left the spam label costs 1 bit and the free flag adds 0.722 bits once the label is known; on the right the same two terms arrive in the other order. Both stacks reach 1.722 bits, which is the chain rule drawn as two bars. Either fact alone is a fair coin, and knowing the other removes 0.278 bits from that one bit. Status: synthetic.

Each row and each column adds to fifty, so each fact alone is a fair coin with one bit of uncertainty. The pair is not a fair coin: two cells hold forty emails each, so the pair is more predictable than two separate facts. The table's four cells carry less uncertainty than the two marginal entropies added together.

How do entropies combine? Add the uncertainty of one fact to the uncertainty that remains about the second once the first is known. This is the chain rule, and it answers this section's question.

Three entropies. In the email table the pair has joint entropy 1.722 bits. Each fact alone has marginal entropy 1 bit, and what is left about the spam label once the free flag is known is the conditional entropy, 0.722 bits. For two variables A and B, the joint entropy is the entropy of the pair, H(A,B).

The marginal entropy is the entropy of one variable on its own, $H(A)$. The conditional entropy is the average uncertainty left about one variable after the other is known, $H(A\mid B)$.

The chain rule for entropy connects them. For those two variables:

$$H(A,B)=H(A)+H(B\mid A)$$

The equation says that the uncertainty of a pair is the uncertainty of the first variable plus what the second adds once the first is known. Read the conditional term as the surprise that remains about B after A is fixed.

Conditioning. The conditional entropy has a plain reading. It is the average surprise about one variable given a particular value of the other, averaged over all the values the other can take [S:60:172]. It answers the question a filter asks when it already knows one fact and wants to know how much the second can still tell it.

When the two variables are independent, so that learning one leaves the probability of the other unchanged, the second adds nothing and the chain rule collapses to $H(A,B)=H(A)+H(B)$ [S:36:150]. The email table fails that test, and the size of the failure is the subject of the next section.

Worked example. The pair has four cells with probabilities 0.4, 0.1, 0.1 and 0.4. Its joint entropy is the sum $-(0.4{\log }_{2}0.4+0.1{\log }_{2}0.1+0.1{\log }_{2}0.1+0.4{\log }_{2}0.4)$ bits.

The chain rule in the other order gives $H(A\mid B)=H(A,B)-H(B)=1.722-1=0.722$ bits: subtract the entropy of the variable you condition on, not the one you are asking about. Knowing whether the email says free removes 0.278 bits of the one bit you had.

Relative entropy. Suppose you build a code for the wrong distribution. The KL divergence D_KL, also called relative entropy, measures the average extra surprise that mistake costs. The double bar separates the two distributions p and q, which range over the same outcomes:

$$D_{\mathrm{KL}}(p\Vert q)=\sum _{x}p(x){\log }_2\frac{p(x)}{q(x)}$$

The equation says that each outcome contributes its probability times the log ratio of the two probabilities. If q gives each of the four cells the same probability, the divergence from the email distribution is $2\times 0.4\times {\log }_2(0.4/0.25)+2\times 0.1\times {\log }_2(0.1/0.25)=0.278$ bits. A code built for the uniform table spends 0.278 extra bits per email.

The coding reading is exact for the ideal code whose lengths are ${\log }_2(1/q(x))$. For any actual prefix code with whole-number lengths the identity reads $L=H+D_{\mathrm{KL}}(p\Vert q_l)$ with $q_l(x)=2^{-l(x)}$, so rounding adds a term that the divergence from q does not contain. For the ideal code, the divergence is the average number of additional bits needed to encode data from p when you use a code built for q [S:36:110]. The 0.278 bits quoted here is that ideal-length value.

Swap the two distributions and the number changes: the divergence from the uniform table to the email table is 0.322 bits. The two values differ, so the quantity is not a distance.

The divergence is zero if and only if $p(x)=q(x)$ for every outcome with $p(x)>0$, and positive otherwise. It is not symmetric: swapping p and q can change the value, as the two numbers above show [S:36:46]. It can also be infinite when q gives zero probability to an outcome that p allows [S:75:467].

The chain rule has a cost. It needs the joint distribution, and that table grows fast: ten binary variables need 1024 cells, and thirty need more than a billion. The divergence adds a second cost, because it is asymmetric and can be infinite when one distribution forbids an outcome the other allows. Both facts matter when you estimate these numbers from data, because a table you fill from a finite sample is mostly empty.

The formal statement. Let A and B be random variables on finite alphabets with a joint distribution p(a,b). The joint entropy is the entropy of the pair. The marginal entropy is the entropy of one variable alone. The conditional entropy is

$$H(A\mid B)=\sum _{a,b}p(a,b){\log }_2\frac{1}{p(a\mid b)}.$$

The equation says that you average the surprise about A over the joint table, using the conditional probability of A in each cell. The chain rule is

$$H(A,B)=H(A)+H(B\mid A).$$

The equation says that the uncertainty of the pair is the uncertainty of A plus what B adds once A is fixed [S:36:151].

The derivation. The product rule gives $p(a,b)=p(a)p(b\mid a)$. Take the base-two logarithm of the reciprocal on both sides. The information content of a cell becomes the information content of a plus the conditional information content of b given a. Take the expectation over the joint table. The left side is the joint entropy, and the right side splits into the marginal entropy plus the conditional entropy. No approximation enters, and the same argument gives the mirror form with the roles swapped [S:36:150].

The edge case. Conditioning lowers entropy on average, but it can raise it for a particular value. The conditional entropy of A given one specific value of B may exceed the entropy of A, while the average over B is lower [S:36:152]. A rare value of B can make A less predictable than it looked before you saw that value. L1's sentence about the average hides exactly this case.

Relative entropy. For two distributions over the same outcomes,

$$D_{\mathrm{KL}}(p\Vert q)=\sum _{x}p(x){\log }_2\frac{p(x)}{q(x)}.$$

The equation says that each outcome contributes its probability times the log ratio of the two probabilities. The quantity is non-negative by Gibbs' inequality, and it is zero if and only if $p(x)=q(x)$ for every $x$ with $p(x)>0$ [S:58:75]. It is infinite when q forbids an outcome that p allows, and it is not symmetric [S:36:46].

What L1 hid, and why that was safe. L1 wrote the conditional entropy as a single number and read it as "what remains". The definition is an average of a different entropy for each value of the conditioning variable, so the single number is a weighted mean of several curves. L1 also treated the KL divergence as an exact extra cost. That reading is exact only when the code uses ideal, non-integer lengths; an integer-length code adds the rounding from Section 16.4. The simplification was safe because the section compared distributions, not code implementations.

Where the analogy breaks. The picture of relative entropy as a distance fails twice. A distance is symmetric and obeys the triangle inequality, and this quantity does neither. The coding reading is the reliable one: it measures wasted bits, and wasted bits have a direction.

Original sources. Shannon defines joint and conditional entropy and proves that the uncertainty of a pair is at most the sum of the individual uncertainties [S:156:12]. Kullback and Leibler give the directed divergence its name in 1951, and Bishop records the attribution together with the asymmetry [S:58:75]. MacKay states the chain rule and the coding reading: a code built for the wrong distribution exceeds the entropy by the divergence [S:36:110].

An open question. How do you estimate a divergence from finite data? The plug-in estimate is biased, and for a fixed alphabet the mean bias falls as the number of cells over twice the sample size [S:34:163]. When the alphabet $k$ grows with the sample $n$, the plug-in bias is of order $k/n$; polynomial-approximation de-biasing reduces it to order $k/(n\log k)$, and consistent entropy estimation is possible if and only if $n\gg k/\log k$, with minimax quadratic risk of order $(k/(n\log k){)}^2+{\log }^{2}k/n$ [S:34:609]. An estimator with a proved rate that matches the lower bound on alphabets it was not tuned on would settle which correction to trust in practice.

A frontier result. Variational inference maximises a lower bound on the log evidence, and the gap is exactly a KL divergence [S:74:347]. So every variational autoencoder optimises the quantity this section defines. The direction of the divergence matters: the bound uses the divergence from the approximation to the posterior, not the other way round, and the two directions penalise different errors [S:74:348].

The general form. Repeated conditioning extends the chain rule to any number of variables, so the entropy of a sequence is the sum of the conditional entropies of each symbol given the ones before it [S:36:151]. That sum is the bridge to models of text, where each conditional term becomes a prediction problem.

What to read next. Read Bishop 1.6.1 for the definition and the convexity proof [S:58:75]. Read MacKay 8.1 for the chain rule in coding language [S:36:150]. Read Polyanskiy 7.9 and 29.4 for the estimation bias and its minimax rate [S:34:163]. The last two turn the definition into a number you can defend.