Entropy and KL divergence

Overview

Entropy measures the average uncertainty or information content in a probability distribution. KL divergence measures how one probability distribution differs from another. Both are foundational to machine learning: entropy guides decision trees, loss functions, and compression; KL divergence powers variational inference, GANs, and policy optimization.

Shannon Entropy

Derivation from First Principles

Goal: Design a measure of "average surprise" that satisfies:

1. Additivity: Information from independent events adds up
2. Monotonicity: Rarer events carry more surprise
3. Continuity: Small probability changes → small entropy changes

Step 1: Surprise for a single outcome

• If outcome $x$ has probability $p(x)$, define its surprisal (information content): $I(x) = -\log_2 p(x)$

Why this step? We need surprise to decrease as probability increases. A certain event ($p=1$) should have zero surprise: $-\log_2(1) = 0$. A rare event ($p=0.01$) has high surprise: $-\log_2(0.01) \approx 6.64$ bits. The log makes independent events' information add: $I(x,y) = I(x) + I(y)$ when $x,y$ independent.

Step 2: Average surprise over all outcomes $H(X) = \mathbb{E}_{x \sim p}[I(x)] = \sum_{x} p(x) \cdot (-\log_2 p(x)) = -\sum_{x} p(x) \log_2 p(x)$

Why this step? Entropy is the expected information you gain when you observe $X$. Weighted average by probability.

Proof of Maximum Entropy (uniform distribution achieves it): Let $u(x) = \frac{1}{n}$ be the uniform distribution over $n$ outcomes. Use Gibs' inequality: for any two distributions $p, q$, $-\sum_x p(x) \log p(x) \leq -\sum_x p(x) \log q(x)$ with equality iff $p = q$.

Set $q = u$: $H(X) = -\sum_x p(x) \log p(x) \leq -\sum_x p(x) \log \frac{1}{n} = \log n$ Equality when $p(x) = \frac{1}{n}$ for all $x$.

Kullback-Leibler (KL) Divergence

Derivation: Why This Formula?

Context: You're designing an optimal code for distribution $p$, but you accidentally use the code optimized for $q$. How much extra information do you transmit?

Step 1: Optimal code length for $p$ Usingp$'s code, average message length =$H(p) = -\sum_x p(x) \log p(x)$

Step 2: Actual code length when using $q$'s code If you encode using $q$'s code (which assigns $-\log q(x)$ bits to outcome $x$), but outcomes follow $p$, average length = $-\sum_x p(x) \log q(x)$ (called cross-entropy $H(p,q)$).

Step 3: Extra cost $D_{KL}(p \| q) = H(p,q) - H(p) = -\sum_x p(x) \log q(x) - \left(-\sum_x p(x) \log p(x)\right)$ $= \sum_x p(x) [\log p(x) - \log q(x)] = \sum_x p(x) \log \frac{p(x)}{q(x)}$

Why this step? Cross-entropy is the code length under $q$, entropy is the optimal length under $p$. The difference is the inefficiency.

Proof of Non-negativity (Gibs' inequality): $D_{KL}(p \| q) = -\sum_x p(x) \log \frac{q(x)}{p(x)}$ Use Jensen's inequality on the concave function $\log$: $-\sum_x p(x) \log \frac{q(x)}{p(x)} \geq -\log \left(\sum_x p(x) \frac{q(x)}{p(x)}\right) = -\log \left(\sum_x q(x)\right) = -\log 1 = 0$ Equality iff $\frac{q(x)}{p(x)}$ is constant, i.e., $p = q$.

Cross-Entropy

In machine learning, when $p$ is the true label distribution (often one-hot) and $q$ is the model's predicted probabilities, minimizing cross-entropy = minimizing KL divergence (since $H(p)$ is constant).

Applications in Machine Learning

1. Decision Trees: Split criterion uses information gain = entropy reduction $\text{Gain} = H(\text{parent}) - \sum_{\text{children}} \frac{|child|}{|parent|} H(\text{child})$

2. Classification: Cross-entropy loss for neural networks $\mathcal{L} = -\sum_{i} y_i \log \hat{y}_i$ where $y$ is true distribution (one-hot), $\hat{y}$ is predicted probabilities.

3. Variational Inference: Minimize $D_{KL}(q\phi(z) \| p(z|x))$ to approximate posterior

4. GANs: Discriminator maximizes cross-entropy; generator minimizes JS divergence (related to KL)

5. Reinforcement Learning: Policy gradient methods use KL penalties to prevent policy collapse

Connections

• Mutual Information - Uses entropy: $I(X;Y) = H(X) + H(Y) - H(X,Y)$
• Maximum Entropy Principle - Justifies probability distributions
• Cross-Entropy Loss - Direct application in neural networks
• Variational Autoencoders - ELBO = reconstruction - KL divergence
• Jensen-Shannon Divergence - Symmetric version of KL
• Information Gain - Entropy reduction in decision trees
• Evidence Lower Bound (ELBO) - Uses KL divergence for Bayesian inference
• F-divergences - Family of divergences including KL

#flashcards/ai-ml

What is Shannon entropy? :: The average amount of information (in bits) gained when observing a random variable; $H(X) = -\sum_x p(x) \log_2 p(x)$

Concept Map

Hinglish (regional understanding)