The Minimum Entropy Principle (I): The Foundations of Unsupervised Learning

最小熵原理（一）：无监督学习的原理 苏剑林 · 2018-04-18 · Machine Learning entropy unsupervised NLP minimum entropy

Opening Remarks

Today, as end-to-end deep learning approaches have gradually swept through NLP, are you still willing to think about the fundamental principles behind natural language? We often talk about "text mining" — have you really felt the sense of "mining" in it?

An Unexpected Encounter

Some time ago I read an article about unsupervised syntactic parsing, and from its references I discovered the paper Redundancy Reduction as a Strategy for Unsupervised Learning. This paper describes how to recover English words from an English text with the spaces removed. Mapped onto Chinese, isn't this exactly vocabulary construction? So I read through it with great interest, and found that its line of thought was clear, its theory complete, and its results elegant — altogether a pleasure to read.

Although in hindsight this paper's practical value may not be huge, and its results have perhaps already been rediscovered by many people independently, it's worth noting: this is a paper from 1993! In an era when PCs weren't even yet widespread, such forward-looking research was already being done. Even though deep learning is now popular and NLP tasks have grown ever more elaborate — which is certainly progress — our genuine understanding of the principles underlying NLP may not actually exceed that of our predecessors from decades ago by much.

This paper achieves unsupervised vocabulary construction through "redundancy reduction." From the perspective of information theory, "redundancy reduction" is simply the minimization of information entropy. The article on unsupervised syntactic parsing also points out that "minimizing information entropy is the only viable approach to unsupervised NLP." I went on to study some related material, and combined with my own reflections, I found this remark genuinely thought-provoking. I believe that minimum entropy is likely the foundation not just of NLP, but of all unsupervised learning. more

What Is the Minimum Entropy Principle?

Readers have probably already heard of the maximum entropy principle and the maximum entropy model. So what, then, is this minimum entropy principle? Doesn't it contradict maximum entropy?

We know that entropy is a measure of uncertainty. The maximum entropy principle says that, when making inferences about an outcome, we should acknowledge our own ignorance and therefore maximize uncertainty, in order to obtain the most objective result. As for the minimum entropy principle, there are two ways to understand it:

1. Intuitive understanding: the evolution of civilization is always a process of exploration and discovery. Through our efforts, more and more things move from being uncertain to being certain, and entropy gradually tends toward a minimum. Therefore, to discover the hidden regularities in a pile of raw data (i.e., to replay the process of civilization), we should ask whether a given regularity helps reduce the overall information entropy, since this represents the direction in which civilization evolves — this is the "minimum entropy principle."
2. A slightly more rigorous understanding: "knowledge" has an intrinsic information entropy, representing its essential amount of information. But before we fully understand it, there will always be unknown factors, which means that when we express this knowledge, we inevitably introduce redundancy. So the entropy we estimate based on our current understanding is, in fact, an upper bound on the intrinsic entropy, and minimizing information entropy means finding ways to lower this upper bound — which in turn means reducing the unknown and approaching the intrinsic entropy.

So, following this path of the "minimum entropy principle," I reorganized earlier work and added some new extensions, and the result is this piece of writing. Readers will gradually see that the minimum entropy principle can be used to derive a rich set of results in a highly explanatory and inspiring way.

The Information Content of Language

Let's begin by examining the information entropy of language, and slowly enter the world of the minimum entropy principle.

Information Entropy = Learning Cost

From "Falling Short of 'Entropy': From Entropy and the Maximum Entropy Principle to the Maximum Entropy Model (I)" we know that the information entropy of an object is proportional to the negative logarithm of its probability, that is,

$$I(c)\sim -\log p_c\tag{1.1}$$

If we take the basic unit of Chinese to be the character, then Chinese text is a combination of characters, where $p_c$ denotes the probability of the corresponding character, and $-\log p_c$ is the amount of information carried by that character. Using a large corpus, we can estimate the average information content of each Chinese character:

$$\mathcal{H}_c = -\sum_{c\in\text{Chinese character}} p_c\log p_c\tag{1.2}$$

If $\log$ is taken with base 2, then according to figures circulating online, this value is about 9.65 bits (from my own statistics on a sample of articles, I got a value of about 9.5, which is roughly consistent). Similarly, the average information content of each letter in English is about 4.03 bits.

What does this number mean? Generally speaking, we can assume that the rate at which we receive or memorize information is fixed, so the amount of information is in effect equivalent to the time (or effort, etc.) required to receive it — and hence this number can also be said to reflect the difficulty (memory load) of learning that thing. For example, suppose we can only receive 1 bit of information per second; then memorizing an 800-character article character by character would take $9.65\times 800$ seconds.

Which Is Better, Chinese or English?

Since the entropy per Chinese character is 9.65 while the entropy per English letter is only 4.03, does this mean English is a more efficient form of expression?

Obviously we can't jump to such a conclusion. Is memorizing an English essay necessarily easier than memorizing a Chinese one?

For instance, if an 800-character Chinese essay is translated into English, it might come out to about 500 words; with an average of 4 letters per English word, the total information content would be $4.03\times 500\times 4 \approx 9.65\times 800$, which turns out to be roughly comparable. In other words, comparing the information content of different linguistic units is meaningless — what matters is the total information content, i.e., which language expresses the same meaning more concisely.

When two sentences carry the same meaning, the intrinsic information content of that "meaning" stays the same, but expressing it in different languages inevitably introduces "redundancy." So the amount of information required varies from language to language, and this amount of information is essentially equivalent to the memory load — the more cumbersome the language, the greater the information content, and the heavier the memory load. It's like teaching the same course: some teachers explain things clearly and concisely, and students grasp it easily, while other teachers ramble on and on, and students suffer through the learning. Even though it's the same course with essentially the same amount of underlying knowledge, a poorly teaching instructor introduces excessive irrelevant information during the lecture — this is "redundancy," and so we need to find ways to "reduce redundancy."

The fact that the estimates above for Chinese and English come out comparable suggests that both languages have, through long processes of optimization, arrived at roughly optimal states, and there's no clear sense in which one is superior to the other.

The Road to Patterns

Note that in the estimation above, we emphasized "memorizing character by character." Perhaps because we're so familiar with Chinese, we don't realize what this implies — in fact, this represents a very mechanical style of memorization, and it's not actually how we do things in practice.

There's Skill Even in Chanting Scripture

Recall the experience of memorizing classical poetry and classical Chinese prose as children. At first, we memorized by rote without any understanding at all — recognizing every individual character but having no idea what the string of characters as a whole meant. This is what we might call "reading character by character." Clearly, this makes memorization very difficult. Later on, we gradually came to grasp the compositional patterns of classical writing, and gradually began to understand the meaning of the poems or classical texts, which made memorization easier. By high school, we would also learn grammatical rules in classical Chinese such as "object fronting" and "postposed attributives," which greatly helped both our memorization and our understanding of classical texts.

Here comes the key point!

From this example of classical Chinese, we can sense that memorizing character by character, like chanting scripture, is very difficult; it becomes easier once we understand things in terms of word groupings; and it becomes even easier to memorize and understand if we can identify some grammatical regularities. But the speed at which we receive (memorize) information remains fixed — which means that steps like tokenization and grammar reduce the information content of language, thereby lowering our learning cost!

Thinking about it further, this applies not just to language but to everything we learn. If there's only a small amount of content to learn, we can simply force ourselves to memorize it directly. But when there's a lot to learn, we try to find the underlying "patterns" within it. For example, in Chinese chess, the game is divided into the opening, the middle game, and the endgame, and each phase has many established "set patterns" that lower the learning barrier for beginners and also form the basis for improvisation in complex positions. Likewise, we have texts like The Art of War and the Thirty-Six Stratagems, which are essentially compendiums of "patterns." By mining out these "patterns," we reduce the burden of memorizing things one by one — and the very emergence of a "pattern" is a process of reducing the amount of information.

At the end of the day, chant enough scripture, and you'll start noticing the patterns in it too.

Meeting Infinite Change with Constancy

In a nutshell: the rate at which we receive information is fixed, so the only way to speed up our learning is to reduce the redundant information in the learning target — to "discard the chaff and keep the essence." This is the minimum entropy principle in NLP, which is exactly the "redundancy reduction" mentioned at the outset. We can understand it as "eliminating unnecessary learning costs."

In fact, any efficient learning process must embody this idea, and teachers likewise design their lesson plans according to this same principle. In teaching, instructors tend to prefer teaching "general methods" (even if they involve more steps), rather than presenting a unique, clever trick for every single problem. When preparing for the college entrance exam, we work hard to identify various patterns in how questions are posed and how they should be solved. All of these are processes of reducing information entropy — and hence learning cost — by mining out "patterns." A "pattern" is precisely a method of "redundancy reduction."

A "pattern" is a kind of "fixed template." Only once we have accumulated enough patterns can we meet ten thousand changes with unchanging constancy. As the saying goes, "no matter how much things change, they never stray from their underlying essence" — and this "underlying essence" is, presumably, exactly the pattern. And when there are too many patterns to keep track of, we go on to look for "patterns of patterns" — meta-patterns — to lighten the burden of memorizing the patterns themselves. It's a layered, progressive process. It would seem that elevating individual phenomena into general patterns is precisely a manifestation of human intelligence.

Alright, enough abstract talk — let's now formally set out on the journey of mastering these patterns.