Information Theory for ML

Entropy, cross-entropy, KL divergence, mutual information

You are building a compression system for text messages. The word "the" appears in 7% of positions; the word "zymurgy" appears in 0.0001% of positions. If you give both words the same-length code, you waste bits every time you encode "the." Efficient encoding gives short codes to common words and long codes to rare ones. But how short and how long, exactly?

The answer falls out of a simple observation: the minimum number of bits needed to encode an event with probability $p$ is $-log_2(p)$. A word appearing with probability 0.07 needs $-log_2(0.07) \approx 3.8$ bits. A word at probability 0.000001 needs about 20 bits. If all events were equally probable, the average bits needed would be $log_2(N)$ where $N$ is the number of possible events. In general, the average bits over the whole distribution is the entropy: $H = -\sum p(x) \log p(x)$. Entropy measures how uncertain the distribution is — how many bits you need on average to describe a draw from it.

Now suppose your compression algorithm was designed for the wrong distribution. You built it assuming word frequencies $q$, but the true frequencies are $p$. The average bits you actually spend is $H(p, q) = -\sum p(x) \log q(x)$ — cross-entropy. The extra bits you waste compared to an optimal encoder is $KL(p | q) = H(p, q) - H(p)$. Since $H(p)$ is fixed by the true distribution, minimising cross-entropy is identical to minimising KL divergence — the extra waste from using the wrong distribution.

This is where ML enters. Your model produces a predicted distribution $\hat{y}$. The true label is a one-hot distribution $y$. Cross-entropy loss $= -\log(\hat{y}_{correct})$ measures how many bits your model`s encoding wastes relative to optimal. Minimising cross-entropy is fitting your model`s distribution to the true data distribution.

NOT this. Most people think cross-entropy is just a loss function that happens to work well. Cross-entropy is an information-theoretic quantity measuring encoding efficiency. When the model is perfectly calibrated, cross-entropy equals entropy — no wasted bits. The loss function framing hides why cross-entropy is the *right* choice, not merely a convenient one. It also hides the direction of KL: forward KL ($KL(p | q)$, used in training) forces the model to cover all modes of the true distribution. Reverse KL ($KL(q | p)$) is mode-seeking. A VAE's ELBO decomposes as $log p(x) = ext{ELBO} + KL(q(z|x)|p(z|x))$, so maximising the ELBO implicitly minimises the reverse KL between the approximate and true posterior — that's what lets the approximate posterior concentrate on a subset of the true posterior's modes rather than spreading across all of them. (The ELBO's explicit $q(z|x)$-to-prior term is a separate regulariser toward $p(z)$, not the mechanism behind this mode-seeking behaviour.) In VAEs this shows up as *posterior collapse* (an uninformative latent code and blurry, averaged reconstructions), not literally a single repeated output — that failure mode is GAN-style mode collapse instead. These produce qualitatively different learned distributions — mode-covering versus mode-seeking.

Key points

• Use cross-entropy loss for classification, not MSE. Cross-entropy penalises confident wrong predictions exponentially: predicting 0.99 probability for the wrong class means the correct class gets only 0.01, so cross-entropy charges $-\log(0.01) \approx 6.6$ bits of punishment. MSE on that same 0.01 is $(1 - 0.01)^2 = 0.9801$ — also large, so a small loss *value* is not why MSE loses here. The real reason is the gradient: MSE's gradient through a saturated sigmoid/softmax vanishes as the prediction nears 0 or 1, so a confidently wrong prediction barely gets corrected. Cross-entropy's gradient stays large exactly when the prediction is confidently wrong, so training keeps pushing. Any classifier trained with MSE on softmax outputs will be underpenalised for overconfident errors.
• The production trap: KL direction determines whether your model covers all modes or seeks just one. Maximum likelihood training minimises forward KL — the model must assign non-zero probability everywhere the data has density (mode-covering). Maximising a VAE's ELBO implicitly minimises the reverse KL between the approximate and true posterior ($KL(q(z|x)|p(z|x))$, which falls out of the $log p(x)= ext{ELBO}+KL(q(z|x)|p(z|x))$ identity, not the ELBO's explicit prior-matching term) — mode-seeking, so the approximate posterior can concentrate on a subset of the true posterior's modes and ignore the rest. In practice this shows up in VAEs as *posterior collapse*, not GAN-style output mode collapse: the latent code goes uninformative and the decoder falls back to blurry, averaged reconstructions rather than literally one repeated output. If your VAE produces near-identical, averaged-looking outputs regardless of the latent code, posterior collapse — not "reverse KL mode collapse" — is the diagnosis to reach for.
• The diagnostic: use mutual information $I(X;Y) = H(X) - H(X|Y)$ for feature selection, not Pearson correlation. Correlation only detects linear relationships. A feature where $Y = X^2$ has zero correlation with $X$ but high mutual information — the feature is perfectly predictive but nonlinearly so. Any feature with $I(X;Y) = 0$ is truly independent of the label, but the reverse direction is not free: zero covariance does not generally imply zero mutual information — that guarantee only holds when X and Y are jointly Gaussian. For a general (non-Gaussian) joint distribution, Cov(X,Y) = 0 can still coexist with I(X;Y) > 0, exactly as in the $Y=X^2$ example above. Estimators like MINE make this tractable even for high-dimensional continuous features.
• Functions of a random variable can only lose information, never gain it — the data processing inequality. If $Y = f(X)$ for any function $f$, then $H(Y) \le H(X)$: coarsening, discretising, or summarising a variable can hold or destroy information but never create it. This is why grouping a six-sided die roll into 'even or odd' has lower entropy than the die itself — the coarsened variable is a function of the original, so it cannot carry more uncertainty than its input.

Recap

• Bits to encode probability $p$ = $-\log_2(p)$; entropy $H=-\sum p(x)\log p(x)$ = average bits / uncertainty.
• Cross-entropy $H(p,q)=-\sum p\log q$ = bits spent when you encode true $p$ with wrong $q$.
• KL = the waste: $KL(p\|q)=H(p,q)-H(p)$. Minimising cross-entropy = minimising KL to the true distribution.
• Cross-entropy loss $=-\log(\hat{y}_{correct})$ — an encoding-efficiency measure, not an arbitrary loss.
• Use cross-entropy, not MSE, for classification: confident wrong 0.99 → $-\log(0.01)\approx 6.6$ bits; MSE gives $0.9801$, also large — the real reason CE wins is that MSE's gradient vanishes under sigmoid/softmax saturation, while CE's does not.
• KL direction matters: forward KL (MLE) is mode-covering; reverse KL (the implicit KL(q(z|x)‖p(z|x)) a VAE's ELBO minimises) is mode-seeking — in VAEs this shows up as posterior collapse (uninformative latents, blurry output), not GAN-style mode collapse.
• Mutual information $I(X;Y)=H(X)-H(X|Y)$ detects nonlinear dependence correlation misses; $I=0$ ⟹ truly independent. Cov=0 ⟹ $I=0$ only for jointly Gaussian variables.
• Data processing inequality: $Y=f(X)$ ⟹ $H(Y) \le H(X)$ — a function/coarsening of a variable can only lose information, never gain it.

Check your understanding