"Entropy" Speaks: From Entropy and the Maximum Entropy Principle to the Maximum Entropy Model (Part 3)

“熵”不起：从熵、最大熵原理到最大熵模型（三） 苏剑林 · 2015-12-20 · Mathematics model probability maximum entropy entropy

Recap

In the previous article, I shared my understanding of the maximum entropy principle, including its meaning, how to solve for it, and a few simple and common applications. At the end of that article, we also derived the normal distribution using the maximum entropy principle, as a way to illustrate the depth and broad significance of the principle.

In this article, I'll introduce a model based on the maximum entropy principle—the maximum entropy model. I'll present the maximum entropy model in the context of a supervised classification problem; "supervised" here simply means that we're working from data that already has labels.

In fact, the maximum entropy principle covered in the second article is the real core of this series; the maximum entropy model is, in essence, merely an extension—or application—of that principle.

The Maximum Entropy Model

What Does Classification Really Mean?

Before introducing the maximum entropy model, let's take a detour and talk about what a classification problem really means. Suppose we have a batch of labeled data:

$$\begin{array}{c|cccccccc} \hline \text{data}x & 1 & 2 & 3 & 4 & 5 & 6 & \dots & 100 \\ \hline \text{label}y & 1 & 0 & 1 & 0 & 1 & 0 & \dots & 0\\ \hline \end{array}$$more

A classification problem, put simply, is about giving a model: I tell the model $x$, and the model tells me the corresponding $y$. So naturally, we can view classification as a fitting problem—that is, finding a function $y=f(x)$ that fits this batch of data. There are many functions we could use for fitting: simple ones such as linear functions (linear regression) or the logistic function (logistic regression), and more complex ones such as multilayer neural networks. All of these solve classification by treating it as a fitting problem.

However, this is not the only way to look at it—we can also approach classification from a probabilistic perspective. Since almost nothing in the world is truly deterministic, when we input $x$, the output value $y$ is not fixed either. For instance, in the data above, when we input 1, the output might be 1 or 0 with some probability—it's just that the probability of 1 is higher. From this viewpoint, the classification problem becomes: given $x$, find the probability distribution over $y$—that is, find the conditional distribution $p(Y|X)$.

And as we already know from the earlier article, the maximum entropy principle is, by its very nature, designed for finding probability distributions. So here, the maximum entropy principle naturally connects with the classification problem, giving rise to the maximum entropy model.

The Maximum Entropy Model

Now, the classification problem becomes one of finding the conditional distribution $p(Y|X)$. We still use the maximum entropy principle to solve it; the difference is that, since this is a conditional distribution, the entropy we need to maximize is the conditional entropy (see the first article):

$$S(Y|X)=S[p(x,y)]-S[p(x)]\tag{37}$$

and

$$p(y|x)=\frac{p(x,y)}{p(x)}\tag{38}$$

So, once we've found $p(x,y)$ and $p(x)$, we can obtain the conditional distribution $p(Y|X)$. Here, both $p(x,y)$ and $p(x)$ are unknown, but we assume that through large-scale statistics, we can obtain the empirical distribution $\tilde{p}(x)$ of $p(x)$ (since $x$ is simply data that needs to be collected, this kind of statistical estimation is theoretically feasible). Therefore, the only unknown distribution is $p(x,y)$, and we'll focus our efforts on solving for it. At this point, maximizing expression $(37)$ is equivalent to maximizing $S[p(x,y)]$.

How do we determine the relationship between $x$ and $y$? Simple—by statistics! By counting up the labeled data we already have, we can work out the probabilistic relationships between them. To describe this mathematically, we need to define a feature function:

$$\chi(x,y)=\left\{\begin{aligned}&1,\quad x,y\text{satisfies some fact}\\ &0,\quad x,y\text{does not satisfy some fact}\end{aligned}\right.\tag{39}$$

For example, in the labeled data table above, we notice that when $x$ is odd, the output is $y=1$, and when $x$ is even, the output is $y=0$. So we might guess that the outcome is related to parity, and accordingly define the feature function

$$\chi(x,y)=\left\{\begin{aligned}&1,\quad \text{if x is odd and y=1}\\ &0,\quad \text{other cases}\end{aligned}\right.\tag{40}$$

We then count how many samples satisfy this feature function, giving us a count $N_{\chi}$, and divide by the total number of samples $N$ to get $\tau=N_{\chi}/N$. We treat this "count," when the data is abundant enough, as an average-sense result:

$$E[\chi(x,y)]=\sum_{x,y} p(x,y)\chi(x,y)=\tau\tag{41}$$

We can define multiple features, yielding multiple feature functions, and thus multiple statistical results:

$$\left\{\begin{aligned}&E[\chi_1(x,y)]=\sum_{x,y} p(x,y)\chi_1(x,y)=\tau_1\\ &\vdots\\ &E[\chi_k(x,y)]=\sum_{x,y} p(x,y)\chi_k(x,y)=\tau_k\end{aligned}\right.\tag{42}$$

These become constraints on the maximum entropy problem, turning it once again into a constrained maximization problem. In the second article, we already derived the result (analogous to equation $(20)$):

$$p(x,y)=\frac{1}{Z}\exp\left(-\sum_{i=1}^k \lambda_i \chi_i (x,y)\right)\tag{43}$$

and

$$Z=\sum_{x,y} \exp\left(-\sum_{i=1}^k \lambda_i \chi_i (x,y)\right)\tag{44}$$

Note that here we've solved for $p(x,y)$; if we're only interested in $p(y|x)$, it's best to rewrite it in the form of $p(y|x)$, that is,

$$p(y|x)=\frac{p(x,y)}{p(x)}=\frac{1}{Z(x)}\exp\left(-\sum_{i=1}^k \lambda_i \chi_i (x,y)\right)\tag{45}$$

Here, $Z(x)=Z\times p(x)$ is a normalization factor depending on $x$.

A Brief Discussion of Practical Applications

Next comes the question of how to actually solve the model. As mentioned earlier, models based on the maximum entropy principle have the virtues of being simple in form and highly adaptable—but they also have a fatal drawback: they're hard to solve, and generally can only be tackled via numerical methods. I don't have particular insight of my own on this front, so I won't go into detail here. Interested readers can consult other references, such as this one.

Let's take a closer look at how the maximum entropy model is actually used. Suppose we extract a feature that can take $N$ possible values (say, this feature is a word's part of speech, taking values like verb, noun, adjective, etc.), and we're doing binary classification (such as sentiment classification: positive or negative). In that case, we could in principle construct $2N$ feature functions (verb-positive, noun-positive, verb-negative, noun-negative, and so on, for every combination). And if we extract multiple features, the number of feature functions can become quite substantial. So the main work involved in the maximum entropy model lies in (manually) extracting features; once feature extraction is done, the maximum entropy model provides an optimal scheme for making use of those features (the entropy-maximizing scheme).

As a result, while the maximum entropy model is highly adaptable (its adaptability comes from the fact that it can compute a probability distribution subject to any constraints we propose, with, in principle, no limit on the number of constraints) and performs very well (when it can be solved, the results are typically excellent), its range of application is fairly narrow, because we lack a general, effective way to extract features. So for ordinary classification problems, the maximum entropy model is rarely used directly. This is especially true now that deep learning has become dominant—the powerful fitting capacity and excellent performance of multilayer neural networks mean that we almost never resort to the maximum entropy model for typical classification tasks anymore.

So when should we actually use the maximum entropy model? Generally, we "pick out" the problems that are well-suited to it (typically, cases where the features take binary values, or where there aren't too many features). In such cases, the maximum entropy model is a good fit, and, as a standalone model, it often performs better than other alternatives. (Recall the deeper meaning of maximum entropy discussed earlier.)

Closing Remarks

This concludes the series. Many articles and textbooks online also cover the derivation and solution of the maximum entropy model, but I've always felt that the way it's typically presented in textbooks isn't clear or precise enough. Things like the definition of entropy, the meaning of entropy, the significance of maximum entropy, and the derivation of the maximum entropy model never quite satisfied me. So, drawing on my own understanding, I wrote these three short pieces—partly as my own notes, and partly to share my perspective with all of you. If there are any errors, I welcome readers' criticism.

In this series, the maximum entropy model was really just an occasion—the true focus of these three articles is the concept of entropy and the maximum entropy principle, which are well worth pondering again and again. Entropy quantifies information, quantifies uncertainty, and we can put it to use in all sorts of ways. Although this series has come to an end, the topics of information and entropy will surely keep resurfacing in future posts on this blog, because when it comes to entropy, there's simply too much beautiful material still worth talking about.

For more on the maximum entropy model, readers may also refer to Wu Jun's The Beauty of Mathematics, which contains two chapters introducing the maximum entropy model, along with plenty of other data analysis material and stories well worth reading.