Minimum Entropy Principle (II): Lexicon Construction via ``Decisive Action''

Average Character Information Entropy

Suppose there is a corpus. If we segment it into words and use the word as the unit of Chinese, the information content of each word is -\log p_w. Therefore, we can calculate the time spent memorizing this corpus as: -\sum_{w \in \text{corpus}} \log p_w \tag{2.1} Here, w \in \text{corpus} denotes the summation over each word in the corpus without deduplication. If we do not segment it and understand it character by character, the time required is: -\sum_{c \in \text{corpus}} \log p_c \tag{2.2} According to our previous understanding, word segmentation is intended to reduce the memory burden, so theoretically: -\sum_{w \in \text{corpus}} \log p_w < -\sum_{c \in \text{corpus}} \log p_c \tag{2.3} Of course, many words appear repeatedly, so we can merge identical terms: -\sum_{w \in \text{lexicon}} N_w \log p_w < -\sum_{c \in \text{alphabet}} N_c \log p_c \tag{2.4} Where N_w and N_c are the frequencies of words and characters obtained from the corpus. Dividing both sides of Eq (2.4) by the total number of characters in the corpus, the right side becomes: -\sum_{c \in \text{alphabet}} \frac{N_c}{\text{total characters}} \log p_c = -\sum_{c \in \text{alphabet}} p_c \log p_c \tag{2.5} Where N_c / \text{total characters} = p_c is the frequency of character c. Thus, the above expression is the average information per character. The left side of (2.4) can be transformed as: \begin{aligned} \mathcal{L} &= -\sum_{w \in \text{lexicon}} \frac{N_w}{\text{total characters}} \log p_w \\ &= \left(-\sum_{w \in \text{lexicon}} \frac{N_w}{\text{total words}} \log p_w\right) \div \left(\frac{\text{total characters}}{\text{total words}}\right)\\ &=\left(-\sum_{w \in \text{lexicon}} \frac{N_w}{\text{total words}} \log p_w\right) \div \left(\frac{\sum\limits_{w \in \text{lexicon}} N_w l_w}{\text{total words}}\right)\\ &=\left(-\sum_{w \in \text{lexicon}} \frac{N_w}{\text{total words}} \log p_w\right) \div \left(\sum\limits_{w \in \text{lexicon}} \frac{N_w}{\text{total words}} l_w\right)\\ &=\frac{\mathcal{H}}{l} \end{aligned} \tag{2.6} Where N_w / \text{total words} = p_w is the frequency of word w, and l_w is the number of characters in word w. Thus, \mathcal{H} is the average information per word, and l is the average number of characters per word: \mathcal{H} = -\sum_{w \in \text{lexicon}} p_w \log p_w, \quad l = \sum_{w \in \text{lexicon}} p_w l_w \tag{2.7} Therefore, \mathcal{L} is actually the average information per character when memorizing by words, which is our ultimate goal to compare and optimize. We convert the total information into the average information per character to obtain a unified measurement standard.

Enrich Your Vocabulary

Is word segmentation really as effective at reducing learning difficulty as expected? I did a simple statistical analysis: after basic word segmentation on WeChat public account articles, \mathcal{H} \approx 10.8 bits, and each word averages 1.5 characters (l \approx 1.5), so \mathcal{L} = 7.2 bits. This is significantly smaller than the 9.65 bits for character-by-character memorization. This proves that in Chinese, memorizing by words is indeed easier than memorizing by characters.

The operation of “word segmentation” reduces the difficulty of learning Chinese, which is why word segmentation is usually the first step in Chinese NLP.

Simply put, after segmenting the language, the lexicon we need to memorize becomes larger, but the length of each sentence becomes shorter. Overall, the learning difficulty is reduced. Therefore, it is not difficult to understand why learning English requires memorizing words: enriching our vocabulary reduces the difficulty of learning the language.

The Journey of a Routine Begins Locally

First, we localize the average character information entropy \mathcal{L}. Localization refers to examining what kind of merger of two basic elements into a new element will lead to a decrease in \mathcal{L}. In this way, we can gradually merge elements to achieve the goal of entropy minimization. We use the term “basic elements” to generalize the problem because characters can be merged into words, words into phrases, and so on. This process is iterative, and the “basic elements” change during the iteration.

“Localization” is the foundation for most of the following content. Although the derivation process is lengthy, it involves simple operations that can be understood with a little thought.

Suppose the current frequency of i is N_i and the total frequency is N, then we can estimate p_i = N_i / N. If the character length of i is l_i, we can calculate the current: \mathcal{L} = \frac{\mathcal{H}}{l} = \frac{-\sum\limits_i p_i \log p_i}{\sum\limits_i p_i l_i} \tag{2.8} What if we merge two adjacent elements a and b into one item? Suppose the frequency of (a, b) is N_{ab}, then before merging, we estimate p_{ab} = N_{ab} / N. If we treat them as a single “word,” the total frequency actually decreases to \tilde{N} = N - N_{ab}, while \tilde{N}_a = N_a - N_{ab}, \tilde{N}_b = N_b - N_{ab}, and other frequencies remain unchanged. Thus, we can re-estimate the frequencies: \begin{aligned} \tilde{p}_{ab} &= \frac{N_{ab}}{\tilde{N}} = \frac{p_{ab}}{1 - p_{ab}} \\ \tilde{p}_{a} &= \frac{\tilde{N}_{a}}{\tilde{N}} = \frac{p_a - p_{ab}}{1 - p_{ab}}, \quad \tilde{p}_{b} = \frac{\tilde{N}_{b}}{\tilde{N}} = \frac{p_b - p_{ab}}{1 - p_{ab}} \\ \tilde{p}_{i} &= \frac{N_{i}}{\tilde{N}} = \frac{p_i}{1 - p_{ab}}, \quad (i \neq a, b) \end{aligned} \tag{2.9} Then: \begin{aligned} \tilde{\mathcal{H}} &= -\frac{1}{1 - p_{ab}} \Bigg\{ p_{ab} \log \left( \frac{p_{ab}}{1 - p_{ab}} \right) + \\ & \qquad \sum_{i=a,b} (p_i - p_{ab}) \log \left( \frac{p_i - p_{ab}}{1 - p_{ab}} \right) + \sum_{i \neq a, b} p_i \log \left( \frac{p_i}{1 - p_{ab}} \right) \Bigg\} \\ &= \frac{1}{1 - p_{ab}} (\mathcal{H} - \mathcal{F}_{ab}) \end{aligned} \tag{2.10} Where: \begin{aligned} \mathcal{F}_{ab} &= p_{ab} \log \frac{p_{ab}}{p_a p_b} - (1 - p_{ab}) \log (1 - p_{ab}) \\ & \quad + \sum_{i=a,b} (p_i - p_{ab}) \log \left( 1 - \frac{p_{ab}}{p_i} \right) \end{aligned} \tag{2.11} And: \begin{aligned} \tilde{l} &= \frac{p_{ab}}{1 - p_{ab}} (l_a + l_b) + \sum_{i=a,b} \frac{p_i - p_{ab}}{1 - p_{ab}} l_i + \sum_{i \neq a, b} \frac{p_i}{1 - p_{ab}} l_i \\ &= \frac{l}{1 - p_{ab}} \end{aligned} \tag{2.12} Therefore: \frac{\tilde{\mathcal{H}}}{\tilde{l}} - \frac{\mathcal{H}}{l} = -\frac{\mathcal{F}_{ab}}{l} \tag{2.13} Our goal is to make \tilde{\mathcal{H}} / \tilde{l} smaller, so clearly, a good “routine” should make \mathcal{F}_{ab} \gg 0.

A Simple and Elegant Approximation

The expression for \mathcal{F}_{ab} is too complex to easily find patterns, so we can make some approximations. p_{ab} \leq p_a, p_b always holds, and often we can even assume p_{ab} \ll p_a, p_b. In this case, using the natural logarithm: \begin{aligned} &\ln(1 - p_{ab}) \approx -p_{ab} \\ &\ln \left( 1 - \frac{p_{ab}}{p_i} \right) \approx -\frac{p_{ab}}{p_i} \end{aligned} \tag{2.14} Since this approximation requires the natural logarithm (\ln(1+x) \approx x), we change all \log below to the natural logarithm \ln. Substituting into the expression for \mathcal{F}_{ab} and removing terms of p_{ab} higher than the first order, we get: \mathcal{F}_{ab} \approx F_{ab}^* = p_{ab} \left( \ln \frac{p_{ab}}{p_a p_b} - 1 \right) \tag{2.15} This indicator is much simpler and more beautiful, where PMI(a, b) = \ln \frac{p_{ab}}{p_a p_b} is called Pointwise Mutual Information.

Using Taylor series, a more general expansion can be obtained: \mathcal{F}_{ab} = p_{ab} \left( \ln \frac{p_{ab}}{p_a p_b} - 1 \right) + \frac{1}{2} \left( \frac{1}{p_a} + \frac{1}{p_b} - 1 \right) p_{ab}^2 + \dots It can be seen (and strictly proven) that the approximation F_{ab}^* is always smaller than the true value of \mathcal{F}_{ab}. Therefore, F_{ab}^* = p_{ab} \left( \ln \frac{p_{ab}}{p_a p_b} - 1 \right) \gg 0 is actually a sufficient condition for \mathcal{F}_{ab} \gg 0.

The above discussion concerns the merger of two elements. If k basic elements \boldsymbol{a} = (a_1, \dots, a_k) are merged, we can similarly derive: \begin{aligned} \mathcal{F}_{\boldsymbol{a}} &= p_{\boldsymbol{a}} \ln \frac{p_{\boldsymbol{a}}}{\prod\limits_{i \in \boldsymbol{a}} p_i} - [1 - (k - 1) p_{\boldsymbol{a}}] \ln [1 - (k - 1) p_{\boldsymbol{a}}] \\ & \qquad + \sum_{i \in \boldsymbol{a}} (p_i - p_{\boldsymbol{a}}) \ln \left( 1 - \frac{p_{\boldsymbol{a}}}{p_i} \right) \end{aligned} \tag{2.16} Its approximation formula is: \mathcal{F}_{\boldsymbol{a}} \approx \mathcal{F}_{\boldsymbol{a}}^* = p_{\boldsymbol{a}} \left( \ln \frac{p_{\boldsymbol{a}}}{\prod\limits_{i \in \boldsymbol{a}} p_i} - 1 \right) \tag{2.17}

Derivations End, Lexicon Appears

Now we can see that to make the target \tilde{\mathcal{H}} / \tilde{l} smaller, we should have \mathcal{F}_{ab} \gg 0. Since a lower bound approximation of \mathcal{F}_{ab} is F_{ab}^*, we can use F_{ab}^* \gg 0 to determine which elements should be merged. Corresponding to the lexicon construction process, F_{ab}^* \gg 0 tells us which characters should be merged into words.

Based on the characteristics of F_{ab}^*, it is not difficult to see that a necessary condition for F_{ab}^* \gg 0 is \ln \frac{p_{ab}}{p_a p_b} > 1. That is, the mutual information must be at least greater than 1. Under this necessary condition, the larger the mutual information and the higher the co-occurrence frequency of a and b, the better. This tells us to judge whether to merge elements from both the perspective of co-occurrence frequency and mutual information.

In the matter of lexicon construction, there is another clever trick: the “inverse application” of F_{ab}^*. Equation F_{ab}^* tells us that when \mathcal{F}_{ab}^* \gg 0 is satisfied, the two elements should be merged. Conversely, if \mathcal{F}_{ab}^* is less than some \theta, should they be split? (Reverse thinking: from determining what to “merge” to determining what to “split,” the so-called “Decisive Action.”) In this way, we only need to use the formula for merging two elements to guide us in a rough segmentation of the corpus, and then perform statistical filtering on the segmentation results to obtain many words.

Thus, we obtain a simple and effective algorithm for building a lexicon:

1. Statistics: Count the frequency of each character (p_a, p_b) and the co-occurrence frequency of adjacent characters (p_{ab}) from a large corpus.

2. Segmentation: Set a frequency threshold min\_prob and a mutual information threshold min\_pmi. Then, in the corpus, split adjacent characters where p_{ab} < min\_prob or \ln \frac{p_{ab}}{p_a p_b} < min\_pmi (“Decisive Action,” equivalent to a rough word segmentation).

3. Truncation: After the segmentation in step 2, count the frequency p_{w'} of each “candidate word” and retain only those where p_{w'} > min\_prob.

The dictionary obtained from the first three steps still has redundancy. This is manifested as: If you directly use this dictionary to build a 1-gram word segmentation model, some words in the dictionary will never be segmented out because those words can be represented by their sub-words, and the product of the sub-words’ probabilities is greater than the probability of the word itself. For example, in experiments, because the mutual information of “of, main” and “main, ly” are both greater than 1, the “word” “of mainly” appeared in the lexicon. However, statistics show that p(\text{of mainly}) < p(\text{of})p(\text{mainly}). Thus, this word will not be segmented out in 1-gram model segmentation. Keeping this “word” in the lexicon only wastes memory, so “of mainly” should be removed, and its frequency should be added to the words “of” and “mainly.”

Therefore, based on this principle, we can filter out some candidate words:

1. Redundancy Removal: Sort the candidate words in the dictionary by the number of characters from most to least. Then, sequentially delete each candidate word from the lexicon, segment this candidate word using the remaining words and frequencies, and calculate the mutual information between the original word and the sub-words. According to Eq (2.17), if the mutual information is greater than 1, restore the word; otherwise, keep it deleted and update the frequencies of the segmented sub-words.

The effect of this “redundancy removal” step is quite obvious, removing 30% or even more than 50% of “failing” candidate words. Below are some of the filtered results (100 examples):

of research, on the, one of the, method of, is in, in China, the main, a kind of, -al/ic (suffix), systematic, is China, developing, aspects of, the way of, the social, more than, traditional, -ized (suffix), our, function of, need for, various, Chinese people, formation of, problem of, as a, material, famous, product’s, data of, in the, organized, period of, coming, structure of, information of, -style, good, some of, the traditional, cultural, standard of, goal of, main, for China, and society, people’s, regulated, regulation of, support of, the maximum, in a, -ism, value of, so-called, country and, of the main, characteristics of, amount of, ability of, in the middle, world’s, in the system, -er/or (suffix), space of, established, the highest, direction of, is not, general, is through, built, in his, the last, later, -al (suffix), major, in areas such as, here, power, field of, between people, specific, reaction of, degree of, obvious, aspect, electronic, everything, national, quantity of, discovery of, technology and, early, occurrence of, knowledge, is America, project’s, advantage of, in one

It can be seen that, except for “Chinese people,” the others are indeed words we recognize as “failing” (not true standalone words).

PS: The “redundancy removal” step requires some manual rules to down-weight long words, because a finite corpus is insufficient for the statistics of long words, leading to overestimation of their probabilities. Since these are “manual rules,” I leave them to the reader’s discretion and will not provide them explicitly here.

Is It Really This Simple?

Of course, even after these 4 steps, the algorithm seems too simple, which might lead one to doubt its effectiveness. Some readers might think: \ln \frac{p_{ab}}{p_a p_b} < min\_pmi does not imply \ln \frac{p_{abc}}{p_a p_b p_c} < min\_pmi. That is, the mutual information of two adjacent characters might be small, but the mutual information of three characters might be large. Is it too arbitrary to split based only on the mutual information of two characters?

There are indeed such examples. For instance, in some corpora, the mutual information between characters in names or specific terms might be small for pairs but large for triplets. However, in the context of Chinese lexicon construction, such cases are rare. Unlike English, where the basic units are 26 letters (resulting in only 676 pairs), Chinese has thousands of characters, meaning there are millions of possible character pairs (2-grams). Therefore, statistics on 2-grams are usually sufficient to reflect the combinatorial features of Chinese characters. If errors occur, it is likely because these words are not significant in the input corpus. Simply put, an error is just an error.

Therefore, we basically do not need to discuss the formulas for merging three or more elements. The neighbor-character discrimination algorithm described above is sufficient for many scenarios. Any attempt to improve it would inevitably involve introducing third-order or higher-order language models and might require dynamic programming, which would greatly reduce the algorithm’s efficiency. In other words, while there are ideas for improvement, the cost of improvement is somewhat high.

A New Interpretation of 1-gram Segmentation

With the previous discussion, it becomes very simple. From beginning to end, we look for routines to reduce the memory burden and lower the total information content of the corpus. We have: -\sum_{w \in \text{corpus}} \ln p_w = -\sum_{w \in \text{sentence} \subset \text{corpus}} \ln p_w \tag{2.18} This means minimizing the total information content is equivalent to minimizing the information content of each sentence. Thus, for a given sentence, the best segmentation scheme—let’s say w_1, w_2, \dots, w_n—should minimize the total information content of the sentence: -\sum_{k=1}^n \ln p(w_k) = -\ln \prod_{k=1}^n p(w_k) \tag{2.19} This is actually the 1-gram word segmentation model—maximizing the product of the probabilities of each word. But here, we have given it a new interpretation through the Minimum Entropy Principle.

The Core: Dynamic Programming

The 1-gram segmentation model can be solved via dynamic programming. Dynamic programming is one of the core algorithms in NLP; it is a method for finding the optimal path in a graphical model that satisfies the Markov assumption.

Finding the optimal path is generally a high-complexity problem. However, the existence of the Markov assumption allows for an efficient algorithm with a complexity of \mathcal{O}(n), known as dynamic programming or the Viterbi algorithm, proposed by Andrew Viterbi in 1967. The fundamental idea of dynamic programming is: If an optimal path is split into two parts, then each part is also a (locally) optimal path.

Specifically, in shortest-path word segmentation, dynamic programming means: Scan the sentence from left to right. When scanning to the current character, only retain the optimal segmentation result up to that character, as well as all “quasi-optimal sequences” passing through the current character (to prevent premature incorrect cuts).

For example, for the sentence “Famous works of Chinese and foreign science,” first scan the first character. It is the only segmentation result and is saved. Words passing through this character, like “Sino-foreign,” are also saved. That is, when scanning the first character, the temporary variables store two candidate results. In the second step, scan the second character. We know “Sino-foreign” can be split into two characters or treated as one word. Naturally, the latter has a higher probability, so the split result is discarded, and “Sino-foreign” is kept. However, words passing through the second character might include “Surgery,” so the possibility of “Sino / Surgery” should be kept. Thus, when scanning the second character, the candidates are “Sino-foreign” and “Sino / Surgery.”

Next, at the third character, since the probability of “Sino-foreign / Sci” is not as high as “Sino / Surgery,” the optimal scheme at this step is “Sino / Surgery.” But words passing through the third character include “Science,” so the possibility of “Sino-foreign / Science” is also kept. By the end of the sentence, we successfully segment it into “Sino-foreign / Science / Masterpiece.” The principle of the whole process is: retain the optimal scheme up to the current character and do not ignore any words passing through the current character (to avoid premature incorrect cuts).

I believe the importance of dynamic programming in NLP cannot be overstated. Whether you are dealing with traditional machine learning or deep learning, you must master the dynamic programming algorithm, not only knowing how to use it but also how to implement it yourself (combined with a Trie tree or AC automaton).