Entropy, KL Divergence, MLE, and Cross-Entropy Loss

Information Theory Background¹

Consider a random variable $X$ that takes on certain values $x_i$ with a probability distribution $p(x)$. We want to convey in a message to someone which events in $X$ have occurred in the sequence they occurred. (Think of $x_i$ as words from a vocabulary and the message as a sentence from the language.) We can simply send the actual $x_i$ in whatever encoding (say, 8-bit binary) we like. But let’s consider the problem of finding the encoding that leads to the smallest average message length.

First off, we immediately realize that fixed length codes will be wasteful when the objective is to not waste any bits, since we would necessarily have to choose an encoding length capable of covering all the events (the entire support of $X$), but not all events would be equally likely, and we’ll end up sending even the most likely events in the same encoding, thereby wasting bits. What if we could use shorter encodings for more frequent events and longer for less frequent ones? That’s called variable length encoding, and turns out its a great idea for optimality.

When finding variable length encodings, in order to decode the message, we need to know where the code for each event ends (since we can’t rely on length). Using stop “words” would again be wasteful. To achieve this without stop “words”, we need to make sure that no code is a prefix of another code (such as 10 and 1011), otherwise we wouldn’t be able to tell those two codes apart. This is called the prefix property, and the codes prefix codes.

However, with prefix codes, choosing a codeword for an event means sacrificing the rest of the space of codes starting with that codeword. Thus, choosing a shorter codeword for one event forces us to choose a longer code for another, thereby potentially increasing the average code length. This is our cost in terms of the space of possible codewords when assigning codes. If $L(x)$ is the length of the codeword in bits, we sacrifice $\frac{1}{2^L}$ of the space of codewords for this event.

For example, 3 bits can possibly represent 8 numbers or partitions, and by reserving one of those codes, we effectively block $\frac{1}{8}th$ of the space for this event, since every other event is now restricted to using the other 7 partitions. So that’s our cost in terms of the space of possible codes.

We are interested in finding the optimal encoding for this set - one where the average message length is shortest.

It turns out that this optimal encoding occurs when we allot our budget to each word in proportion to its frequency distribution, i.e., more frequent words get shorter codes. In other words, for each $x$, we bear a cost exactly equal to its probability $p(x)$,

$$\frac{1}{2^{L(x)}}=p(x)$$

which gives us the optimal code length for each word.

$$⟹L(x)={\log }_2\left(\frac{1}{p(x)}\right)$$

Entropy

Entropy of a distribution $p$, $H(p)$ is the expected length of a message in the optimal encoding for $p$.

$$H(p)={\mathbb{E}}_p\left[L(x)\right]=\sum _x\left[p(x){\log }_2\left(\frac{1}{p(x)}\right)\right]$$

Entropy, directly, is the least number of bits you need to communicate events from $p$. It gives us a way of quantifying how much information is contained in a distribution.

Which brings us to uncertainty. How much information does an absolutely certain event convey? None! We knew anyway it was going to happen. How much information does a uniform distribution over a bunch of numbers convey? A lot! We can’t predict one event over another since they all have equal probabilities of occurring.

The more diffuse the probability distribution, the more uncertain we are about any of the values, the more we learn on average when we find out what happened, and the longer our messages have to be on average.

Perplexity

Perplexity is a measure of uncertainty in the value of a sample from a discrete probability distribution. The larger the perplexity, the less likely it is that an observer can guess the value which will be drawn from the distribution.

The perplexity of a discrete probability distribution p is defined as

$$\mathrm{perplexity}(p)=2^{H(p)}$$

Cross Entropy

Now, suppose we use the optimal encoding for one distribution $p$ to encode events occurring according to a different distribution $q$. We define the cross-entropy of $q$ wrt $p$ as the average length of messages from $q$ using the optimal encoding scheme of $p$:

$$H_p(q)={\mathbb{E}}_q\left[L_p(x)\right]=\sum _x\left[q(x){\log }_2\left(\frac{1}{p(x)}\right)\right]$$

Note that it is not symmetrical.

Cross entropy gives us a way to think about how different a distribution $p$ is from $q$. $H_p(q)$ is longer than $H(q)$ because the values in $q$ occur with different frequencies than in $p$. Had the two distributions been the same, they would’ve had the same encoding and thus the cross entropy would’ve been equal to the entropy of either of them.

The more different these distributions are, the longer the cross entropy will be compared to the entropy, i.e., the larger $H_p(q)-H(q)$ will be.

Kullback–Leibler Divergence

$H_p(q)-H(q)$ therefore gives us a neat way to compare two distributions, and is called the KL Divergence of $q$ wrt $p$. It is the extra number of bits we need to use to encode $q$ in the optimal encoding of $p$.

$$D_{KL}(q\Vert p)=H_p(q)-H(q)\text{\hspace{1em}(1)}$$

which, if you do the math, is

$$D_{KL}(q\Vert p)=\sum _x\left[q(x){\log }_2\left(\frac{q(x)}{p(x)}\right)\right]$$

which is also written as the expected value of the log likelihood ratio:

$$D_{KL}(q\Vert p)={\mathbb{E}}_{x\sim q(x)}\left[{\log }_2\left(\frac{q(x)}{p(x)}\right)\right]$$

KL divergence is again not symmetrical. It’s not a distance metric (which are symmetric), it’s a divergence measure.

A note on distance metrics vs divergence.

While both distance metrics and divergences indicate how far apart two entities are, they are a bit different. Distance metrics² are:

• symmetrical,
• and satisfy the triangle inequality.

Divergences are defined specifically on probability metrics. While all distances between probability distributions are divergences, the converse is not true.

Taking a look at $Eq.(1)$, we see that the cross-entropy and KL divergence differ by the entropy term. If $p_{data}$ is the true data distribution³ and $q_{\theta }$ is our model distribution that we are trying to match to $p_{data}$, since the entropy of true data distribution $H_{p_{data}}$ is independent of model parameters, minimizing the cross-entropy $H_{q_{\theta }}(p_{data})=-{\sum }_i^n\left[y_{data}^{(i)}{\log }_2(y_{pred}^{(i)})\right]$ is equivalent to minimizing the KL divergence $D_{KL}(p_{data}\Vert q_{\theta })$. This is what we do often in classification problems.⁴

Suppose we want to approximate a distribution $p$ using a simpler distribution $q$. We can do this by minimizing $D_{KL}(q\Vert p)$ or $D_{KL}(p\Vert q)$. The resulting distribution $q$ will have different characteristics based on what KL we choose:

Forward KL or Inclusive KL

• $D_{KL}(p\Vert q)=\int p(x)\log \frac{p(x)}{q(x)}dx$
• M-projection or moment projection
• Zero-avoiding or mode-covering
• Minimizing the KL will force $q$ to include all the areas of space for which $p$ has non-zero probability, and will typically over-estimate the support of p.

Reverse KL or Exclusive KL

• $D_{KL}(q\Vert p)=\int q(x)\log \frac{q(x)}{p(x)}dx$
• I-projection or information projection
• Zero-forcing or mode-seeking
• Minimizing the exclusive KL will force $q$ to exclude all the areas of space for which $p$ has zero probability, and $q$ will typically under-estimate the support of $p$.

Maximum Likelihood Estimation

Defining Likelihood

In probability theory, likelihood $L(\theta ;\mathbf{x})$ or $L(\theta \mid \mathbf{x})$ of parameter $\theta$ given some fixed data $\mathbf{x}$ is any function of $\theta$ that is proportional to the sampling density (of $\mathbf{x}$), i.e.,

$$L_{\mathbf{x}}(\theta )=f_{\theta }(\mathbf{x})$$

In Bayesian statistics, we usually express Bayes’ theorem in its simplest form as:

$$\pi (\theta \mid \mathbf{x})\propto \pi (\theta )\cdot L(\theta \mid \mathbf{x})$$

also expressed as:

$$\text{ posterior }\propto \text{ prior }\times \text{ likelihood }$$

Strictly speaking we do not require that the likelihood be equal to the sampling density; it needs only be proportional, which allows removal of multiplicative parts that do not depend on the parameters.

We know that minimizing the KL divergence is a way to bring two distributions closer. Let $x_1,x_2,\dots ,x_n$ be some data that we assume is distributed according to a true data distribution $p_{data}$. Let $q_{\theta }$ be some parametric distribution with parameters $\theta$ that we are trying to fit the data we have (since $q$ is a function of both $X$ and $\theta$, we can also write the density as $q_{\theta }(X;\theta )$ - this just means $q$ is a function of $X$ parameterized by $\theta$). We can do this by choosing $\theta$ in a way that maximizes the likelihood of that data, i.e.,

$${\theta }_{\mathrm{MLE}}^{\ast }=\underset{\theta }{\mathrm{argmax}}{q}_{\theta }(X)$$

Since we assume the training data is $i.i.d$, the expression becomes

$${\theta }_{\mathrm{MLE}}^{\ast }=\underset{\theta }{\mathrm{argmax}}\prod _{i=1}^n{q}_{\theta }(x_i)$$

Taking $\log$ allows us to change the product to a summation outside, and since it is an increasing function, does not affect $\mathrm{argmax}$.

$${\theta }_{\mathrm{MLE}}^{\ast }=\underset{\theta }{\mathrm{argmax}}\sum _{i=1}^n\log \left(q_{\theta }(x_i)\right)$$

Conditional MLE

While here we considered the unconditional distribution of data (such as a normal distribution fitting the height data of sampled males in a country), MLE can just as easily be applied to conditional distributions, and is actually the most common situation because it forms the basis for most supervised learning.

If $\mathbf{X}$ represents all our inputs and $\mathbf{Y}$ all our observed targets, then the conditional maximum likelihood estimator is:

$${\theta }_{\mathrm{MLE}}^{\ast }=\underset{\theta }{\mathrm{argmax}}{q}_{\theta }(Y|X))$$

which in the $i.i.d.$ case becomes:

$${\theta }_{\mathrm{MLE}}^{\ast }=\underset{\theta }{\mathrm{argmax}}\prod _{i=1}^n{q}_{\theta }(y_i|x_i)$$

KL Divergence and MLE

Because the $\mathrm{argmax}$ does not change when we rescale the expression, we can divide the above expression by $n$ to get the sample mean ($\overline{X_n}$) of the log likelihood:

$${\theta }_{\mathrm{MLE}}^{\ast }=\underset{\theta }{\mathrm{argmax}}\frac{1}{n}\sum _{i=1}^n\log \left(q_{\theta }(x_i)\right)$$

Then, by the law of large numbers, this sample mean must converge to the true expectation as $n\to \infty$, so asymptotically:

$${\theta }_{\mathrm{MLE}}^{\ast }=\underset{\theta }{\mathrm{argmax}}{\mathbb{E}}_{x\sim p_{data}}\left[\log (q_{\theta }(x))\right]\text{\hspace{1em}(2)}$$

We can also estimate $p_{data}$ with $q_{\theta }$ by choosing $\theta$ in a way that we minimize the KL divergence $D_{\mathrm{KL}}(p_{data}\Vert q_{\theta })$:

$${\theta }_{\mathrm{KL}}^{\ast }=\underset{\theta }{\mathrm{argmin}}{D}_{\mathrm{KL}}(p_{data}\Vert q_{\theta })\text{\hspace{1em}(3)}$$

Using the definition of $D_{\mathrm{KL}}(p_{data}\Vert q_{\theta })$:

$$D_{\mathrm{KL}}(p_{data}\Vert q_{\theta })={\mathbb{E}}_{x\sim p_{data}}\left[{\log }_2\left(\frac{p_{data}(x)}{q_{\theta }(x)}\right)\right]$$

Simplifying,

$$D_{\mathrm{KL}}(p_{data}\Vert q_{\theta })={\mathbb{E}}_{x\sim p_{data}}\left[{\log }_2\left(p_{data}(x)\right)\right]-{\mathbb{E}}_{x\sim p_{data}}\left[{\log }_2\left(q_{\theta }(x)\right)\right]$$

Plugging it back into $(3)$ and noting the first term is a constant wrt $\theta$:

$${\theta }_{\mathrm{KL}}^{\ast }=\underset{\theta }{\mathrm{argmin}}\left[C-{\mathbb{E}}_{x\sim p_{data}}\left[{\log }_2\left(q_{\theta }(x)\right)\right]\right]$$

which further simplifying (taking the minus sign out, changing $\mathrm{argmin}$ to $\mathrm{argmax}$, and multiplying by $\log (2)$) gives us

$${\theta }_{\mathrm{KL}}^{\ast }=\underset{\theta }{\mathrm{argmax}}{\mathbb{E}}_{x\sim p_{data}}\left[\log \left(q_{\theta }(x)\right)\right]$$

which is exactly equal to ${\theta }_{\mathrm{MLE}}^{\ast }$ in $(2)$, thus proving that maximizing likelihood is asymptotically equal to minimizing KL divergence.

Also note that the non constant quantity is the cross-entropy $H_{q_{\theta }}(p_{data})$. Thus, maximizing likelihood is also equivalent to minimizing the cross entropy.

Some Related Loss Functions

Negative Log Likelihood Loss (NLL) a.k.a. Log Loss

Negative of Log likelihood, so that instead of maximizing likelihood, we can estimate by minimizing the negative of it like a typical loss function.

Cross Entropy Loss

Softmax + NLL loss.

Bibliography

Footnotes

1. This section is a condensed version of the excellent blog: Visual Information Theory -- Colah’s Blog (2015) ↩

2. For formal definition of distances, see Metric space - Wikipedia ↩

3. Technically, while the generating process may generate data with a true data distribution of $p_{data}$, the sample distribution may differ slightly, and is called the empirical distribution. Since we don’t have access to the true distribution, this sample distribution is what we try to estimate. ↩

4. See also on why cross entropy is a better idea sometimes: What is the difference between Cross-entropy and KL divergence? ↩

Visual Information Theory -- colah’s blog. (2015, October 14). https://colah.github.io/posts/2015-09-Visual-Information/