The Principle of Minimum Entropy (III): ``Flying Elephant Across the River'' - Sentence Templates and Language Structure

Sentence Templates

For example, “What is the Y of X?” is a simple template. It contains explicit words like “is,” “the,” “of,” and “what,” as well as placeholders X and Y. By substituting any two nouns for X and Y, we get a grammatically correct sentence (whether it fits the facts is another matter). Many such templates can be listed: “X and Y,” “X’s Y,” “Can X do Y?,” “What are the Ys of X?,” “Is it X, Y, or Z?,” etc.

Of course, while we can extract as many templates as possible, a finite set of templates cannot cover the infinite variations of linguistic imagination. Therefore, the nested use of templates is more important. For instance, in the template “What is the Y of X?”, X can be replaced by the template “A and B,” resulting in “What is the Y of (A and B)?” In this way, templates nested within each other can generate a vast number of sentences.

Equivalence Classes

Next, given the template “What is the Y of X?”, how do we know what can be filled into X and Y?

We just said “substitute any two nouns,” but according to our approach so far, we only know how to build a lexicon. We don’t even know what a “noun” is, let alone that nouns should be filled in. In fact, we don’t need to know anything in advance. We can extract “equivalence classes” for each candidate position through a large corpus, where the candidate words for X form one word equivalence class, the candidate words for Y form another, and so on.

Of course, such a vision is ideal. In fact, the raw corpus we can currently obtain is in much worse condition. However, a thousand-mile journey begins with a single step; we first solve the ideal case and then consider general situations during actual use.

Below, we will explore how to obtain sentence templates from large amounts of raw corpus, and consider how to identify the templates used in a sentence, or even mine the hierarchical structure of the sentence.

Directed Acyclic Graphs

A Directed Acyclic Graph (DAG) is a graph theory model frequently encountered in NLP. In fact, the unigram segmentation model can be directly abstracted as a shortest path planning problem on a DAG. The construction of candidate template sets here also requires the use of a DAG.

Because we consider the Skip-Gram model, we can connect “word pairs” within a sentence that are relatively “compact” (having high mutual information). From a graph theory perspective, this constitutes a “Directed Acyclic Graph”:

We directly extract all paths from the graph. If a path skips adjacent nodes, we insert a placeholder (denoted as X below). This gives us the candidate template set. For example, from the figure above, the extracted candidate templates might be:

Computer X Mouse X
X ’s X has what X ’s X [particle]
X ’s X has what X [particle]
X relatively X

Algorithm Steps

We can describe the above process specifically as follows:

1. Segment the corpus into sentences and perform word segmentation;

2. Select a window size window, and count the frequency of each word (p_a, p_b) and the co-occurrence frequency of any two words within the window (p_{ab}) from the corpus;

3. Set a threshold for occurrence frequency min_prob and a threshold for mutual information min_pmi;

4. Traverse all sentences:

   • 4.1. Construct a graph for each sentence, treating words as nodes;

   • 4.2. For word pairs (a, b) within the window, if they satisfy p_{ab} > \text{min\_prob} and \ln\frac{p_{ab}}{p_a p_b} > \text{min\_pmi}, add a directed edge “a \rightarrow b” to the graph;

   • 4.3. Find all paths on the graph (isolated points also count as paths) and add them to the statistics as candidate templates.

5. Count the frequency of each “quasi-template,” sort them in descending order of frequency, and take the top portion.

This algorithm can be used for both sentence template extraction and simple phrase extraction (by setting the window to 1). Therefore, it essentially encompasses the lexicon construction mentioned in the previous article, making it a generalized extraction framework.

Performance Demonstration

Below are some sentence templates extracted from the Baidu Zhidao question set (the numbers are the counted frequencies, which can be ignored):

< Template: [X] ’s [X] > 20199
< Template: [X] [Question Particle] > 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] [Aspect Particle] > 2910
< Template: [X] [Aspect Particle] [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: Request [X] > 1547
< Template: [X] how is it > 1371

Note that templates like “X ’s X” or “X how X”, where a word is sandwiched between two placeholders, are trivial; they simply tell us that the word can be inserted into a sentence. Therefore, to see the effect more clearly, we exclude this type of template and get:

< Template: [X] [Question Particle] > 9695
< Template: [X] ’s > 3979
< Template: I [X] > 3766
< Template: [X] [Aspect Particle] > 2910
< Template: Request [X] > 1547
< Template: [X] how is it > 1371
< Template: [X] [Exclamatory Particle] > 1324
< Template: Has [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] is good > 798
< Template: [X] is [X] meaning > 728
< Template: Is [X] > 727
< Template: What does [X] mean > 721
< Template: What is [X] > 684
< Template: What to do > 589
< Template: Is there [X] > 582
< Template: How much is [X] > 550
< Template: From [X] > 526
< Template: What [X] > 522
< Template: What are the [X] > 490
< Template: [X] is what [X] > 483

From the results, our sentence template generation algorithm is indeed effective. These templates help us discover the rules of language usage. For example:

1. In templates like “X [Question Particle],” “X [Aspect Particle],” “X how is it,” the placeholder appears at the beginning, indicating these words can be placed at the end of a question.

2. In templates like “I X,” “Request X,” “Why X,” “May I ask X,” the placeholder appears at the end, indicating these words can be placed at the beginning of a question.

3. Templates like “Thank you” and “What to do” have no placeholders, indicating they can stand alone as sentences.

4. Templates like “X is X meaning” and “X is what X” reflect certain fixed collocations in the language.

From a general perspective, these templates describe syntactic-level linguistic phenomena. Of course, to avoid confusion with current mainstream syntactic analysis, we might as well call them language structural patterns, or simply “sentence templates.”

Projectivity Hypothesis

To achieve hierarchical decomposition of sentences, we can first draw on the “projectivity hypothesis” commonly used in syntactic analysis.

Projectivity roughly means that if a sentence can be divided into several “semantic blocks,” these blocks do not cross each other. That is, if words 1, 2, and 3 form one semantic block and words 4 and 5 form another, this is allowed. However, if words 1, 2, and 4 form one block and words 3 and 5 form another, this is impossible. Most languages, including Chinese and English, basically satisfy projectivity.

Structural Assumptions

To complete the hierarchical decomposition of a sentence, we need to make more complete assumptions about its composition. Inspired by the projectivity hypothesis, I believe the following assumptions can be made:

1. Each semantic block is a continuous substring of the sentence, and the sentence itself is also a semantic block;

2. Each semantic block is generated by a primary sentence template, where the placeholder parts of the template are also semantic blocks;

3. Each individual word can be seen as a trivial sentence template or a semantic block of minimum granularity.

In short, these three assumptions can be summarized in one sentence:

Every sentence is generated by the mutual nesting of sentence templates.

At first glance, this assumption might seem unreasonable, but careful thought reveals it is sufficient to describe the structure of most sentences. Readers might wonder: “Is it possible to use two sentence templates in parallel rather than nesting?” The answer is: probably not. If this happens, one simply needs to treat the “parallelism” itself as a template. For example, if “X and X” is treated as a template, then the two semantic blocks in this template are parallel. It can even be nested with itself to get “X and (X and X)” to describe more parallel phenomena.

Because we have made this assumption about language structure, once we identify the optimal combination of sentence templates for a sentence, we obtain its hierarchical structure—because according to the assumption, templates are combined via nesting, and nesting implies recursion, which is a hierarchical tree structure.

Decomposition Algorithm

With the assumptions about sentence structure, we can describe the template identification algorithm. First, let’s restate the word segmentation algorithm. The idea of unigram segmentation is:

Partition the sentence into words such that the sum of the log-probabilities of these words is maximized (the sum of information is minimized).

It can also be expressed as:

Find a series of words to cover every character in the sentence without overlap or omission, such that the sum of the log-probabilities of these words is maximized.

Previously, we thought of segmentation as cutting the sentence; this equivalent expression is the reverse—covering the sentence. With this reverse thinking, we can propose the template identification algorithm:

Find a series of sentence templates to cover every word in the sentence without overlap, omission, or crossing, such that the sum of the log-probabilities of these templates is maximized.

Of course, this is just the idea. In implementation, the main difficulty is handling placeholders. That is, each word in the sentence represents both the word itself and potentially a placeholder. This duality makes scanning and identification difficult. Fortunately, if we follow the language structure assumed above, we can transform it into a recursive operation:

In the optimal structural decomposition scheme, the decomposition scheme for each semantic block under the main template is also optimal.

Thus, we obtain the algorithm:

1. Scan all possible templates in the sentence (this can be done quickly using a Trie structure);

2. The score of each decomposition scheme equals the score of the sentence’s main template plus the score of the optimal decomposition scheme for each semantic block.

Results Display

Below are demonstrations of some simple examples analyzed using a limited number of templates. As we can see, hierarchical structural analysis of sentences has indeed been initially achieved.

+---> (Egg) can (be eaten) ?
|     +---> Egg
|     |     +---> Egg
|     +---> Can
|     +---> Eat
|     |     +---> Eat
|     +---> ?

+---> (Beef Egg) can (be eaten) ?
|     +---> Beef Egg
|     |     +---> Beef
|     |     +---> Egg
|     +---> Can
|     +---> Eat
|     |     +---> Eat
|     +---> ?

+---> (Apple) 's (color) is (what) ?
|     +---> Apple
|     |     +---> Apple
|     +---> 's
|     +---> Color
|     |     +---> Color
|     +---> Is
|     +---> What
|     |     +---> What
|     +---> ?

+---> (Pear and Apple and Banana) 's (color) is (what) ?
|     +---> (Pear and Apple) and (Banana)
|     |     +---> (Pear) and (Apple)
|     |     |     +---> Pear
|     |     |     |     +---> Pear
|     |     |     +---> and
|     |     |     +---> Apple
|     |     |     |     +---> Apple
|     |     +---> and
|     |     +---> Banana
|     |     |     +---> Banana
|     +---> 's
|     +---> Color
|     |     +---> Color
|     +---> Is
|     +---> What
|     |     +---> What
|     +---> ?

Of course, we must report the bad news along with the good; there are also some failed examples:

+---> (My delicious) 's (color of apple) is (what) ?
|     +---> (My) 's (delicious)
|     |     +---> My
|     |     |     +---> My
|     |     +---> 's
|     |     +---> Delicious
|     |     |     +---> Delicious
|     +---> 's
|     +---> (Apple) 's (color)
|     |     +---> Apple
|     |     |     +---> Apple
|     |     +---> 's
|     |     +---> Color
|     |     |     +---> Color
|     +---> Is
|     +---> What
|     |     +---> What
|     +---> ?

+---> (Apple) 's (color) is (what the meaning of what is) ?
|     +---> Apple
|     |     +---> Apple
|     +---> 's
|     +---> Color
|     |     +---> Color
|     +---> Is
|     +---> (What) 's (meaning) is (what)
|     |     +---> What
|     |     |     +---> What
|     |     +---> 's
|     |     +---> Meaning
|     |     |     +---> Meaning
|     |     +---> Is
|     |     +---> What
|     |     |     +---> What
|     +---> ?

We will analyze the failed examples later.

Jigsaw Puzzle

From words and phrases to sentence templates, we are always playing a jigsaw puzzle: as we assemble pieces, we find that putting these two together works well, so we merge them. Because merging items with high mutual information and treating them as a whole helps reduce the overall information entropy and thus the overall learning difficulty.

For sentence templates, if it’s hard to grasp in the context of Chinese, just recall how we learned English in primary and middle school—we probably learned many English sentence templates back then.

What is the Use?

“Sentence template” is a new concept proposed in this article, and using it to identify language structure is a new attempt. Readers might ask: what is the use of this?

I think the best way to answer this is to quote Isaac 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 sea-shore, 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 cite this to show that the fundamental reason for this exploration is not for some practical purpose, but for the pure exploration of the mysteries of natural language.

Of course, if the research results also possess certain application value, that would be even more perfect. From the current results, such value likely exists. In NLP, we face infinite variations of sentences, but in fact, “sentence patterns” are finite, which means sentence templates are also finite. If necessary, we can manually annotate the meanings of placeholders in each template, allowing the template structure to correspond with conventional syntactic descriptions. Decomposing (infinite) sentences through finite templates can make NLP scenarios more flexible and versatile.

Perhaps similar things have appeared in traditional natural language processing, but the content described here is purely the result of unsupervised mining and has a self-consistent theoretical description. It is a relatively complete framework, and the initial results are acceptable, so it is worth further considering its application value.

Moving Forward with Difficulty

After reading this article, the reader’s biggest feeling might be “total confusion”: Can it be simplified a bit more?

To answer this, I must mention that more than a month has passed since the previous article in this series, which seems like a long time. Formally, this article is just a simple extension of the previous one: isn’t it just extending adjacent associations to non-adjacent ones?

Indeed, formally it is. But extending this idea to possess both theoretical and practical value is not so simple or smooth. For example, in template generation, how to obtain all candidate templates without omission is a difficult problem. Secondly, after obtaining templates (whether automatically or manually), how to identify them in a sentence is even harder—both in theoretical thinking and programming implementation. There are many obstacles, requiring a clear grasp of tree structures and recursive programming. I spent over half a month debugging intermittently before I could get the whole process to run, and it is likely still incomplete.

So, it is perfectly normal if you feel confused. Even after finishing the work and writing this article, I still feel quite confused myself!

Ideas for Improvement

In the results display section, we also presented some failed examples. In fact, there might be many more.

We should look at this from two perspectives. On one hand, we have successful examples; for a purely unsupervised exploration, even getting a small portion of successful results is worth celebrating. On the other hand, for failed examples, we need to think about the reasons and consider solutions.

I believe the overall idea of sentence templates is sound, but the problem lies in the fact that we have not reached true semantic-level understanding. For example, in the first failed example, the result was:

(My delicious) ’s (color of apple) is (what) ?

Can we say this decomposition is completely wrong? Obviously not. Strictly speaking, this decomposition has no grammatical errors; it just doesn’t fit the semantics or our common sense. Therefore, it is not the fault of the sentence templates, but rather that we cannot yet fully integrate semantics to construct templates.

Recalling current mainstream syntactic analysis work, whether supervised or unsupervised, they basically combine “part-of-speech” (POS) to complete the analysis. This provides us with a direction: the next step in the Minimum Entropy series is to explore word clustering to better capture word meanings and linguistic commonalities.

Reprinted to please include this article address: https://kexue.fm/archives/5577

For more detailed reprint matters, please refer to: Scientific Space FAQ