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$ — no uncertainty, no information needed. A uniform distribution over $k$ outcomes has $H = \log k$ — 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 — 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 — it forces $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 — it forces $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(f"Asymmetry — these minima are at different q values")