Entropy, Cross Entropy, and KL Divergence
Entropy, Cross Entropy, and KL Divergence
Entropy, Cross Entropy, and KL divergence are fundamental quantities in information theory and have found applications in machine learning. Let’s walk through some definitions and motivations.
Information of an Event
We first define the “information” or “surprise” of a random event. Specifically, we want to define a function \(s(x): X \to \mathbb{R}\) acting on random variables. This function will have the desired properties
- \(s(A)\) depends continuously on \(\mathbb{P}(A)\)
- \(s(A)\) increases as \(\mathbb{P}(A)\) decreases. Rarer events should hold more “information” or induce more “surprise”
- \(s(A\cap B) = s(A) + s(B)\) if \(A, B\) are independent
We skip the derivation, but these properties dictate that the function \(s\) must be, up to a constant: \(s(A) = -\log(P(A))\).
Since we are usually communicating over a binary channel, we typically work with log base 2 and units of bits.
Entropy
Now that we have the definition of \(s\), we can define the entropy function \(H(X)\).
\[\begin{aligned} H(X) = -\sum_{x\in X} \log(P(X = x)) \\ \end{aligned}\]and when \(P=0\), we define \(0\log(0) = 0\)
The entropy of a random variable is just the average of the “surprise” of the possible events weighted by its probability.
For a fair coin with only two possiblities, its entropy is
\[\begin{aligned} H(X) &= -P(H)\log_2(P(H)) - P(T)\log_2(P(T)) \\ &= -(0.5\log(0.5)) -(0.5\log(0.5)) \\ &= \log 2 \\ &= 1 \end{aligned}\]For a biased coin with probabilities \(H=0.9\) and \(T=0.1\), the entropy is
\[\begin{aligned} H(X) &= -P(H)\log_2(P(H)) - P(T)\log_2(P(T)) \\ &= -(0.9\log(0.9)) -(0.1\log(0.1)) \\ &\approx 0.1412 \end{aligned}\]It turns out for random variables over a finite set, the entropy is maximized for uniform distributions.
Cross-Entropy and KL Divergence
Suppose we have two pdfs \(P, Q\) on the same random variable \(X\) that we would like to compare or measure the discrepancy between.
We define the cross-entropy as the quantity:
\[\begin{aligned} H(P, Q) &= -\sum_i p_i \log(q_i) \\ \end{aligned}\]It is the “surprise” of events under \(Q\), but weighted by \(P\).
Unrigorously, if \(H(P)\) describes the amount of “chaos” of \(P\), then \(H(P, Q)\) is the amount of “chaos” of using \(Q\) when \(P\) is the true distribution.
Now we can define the definition of the KL divergence: \(D(P \lvert\rvert Q)\).
\[\begin{aligned} D(P||Q) &= \mathbb{E}_P[(\log \frac{p(x)}{q(x)})] \\ &= \mathbb{E}_P[\log\frac{1}{q(x)}] - \mathbb{E}_P[\log\frac{1}{p(x)}] \\ &= -\mathbb{E}_P[\log q(x)] - H(P) \\ &= H(P, Q) - H(P) \end{aligned}\]By Gibb’s inequality, this quantity is non-zero and is 0 when \(P = Q\).
What’s interesting is that this portrays a relationship between \(D(P\lvert\rvert Q)\), \(H(P,Q)\), \(H(P)\)
- \(H(P, Q)\) is always greater than equal to \(H(P)\)
- \(D(P\lvert\rvert Q)\) is exactly that gap quantity
Usages in Machine Learning
Suppose we are training a machine learning classifier that determines what animal is in the provided image.
The standard loss function is the cross entropy loss, defined as
\(\mathcal{L} = -\sum_{k=1}^Ky_k\log(\hat{y}_k)\)
But this is exactly the cross entropy we discussed earlier with \(Y\) being the labelled distribution and \(\hat{Y}\) being the model’s output distribution. Furthermore, because the distribution \(Y\) is typically one-hot decoded, the whole quantity reduces down to just a single value \(-\log \hat{y}_k\). Numerically, there are even more optimizations involved combined with softmax.
Now consider the case where we want to perform distillation from a teacher model to a student model, where we want student’s output distribution to match the teacher’s distribution. \(D(P\lvert\rvert Q)\) is the natural choice, as it better encapsulates the idea that we aim to match the target distribution. When the quantity is ideally minimized, then we have exactly \(D(P\lvert\rvert Q)=0\) and \(P=Q\).
Based on the equation \(D(P\lvert\rvert Q) = H(P,Q) - H(P)\), optimizing one of \(D(P\lvert\rvert Q), H(P,Q)\) also optimizes the other. However, each has found its place unique place within machine learning for reasons outside just mathematical properties.