Making Sense of "Entropy": From Entropy, the Maximum Entropy Principle, to Maximum Entropy Models (I)
The Concept of Entropy
As a physics enthusiast, I have always found the concept of "entropy" in statistical mechanics both mysterious and fascinating. So naturally, when I first got into data science, I also developed a strong interest in maximum entropy models.
What exactly is entropy? In popular accounts, entropy is generally explained in two ways: (1) entropy is a measure of uncertainty; (2) entropy is a measure of information. These sound like different things, but they're really saying the same thing. First, entropy as a measure of uncertainty quantifies our "degree of ignorance" about something. Why is entropy also a measure of information? Well, if entropy represents our ignorance about something, then as we move from "ignorance" to "complete knowledge," we gain a certain amount of information — the more ignorant we start out, the more information we gain by the time we reach "complete knowledge." Hence entropy, as a measure of uncertainty, can equally be seen as a measure of information — more precisely, the maximum amount of information we can possibly extract.
How do we measure uncertainty? In other words, how do we compute entropy? To answer this, note that we describe uncertainty using probability: we can assign a probability (or probability density — we won't distinguish between the two here) to each state a system might occupy, and as long as that probability isn't 1, there's uncertainty involved. So entropy must be tied to a probability distribution. But how exactly is it computed? The usual approach in textbooks or popular science writing is to simply state the formula for entropy outright. Here, instead, I'll try to derive the origin of the entropy formula from two angles, in the hope of giving the reader a sense of where it actually comes from.
The basic formula for entropy is
$$S=-\sum_x p(x)\log p(x)\tag{1}$$
Here $\log$ can be the natural logarithm, or the logarithm base 2 — in fact, any base greater than 1 works, since changing the base just amounts to changing the unit of information. $p(x)$ is the probability that the quantity $X$ takes the value $x$. For a continuous probability distribution, entropy is defined analogously (replacing the sum with an integral):
$$S=-\int p(x)\log p(x) dx\tag{2}$$
where $p(x)$ is the probability density function of $X$.
Notice a few features of equations $(1)$ and $(2)$: the logarithm $\log$, the summation $\sum_x$, and the leading minus sign. Below I'll focus on explaining these features from two perspectives — one more intuitive, the other more abstract (mathematical).
The Intuitive Angle
Let's start with the following example:
After the World Cup ends, everyone is curious about who the champion is. Suppose I missed watching the World Cup, and afterward I ask a spectator who knows the result, "Which team is the champion?" He doesn't want to tell me directly — instead he wants me to guess, and for each guess he charges me one dollar to tell me whether I'm right or wrong. So how much money would I need to pay him to find out who the champion is? I could number the teams from 1 to 32, and then ask: "Is the champion team among numbers 1–16?" If he tells me I'm right, I follow up with: "Is the champion among 1–8?" If he tells me I'm wrong, then naturally I know the champion is among 9–16. In this way, it only takes 5 questions for me to find out which team is the champion. So the information contained in the message "who is the World Cup champion" is worth only 5 dollars.
This example is drawn from Wu Jun's book The Beauty of Mathematics, in the chapter "On the Maximum Entropy Model." The example only works under the premise that "I" know absolutely nothing about soccer — I haven't studied it, nor heard any news about it. In that case, I can only guess, and the most naive approach would be to guess team by team: Is it China? Is it Brazil? Is it Japan? ... With this method we might not get the answer until the 31st question. Clearly, that's not the most efficient approach. In the example, we first number the teams (in data processing, we'd call this building an "index"), and then use binary search, with efficiency $\mathcal{O}(\log_2 N)$.
This gives us two insights: first, building an index and using binary search can dramatically speed up the search — though that's not really the point of this article; second, and more importantly, $\log_2 N$ — a logarithm has appeared! It can be rewritten as
$$\log_2 N=-\log_2 \frac{1}{N}=-\sum_{N\text{team}}\frac{1}{N}\log_2 \frac{1}{N}$$
which is exactly the form of equation $(1)$. Here, since we know nothing at all about soccer, each team has an equal probability of winning, i.e., $p=1/N$.
Readers might feel this example is too special a case to be representative. Fair enough — it's just an intuitive impression. We can also approach this in a more abstract, more precise mathematical way, in which case our line of reasoning is reversed.
The Abstract Angle
First, we want to construct a formula representing the amount of information — or equivalently, the degree of uncertainty — which we call "entropy." (Note: here we are constructing a quantity to serve a purpose we already have in mind, rather than having derived the quantity first and then proving it happens to serve that purpose. The logic runs in the opposite direction: we build what we need.) Since "entropy" is meant to represent an amount of information, it should have the following simple properties:
1. It is a function of the probability distribution $p(x)$, and for convenience of analysis, we would also like it to be a smooth function;
2. It is additive, meaning entropy takes the form
$$S[p(x)]=\sum_{x}f(p(x))\tag{3}$$
The question now is: what is the specific form of $f()$? We need some additional information to pin it down. For instance, suppose $X,Y$ are two independent random variables with probability distributions $p(x)$ and $p(y)$ respectively, so that the joint probability of $X,Y$ is $p(x)p(y)$. Because the two random variables are independent, their joint distribution $p(x)p(y)$ and the two individual distributions $p(x),p(y)$ carry equivalent information (from the joint density we can compute the individual densities, and from the individual densities we can reconstruct the joint density). That is,
3. When $X,Y$ are independent random variables, we have
$$S[p(x)p(y)]=S[p(x)]+S[p(y)]\tag{4}$$
In fact, constraints 1, 2, and 3 together are enough to pin down the expression for entropy. To determine the form of $f()$ from equation $(4)$, we only need to start from the simplest case of a binary distribution. Suppose $X,Y$ are both binary random variables, $X$ has distribution $p,1-p$, and $Y$ has distribution $q,1-q$, so the joint distribution is $pq,p(1-q),(1-p)q,(1-p)(1-q)$. According to equation $(4)$, we then have
$$\begin{aligned}&f(pq)+f\big(p(1-q)\big)+f\big((1-p)q\big)+f\big((1-p)(1-q)\big)\\ =&f(p)+f(1-p)+f(q)+f(1-q)\end{aligned}\tag{5}$$
This is a functional equation in $f()$, and with suitable reasonable restrictions it has a unique solution. Here we'll work out a solution without proving its uniqueness. The derivation is somewhat exploratory: we notice that the left-hand side involves products of the variables, such as $pq$, while the right-hand side involves the variables individually, such as $p$. Recalling basic mathematics, the operation that turns products into sums is the logarithm, so let's try setting $f(x)=h(x)\ln x$, giving
$$\begin{aligned}&h(p)\ln p+h(1-p) \ln (1-p)+h(q)\ln q+h(1-q)\ln (1-q)\\ =&h(pq)\ln p+h(pq)\ln q \\ &+ h\big(p(1-q)\big)\ln p + h\big(p(1-q)\big)\ln(1-q)\\ &+h\big((1-p)q\big)\ln(1-p)+h\big((1-p)q\big)\ln q \\ &+ h\big((1-p)(1-q)\big)\ln(1-p)+h\big((1-p)(1-q)\big)\ln(1-q)\end{aligned}\tag{6}$$
Looking long and messy and confusing? Don't worry, we're almost there. Let's group together terms with the same logarithm — for instance, the $\ln p$ term is
$$\big[h(p)-h(pq)-h(p(1-q))\big]\ln p\tag{7}$$
The remaining three terms are similar. We notice that if $h()$ is a linear function, the expression above vanishes exactly, and the remaining three terms vanish too — the equation is automatically satisfied! So we've found a solution:
$$f(x)=\alpha x\ln x\tag{8}$$
And so we arrive at the expression for entropy:
$$S=\sum_{x}\alpha p(x)\ln p(x)\tag{9}$$
Finally, we still need to pin down $\alpha$. Of course, the value of $\alpha$ itself doesn't matter much — it's merely the unit in which information is measured — but the sign of $\alpha$ does matter. We require entropy to satisfy the following property:
4. The greater the amount of information, the greater the entropy.
Point 4 is really just there to match our intuitive conventions — if you preferred, you could equally well define things so that "the greater the amount of information, the smaller the entropy." Given this convention, we know that a deterministic event must have smaller entropy than an uncertain event (since uncertain events carry more information). A deterministic event has a probability distribution identically equal to 1, and its corresponding entropy is 0. For an uncertain event, taking again the binary distribution with probabilities $p,1-p$, we must have
$$\alpha p\ln p + \alpha (1-p)\ln (1-p) > 0\tag{10}$$
which forces $\alpha < 0$.
A Bit More Digression
Now that we've obtained the expression for entropy, we've come rather far — readers don't necessarily need all of this. I simply wanted to share my own understanding of where entropy comes from. Readers who care about applications of entropy but not so much about its origins can skip this section, while those who want to understand entropy from more angles may find this section a worthwhile reference.
I want to stress again: this article determines the expression for entropy through constraints 1, 2, 3, and 4 — these are the properties of entropy, and the expression is derived to satisfy them. Most textbooks do the opposite: they give the expression for entropy first, and only afterward derive properties 1, 2, 3, 4. In a sense, this puts the cart before the horse.
From the discussion above, we can see that entropy is no longer merely an abstraction from physics — it has become a fully independent object in its own right. Entropy originated in physics, but it has essentially outgrown its origins to become a powerful tool spanning information theory, physics, biology, and other fields. In fact, in physics applications, we can go the other way around: starting from the maximum entropy principle (discussed later), we can derive physical laws. In that sense, entropy is not merely a derived quantity, but can itself be the source of physical laws.
"Derivatives" of Entropy
With the definitions of entropy given in $(1)$ and $(2)$, we can now obtain some "derived" quantities, such as "joint entropy":
$$S[p(x,y)]=-\sum_{x}\sum_{y} p(x,y)\ln p(x,y)\tag{11}$$
This is simply the natural extension of single-variable entropy.
To set up the maximum entropy model discussed later, we need to introduce conditional entropy, which relates to the conditional distribution $p(y|x)$. But I feel that many textbooks make things needlessly complicated here, leaving readers confused. For instance, some textbooks define conditional entropy directly as
$$S(Y|X)=\sum_x p(x)S(Y|X=x)=-\sum_x p(x)\sum_y p(y|x)\log p(y|x)\tag{12}$$
while others define it directly as
$$S(Y|X)=-\sum_x\sum_y p(x,y)\log p(y|x)\tag{13}$$
These two expressions are equivalent, and of course both are correct. But I really have to ask: what kind of definition is this? A reader's first reaction might well be: why on earth is it defined this way? Can you just define things however you please — are you pulling my leg?
I honestly can't understand why the most direct, most intuitive definition isn't given up front. We already know that a conditional distribution is: given the joint distribution $p(x,y)$ and the distribution of $p(x)$, find the distribution of $Y$ once $X$ is fixed. So conditional entropy should naturally be: starting from the joint entropy, subtract off the entropy contributed by $X$, leaving:
$$S(Y|X)=S[p(x,y)]-S[p(x)]\tag{14}$$
In plain terms, conditional entropy says: originally there was this much uncertainty $S[p(x,y)]$, and then $p(x)$ brings in an amount of information $S[p(x)]$, reducing the uncertainty by that much; what remains is the conditional entropy. It's not hard to show that this equation $(14)$ is equivalent to equation $(12),(13)$, but clearly, equation $(14)$ is the one that carries obvious meaning.
Translated automatically with claude-sonnet-5; all equations are reproduced verbatim from the source. Copyright remains with the original author.