Recap of the Previous Episode
In the previous article, I shared my understanding of the Maximum Entropy Principle, including its significance, its solution, and some simple and common applications. At the end of the last post, we derived the normal distribution through the Maximum Entropy Principle to illustrate its profound connotations and broad significance.
In this article, I will introduce a model based on the Maximum Entropy Principle—the Maximum Entropy Model. This article introduces the Maximum Entropy Model in the context of supervised classification problems. So-called "supervised" means it is based on data that has already been labeled.
In fact, the Maximum Entropy Principle discussed in the second article is the primary focus; the Maximum Entropy Model is essentially just an extension or application of that principle.
The Maximum Entropy Model
Classification: What Does It Mean?
Before introducing the Maximum Entropy Model, let’s discuss a bit more about what a classification problem implies. Suppose we have a set of labeled data:
| Data x | 1 | 2 | 3 | 4 | 5 | 6 | \dots | 100 |
|---|---|---|---|---|---|---|---|---|
| Label y | 1 | 0 | 1 | 0 | 1 | 0 | \dots | 0 |
A classification problem involves providing a model where, if I tell the model x, the model can tell me the corresponding y. Therefore, it is natural to view the classification problem as a fitting problem—that is, finding a function y=f(x) to fit this data. There are many functions that can be used for fitting, ranging from simple linear functions (linear regression) and Logistic functions (Logistic regression) to complex multi-layer neural networks. All of these solve the classification problem by treating it as a fitting problem.
However, this perspective is not unique. We can also view the classification problem from a probabilistic perspective. Since almost nothing in the world is certain, when we input x, the output y value is not deterministic. For example, in the data above, when we input 1, it outputs 1 or 0 with a certain probability, it’s just that the probability of 1 is higher. In this case, the classification problem becomes a matter of finding the probability distribution of y given x, which is the conditional distribution p(Y|X).
As we learned in the previous article, the Maximum Entropy Principle is naturally designed to find probability distributions. Therefore, here, the Maximum Entropy Principle naturally combines with the classification problem to produce the Maximum Entropy Model.
The Maximum Entropy Model
Now, the classification problem has become the problem of finding the conditional distribution p(Y|X). We still use the Maximum Entropy Principle to solve it. The difference is that since it is a conditional distribution, the entropy we need to maximize is the conditional entropy (refer to 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} Therefore, by finding p(x,y) and p(x), we can determine the conditional distribution p(Y|X). Here, both p(x,y) and p(x) are unknown. However, we believe that through extensive statistics, we can obtain the empirical distribution \tilde{p}(x) of p(x) (since x is simply the data to be collected, this statistical approach is theoretically feasible). Thus, the only unknown distribution is p(x,y), and we concentrate our efforts on finding it. At this point, maximizing equation (37) is equivalent to maximizing S[p(x,y)].
How do we determine the relationship between x and y? Simple: Statistics! By analyzing the labeled data, we derive the probabilistic relationship between them. To describe this mathematically, we need to define feature functions: \chi(x,y) = \left\{ \begin{aligned} &1, \quad x,y \text{ satisfy a certain fact} \\ &0, \quad x,y \text{ do not satisfy that fact} \end{aligned} \right. \tag{39} For example, in the labeled data table provided above, we find that when x is odd, y=1, and when x is even, y=0. Therefore, we suspect the result is related to parity. Thus, we can define a feature function: \chi(x,y) = \left\{ \begin{aligned} &1, \quad \text{when } x \text{ is odd and } y=1 \\ &0, \quad \text{otherwise} \end{aligned} \right. \tag{40} Then, we count the number of occurrences N_{\chi} that satisfy the feature function and divide by the total number of samples N to get \tau = N_{\chi}/N. We assume that when the data is sufficient, this "count" represents the result in an average sense: E[\chi(x,y)] = \sum_{x,y} p(x,y)\chi(x,y) = \tau \tag{41} We can define multiple features, obtain multiple feature functions, and get 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 for the maximum entropy. Thus, it turns into a constrained maximization problem. In the second article, we already provided the result (similar to equation (20)): p(x,y) = \frac{1}{Z} \exp\left( -\sum_{i=1}^k \lambda_i \chi_i(x,y) \right) \tag{43} Where: Z = \sum_{x,y} \exp\left( -\sum_{i=1}^k \lambda_i \chi_i(x,y) \right) \tag{44} Note that we have solved for p(x,y). If we are only concerned with p(y|x), it is best to transform it into the form of p(y|x), namely: 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 related to x.
A Brief Discussion on Model Application
Next is the issue of solving the model. As mentioned, models related to the Maximum Entropy Principle have characteristics such as simple form and strong adaptability. However, they have a fatal flaw—they are difficult to solve and generally can only be solved through numerical methods. I do not have unique insights in this area, so I will not go into detail. Interested readers can refer to other literature, such as here.
Let’s look more closely at how to use the Maximum Entropy Model. Suppose we extract a feature that has N possible values (for example, the feature is the part of speech of a word, with values like verb, noun, adjective, etc.), and we are performing binary classification (such as sentiment analysis: positive or negative). In fact, we can construct 2N feature functions (verb-positive, noun-positive, verb-negative, noun-negative, and so on). Furthermore, if multiple features are extracted, the number of feature functions will be quite substantial. Therefore, the main work of the Maximum Entropy Model lies in (manually) extracting features. Once feature extraction is complete, the Maximum Entropy Model provides an optimal scheme for utilizing those features (the entropy maximization scheme).
Therefore, although the Maximum Entropy Model has strong adaptability (because it can find a probability distribution based on any constraints we propose, and the number of constraints is theoretically unlimited) and good performance (if it can be solved, the results are usually very good), its application is relatively narrow because we lack general means to extract features effectively. Consequently, for general classification problems, the Maximum Entropy Model is rarely used directly. Especially after the popularity of deep learning algorithms, the powerful fitting capabilities and excellent performance of multi-layer neural networks mean that we almost never use the Maximum Entropy Model for common classification problems anymore.
So when should we use this Maximum Entropy Model? We generally "pick out" problems suitable for it (generally, where feature values are binary or there aren’t many features). In these cases, the Maximum Entropy Model is appropriate, and as a standalone model, its performance is generally better than other models (please recall the significance of maximum entropy).
Concluding Remarks
This series concludes here. Many online articles or books also explain the derivation and solution of the Maximum Entropy Model, but I still feel that the way it is taught in textbooks is not clear or explicit enough. Aspects such as the definition of entropy, the meaning of entropy, the significance of maximum entropy, and the derivation of the Maximum Entropy Model did not fully satisfy me. Therefore, combining my own understanding, I wrote these three short articles, both as my own notes and as a way to share my understanding with everyone. If there are any inaccuracies, I welcome criticism from readers.
In this series, the Maximum Entropy Model is just an entry point. In fact, the focus of the three articles is the concept of entropy and the Maximum Entropy Principle; they are what deserve repeated contemplation. Entropy quantifies information and uncertainty, and we can use it to do many things. Although this series has ended, content regarding information and entropy will still appear frequently in future posts on this blog, because there is simply too much beautiful and necessary content to say about entropy.
Regarding the Maximum Entropy Model, readers can also refer to Dr. Wu Jun’s The Beauty of Mathematics. The book contains two chapters introducing the Maximum Entropy Model, along with many other data analysis materials and stories, all of which are well worth reading.
When reposting, please include the original address of this article: https://kexue.fm/archives/3567
For more detailed reposting matters, please refer to: Scientific Space FAQ