Information Theory: Quick recap

01 Surprise, bits and entropy

The surprisal of an outcome with probability $p$ is $-\log p$ : 0 for a sure outcome, 1 bit for a fair coin, 1 more bit every time $p$ is halved.
A logarithm makes surprisals of independent events add, while their probabilities multiply.
Entropy is the average surprisal: $H(X) = -\sum_x p(x)\log p(x) = \mathbb{E}[-\log p(X)]$ , with the convention $0\log 0 = 0$ .
Entropy is the average number of yes/no questions of a good question strategy; the best tree needs between $H$ and $H + 1$ questions.
$\log_2$ gives bits and $\ln$ gives nats; $1$ nat $= 1.443$ bits, $1$ bit $= 0.693$ nats. NumPy and PyTorch use nats.
$0 \le H(X) \le \log K$ for $K$ outcomes: $H = 0$ only for a constant, $H = \log K$ only for the uniform distribution.
Entropy depends only on the probabilities, not on the values or labels of the outcomes.
The binary entropy $H_b(p)$ is 0 at $p \in \{0, 1\}$ , 1 bit at $p = \frac12$ , symmetric, and $H_b(0.1) = 0.469$ bits.

02 Joint and conditional entropy

The joint entropy $H(X, Y) = \mathbb{E}[-\log p(X, Y)]$ is the entropy of the pair seen as one variable.
$H(Y \mid X) = \sum_x p(x)\, H(Y \mid X = x)$ is one number: the average of the row entropies, weighted by $p(x)$ . It is 0 exactly when $Y$ is a function of $X$ .
Chain rule: $H(X, Y) = H(X) + H(Y \mid X) = H(Y) + H(X \mid Y)$ ; for $n$ variables, $H(X_1, \dots, X_n) = \sum_i H(X_i \mid X_1, \dots, X_{i-1})$ .
Conditioning reduces entropy on average: $H(Y \mid X) \le H(Y)$ , with equality exactly for independent $X$ and $Y$ .
One value can raise the uncertainty: $H(Y \mid X = x) > H(Y)$ is possible (weather: 1.5 > 1.299 bits).
$\max(H(X), H(Y)) \le H(X, Y) \le H(X) + H(Y)$ , and $H(g(X)) \le H(X)$ for any function $g$ .
Conditional entropy is not symmetric: $H(Y \mid X) - H(X \mid Y) = H(Y) - H(X)$ .
$I(X;Y) = H(Y) - H(Y \mid X) = H(X) - H(X \mid Y) \ge 0$ is the shared part in the two-bar diagram $H(X, Y) = H(X \mid Y) + I(X;Y) + H(Y \mid X)$ .

03 Jensen and KL divergence

Jensen's inequality: for convex $f$ , $f(\mathbb{E}[X]) \le \mathbb{E}[f(X)]$ ; for concave $f$ the inequality is reversed. For strictly convex or concave $f$ , equality holds only when $X$ is constant.
For the concave log, $\mathbb{E}[\log X] \le \log \mathbb{E}[X]$ ; the gap is about $\operatorname{Var}(X)/(2\,\mathbb{E}[X]^2)$ when the spread is small.
The KL divergence $\mathrm{KL}(p\,\|\,q) = \sum_x p(x) \log \frac{p(x)}{q(x)}$ is the average extra surprise, under the truth $p$ , of predicting with the model $q$ .
Gibbs' inequality: $\mathrm{KL}(p\,\|\,q) \ge 0$ , with equality if and only if $p = q$ . The proof is Jensen applied to $\log \frac{q(X)}{p(X)}$ .
$\mathrm{KL}(p\,\|\,q) = \infty$ if $q(x) = 0$ for an outcome with $p(x) > 0$ ; outcomes with $p(x) = 0$ cost nothing.
$\mathrm{KL}(p\,\|\,u) = \log K - H(p)$ for the uniform $u$ on $K$ values, so $H(p) \le \log K$ ; and $H(Y) - H(Y \mid X)$ $= \mathrm{KL}(p(x,y)\,\|\,p(x)p(y)) \ge 0$ .
KL is not a metric: it is not symmetric (fair coin vs $(0.8, 0.2)$ : $0.223$ vs $0.193$ nats) and it breaks the triangle inequality.

04 Cross-entropy as a loss

Cross-entropy $H(p, q) = -\sum_x p(x) \log q(x)$ is the average surprise of the model $q$ on data from $p$ ; the data distribution is the first argument.
$H(p, q) = H(p) + \mathrm{KL}(p\,\|\,q) \ge H(p)$ , with equality only for $q = p$ : log-loss is a strictly proper scoring rule.
Minimizing the average log-loss on data is maximum likelihood, and it minimizes the forward KL $\mathrm{KL}(\hat p\,\|\,q_\theta)$ from the empirical distribution to the model.
With logits $z$ and $q = \operatorname{softmax}(z)$ , the loss is $\operatorname{LSE}(z) - z_c$ and its gradient is $q - y$ (prediction minus target); for soft targets $t$ it is $q - t$ .
A classifier's expected loss is $H(Y \mid X)$ plus an average KL; only the KL part can be trained away, so noisy labels set a floor above 0.
With soft targets (label smoothing, distillation) the loss is $H(t) + \mathrm{KL}(t\,\|\,q)$ , so the minimum loss is $H(t)$ , not 0.
Perplexity $= e^{\bar\ell}$ (the effective number of choices), bits per token $= \bar\ell/\ln 2$ , bits per dimension $= \text{NLL}/(D \ln 2)$ : one quantity in different units.

05 Compression is prediction

A prefix-free code decodes instantly; its codewords are the leaves of a binary tree.
Kraft inequality: binary prefix codes (and all uniquely decodable codes) satisfy $\sum_i 2^{-l_i} \le 1$ , and any lengths that satisfy it have a prefix code.
Source coding theorem: $H(X) \le L^* < H(X) + 1$ ; blocks of $n$ symbols get within $1/n$ bit of $H(X)$ per symbol.
Huffman's algorithm (merge the two least likely nodes) gives an optimal symbol code; ties change the tree but not $L$ .
Arithmetic coding codes a whole sequence with any next-symbol model in fewer than $-\log_2 q(x_{1:n}) + 2$ bits.
Coding data from $p$ with a model $q$ costs $H(p, q) = H(p) + \mathrm{KL}(p\,\|\,q)$ : the wrong model costs exactly the KL divergence.
Compression = prediction: a language model's loss in bits is the size of the text after arithmetic coding with that model.

06 Differential entropy and KL fits

The differential entropy of a density is $h(X) = -\int p\log p = \mathbb{E}[-\log p(X)]$ , in nats with the natural log.
Quantizing into bins of width $\Delta$ gives $H(X_\Delta) \approx h(X) + \log(1/\Delta)$ : the discrete entropy goes to infinity, and $h$ is the finite remainder.
$h$ can be negative (a density can exceed 1) and depends on the units: $h(AX + b) = h(X) + \log|\det A|$ .
A Gaussian has $h = \frac12\log\big((2\pi e)^d\det\Sigma\big)$ , a log-volume; in 1-D it is negative for $\sigma < 0.242$ .
KL between densities is $\ge 0$ and does not change under invertible maps of the variable; the same holds for mutual information.
Among densities with a given covariance the Gaussian has the largest $h$ , and the gap $h(g) - h(p)$ equals $\mathrm{KL}(p\,\|\,g)$ .
$\mathrm{KL}(\mathcal{N}(\mu_0, \sigma_0^2)\,\|\,\mathcal{N}(\mu_1, \sigma_1^2)) = \log\frac{\sigma_1}{\sigma_0} + \frac{\sigma_0^2 + (\mu_0 - \mu_1)^2}{2\sigma_1^2} - \frac12$ .
Forward KL is mode covering (for Gaussians: moment matching, maximum likelihood); reverse KL is mode seeking, needs $p$ only up to a constant, and gives too narrow mean-field fits ( $s_i^2 = 1/(\Sigma^{-1})_{ii}$ ).

07 Mutual information

Mutual information $I(X;Y) = H(X) - H(X \mid Y) = H(X) + H(Y) - H(X, Y)$ is the average reduction in uncertainty about one variable when you learn the other; it is symmetric.
$I(X;Y) = \mathrm{KL}\big(p(x, y)\,\|\,p(x)p(y)\big) \ge 0$ , with equality exactly for independent variables; it is the average pointwise mutual information $\log\frac{p(x, y)}{p(x)p(y)}$ .
For a fair bit through a binary symmetric channel, $I = 1 - H_b(\varepsilon)$ : $0.278$ bits at $\varepsilon = 0.2$ , and 0 at $\varepsilon = 0.5$ .
For jointly Gaussian variables, $I = -\frac12\log(1 - \rho^2)$ , and in general $\frac12\log\frac{\det\Sigma_{XX}\det\Sigma_{YY}}{\det\Sigma}$ .
Mutual information is unchanged by invertible maps of each variable and sees nonlinear dependence that correlation misses.
Data processing inequality: if $X \to Y \to Z$ is a Markov chain, then $I(X;Z) \le I(X;Y)$ , with equality when $Z$ is sufficient ( $I(X;Y \mid Z) = 0$ ).
The plug-in estimate of mutual information is biased upward for independent variables, by about $(K_X - 1)(K_Y - 1)/(2N)$ nats; compare it with a permutation baseline.

08 InfoNCE and contrastive learning

The best classifier between samples of $P$ (label 1) and $Q$ (label 0), with equal class sizes, has the logit $\log p(x)/q(x)$ : the density-ratio trick.
An f-divergence is $D_f(P\,\|\,Q) = \mathbb{E}_Q[f(p/q)]$ with convex $f$ and $f(1) = 0$ ; Jensen gives $D_f \ge 0$ . KL, reverse KL, TV, $\chi^2$ , squared Hellinger and JS are f-divergences.
The convex conjugate $f^*(t) = \sup_u [tu - f(u)]$ gives the tangent lines of $f$ , and the Fenchel–Young inequality $f(u) \ge tu - f^*(t)$ .
Variational bound: for every critic $T$ , $D_f(P\,\|\,Q) \ge \mathbb{E}_P[T] - \mathbb{E}_Q[f^*(T)]$ , with equality at $T^* = f'(p/q)$ . Only samples of $P$ and $Q$ are needed.
For KL: NWJ $\mathbb{E}_P[T] - \mathbb{E}_Q[e^{T-1}]$ (optimal $1 + \log r$ ) and DV $\mathbb{E}_P[T] - \log\mathbb{E}_Q[e^T]$ (optimal $\log r + c$ ). With $P = p(x,y)$ and $Q = p(x)p(y)$ they bound $I(X;Y)$ , but their variance grows like $e^{I}$ .
InfoNCE: $I(X;Y) \ge \log N - \mathcal{L}_{\text{InfoNCE}}$ , where the loss is the softmax cross-entropy of picking the true partner among $N$ candidates. The bound never exceeds $\log N$ , and its optimal critic is $\operatorname{pmi}(x,y) + a(x)$ .
Contrastive learning (CPC, SimCLR, CLIP) minimizes InfoNCE with the critic $\cos(g(x), h(y))/\tau$ ; large batches raise the $\log N$ ceiling.
A GAN discriminator is a density-ratio classifier: $D^* = p/(p+q)$ , and the GAN value at $D^*$ is $2\,\mathrm{JS}(P\,\|\,Q) - \log 4$ .

09 The ELBO and VAEs

The ELBO is $\mathrm{ELBO}(q) = \mathbb{E}_q[\log p(x, z) - \log q(z)]$ , and $\log p(x) = \mathrm{ELBO}(q) + \mathrm{KL}(q(z)\,\|\,p(z \mid x))$ ; so the ELBO is a lower bound on $\log p(x)$ , tight exactly at the posterior.
Jensen's inequality also gives the bound: $\log \mathbb{E}_q[w] \ge \mathbb{E}_q[\log w]$ with weights $w = p(x, z)/q(z)$ ; the ELBO is the log of the geometric mean of the weights, $\log p(x)$ the log of their arithmetic mean.
Two standard forms: $\mathrm{ELBO} = \mathbb{E}_q[\log p(x, z)] + H(q)$ (energy + entropy) and $\mathrm{ELBO} = \mathbb{E}_q[\log p(x \mid z)] - \mathrm{KL}(q\,\|\,p(z))$ (reconstruction − KL to the prior).
Maximizing the ELBO over $q$ minimizes the reverse KL $\mathrm{KL}(q\,\|\,p(z \mid x))$ : variational inference is mode seeking, and a mean-field Gaussian gets the too-small variances $1/(\Sigma^{-1})_{ii}$ .
Maximizing the ELBO over the model parameters is approximate maximum likelihood; EM is the case where $q$ is set to the exact posterior before each step.
The VAE loss is $-\mathrm{ELBO}$ with a Gaussian encoder, the reparameterization $z = \mu + \sigma \odot \varepsilon$ , the KL $\frac12\sum_i(\mu_i^2 + \sigma_i^2 - 1 - \log\sigma_i^2)$ , and a reconstruction term that is minus a cross-entropy (Bernoulli) or a scaled squared error (Gaussian).
The IWAE bound $\mathcal{L}_K = \mathbb{E}[\log \frac1K\sum_k w_k]$ satisfies $\mathrm{ELBO} = \mathcal{L}_1 \le \mathcal{L}_K \le \mathcal{L}_{K+1} \le \log p(x)$ , and its gap is about $\operatorname{Var}_q(w)/(2K\,p(x)^2)$ for large $K$ .
With an encoder, the gap is the approximation gap (family too simple) plus the amortization gap (one shared network); posterior collapse means $q_\phi(z \mid x) = p(z)$ for every $x$ .

10 Rate–distortion and β-VAE

The rate–distortion function $R(D) = \min I(X; \hat X)$ over test channels with $\mathbb{E}[d(X, \hat X)] \le D$ is the fewest bits per symbol for an average distortion $D$ ; long block codes reach it.
$R(D)$ is non-increasing and convex, equals $H(X)$ at $D = 0$ for discrete sources with Hamming distortion, and is 0 for $D \ge D_{\max}$ .
Bernoulli( $p$ ), Hamming: $R(D) = H_b(p) - H_b(D)$ for $D \le \min(p, 1-p)$ ; a fair coin with 11% errors needs 0.5 bits per flip.
Gaussian, squared error: $R(D) = \frac12\log_2(\sigma^2/D)$ for $D \le \sigma^2$ ; each extra bit divides the MSE by 4 (6.02 dB).
Reverse water-filling: independent Gaussian components get $D_i = \min(\theta, \lambda_i)$ ; components below the water level get no bits.
Blahut–Arimoto alternates $r = $ output marginal and $q \propto r\,e^{-\beta d}$ ; it converges to the point of slope $-\beta$ (nats).
Information bottleneck: $\min I(X;T) - \beta I(T;Y)$ , a rate–distortion problem with distortion $\mathrm{KL}(p(y\mid x)\,\|\,p(y\mid t))$ .
β-VAE: loss = distortion + $\beta\cdot$rate, and the rate $\mathbb{E}_x \mathrm{KL}(q(z\mid x)\,\|\,p(z)) = I_q(X;Z) + \mathrm{KL}(q(z)\,\|\,p(z)) \ge I_q(X;Z)$ .