Week 11: Information Theory for ML

Entropy#

Shannon entropy measures the uncertainty (or information content) of a distribution. For a discrete distribution $p$ over outcomes $\{x_1, \ldots, x_k\}$:

Using $\log_2$ gives entropy in bits; using natural log gives nats. In ML, natural log is standard (connection to e-based calculus).

Interpretation: $H(p)$ is the minimum average number of bits (or nats) needed to encode a symbol drawn from $p$. A deterministic distribution ($p(x_1) = 1$, all others 0) has $H = 0$, meaning no uncertainty and no information needed. A uniform distribution over $k$ outcomes has $H = \log k$, the maximum uncertainty. Entropy is always $\ge 0$.

Worked example: biased coin. $p = 0.7$ for heads, $0.3$ for tails (nats):

A fair coin has $H = \ln 2 \approx 0.693$ nats, showing more uncertainty. A deterministic coin ($p = 1$) has $H = 0$.

Differential entropy is the continuous analogue (for PDFs), but it lacks some nice properties of discrete entropy (e.g., it can be negative). We focus on the discrete case; KL divergence handles continuous distributions fine.

Cross-entropy and KL divergence#

Cross-entropy $H(p, q)$ measures the average number of bits needed to encode samples from $p$ using a code optimised for $q$:

KLKullback–Leibler divergence divergence (relative entropy) measures how much extra information is needed when using $q$ instead of $p$:

KL is not a distance metric: it is asymmetric ($D_{\mathrm{KL}}(p \parallel q) \ne D_{\mathrm{KL}}(q \parallel p)$ in general) and does not satisfy the triangle inequality. But it is always $\ge 0$, with equality iff $p = q$.

Gibbs inequality (proof sketch for KL $\ge 0$):

Using the inequality $\ln t \le t - 1$ for $t > 0$ (with equality only at $t = 1$):

Thus $-D_{\mathrm{KL}} \le 0$, so $D_{\mathrm{KL}} \ge 0$. The inequality is strict unless $p = q$ everywhere.

KL and MLE#

There is a deep equivalence: maximising likelihood is minimising KL divergence to the empirical distribution.

Let $\hat p$ be the empirical distribution of the data (puts mass $1/n$ at each observed $x_i$). The KL from $\hat p$ to the model $p_\theta$ is:

$H(\hat p)$ does not depend on $\theta$, so:

Training a model by MLE is equivalent to finding the model distribution that is "closest" (in forward KL sense) to the empirical data distribution. This is why the negative log-likelihood is called the cross-entropy loss in classification: it is the cross-entropy between the one-hot label distribution and the model's predicted distribution.

Forward vs reverse KL#

Because KL is asymmetric, the direction matters for optimisation behaviour.

Forward KL: $D_{\mathrm{KL}}(p_{\text{data}} \parallel q_\theta)$

This penalises $q_\theta$ heavily where $p_{\text{data}}$ has mass but $q_\theta$ has little, forcing $q_\theta$ to cover all regions where data appear. This is mode-covering: the model spreads probability mass across all modes of the data, even if it must put some mass in low-density regions. MLE training uses forward KL implicitly.

Reverse KL: $D_{\mathrm{KL}}(q_\theta \parallel p_{\text{data}})$

This penalises $q_\theta$ heavily where $q_\theta$ has mass but $p_{\text{data}}$ has little, forcing $q_\theta$ to avoid regions with no data. This is mode-seeking: the model concentrates on a subset of modes, ignoring others. Variational inference (used in VAEs) minimises reverse KL, which is why VAEs can produce sharp but limited-diversity samples.

Cartoon illustration. Suppose $p_{\text{data}}$ is a mixture of two well-separated Gaussians. Forward KL yields a $q$ that covers both bumps (even if it puts mass in the gap). Reverse KL yields a $q$ that locks onto one bump and ignores the other.

Link to generative models#

This week sets up the information-theoretic vocabulary you need to read about:

• VAEs: the ELBOEvidence Lower Bound is $\mathbb{E}_q[\log p(x \mid z)] - D_{\mathrm{KL}}(q(z \mid x) \parallel p(z))$, a reconstruction term plus a KL regulariser.
• Diffusion models: the training objective is a weighted sum of denoising score-matching terms, which can be derived from a variational bound on the KL between data and model distributions.
• RL exploration: entropy bonuses ($H(\pi)$) encourage policies to remain stochastic, preventing premature convergence.

You do not need to derive these now. This course gives you the vocabulary so the derivations are readable when you encounter them.

Knowledge check#

Browser lab#

Compute KL divergence between categorical distributions over a grid of $q$ values vs a fixed $p$, and show the asymmetry.

import numpy as np
import matplotlib.pyplot as plt

p = np.array([0.7, 0.2, 0.1])

def kl(p, q):
    """KL(p || q) in nats. Assumes q > 0 where p > 0."""
    mask = p > 0
    return np.sum(p[mask] * np.log(p[mask] / q[mask]))

qs = []
kl_forward = []
kl_reverse = []

for a in np.linspace(0.05, 0.9, 30):
    for b in np.linspace(0.05, 0.9, 30):
        c = 1 - a - b
        if c <= 0:
            continue
        q = np.array([a, b, c])
        qs.append(q)
        kl_forward.append(kl(p, q))
        kl_reverse.append(kl(q, p))

qs = np.array(qs)
kl_forward = np.array(kl_forward)
kl_reverse = np.array(kl_reverse)

fig, axes = plt.subplots(1, 3, figsize=(14, 4.5))

sc = axes[0].scatter(qs[:, 0], qs[:, 1], c=kl_forward, cmap="Reds", s=20)
axes[0].scatter(p[0], p[1], color="black", s=100, marker="*", label="p")
axes[0].set_xlabel("q₁"); axes[0].set_ylabel("q₂")
axes[0].set_title("Forward KL(p || q)")
plt.colorbar(sc, ax=axes[0], label="nats")

sc = axes[1].scatter(qs[:, 0], qs[:, 1], c=kl_reverse, cmap="Blues", s=20)
axes[1].scatter(p[0], p[1], color="black", s=100, marker="*", label="p")
axes[1].set_xlabel("q₁"); axes[1].set_ylabel("q₂")
axes[1].set_title("Reverse KL(q || p)")
plt.colorbar(sc, ax=axes[1], label="nats")

axes[2].scatter(kl_forward, kl_reverse, c=qs[:, 0], s=10, alpha=0.7)
axes[2].set_xlabel("KL(p || q)"); axes[2].set_ylabel("KL(q || p)")
axes[2].set_title("KL Asymmetry")
axes[2].plot([0, max(kl_forward)], [0, max(kl_forward)], "k--", alpha=0.3)

plt.tight_layout()
plt.show()

idx_min_fwd = np.argmin(kl_forward)
idx_min_rev = np.argmin(kl_reverse)
print(f"p = {p}")
print(f"min KL(p||q) at q = {np.round(qs[idx_min_fwd], 3)}, value={kl_forward[idx_min_fwd]:.4f}")
print(f"min KL(q||p) at q = {np.round(qs[idx_min_rev], 3)}, value={kl_reverse[idx_min_rev]:.4f}")
print("Both directions bottom out at q ≈ p — the asymmetry is in how steeply each surface penalises moving mass, not in where the minimum sits.")

print("Notice: both surfaces bottom out at the same q ≈ [0.695, 0.197, 0.109] — the asymmetry is in how steeply each one punishes a mismatch.")

Key takeaways#

• Shannon entropy measures uncertainty: zero for a deterministic distribution, maximal at $\log k$ for the uniform distribution over $k$ outcomes.
• Cross-entropy is the cost of encoding samples from one distribution with a code built for another; KL divergence is the excess cost, $D_{\mathrm{KL}}(p \parallel q) = H(p, q) - H(p)$.
• KL is non-negative and zero only when the distributions match, but it is asymmetric and not a metric.
• Maximum likelihood is exactly minimising forward KL from the empirical distribution to the model, which is why classification uses the cross-entropy loss.
• Forward KL is mode-covering; reverse KL is mode-seeking. That asymmetry is why VAEs produce sharp but limited-diversity samples.
• The ELBO, diffusion training objectives, and reinforcement-learning entropy bonuses are all built from this vocabulary.

Further reading#

• Thomas M. Cover & Joy A. Thomas, Elements of Information Theory (2nd ed., Wiley, 2006): Chapter 2 is the canonical treatment of entropy, cross-entropy, and KL.
• David J. C. MacKay, Information Theory, Inference, and Learning Algorithms (Cambridge University Press, 2003): free online; links information theory directly to inference.
• Christopher M. Bishop, Pattern Recognition and Machine Learning (Springer, 2006): §1.6 gives the ML-facing summary of these quantities.