The Principle of Minimum Entropy (Part 2): "Decisive Cutting" for Vocabulary Construction

最小熵原理（二）：“当机立断”之词库构建 苏剑林 · 2018-04-24 · Machine Learning entropy unsupervised NLP minimum entropy

In this post, we introduce the first move of the "playbook of tricks" — "decisive cutting": 1) deriving the concept of average per-character entropy, and then, based on the principle of minimum entropy, deriving a mutual information formula; 2) completing an unsupervised construction of a vocabulary, and giving an information-theoretic interpretation of the unigram tokenization model, thereby demonstrating the basic methods and techniques for both generating and recognizing "tricks" (patterns).

This is both the first use case of the minimum entropy principle and the overarching outline of the entire "playbook of tricks."

Whether you practice it or not, the trick is already there, neither increasing nor decreasing.

Why We Need Words

From the previous post, we saw that if we assume we know nothing about Chinese, then at first we would treat Chinese text as a string formed by random combinations of "characters." But gradually we would notice that context matters — the text isn't a random combination of characters at all, but rather a random combination of "patterns." So, in order to lighten our memory burden, we start to dig out the language's "patterns." The first "pattern" is the fixed combination rule between adjacent characters — and these fixed combinations are exactly what we understand as "words."

Average Per-Character Entropy

Suppose we have a corpus that we've already segmented into words, and we use the word as the unit for Chinese. Then the amount of information carried by each word is $-\log p_w$, so we can compute the time it takes to memorize this corpus as

$$-\sum_{w\in \text{corpus}}\log p_w\tag{2.1}$$

Here $w\in \text{corpus}$ is a sum over every word occurrence in the corpus, without deduplication. If we don't segment into words and instead treat characters as the unit, then the time required is

$$-\sum_{c\in \text{corpus}}\log p_c\tag{2.2}$$more

Following the logic from the previous section, segmenting into words is supposed to reduce memory burden, so in theory we should have

$$-\sum_{w\in \text{corpus}}\log p_w < -\sum_{c\in \text{corpus}}\log p_c\tag{2.3}$$

Of course, many words repeat, so we can merge identical terms:

$$-\sum_{w\in \text{vocab}}N_w\log p_w < -\sum_{c\in \text{vocabulary}}N_c\log p_c\tag{2.4}$$

where $N_w,N_c$ are, respectively, the counted frequencies of words and characters in the corpus. Dividing both sides of equation $(2.4)$ by the total number of characters in the corpus, the right-hand side becomes

$$-\sum_{c\in \text{vocabulary}}\frac{N_c}{\text{total word count}}\log p_c = -\sum_{c\in \text{vocabulary}}p_c \log p_c\tag{2.5}$$

where $N_c/\text{total word count}=p_c$ is exactly the frequency of character $c$, so the expression above is the average information per character, while $(2.4)$, the left-hand side, can be rewritten as

$$\begin{aligned}\mathcal{L} =& -\sum_{w\in \text{vocab}}\frac{N_w}{\text{total word count}}\log p_w \\ =& \left(-\sum_{w\in \text{vocab}}\frac{N_w}{\text{total word count}}\log p_w\right)\div \left(\frac{\text{total word count}}{\text{total word count}}\right)\\ =&\left(-\sum_{w\in \text{vocab}}\frac{N_w}{\text{total word count}}\log p_w\right)\div \left(\frac{\sum\limits_{w\in \text{vocab}}N_w l_w}{\text{total word count}}\right)\\ =&\left(-\sum_{w\in \text{vocab}}\frac{N_w}{\text{total word count}}\log p_w\right)\div \left(\sum\limits_{w\in \text{vocab}}\frac{N_w}{\text{total word count}} l_w\right)\\ =&\frac{\mathcal{H}}{l}\end{aligned}\tag{2.6}$$

where $N_w/\text{total word count}=p_w$ is the frequency of word $w$, and $l_w$ is the number of characters in word $w$, so $\mathcal{H}$ is the average information per word, and $l$ is the average number of characters per word:

$$\mathcal{H} = -\sum_{w\in\text{vocab}} p_w\log p_w,\quad l=\sum_{w\in\text{vocab}} p_w l_w\tag{2.7}$$

Therefore, $\mathcal{L}$ is in fact the average information per character when memorizing by word, and this is the ultimate quantity we want to compare and optimize. By converting the total amount of information into a per-character average, we obtain a unified measure of comparison.

Enriching Your Vocabulary

Does segmenting into words really lower the difficulty of learning, as we'd hope? I did a rough calculation: after performing basic tokenization on articles from WeChat public accounts, we get $\mathcal{H}\approx 10.8$ bits, with an average of 1.5 characters per word, i.e. $l\approx 1.5$, giving $\mathcal{L}=7.2$ bits, which is clearly smaller than the 9.65 bits obtained by memorizing character by character. This confirms that, for Chinese, memorizing by word really is easier than memorizing character by character.

The operation of "word segmentation" lowers the difficulty of learning Chinese, and this is exactly why segmentation is usually the first step in Chinese NLP.

Intuitively, after segmenting a language into words, the vocabulary we need to memorize grows larger, but the length of each sentence becomes shorter — overall, the learning difficulty goes down. This also explains why, to learn English well, you have to memorize vocabulary: enriching our vocabulary reduces the difficulty of learning a language.

How Patterns Are Forged

Conversely, we can also use the minimization of $\mathcal{L}$ to guide us in constructing a vocabulary in an unsupervised way. This is the main content of the lesson "How Patterns Are Forged."

The Path of Patterns Begins Locally

First, we localize the average per-character entropy $\mathcal{L}$. By "localizing," we mean examining under what conditions merging two basic elements into a new element causes $\mathcal{L}$ to decrease, so that we can progressively merge elements to achieve the goal of minimizing entropy. We use the term "basic element" to keep the discussion general, since characters can be merged into words, words can be merged into phrases, and so on — this is an iterative process, and the "basic element" changes at each iteration.

"Localization" is the foundation of most of what follows. The derivation, though lengthy, involves only fairly simple operations, and should be understandable with a little thought.

Suppose the current frequency of $i$ is $N_i$, and the total frequency is $N$, so we can estimate $p_i=N_i/N$; suppose the number of characters in $i$ is $l_i$, so we can compute 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 $a,b$ into a single item? Suppose the frequency of $(a,b)$ is $N_{ab}$; before merging we can estimate $p_{ab}=N_{ab}/N$. If we treat them as merged into a single "word," then the total frequency actually decreases, becoming $\tilde{N}=N-N_{ab}$, while $\tilde{N}_a=N_a-N_{ab}$, $\tilde{N}_b = N_b-N_{ab}$, with all other frequencies unchanged; hence we can re-estimate each of 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}},\,\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}},\, (i\neq a,b) \end{aligned}\tag{2.9}$$

so that

$$\begin{aligned}\tilde{\mathcal{H}}=&-\frac{1}{1-p_{ab}}\Bigg\{p_{ab}\log\Big(\frac{p_{ab}}{1-p_{ab}}\Big) + \\ &\qquad \sum_{i=a,b}(p_i - p_{ab})\log\Big(\frac{p_i - p_{ab}}{1-p_{ab}}\Big)+\sum_{i\neq a,b} p_i\log \Big(\frac{p_i}{1-p_{ab}}\Big)\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}) \\ &+ \sum_{i=a,b}(p_i-p_{ab})\log\Big(1-\frac{p_{ab}}{p_i}\Big)\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 it's clear that a good "pattern" should satisfy $\mathcal{F}_{ab} \gg 0$.

A Simple, Elegant Approximation

The expression for $\mathcal{F}_{ab}$ is too complicated to reveal an obvious pattern, so let's make some approximations. $p_{ab} \leq p_a, p_b$ always holds, and in many cases we can even take $p_{ab}\ll p_a,p_b$, in which case, if we use the natural logarithm, we get

$$\begin{aligned}&\ln(1-p_{ab})\approx -p_{ab}\\ &\ln\Big(1-\frac{p_{ab}}{p_i}\Big)\approx -\frac{p_{ab}}{p_i}\end{aligned}\tag{2.14}$$

Since this approximation requires using natural logarithms ($\ln(1+x)\approx x$), we will from now on replace all instances of $\log$ below with the natural logarithm $\ln$. Substituting into the expression for $\mathcal{F}_{ab}$ and dropping terms of order two or higher in $p_{ab}$, we obtain

$$\mathcal{F}_{ab}\approx F_{ab}^*=p_{ab} \left(\ln \frac{p_{ab}}{p_{a} p_{b}}-1\right)\tag{2.15}$$

This criterion is now much simpler and more elegant, where $PMI(a, b)=\ln\frac{p_{ab}}{p_{a} p_{b}}$ is what we call the pointwise mutual information.

Using a Taylor series, we can obtain a more general expansion:
$$\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$$
One can see (and it can also be rigorously proven) that the approximation $F_{ab}^*$ is always smaller than the true value of $\mathcal{F}_{ab}$, so $F_{ab}^* = p_{ab} \left(\ln \frac{p_{ab}}{p_{a} p_{b}}-1\right)\gg 0$ is in fact a
sufficient condition
for $\mathcal{F}_{ab}\gg 0$.

The discussion above concerns the merging of two elements; if instead we merge $k$ basic elements $\boldsymbol{a}=(a_1,\dots,a_k)$, 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} -\big[1-(k-1)p_{\boldsymbol{a}}\big]\ln\big[1-(k-1)p_{\boldsymbol{a}}\big] \\ &\qquad+ \sum_{i\in\boldsymbol{a}}(p_i- p_{\boldsymbol{a}})\ln\Big(1-\frac{ p_{\boldsymbol{a}}}{p_i}\Big)\end{aligned}\tag{2.16}$$

with the approximate formula

$$\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}$$

Once the Derivation Is Complete, the Vocabulary Emerges

We can now see that, to make $\tilde{\mathcal{H}}/\tilde{l}$ smaller, we need $\mathcal{F}_{ab} \gg 0$, and a lower-bound approximation of $\mathcal{F}_{ab}$ is $F_{ab}^*$, so we can use $F_{ab}^*\gg 0$ to determine which elements need to be merged. Corresponding to the process of vocabulary construction, $F_{ab}^*\gg 0$ effectively tells us which characters need to be merged into words.

Given the properties of $F_{ab}^*$, it's not hard to see that a necessary condition for $F_{ab}^* \gg 0$ is $\ln \frac{p_{ab}}{p_{a} p_{b}} > 1$, meaning that the mutual information must be at least greater than 1. Under this necessary condition, the larger the mutual information, the better — and the higher the co-occurrence frequency of $a,b$, the better as well. This tells us that we should judge whether elements should be merged from two angles: co-occurrence frequency and mutual information.

There is also a clever trick for vocabulary construction — the "inverse application" of $F_{ab}^*$: equation $F_{ab}^*$ tells us that when $\mathcal{F}_{ab}^* \gg 0$ is satisfied, two elements should be merged. Conversely, shouldn't we split them when $\mathcal{F}_{ab}^* $ is below some threshold $\theta$? (This is inverse thinking — turning the question of determining what to "merge" into determining what to "split," what we call "decisive cutting.") In this way, we only need the merging formula for two elements to guide us in performing a rough split of the corpus, and then filter the split results statistically to obtain a large number of words.

This gives us a simple and effective algorithm for building a vocabulary:

1. Statistics: From a large corpus, count the frequency of each character ($p_a,p_b$), as well as the co-occurrence frequency of adjacent character pairs ($p_{ab}$);
2. Splitting: Set thresholds for the occurrence frequency $min\_prob$ and for the mutual information $min\_pmi$, then split adjacent characters in the corpus wherever $p_{ab} < min\_prob$ or $\ln\frac{p_{ab}}{p_a p_b} < min\_pmi$ ("decisive cutting" — equivalent to a single rough tokenization pass);
3. Truncation: After the splitting in step 2, count the frequency $p_{w'}$ of each "candidate word," and keep only the portion satisfying $p_{w'} > min\_prob$;

The dictionary obtained from these first three steps still contains redundancy. This shows up in the following way: if we directly use this dictionary to build a unigram tokenization model, some words in the dictionary will never actually get segmented out, because those words can be represented by their sub-words, and the product of the sub-word probabilities is even larger than the probability of the word itself. For instance, in experiments, because the mutual information of "的" ("of") and "主" ("main"), as well as of "主" and "要" ("essential"), are both greater than 1, the vocabulary ends up containing the "word" "的主要" ("of the main"). But statistically we find that $p(\text{main}) < p(\text{of})p(\text{main})$, so this word would never actually be split out under the unigram model — keeping it in the vocabulary only wastes memory. So we should remove "的主要" from the vocabulary and add its frequency count to the frequencies of "的" and "主要" instead.

Based on this principle, we can filter out some of the candidate words:

4. Deduplication: Sort the candidate words in the dictionary from longest to shortest, and for each candidate word in turn, remove it from the dictionary, then use the remaining words and their frequencies to segment this candidate word; compute the mutual information between the original word and its sub-words according to equation $(2.17)$. If the mutual information is greater than 1, restore the word; otherwise, keep it removed, and update the frequency counts of the resulting sub-words.

This "deduplication" step has a very noticeable effect, removing 30% or even over 50% of "sub-par" candidate words. Below is a sample of 100 words filtered out this way:

的研究, 上的, 的一个, 的方法, 是在, 在中国, 的主要, 的一, 性的, 系统的, 是中国, 发展的, 方面的, 的方式, 的社会, 以上的, 传统的, 化的, 我们的, 的功能, 的需要, 的各种, 中国人, 的形成, 问题的, 为一, 物质的, 名的, 产品的, 的数据, 里的, 组织的, 时期的, 来的, 的结构, 的信息, 式的, 好的, 的一些, 的传统, 文化的, 的标准, 的目标, 主要的, 为中国, 和社会, 人们的, 规定的, 的规定, 的支持, 的最大, 在一个, 主义的, 的价值, 所谓的, 国家和, 的主, 的特征, 量的, 能力的, 在中, 世界的, 系统中, 者的, 的空间, 成立的, 的最高, 的方向, 是不, 一般的, 是通过, 建立的, 在他, 的最后, 后来的, 体的, 的重大, 等方面的, 这里的, 力的, 领域的, 人之, 具体的, 的反应, 度的, 明显的, 面的, 的电子, 的一切, 民族的, 的数量, 的发现, 技术和, 早期的, 的发生, 知识的, 是美国, 项目的, 的优势, 在一

You can see that, apart from "中国人" ("Chinese people"), the rest are indeed "sub-par" words by our own intuition.

PS: This "deduplication" step requires some manual rules to downweight longer words, because a finite corpus provides insufficient statistics for long words, causing their estimated probabilities to be biased upward. Since these are "manual rules," I'll leave it to readers to work out on their own — I won't give an explicit version here.

Is It Really That Simple?

Of course, even after these four steps, this algorithm still seems too simple, which may make one doubt its effectiveness. Astute readers might point out: $\ln\frac{p_{ab}}{p_a p_b} < min\_pmi$ doesn't necessarily 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, while the mutual information of three characters could be large. Isn't it too crude to base the split purely on two-character mutual information?

Such examples do exist. For instance, in some corpora, the mutual information between "和" and "国" in "共和国" ("republic"), or between "心" and "如" in "林心如" (a name), is fairly small, while the three-character mutual information is large. However, in practice, when it comes to constructing a Chinese vocabulary, this situation is not very common, because Chinese differs from English: English's basic units are letters, of which there are only 26, so pairwise combinations number only 676, and even three-way combinations number just over ten thousand. Chinese characters, by contrast, number in the thousands, and in theory the number of character pairs (i.e., 2-grams) reaches into the millions — so simply counting 2-grams is already enough to reasonably capture the combinatorial characteristics of Chinese characters. So if such counterexamples do occur, it's most likely because these particular combinations aren't salient patterns in our input corpus. To put it bluntly: if it's wrong, it's wrong, and that's fine.

Thus we don't really need to work out the formula for merging three or more elements; the pairwise adjacent-character criterion described above suffices, and works well enough in most scenarios. If we wanted to improve it, we would inevitably need to introduce a third-order or higher-order language model, and might also need to bring in dynamic programming, which would greatly reduce the algorithm's efficiency. In other words, there is a path toward improvement, but it comes at a considerable cost.

Recognizing the First Kind of Pattern

Now we're able to find some "patterns" in natural language — namely, words. The next question is: given a sentence, how do we recognize the patterns within it? For the pattern we call "words," put simply: once we have a vocabulary and word frequencies, how do we actually tokenize a sentence?

A New Interpretation of Unigram Tokenization

Given the discussion above, this turns out to be simple. From start to finish, our goal in finding patterns has been to reduce memory burden, i.e., to lower the total information content of the corpus, and we have

$$-\sum_{w\in \text{corpus}}\ln p_w = -\sum_{w\in \text{sentence}\subset \text{corpus}}\ln p_w\tag{2.18}$$

That is, minimizing the total information content is equivalent to minimizing the information content of each individual sentence. So for a given sentence, the best tokenization scheme — call it $w_1,w_2,\dots,w_n$ — should be the one that minimizes 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 exactly the unigram tokenization model — maximizing the product of the probabilities of the individual words — except here, through the minimum entropy principle, we've given it a fresh interpretation.

The Core Algorithm: Dynamic Programming

The unigram tokenization model can be solved via dynamic programming. Dynamic programming is one of the core algorithms in NLP: it's the method for finding the optimal path through a graphical model that satisfies the Markov assumption.

Finding an optimal path in general is a problem of high complexity. However, because of the Markov assumption, there exists an efficient algorithm here, with complexity $\mathcal{O}(n)$. This algorithm is called dynamic programming, also known as the Viterbi algorithm, proposed by Andrew Viterbi in 1967. The fundamental idea behind dynamic programming is: if an optimal path is split into two parts, then each part is itself a (locally) optimal path.

Concretely, in shortest-path tokenization, dynamic programming means: scan the sentence from left to right, and when scanning up to the current character, keep only the best tokenization result up to that character, along with all "quasi-optimal sequences" that pass through the current character (to avoid cutting incorrectly too early).

For example, consider the sentence "中外科学名著" ("Famous Works of Chinese and Foreign Science"). First we scan "中": it is the only tokenization result so far, and we save it; since "中外" also passes through "中," we save that as well. So after scanning the first character, the temporary variable holds two candidate results: "中" and "中外." Next, we scan "外." Now we know that "中外" could be split as "中 / 外" (two single characters) or kept as the single word "中外" — the latter obviously has higher probability, so we discard "中 / 外" and keep only "中外." However, since "外科" also passes through "外," we should keep open the possibility of "中 / 外科." That is, after scanning the second character, we're holding two candidates: "中外" and "中 / 外科."
Next comes "科." Since the probability of "中外 / 科" is not as high as that of "中 / 外科," the current best tokenization is "中 / 外科." But since "科学" also passes through "科," we should still keep open the possibility of "中外 / 科学." So after scanning the third character, we hold "中 / 外科" and "中外 / 科学." Continuing this way, up to the last character, we finally arrive at the successful split "中外 / 科学 / 名著." The guiding principle throughout is: keep the best solution up to the current character, and don't discard any word that passes through the current character (to avoid cutting incorrectly too early).

Here, I think the importance of dynamic programming in NLP cannot be overstated. Whether you're working with traditional machine learning or deep learning, you must master the dynamic programming algorithm — not just know how to use it, but be able to implement it fully yourself (in conjunction with a Trie tree or an Aho–Corasick automaton).

Decoding the Beauty of Language

Although we have only preliminarily completed the task of unsupervised vocabulary construction, its implications go far beyond that. I invite readers to brainstorm for a moment: what we've done above is actually something quite remarkable. We didn't manually summarize a set of mechanical rules to construct a vocabulary. Instead, we identified an objective — the average per-character entropy — and tried to minimize it, and out popped a vocabulary.

Doesn't this have a flavor of "reenacting civilization"? Like a naive child, purely amusing ourselves with no particular goal in mind, we ended up successfully decoding the mystery of language.

Readers who have run the experiments themselves might object: a lot of what comes out doesn't look like the "words" we recognize! I would argue that as long as we give the model the capacity to evolve and a direction in which to evolve, it doesn't really matter what shape the resulting output takes. Take word segmentation as an example: we're not segmenting words for the sake of segmenting words — we segment words to prepare for downstream tasks. Given that, why should we care whether the resulting segmentation matches our own intuition? As already stated, the whole point of segmentation is to reduce the difficulty of downstream tasks. What we should really care about is our ability to handle the final task well.

This might sound like a cop-out, but in fact this is exactly what genuine artificial intelligence should feel like — if a group of truly intelligent machines were to gradually develop a civilization from scratch, why on earth should the outcome of their development match ours?

Of course, word segmentation is only the first step. The real reason discrepancies arise is that we've only concerned ourselves with segmentation, without yet performing more sophisticated structural and semantic analysis of language. In future posts we'll try to do more work, deriving further "patterns," and readers will gradually discover that the results we obtain do indeed align with observed linguistic phenomena.