Minimum KL $\rightarrow$ Maximum entropy

In the previous chapter, we saw what happens when we minimize $q$ in the KL divergence $D(p, q)$. We used this to find the best model of data $p$.

In this chapter, we will ponder the second question - what happens if we minimize $p$ in $D(p, q)$? This way, we will build the so-called maximum entropy principle that guides us whenever we want to choose a good model distribuiton.

Conditioning on steroids

Suppose I want to determine a probability distribution modelling the random variable $X$ of how long it takes me to eat lunch. My initial (and very crude) model of $X$ might be a uniform distribution $q$ between and minutes.

Starting with this model, I can try to get some new information and condition on it to get a better model $p$.

For example, let's say that after eating many lunches, I observe that I always finish after at most 30 minutes. I can turn this to a new information that $X \le 30$. I can condition on this information and get a better model:

Let's try again. I eat many more lunches, but this time I keep recording the average time it takes me to eat lunch. Say, it turns out to be 15 minutes. How do I change $q$ to reflect this new information? The probability theory gives a clear answer.

We simply can't do this. In probability theory, we can condition on events like $X \le 30$, i.e., facts that are true for some values that $X$ can attend, but not others. But now we would like to condition on $E[X] = 15$ which is not an event, just a fact that's true for some distributions over $X$, but not others.

The fun part is that we can use KL divergence to 'condition' on $E[X] = 15$. It turns out that the most reasonable way to account for the new information is to choose as the model minimizing KL divergence to $q$. That is, for the set $P$ of distributions $p$ with $E_p[X] = 15$, choose

In the example, happens to look like exponential distribution:

This is sometimes called the minimum relative entropy principle. Why does this make sense? Intuitively, I want to find a distribution that would serve as the new best guess for what the truth is, while the old model distribution remains as good a model of $p$ as possible. This is what we achieve by minimizing KL divergence $D(p, q)$.

Admittedly, this intuition may feel a bit shaky, as we typically prefer $p$ to represent the "true" distribution when using KL divergence, whereas here it's simply a new, improved, model. There's a more technical argument called Wallis derivation that explains why we can derive minimum relative entropy as "conditioning on steroids" from the first principles.

The maximum entropy principle

Let's delve deeper into the minimum relative entropy principle. A conceptual issue with it is that it only allows us to refine an existing model $q$ into a better model $p$. But how did we choose the initial model $q$ in the first place? It feels a bit like a chicken-and-egg dilemma.

Fortunately, there's usually a very natural choice for the simplest possible model $q$: the uniform distribution. This is the unique most 'even' distribution that assigns the same probability to every possible outcome. There's also a fancy name for using the uniform distribution as the safe-haven model in the absence of any relevant evidence: the principle of indifference.

It would be highly interesting to understand what happens when we combine both principles together. That is, say that we start with the uniform distribution (say it's uniform over the set $\{1, \dots, k\}$). What happens if we find a better model by minimizing KL divergence? Let's write it out:

I am a one-trick pony, whenever I see KL divergence, I split it into cross-entropy and entropy:

In the previous chapter, it was the second term that was constant, now it's the first term: $\sum_{i = 1}^k p_i\log \frac{1}{1/k} = \log(k)$ does not depend on $p$, so minimizing KL divergence is equivalent to minimizing $-H(p)$. We get:

We've just derived what's known as the maximum entropy principle: given a set $P$ of distributions to choose from, we should opt for the $p\in P$ that maximizes the entropy $H(p)$.

General form of maximum entropy distributions

Let's now dive a bit deeper into maximum entropy. We'll try to understand what maximum entropy distributions actually look like. For example, we will see soon how does the maximum entropy distribution with $E[X] = 15$ looks like.

Here's what I want you to focus on, though. Let's not worry about concrete numbers like 15 too much. To get the most out of the max-entropy principle, we have to think about the questions a bit more abstractly, more like: _If I fix the value of $E[X]$, what shape will the max-entropy distribution have?

For such a broad question, the answer turns out to be surprisingly straightforward! Before telling you the general answer, let's see a couple of examples.

If we consider distributions with a fixed expectation $E[X] = \mu$ (and the domain is non-negative real numbers), the maximum entropy distribution is the exponential distribution. This distribution has the form . Here, $\lambda$ is a parameter - fixing $E[X]$ to attain different values leads to different $\lambda$s. ¹

Another example: If we fix the values of both $E[X]$ and $E[X^2]$, the maximum entropy distribution is the normal distribution, where To keep things clean, we can rewrite its shape as for some parameters $\lambda_1, \lambda_2$ that have to be worked out from what values we fix $E[X]$ and $E[X^2]$ to.

Spot a pattern?

Notice that this general recipe doesn't tell us the exact values of $\lambda_1, \dots, \lambda_m$. Those depend on the specific values of $\alpha_1, \dots, \alpha_m$, while the general shape remains the same regardless of the $\alpha$ values. But don't get too hung up on the $\alpha$s and $\lambda$s. The key takeaway is that the maximum entropy distribution looks like an exponential, with the "stuff we care about" in the exponent.

Try building your own maximum entropy distribution on the interval $[0,1]$ by playing with $\lambda$ values:

Why?

Let's build some intuition for this. Remember from the previous chapter that the max-entropy principle is essentially about finding a distribution that is as close to uniform as possible, in the sense of minimizing KL divergence.

So, in what way are max-entropy distributions "close" to being uniform? Let's use the exponential distribution $p(x) \propto e^{-x}$ as an example. Say I independently sample two numbers from it, $x_1$ and $x_2$. Here's a little riddle: Is it more probable that I sample $x_1 = 10, x_2 = 20$ or that I sample $x_1' = 15, x_2' = 15$?

The answer is that both options have the same probability density. That's because $p(x_1)\cdot p(x_2) = e^{-x_1 - x_2}$. In our riddle, $x_1 + x_2 = x_1' + x_2'$, so both possibilities have a density proportional to $e^{-30}$.

You can test it in the following widget.

This property isn't exclusive to the exponential distribution; it holds for all max-entropy distributions that fit the form given by our formula [Eq. max-entropy-form?]. If you dare, the widget above also visualizes that if you sample $x_1, x_2, x_3$ from a Gaussian and fix the values of $x_1 + x_2 + x_3$ and $x_1^2 + x_2^2 + x_3^2$, the curve this defines (a circle) has constant density.