The Minimum Entropy Principle (III): "Flying Elephant Fording the River" — Sentence Templates and Language Structure
In the previous post The Minimum Entropy Principle (II): "Prompt Decision Making" for Vocabulary Construction], we carried out a series of mathematical derivations starting from the minimum entropy principle, ultimately arriving at equations $(2.15)$ and $(2.17)$. These tell us that if two elements have relatively large mutual information, we should merge them, since doing so helps reduce the "learning difficulty." Using this principle, we performed unsupervised vocabulary construction by exploiting the mutual information between adjacent characters.
Going from characters to words, and from words to phrases, is a matter of examining whether adjacent elements can be merged into a good "pattern." But why should a pattern necessarily consist of adjacent elements? Of course it doesn't have to. When we learn a language, we don't just pick up words and phrases—we also learn "fixed collocations," i.e., how words are properly combined. This is a manifestation of grammar, and it's what this post sets out to explore, with the hope of eventually achieving a degree of unsupervised syntactic analysis.
Since this time we're considering linguistic associations that span across non-adjacent words, I'll give it the name "Flying Elephant Fording the River" — that is,
The second move of the "Pattern Compendium" — "Flying Elephant Fording the River"
Language Structure
For most people, they don't actually know what grammar formally is; in their minds there are just some "fixed collocations," "set patterns," or, to put it more formally, "templates." In most cases, we produce grammatically valid utterances by drawing on such templates. Different people may have somewhat different sets of templates for speaking—this is what constitutes an individual's speaking style, or even their verbal tics. more
Sentence Templates
For example, "What is the Y of X" is a simple template: it has some fixed words like "the," "is," "what," and some placeholders X and Y. Substitute any two nouns for X and Y, and you get a grammatically valid sentence (whether it's factually correct is a separate matter). Many more templates of this kind can be listed: "X and Y," "the Y of X," "can X do Y," "what Y does X have," "is X Y or Z," and so on.
Example of sentence templates and their mutual nesting
Of course, although we can extract as many templates as possible, a finite set of templates can never cover the endless variety of linguistic imagination. So what matters more is the nested use of templates. For instance, in the template "What is the Y of X," X can itself be replaced by the template "A and B," giving "What is the Y of (A and B)." In this way, by nesting templates within one another, we can generate a great many sentences.
Equivalence Classes
Now, once we have a template like "What is the Y of X?", how do we know what can actually be filled in for X and Y?
A moment ago we casually said "substitute in any two nouns," but according to our approach so far, all we know how to do is build a vocabulary—we don't even know what a "noun" is, let alone know that nouns should be inserted here. In fact, we don't need to know any of this in advance. We can extract, from a large corpus, the "equivalence class" of candidates for each slot: the candidate words for X form one word equivalence class, the candidate words for Y form another, and so on.
The concept of sentence templates and equivalence classes
Of course, this is a rather idealized picture. In reality, the raw corpora we currently have access to are in much worse shape. But regardless, a tall building starts from level ground—let's first solve the idealized case, and worry about the general case when we get to actual usage.
Below we investigate, one step at a time, how to extract sentence templates from a large amount of raw corpus, and then how to recognize which templates are used in a given sentence, and even how to uncover the hierarchical structure of a sentence.
Generating Templates
Given what we learned from building the vocabulary in the previous post, it's actually not hard to devise an algorithm for generating sentence templates.
When we built the vocabulary, the statistical objects were characters; now the statistical objects are words. Moreover, words are formed from adjacent characters, but sentence templates need not be formed from adjacent words (otherwise they'd degenerate into words or phrases). So we also need to account for co-occurrence across non-adjacent words—this is exactly the Skip-Gram model from Word2Vec.
Directed Acyclic Graphs
The directed acyclic graph (DAG) is in fact a graph-theoretic model frequently encountered in NLP. Indeed, unigram-based tokenization can itself be recast directly as a shortest-path problem on a DAG. Here too, constructing the candidate template set relies on a DAG.
Because we're using the Skip-Gram model, we can link together "word pairs" within a sentence that are relatively "tight" (i.e., have relatively large mutual information). From a graph-theoretic perspective, this constitutes a "directed acyclic graph":
The directed acyclic graph formed by a sentence and its Skip-Gram relations
We simply take out every path in the graph; wherever it skips over adjacent nodes, we insert a placeholder (below, X denotes the placeholder throughout). This gives us the candidate template set. For example, from the figure above, the extracted candidate templates are:
computer X mouse X
X 's X has what X 's X ah
X 's X has what X ah
X compared to X
Algorithm Steps
We can describe the above procedure concretely as follows:
1. Split the corpus into sentences and perform word segmentation.
2. Choose a window size, and from the corpus tally the frequency of each word ($p_a,p_b$), as well as the co-occurrence frequency of any two words within the window ($p_{ab}$).
3. Set a threshold for occurrence frequency $min\_prob$ and a threshold for mutual information $min\_pmi$, respectively.
4. Traverse all sentences:
4.1 For each sentence, build a graph, treating the words in the sentence as nodes of the graph;
4.2 For each word pair $(a,b)$ within the window in the sentence, if $p_{ab} > min\_prob$ and $\ln\frac{p_{ab}}{p_a p_b} > min\_pmi$ are satisfied, add a directed edge "a-->b" to the graph;
4.3 Find all paths in the graph (isolated nodes also count as paths), and add them to the candidate-template tally.
5. Tally the frequency of each "proto-template," sort the "proto-templates" in descending order of frequency, and take the top portion.
This algorithm can be used both for extracting sentence templates and, just as simply, for extracting phrases—one only needs to set the window size to 1. So it essentially subsumes the vocabulary-construction approach from the previous post, meaning the algorithm above is a generalized extraction framework.
Demonstration of Results
Below are some sentence templates extracted from Baidu Zhidao's question set] (the numbers are the tallied frequencies, and can be ignored):
< Template: [X] 's [X] > 20199
< Template: [X] ? > 9695
< Template: [X] is [X] > 5358
< Template: [X] 's > 3979
< Template: [X] and [X] > 3919
< Template: I [X] > 3766
< Template: [X] has [X] > 3568
< Template: [X] (past tense marker) > 2910
< Template: [X] (past tense) [X] > 2702
< Template: [X] how [X] > 2340
< Template: [X] to [X] > 2254
< Template: [X] at [X] > 2234
< Template: [X] I [X] > 2147
< Template: [X] not [X] > 1708
< Template: seeking [X] > 1547
< Template: [X] how is it > 1371
Note that templates like "X 的 X" (X 's X) or "X 怎么 X" (X how X), where a single word is sandwiched between two placeholders, are actually trivial—they merely tell us that this word can be inserted into a sentence. So, to see a clearer effect, let's exclude this category of templates, giving:
< Template: [X] ? > 9695
< Template: [X] 's > 3979
< Template: I [X] > 3766
< Template: [X] (past tense marker) > 2910
< Template: seeking [X] > 1547
< Template: [X] how is it > 1371
< Template: [X] ah > 1324
< Template: have [X] > 1319
< Template: [X] what to do > 1232
< Template: why [X] > 1220
< Template: may I ask [X] > 1189
< Template: [X] (question particle) > 1099
< Template: [X] (question particle) > 1003
< Template: thank you > 997
< Template: how [X] > 903
< Template: at [X] > 894
< Template: now [X] > 874
< Template: how to [X] > 867
< Template: [X] good > 798
< Template: [X] is [X] meaning > 728
< Template: is [X] > 727
< Template: [X] what does it mean > 721
< Template: [X] is what > 684
< Template: what to do > 589
< Template: is there [X] > 582
< Template: [X] how much money > 550
< Template: from [X] > 526
< Template: what [X] > 522
< Template: [X] what kinds are there > 490
< Template: [X] is what [X] > 483
Judging from these results, our sentence-template generation approach is indeed effective, since these templates help us uncover the regularities of language use. For instance:
1. Templates like "X 吗" ("X?"), "X 了" ("X (past)"), "X 怎么样" ("How is X") have their placeholder at the front, indicating these words can appear at the end of a question (our corpus consists of questions);
2. Templates like "我X" ("I X"), "求X" ("seeking X"), "为什么X" ("why X"), "请问X" ("may I ask X") have their placeholder at the back, indicating these words can appear at the start of a question;
3. Templates like "谢谢" ("thank you") and "怎么办" ("what to do") contain no placeholder at all, showing they can stand alone as a complete sentence;
4. Templates like "X是X意思" ("X means X") and "X是什么X" ("X is what X") reflect certain fixed collocations of the language.
From a general standpoint, what these templates describe are syntactic-level linguistic phenomena. To avoid confusion with mainstream syntactic parsing, let's just call this "language structural regularities," or simply "sentence templates."
Structural Parsing
Just as with tokenization, once we've built the sentence templates, we also need an algorithm to recognize which templates are being used in a given sentence. Only once we've achieved this can we hope to identify the word equivalence classes from the corpus.
Recalling the tokenization algorithm: tokenization is merely a problem of splitting a sentence, and the resulting words have no "holes" (placeholders). But if we want to identify which templates are used in a sentence, these templates do have "holes," and they may be nested within one another—this makes recognition difficult. Yet, fortunately, once we manage to accomplish this, we obtain a hierarchical decomposition of the sentence, which is a very appealing goal.
The Projectivity Assumption
To achieve a hierarchical decomposition of a sentence, the first thing we can borrow is the "projectivity" assumption commonly used in syntactic parsing in general.
Roughly speaking, projectivity in language means that if a sentence can be divided into several "semantic chunks," these chunks do not cross one another. That is, if words 1, 2, 3 form one semantic chunk and words 4, 5 form another, that's allowed; but words 1, 2, 4 forming one chunk while words 3, 5 form another is not possible. Most languages, including Chinese and English, largely satisfy projectivity.
Structural Assumptions
To accomplish a hierarchical structural decomposition of a sentence, we need a more complete assumption about the compositional structure of the sentence. Inspired by the projectivity assumption, I believe the structure of a sentence can be assumed as follows:
1. Each semantic chunk is a contiguous substring of the sentence, and the sentence itself also counts as a semantic chunk;
2. Each semantic chunk is generated by one primary sentence template, where the placeholder portions of that template are themselves semantic chunks;
3. Each individual word can be regarded as a trivial sentence template, or equivalently as a semantic chunk at the finest granularity.
Put simply, these three assumptions can be condensed into one statement:
Every sentence is generated by sentence templates nested within one another.
At first glance this assumption may seem overly simplistic, but on closer reflection, it turns out to be sufficient to describe the structure of most sentences. Readers might wonder: "Could two sentence templates be used in parallel, rather than nested?" The answer is: this shouldn't happen. Because if such a case arises, we can simply treat the "parallelism" itself as a template—for instance, treating "X and X" itself as a template, so that the two semantic chunks within the "X and X" template are indeed parallel. Moreover, this template can even nest with itself to produce "X and (X and X)," describing even more instances of parallelism.
It is precisely because we've made this assumption about language structure that, once we identify the optimal combination of sentence templates for a given sentence, we obtain the sentence's hierarchical structure—because, by assumption, templates are combined via nesting, and nesting implies recursion, and recursion is itself a hierarchical tree structure.
Decomposition Algorithm
With this assumption about sentence structure in place, we can now describe the sentence-template recognition algorithm. First, let's restate the tokenization algorithm. The idea behind unigram-based tokenization is:
Split the sentence into words such that the sum of the log-probabilities of these words is maximized (i.e., the total information content is minimized).
It can also be phrased differently, as follows:
Find a sequence of words that covers every character in the sentence without repetition or omission, such that the sum of the log-probabilities of these words is maximized (i.e., the total information content is minimized).
We would normally think of tokenization as splitting a sentence, but this equivalent phrasing flips it around: it's about covering the sentence. With this reversed way of thinking, we can now propose the template-recognition algorithm:
Find a sequence of sentence templates that covers every word in the sentence without repetition, omission, or overlap, such that the sum of the log-probabilities of these templates is maximized (i.e., the total information content is minimized).
Of course, this is just the underlying idea. In actual implementation, the main difficulty lies in handling placeholders—that is, each word in a sentence represents both itself and, potentially, a placeholder, and this duality makes scanning and recognition difficult. Fortunately, however, if we adopt the language-structure assumption above, we can recast this as a recursive computation:
In the optimal structural decomposition, the decomposition of every semantic chunk under the primary template is also optimal.
Hierarchical structural parsing of a sentence, involving nested invocations of sentence templates
We can therefore obtain the following algorithm:
1. Scan the sentence for all possible templates that occur within it (this can be done quickly using a trie structure);
2. The score of each decomposition scheme equals the score of the sentence's primary template, plus the score of the optimal decomposition scheme for each corpus chunk.
Presentation of Results
Below are demonstrations on a few simple examples, using analysis performed with a limited number of templates. As we can see, this does indeed achieve, at a preliminary level, hierarchical structural parsing of sentences.
+---> (鸡蛋)可以(吃)吗
| +---> 鸡蛋
| | +---> 鸡蛋
| +---> 可以
| +---> 吃
| | +---> 吃
| +---> 吗
+---> (牛肉鸡蛋)可以(吃)吗
| +---> 牛肉鸡蛋
| | +---> 牛肉
| | +---> 鸡蛋
| +---> 可以
| +---> 吃
| | +---> 吃
| +---> 吗
+---> (苹果)的(颜色)是(什么)呢
| +---> 苹果
| | +---> 苹果
| +---> 的
| +---> 颜色
| | +---> 颜色
| +---> 是
| +---> 什么
| | +---> 什么
| +---> 呢
+---> (雪梨和苹果和香蕉)的(颜色)是(什么)呢
| +---> (雪梨和苹果)和(香蕉)
| | +---> (雪梨)和(苹果)
| | | +---> 雪梨
| | | | +---> 雪梨
| | | +---> 和
| | | +---> 苹果
| | | | +---> 苹果
| | +---> 和
| | +---> 香蕉
| | | +---> 香蕉
| +---> 的
| +---> 颜色
| | +---> 颜色
| +---> 是
| +---> 什么
| | +---> 什么
| +---> 呢
Of course, we shouldn't just report the successes and hide the failures—there are some failure cases too:
+---> (我的美味)的(苹果的颜色)是(什么)呢
| +---> (我)的(美味)
| | +---> 我
| | | +---> 我
| | +---> 的
| | +---> 美味
| | | +---> 美味
| +---> 的
| +---> (苹果)的(颜色)
| | +---> 苹果
| | | +---> 苹果
| | +---> 的
| | +---> 颜色
| | | +---> 颜色
| +---> 是
| +---> 什么
| | +---> 什么
| +---> 呢
+---> (苹果)的(颜色)是(什么的意思是什么)呢
| +---> 苹果
| | +---> 苹果
| +---> 的
| +---> 颜色
| | +---> 颜色
| +---> 是
| +---> (什么)的(意思)是(什么)
| | +---> 什么
| | | +---> 什么
| | +---> 的
| | +---> 意思
| | | +---> 意思
| | +---> 是
| | +---> 什么
| | | +---> 什么
| +---> 呢
We'll analyze the failure cases later.
Summary
For those left utterly bewildered, with all sorts of complaints to voice, please read this section first~
The Jigsaw Puzzle Game
From characters, to words, to phrases, and now to sentence templates, we've essentially been playing a jigsaw puzzle the whole time: we piece things together and, when we find that a particular pair fits well together, we merge them. Because merging items with high mutual information, and treating them as a single unit, helps reduce the overall information entropy, which in turn reduces the overall learning difficulty.
If sentence templates seem hard to wrap your head around in the context of Chinese, just recall how we learned English back in elementary or middle school—we must have learned a great many English sentence templates back then~
What's It Good For
"Sentence templates" is a new concept proposed in this post, and using it to identify language structure is likewise a new attempt. Readers can't help but ask: what's the use of this?
I think the best way to answer this question is to quote a passage from Newton:
I do not know what I may appear to the world, but to myself I seem to have been only like a boy playing on the seashore, and diverting myself in now and then finding a smoother pebble or a prettier shell than ordinary, whilst the great ocean of truth lay all undiscovered before me.
I quote this passage to make clear that the most fundamental reason for pursuing this investigation is not for some practical purpose, but purely to explore the mysteries of natural language.
That said, if the results of this research also happen to have some practical value, that would be all the more wonderful. Judging from the current results, such practical value may well exist. In NLP, the sentences we encounter are endlessly varied, but in fact "sentence patterns" are finite—which means sentence templates are finite too. If necessary, we could manually annotate the meaning of each placeholder in each sentence template, which would connect the structure of sentence templates to conventional syntactic descriptions. Using a finite set of sentence templates to decompose an (infinite) variety of sentences could make NLP more flexible and adaptable to a wide range of scenarios.
Perhaps something similar has appeared in traditional NLP before, but what's described in this post is purely the result of an unsupervised approach, with a self-consistent theoretical description to back it up—it counts as a fairly complete framework, and the preliminary results are passable. So it's worth thinking further about its potential applications.
Pressing Forward, Slowly
Having gotten through this post, readers' biggest reaction might be: "I'm utterly confused—could this be simplified further?"
To answer that, I have to mention: more than a month has passed since the previous post in this series, and only now am I formally publishing this one—which seems like a rather long time, doesn't it? On the surface, this post looks like nothing more than a simple generalization of the previous one: isn't it just generalizing from adjacent associations to non-adjacent ones?
Indeed, formally speaking, that's true. But turning this idea into something that has both theoretical and practical value was by no means simple or smooth. For instance, when generating sentence templates, how do we obtain all candidate templates without missing any—that alone is a hard problem. And once we have the sentence templates (whether automatically generated or manually entered), how do we recognize which templates are used in a given sentence—that's even harder. Whether in theoretical reasoning or in programming implementation, there are quite a few obstacles, requiring a clear grasp of tree structures and recursive programming. I spent more than half a month debugging on and off before I managed to get the whole pipeline working, and I suspect it's still not complete.
So it's perfectly normal if you feel utterly confused reading this—even I, having finished writing this post, still feel a bit dazed myself~
Directions for Improvement
In the Presentation of Results] section, we also showed some failure cases. In fact, there are probably even more failures than we showed.
We should look at this from two angles. On one hand, we do have successful examples, corresponding to purely unsupervised exploration—even if we only manage to get a small portion of results right, that's still cause for some satisfaction. On the other hand, for the failure cases, we need to think about why they fail, and consider possible solutions.
In my view, the overall sentence-template approach is not fundamentally flawed; the problem is that we haven't yet reached a true semantic-level understanding. Take the first failure example, where the result was:
((my delicious) apple's color) is (what)
Can we say this decomposition is entirely wrong? Clearly not—strictly speaking, this decomposition contains no grammatical error whatsoever. It simply doesn't align with semantics, doesn't match our common sense. So the fault doesn't lie with sentence templates per se, but rather with the fact that we haven't yet incorporated semantics adequately into building the templates.
Looking back at mainstream syntactic parsing work today, whether supervised or unsupervised, it basically has to incorporate "part-of-speech" information to complete the parsing. This points us toward a direction: the next step in the minimum-entropy series will be to investigate the clustering of words, in order to better capture word meaning and cross-linguistic commonalities.
Translated automatically with claude-sonnet-5; all equations are reproduced verbatim from the source. Copyright remains with the original author.