Entropy Matters: From Entropy and the Maximum Entropy Principle to the Maximum Entropy Model (I)

An Intuitive Perspective

Let’s start with the following example:

After the World Cup, everyone is concerned about who the champion is. Suppose I missed the World Cup and ask a spectator who knows the result, “Which team is the champion?” He is unwilling to tell me directly and wants me to guess. For every guess I make, he charges me one dollar to tell me if I am right. How much money do I need to pay him to find out who the champion is? I could number the teams from 1 to 32 and ask: “Is the champion team among numbers 1–16?” If he says yes, I would then ask: “Is the champion among 1–8?” If he says no, I naturally know the champion is among 9–16. In this way, it only takes 5 guesses to know which team is the champion. Therefore, the information value of knowing who the World Cup champion is is only worth 5 dollars.

The above example is cited from the chapter “On the Maximum Entropy Model” in Dr. Jun Wu’s book The Beauty of Mathematics. The premise of this example is that “I” know nothing about football—I haven’t studied it, nor have I heard any news about it. In this case, I can only rely on guessing. The most naive method would be to guess team by team: Is it China? Is it Brazil? Is it Japan? ... This way, I might have to ask 31 questions to get the final result. Clearly, this is not the most efficient method. In the example, we first number the teams (in data processing, we call this establishing an “index”) and then use binary search, which has an efficiency of \mathcal{O}(\log_2 N).

This gives us two insights: First, establishing an index and using binary search can greatly speed up the search process, though this is not the main point of this article; second, \log_2 N appears—the logarithm! It can be rewritten as: \log_2 N = -\log_2 \frac{1}{N} = -\sum_{N \text{ teams}} \frac{1}{N} \log_2 \frac{1}{N} This is exactly the form of equation (1). Here, because we know nothing about football, the probability of each team winning is the same, i.e., p = 1/N.

Readers might feel this example is too specific and the result not representative. Indeed, this is just an intuitive perception. It is also possible to understand it from a more abstract and precise mathematical perspective. In that case, our logic is reversed.

An Abstract Perspective

First, we hope to construct a formula to represent the amount of information, or equivalently, the degree of uncertainty, called “entropy.” (Note: here we are constructing a quantity based on our intended use, rather than obtaining a quantity and then proving it has such a use. The logic here is exactly the opposite: we construct what we need.) Since “entropy” is used to represent the amount of information, it should possess the following simple properties:

1. It is a function of the probability distribution p(x). For convenience of study, we also hope it is a smooth function.

2. It is additive, which means entropy has the form: S[p(x)] = \sum_{x} f(p(x)) \tag{3}

3. When X and Y are independent random variables: S[p(x)p(y)] = S[p(x)] + S[p(y)] \tag{4}

In fact, constraints 1, 2, and 3 are sufficient to determine the expression for entropy. To determine the form of f() from equation (4), we only need to start from the simplest binary distribution. Suppose X and Y are both binary random variables. The probability distribution of X is p, 1-p, and the probability distribution of Y is q, 1-q. Then the joint distribution is pq, p(1-q), (1-p)q, (1-p)(1-q). According to equation (4), we 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 for f(). With appropriate and reasonable restrictions, it has a unique solution. Here we attempt to solve it without proving the uniqueness of the solution. The solving process is exploratory. We notice that the left side consists of products of variables, such as pq, while the right side consists of single variables, such as p. Recalling mathematical concepts, we remember that the operation that turns products into sums is the logarithm. So, let’s assume f(x) = h(x) \ln x, which gives: \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} Is it long, messy, and dizzying? Don’t worry, we are almost at the finish line. We group the terms with the same logarithm together. For example, the \ln p terms are: \big[h(p) - h(pq) - h(p(1-q))\big] \ln p \tag{7} The remaining three terms are similar. We find that if h() is a linear function, the above expression is exactly 0, and the other three terms are also 0, so the equation is automatically satisfied! Thus, we have found a solution: f(x) = \alpha x \ln x \tag{8} Therefore, we have the expression for entropy: S = \sum_{x} \alpha p(x) \ln p(x) \tag{9}

Finally, we need to determine \alpha. Of course, the value of \alpha itself is not important; it is merely the unit of information. However, the sign of \alpha is very important. We require entropy to have the following property:

4. The greater the information, the greater the entropy.

Point 4 is defined to align with our intuition. If you prefer, you could define “the greater the information, the smaller the entropy.” With our definition, we know that the entropy of a certain event must be smaller than that of an uncertain event (uncertain events contain more information). For a certain event, the probability distribution is identically 1, and the corresponding entropy is 0. For an uncertain event, using a binary distribution with probabilities p, 1-p, we must have: \alpha p \ln p + \alpha (1-p) \ln (1-p) > 0 \tag{10} Since p \ln p + (1-p) \ln (1-p) is always negative for p \in (0,1), we must have \alpha < 0.