Information Theory Foundations

For any probability distributions $p$ and $q$:

$D_{\text{KL}}(p \| q) \geq 0$

with equality if and only if $p = q$ almost everywhere.

Equivalently: the cross-entropy is at least the entropy:

$H(p, q) \geq H(p)$

Encoding data from $p$ using a code optimized for $q$ can never be more efficient than using the optimal code for $p$. Any mismatch between the true distribution and the coding distribution wastes bits. The extra bits wasted are exactly $D_{\text{KL}}(p \| q)$.

Gibbs inequality is the most fundamental result in information theory. It justifies using cross-entropy as a loss function: minimizing $H(p, q)$ over $q$ is equivalent to minimizing $D_{\text{KL}}(p \| q)$, which finds the best approximation to $p$. Since KL divergence is non-negative, the minimum is achieved at $q = p$.

In ML: training a classifier by minimizing cross-entropy loss is justified because it drives the model distribution toward the true conditional distribution $p(y \mid x)$.

KL divergence can be infinite if $p$ has support where $q$ does not. In variational inference, this means the variational family $q$ must cover the support of the posterior $p$, or the objective becomes undefined. This is one reason why "forward KL" $D_{\text{KL}}(p \| q)$ and "reverse KL" $D_{\text{KL}}(q \| p)$ behave very differently.

If $X \to Y \to Z$ is a Markov chain (i.e., $Z$ is conditionally independent of $X$ given $Y$), then:

$I(X; Z) \leq I(X; Y)$

Processing the data $Y$ through any channel to produce $Z$ cannot increase the information about $X$. No computation on $Y$ can create information about $X$ that $Y$ does not already contain.

You cannot improve your estimate of $X$ by processing the observation $Y$ --- you can only lose information. If you compress data, denoise it, or transform it through any deterministic or stochastic function, you cannot gain information about the source.

Think of a game of telephone: each step can only lose information, never gain it. The original message $X$ is most informative; each retelling $Y, Z, \ldots$ can only degrade the signal.

The data processing inequality is the theoretical foundation for minimax lower bounds in statistics and ML. If you want to estimate a parameter $\theta$ from data $X_1, \ldots, X_n$, any estimator $\hat{\theta}(X_1, \ldots, X_n)$ satisfies $I(\theta; \hat{\theta}) \leq I(\theta; X_1, \ldots, X_n)$.

Combined with Fano's inequality, this gives lower bounds on estimation error: there is a minimum sample size $n$ needed to estimate $\theta$ to accuracy $\epsilon$, regardless of the algorithm used.

In representation learning, DPI constrains what information a learned representation can contain: $I(X; Z) \leq I(X; Y)$ where $X$ is the input, $Y$ the representation, and $Z$ the prediction.

The inequality is tight when $Z$ is a sufficient statistic for $X$ given $Y$, meaning $Z$ preserves all the information that $Y$ has about $X$. In practice, finding sufficient statistics is often impossible, and most processing steps are lossy.

For random variables $X_1, \ldots, X_n$:

$H(X_1, X_2, \ldots, X_n) = \sum_{i=1}^n H(X_i \mid X_1, \ldots, X_{i-1})$

For $n = 2$: $H(X, Y) = H(X) + H(Y \mid X) = H(Y) + H(X \mid Y)$.

Chain rule for KL divergence: $D_{\text{KL}}(p(x, y) \| q(x, y)) = D_{\text{KL}}(p(x) \| q(x)) + \mathbb{E}_{p(x)}[D_{\text{KL}}(p(y \mid x) \| q(y \mid x))]$

The joint uncertainty of $(X_1, \ldots, X_n)$ decomposes into the uncertainty of $X_1$, plus the additional uncertainty of $X_2$ given $X_1$, plus the additional uncertainty of $X_3$ given $(X_1, X_2)$, and so on. Each term measures how much new uncertainty each variable adds beyond what is already known.

If the variables are independent: $H(X_1, \ldots, X_n) = \sum_i H(X_i)$ (uncertainty is additive). If they are dependent, the conditional entropies are smaller (each variable is partly predicted by the others), so the joint entropy is less than the sum of marginals.

The chain rule is used constantly in ML theory. Autoregressive models (GPT, language models) use it directly: the joint distribution of a sequence is factored as $p(x_1, \ldots, x_n) = \prod_i p(x_i \mid x_{<i})$, and the cross-entropy loss decomposes accordingly.

The chain rule for KL divergence is used in variational inference to decompose the ELBO objective and in PAC-Bayes bounds to decompose the complexity term across layers of a neural network.

The chain rule applies to discrete random variables directly. For continuous random variables, entropy must be replaced by differential entropy $h(X) = -\int p(x) \log p(x) \, dx$, which can be negative and is not invariant under changes of variables. The chain rules still hold for differential entropy and KL divergence, but care is needed with absolute continuity conditions.