← Notes

Entropy and KL Divergence

Information Theory

Overview

Entropy, cross-entropy, and KL divergence provide a sequence of increasingly useful information-theoretic quantities. Entropy measures the average surprise inherent in a distribution. Cross-entropy measures the average surprise obtained when outcomes are generated according to one distribution but evaluated using another. KL divergence is the extra average surprise introduced by using the wrong distribution. [2] [3]

These quantities are especially useful in machine learning because they turn differences between probability distributions into scalar objectives that can be analyzed and optimized.

Entropy

The intuition in this section follows the surprise-based explanation used in StatQuest's entropy lesson, with the notation and supporting mathematical discussion expanded here. [1] [5]

Surprise

Suppose an outcome \(x\) occurs with probability \(p(x)\). Intuitively, a rare event should be more surprising than a common event:

\[ p(x) \downarrow \quad \Longrightarrow \quad \text{surprise}(x) \uparrow. \]

Simply using \(1/p(x)\) does not give the behavior we want. In particular, an event that is certain has \(p(x)=1\), but \(1/p(x)=1\), whereas we would like a certain event to carry zero surprise.

The standard information-theoretic measure of surprise, also called self-information or surprisal, is

\[ I(x) = \log\frac{1}{p(x)} = -\log p(x). \]

This has the desired behavior:

\[ p(x)=1 \quad \Longrightarrow \quad I(x)=0, \]

while

\[ p(x)\rightarrow 0 \quad \Longrightarrow \quad I(x)\rightarrow \infty. \]

The logarithm also makes information additive for independent events. If \(x_1\) and \(x_2\) are independent,

\[ -\log\!\left(p(x_1)p(x_2)\right) = -\log p(x_1)-\log p(x_2). \]

The base of the logarithm determines the unit. Base \(2\) measures information in bits, while the natural logarithm measures it in nats. [2] [3]

Expected surprise

Surprise quantifies the information associated with one observed outcome. Entropy asks a different question: how surprised should we expect to be on average?

For a discrete random variable \(X\sim p\),

\[ \boxed{ H(X) = \mathbb{E}_{X\sim p} \left[ \log\frac{1}{p(X)} \right] = -\sum_x p(x)\log p(x) }. \]

Thus, entropy is the expected surprise of an outcome drawn from the distribution itself. A concentrated distribution has low entropy because its typical outcomes are predictable. A more evenly spread distribution has higher entropy because there is greater uncertainty about what will be observed. [1] [2]

For a continuous random variable with density \(p(x)\), the analogous quantity is differential entropy:

\[ h(X) = -\int p(x)\log p(x)\,dx. \]

Differential entropy is useful but does not share every property of discrete Shannon entropy; for example, it can be negative. [3]

Cross-entropy

Entropy assumes that outcomes are both generated and evaluated according to the same distribution \(p\). Cross-entropy separates these roles.

Suppose data is actually generated according to \(p\), but we evaluate its surprise using another distribution \(q\). Then

\[ \boxed{ H(p,q) = \mathbb{E}_{X\sim p} \left[ -\log q(X) \right] }. \]

In the discrete case,

\[ H(p,q) = -\sum_x p(x)\log q(x). \]

Cross-entropy therefore measures the average surprise incurred when the world behaves according to \(p\), but our probabilistic description of it is \(q\). [3]

KL Divergence

Let \(p\) and \(q\) be probability distributions over the same space. The Kullback-Leibler divergence from \(q\) to \(p\) is

\[ \boxed{ D_{\mathrm{KL}}(p\|q) = \mathbb{E}_{X\sim p} \left[ \log\frac{p(X)}{q(X)} \right] }. \]

For continuous densities,

\[ D_{\mathrm{KL}}(p\|q) = \int p(x) \log\frac{p(x)}{q(x)} \,dx, \]

while for discrete distributions,

\[ D_{\mathrm{KL}}(p\|q) = \sum_x p(x) \log\frac{p(x)}{q(x)}. \]

Operationally, the expectation is always taken under \(p\): sample an outcome according to \(p\), compare how much probability \(p\) assigns to that outcome with how much \(q\) assigns, take the log ratio, and average over outcomes that actually occur under \(p\). [3] [4]

If \(q\) assigns similar probability to the outcomes commonly produced by \(p\), then the KL divergence is small. If \(q\) assigns very little probability to outcomes that are common under \(p\), the KL divergence becomes large.

KL divergence as excess cross-entropy

Expanding the logarithm,

\[ \begin{aligned} D_{\mathrm{KL}}(p\|q) &= \mathbb{E}_{p} \left[ \log p(X)-\log q(X) \right] \\[4pt] &= -H(p)+H(p,q). \end{aligned} \]

Therefore,

\[ \boxed{ D_{\mathrm{KL}}(p\|q) = H(p,q)-H(p) }. \]

This gives a useful interpretation: KL divergence is the extra average surprise caused by using \(q\) to describe data that is actually generated by \(p\).

Since \(H(p)\) is fixed with respect to \(q\), minimizing cross-entropy \(H(p,q)\) with respect to a model \(q\) is equivalent to minimizing \(D_{\mathrm{KL}}(p\|q)\). [3]

The log-likelihood ratio

The quantity

\[ \log\frac{p(x)}{q(x)} \]

is the log-likelihood ratio at \(x\). It measures how strongly an observation supports \(p\) relative to \(q\):

KL divergence averages this evidence over observations actually generated according to \(p\):

\[ D_{\mathrm{KL}}(p\|q) = \text{average log-evidence for \(p\) over \(q\), when \(p\) is true}. \]

This also makes clear why KL divergence is asymmetric:

\[ D_{\mathrm{KL}}(p\|q) \neq D_{\mathrm{KL}}(q\|p) \quad \text{in general}. \]

The two directions average different likelihood ratios under different sampling distributions. [3]

Basic properties

KL divergence satisfies

\[ D_{\mathrm{KL}}(p\|q)\geq 0, \]

with equality if and only if \(p=q\) almost everywhere. However, it is not a metric: it is generally asymmetric and does not satisfy the triangle inequality. [3] [4]

KL divergence can also become infinite. If some event has positive probability under \(p\) but zero probability under \(q\), then

\[ p(x)>0,\quad q(x)=0 \quad \Longrightarrow \quad D_{\mathrm{KL}}(p\|q)=\infty. \]

Total Variation and Pinsker's Inequality

KL divergence is an information-theoretic quantity: it measures an average log-likelihood ratio. Sometimes we instead want an operational statement about how much the probability of an observable event can change when replacing one distribution with another.

Total variation distance

The total variation distance between \(P\) and \(Q\) is

\[ \boxed{ D_{\mathrm{TV}}(P,Q) = \sup_A |P(A)-Q(A)| }. \]

For distributions with densities \(p\) and \(q\),

\[ D_{\mathrm{TV}}(P,Q) = \frac{1}{2} \int |p(x)-q(x)| \,dx. \]

The supremum is taken over all measurable events \(A\). Therefore, if

\[ D_{\mathrm{TV}}(P,Q)=0.2, \]

then no event can have its probability change by more than \(0.2\) when replacing \(P\) with \(Q\), and some event attains that maximal difference. [3]

Pinsker's inequality

Pinsker's inequality connects the information-theoretic notion of KL divergence to the directly observable probability differences measured by total variation:

\[ \boxed{ D_{\mathrm{TV}}(P,Q) \leq \sqrt{ \frac{1}{2} D_{\mathrm{KL}}(P\|Q) } } \]

when KL divergence is measured with the natural logarithm. [3] [6]

Consequently, a small KL divergence guarantees that the two distributions are close in total variation. Since

\[ |P(A)-Q(A)| \leq D_{\mathrm{TV}}(P,Q) \]

for every event \(A\), Pinsker's inequality gives

\[ |P(A)-Q(A)| \leq \sqrt{ \frac{1}{2} D_{\mathrm{KL}}(P\|Q) }. \]

Example

Suppose

\[ D_{\mathrm{KL}}(P\|Q)=0.01. \]

The KL value tells us that using \(Q\) instead of \(P\) incurs only a small average log-likelihood penalty on data drawn from \(P\). Pinsker's inequality converts this into a statement about event probabilities:

\[ D_{\mathrm{TV}}(P,Q) \leq \sqrt{\frac{0.01}{2}} = \sqrt{0.005} \approx 0.0707. \]

Therefore, for every event \(A\),

\[ |P(A)-Q(A)| \leq 0.0707. \]

In other words, no event's probability can differ by more than approximately \(0.071\), or about 7.1 percentage points, between \(P\) and \(Q\).

This is the operational importance of Pinsker's inequality: KL divergence describes an average information discrepancy, while Pinsker converts a sufficiently small KL divergence into a uniform bound on observable probability differences.

References

  1. Starmer, J. Entropy (for data science) Clearly Explained!!!, StatQuest with Josh Starmer, 2021. https://www.youtube.com/watch?v=YtebGVx-Fxw . Used particularly for the surprise-to-entropy intuition.
  2. Shannon, C. E. (1948). A Mathematical Theory of Communication. Bell System Technical Journal, 27, 379–423 and 623–656.
  3. Cover, T. M., & Thomas, J. A. (2006). Elements of Information Theory, 2nd ed. Wiley-Interscience.
  4. Kullback, S., & Leibler, R. A. (1951). On Information and Sufficiency. The Annals of Mathematical Statistics, 22(1), 79–86.
  5. OpenAI. ChatGPT (GPT-5.6 Sol). Used for transcription of handwritten notes, typesetting, and organization.