"Sentence construction" is a classic task in primary school designed to help us understand and apply vocabulary. From the perspective of Natural Language Processing (NLP), it is a sentence expansion or sentence completion task, which essentially requires the ability to perform non-directional text generation. However, current mainstream language models are unidirectional (mostly forward, i.e., left-to-right; a few are backward, i.e., right-to-left). In a sentence construction task, the provided words do not necessarily appear at the beginning or the end of the sentence, making it impossible to use language models directly for this task.
In this article, we will introduce the paper "CGMH: Constrained Sentence Generation by Metropolis-Hastings Sampling". It uses MCMC sampling to enable unidirectional language models to perform non-directional generation. By simulating the human process of writing and polishing through insertion, deletion, and modification operations, it can complete various text generation tasks, such as sentence construction, in an unsupervised manner.
Problem Setting
Unsupervised text sampling can be directly performed by a language model. What we want to do is add certain signals \boldsymbol{c} to this sampling process so that it generates the text we expect. In the "Clear Objectives" section of the first article of this series, "[Text from Search] \cdot (1) From Text Generation to Search Sampling", we introduced the guiding ideology: quantitatively write down the goal we are looking for, and then maximize it or sample from it.
Quantitative goals do not have a fixed format, but generally, they take the following form: \rho(\boldsymbol{x}, \boldsymbol{c}) = p(\boldsymbol{x})\cdot \text{sim}(\boldsymbol{x}, \boldsymbol{c})\cdot \chi(\boldsymbol{x}, \boldsymbol{c}) where \boldsymbol{c} is the given condition and \boldsymbol{x} is the sentence we want to generate; p(\boldsymbol{x}) is the fluency score, usually provided by a language model, representing the desire for the target to be a natural sentence; \text{sim}(\boldsymbol{x}, \boldsymbol{c}) is a "soft" relevance score measuring some similarity between \boldsymbol{x} and \boldsymbol{c}; \chi(\boldsymbol{x}, \boldsymbol{c}) is a "hard" constraint, usually represented by an indicator function that is 1 when certain conditions are met and 0 otherwise. These three terms do not all have to be present, nor are they limited to three; they simply represent a way of thinking about design goals.
Theoretically, once we have \rho(\boldsymbol{x}, \boldsymbol{c}), we can construct the conditional probability: p(\boldsymbol{x}|\boldsymbol{c}) = \frac{\rho(\boldsymbol{x},\boldsymbol{c})}{\sum_{\boldsymbol{x}} \rho(\boldsymbol{x},\boldsymbol{c})} and then perform conditional sampling. However, sampling directly from p(\boldsymbol{x}|\boldsymbol{c}) is usually very difficult. Therefore, the MCMC method introduced in the second article, "[Text from Search] \cdot (2) From MCMC to Simulated Annealing", comes into play. It allows us to sample from p(\boldsymbol{x}|\boldsymbol{c}) even when we only know \rho(\boldsymbol{x}, \boldsymbol{c}).
Insertion, Deletion, and Modification
We primarily use the MH (Metropolis-Hastings) sampling method within MCMC. Constructing MH sampling requires a prior transition probability q(\boldsymbol{x} \leftarrow \boldsymbol{y}). The transition probability is the probability of modifying one sample into another. Theoretically, almost any transition probability is acceptable. However, from the "Analytical Thinking" section of the second article, we know that the effectiveness of MH sampling lies in the fact that each transition probability "fine-tunes" the current sample rather than "drastically changing" it. Therefore, the design of the transition probability here must follow this principle.
In this series, "samples" refer to the sentences to be generated. We consider the basic unit of a sentence to be a "word." Thus, the fine-tuning operations for a sentence can be designed as single-word operations, specifically including insertion, deletion, and modification (replace):
Insertion (insert): Insert a new word at a certain position in the sentence;
Deletion (delete): Delete a word from the sentence;
Modification (replace): Replace a word in the sentence with another word.
Note that these three operations have inverse relationships: insertion and deletion are inverses of each other, and modification is its own inverse. Including inverse operations is mandatory because the formula for the acceptance rate is \mathcal{A}(\boldsymbol{y} \leftarrow \boldsymbol{x}) = \min\left(1, \frac{q(\boldsymbol{x} \leftarrow \boldsymbol{y})p(\boldsymbol{y})}{q(\boldsymbol{y} \leftarrow \boldsymbol{x})p(\boldsymbol{x})}\right). It requires both q(\boldsymbol{x} \leftarrow \boldsymbol{y}) > 0 and q(\boldsymbol{y} \leftarrow \boldsymbol{x}) > 0 (i.e., the probability of changing from the original sentence to the new one and vice versa must be non-zero) to calculate the acceptance rate reasonably. Thus, we must define the transition probabilities for each operation and its inverse.
From a mathematical perspective, this is also a requirement for the transition probability to have a unique stationary distribution. As mentioned in the second article, the condition for a unique stationary distribution is that any two states are connected, meaning one can gradually transform from any sentence to any other sentence. Clearly, this is impossible without inverse operations.
Transition Probabilities
Now that we have three fine-tuning operations, we first need to define the probabilities of these operations occurring: p_{\text{insert}}, p_{\text{delete}}, p_{\text{replace}}. Since a properly defined MCMC method will eventually converge to the same stationary distribution, the specific values of these three do not significantly impact the final result. For simplicity, we can set p_{\text{insert}} = p_{\text{delete}} = p_{\text{replace}} = 1/3. Next, we define the transition probability for each operation.
First, we define the transition probability for "replace." Suppose the current sentence is \boldsymbol{x}=(x_1, x_2, \dots, x_l). We randomly select a position i from 1, 2, \dots, l, and then choose a new word y from the probability distribution: p(y|\boldsymbol{x}_{-i})=\frac{p(x_1,\dots,x_{i-1},y,x_{i+1},\dots,x_l)}{\sum_y p(x_1,\dots,x_{i-1},y,x_{i+1},\dots,x_l)} Then, let \boldsymbol{y}=(x_1,\dots,x_{i-1},y,x_{i+1},\dots,x_l) be the fine-tuned sentence. Here, p(x_1, x_2, \dots, x_l) is the sentence probability given by the language model. This is the transition probability q_{\text{replace}}(\boldsymbol{y} \leftarrow \boldsymbol{x}).
Readers who have seen "[Text from Search] \cdot (3) Text Sampling Based on BERT" will realize that p(y|\boldsymbol{x}_{-i}) is essentially BERT’s MLM (Masked Language Model). However, CGMH was work done before the release of BERT, so the concept of MLM likely didn’t exist then; there were only unidirectional language models. If we use a unidirectional language model to calculate p(y|\boldsymbol{x}_{-i}) according to the above formula, it means we have to calculate the probabilities of |V| sentences (traversing all words in the vocabulary for the i-th position), which is computationally expensive. To address this, the authors devised a method to filter out low-probability parts using the language model. Specifically, they use a forward language model \vec{p}(y|x_1,x_2,\dots,x_{i-1}) and a backward language model \stackrel{\leftarrow}{p}(y|x_l,x_{l-1},\dots,x_{i+1}) to predict the word distribution at position i, and then use: \min\big(\vec{p}(y|x_1,x_2,\dots,x_{i-1}),\, \stackrel{\leftarrow}{p}(y|x_l,x_{l-1},\dots,x_{i+1})\big) as an indicator to keep only the top K words as candidates. This way, they only need to calculate the probabilities for K sentences, reducing the computational load. Similarly, this indicator is not a hard requirement; for instance, if we only have a forward language model, using \vec{p}(y|x_1,x_2,\dots,x_{i-1}) as the indicator is also fine.
With q_{\text{replace}}(\boldsymbol{y} \leftarrow \boldsymbol{x}), defining q_{\text{insert}}(\boldsymbol{y} \leftarrow \boldsymbol{x}) for the "insert" operation becomes easy, as it can be treated as a variant of "replace." Let \boldsymbol{x}=(x_1, x_2, \dots, x_l). Randomly select a position i from 1, 2, \dots, l, l+1, insert an arbitrary new word \tilde{x} between x_{i-1} and x_i to get \tilde{\boldsymbol{x}} = (x_1,\dots,x_{i-1},\tilde{x},x_{i},\dots,x_l), and then calculate q_{\text{replace}}(\boldsymbol{y} \leftarrow \tilde{\boldsymbol{x}}) starting from \tilde{\boldsymbol{x}} with i as the sampling position to serve as q_{\text{insert}}(\boldsymbol{y} \leftarrow \boldsymbol{x}).
Finally, the "delete" operation is the simplest. Let \boldsymbol{x}=(x_1, x_2, \dots, x_l). Randomly select a position i from 1, 2, \dots, l, delete the word at that position to get \boldsymbol{y} = (x_1,\dots,x_{i-1},x_{i+1},\dots,x_l), and then directly set q_{\text{delete}}(\boldsymbol{y} \leftarrow \boldsymbol{x})=1.
Acceptance Probabilities
We have defined the transition probabilities, which essentially represent our action space for fine-tuning the sentence at each step. The transition probabilities defined above are independent of the task context; they do not depend on the condition information \boldsymbol{c}, only on an unsupervised language model. The specific task information is contained in the definition of the quantitative indicator \rho(\boldsymbol{x}, \boldsymbol{c}), which influences the final result by affecting the acceptance rate: \begin{aligned} \mathcal{A}_{\text{replace}}(\boldsymbol{y}\leftarrow\boldsymbol{x}) &= \frac{p_{\text{replace}} \cdot \rho(\boldsymbol{y},\boldsymbol{c}) \cdot q_{\text{replace}}(\boldsymbol{x}\leftarrow\boldsymbol{y})}{p_{\text{replace}} \cdot \rho(\boldsymbol{x},\boldsymbol{c}) \cdot q_{\text{replace}}(\boldsymbol{y}\leftarrow\boldsymbol{x})} = \frac{\rho(\boldsymbol{y},\boldsymbol{c}) \cdot q_{\text{replace}}(\boldsymbol{x}\leftarrow\boldsymbol{y})}{\rho(\boldsymbol{x},\boldsymbol{c}) \cdot q_{\text{replace}}(\boldsymbol{y}\leftarrow\boldsymbol{x})} \\[10pt] \mathcal{A}_{\text{insert}}(\boldsymbol{y}\leftarrow\boldsymbol{x}) &= \frac{p_{\text{delete}} \cdot \rho(\boldsymbol{y},\boldsymbol{c}) \cdot q_{\text{delete}}(\boldsymbol{x}\leftarrow\boldsymbol{y})}{p_{\text{insert}} \cdot \rho(\boldsymbol{x},\boldsymbol{c}) \cdot q_{\text{insert}}(\boldsymbol{y}\leftarrow\boldsymbol{x})} = \frac{\rho(\boldsymbol{y},\boldsymbol{c})}{\rho(\boldsymbol{x},\boldsymbol{c}) \cdot q_{\text{insert}}(\boldsymbol{y}\leftarrow\boldsymbol{x})} \\[10pt] \mathcal{A}_{\text{delete}}(\boldsymbol{y}\leftarrow\boldsymbol{x}) &= \frac{p_{\text{insert}} \cdot \rho(\boldsymbol{y},\boldsymbol{c}) \cdot q_{\text{insert}}(\boldsymbol{x}\leftarrow\boldsymbol{y})}{p_{\text{delete}} \cdot \rho(\boldsymbol{x},\boldsymbol{c}) \cdot q_{\text{delete}}(\boldsymbol{y}\leftarrow\boldsymbol{x})} = \frac{\rho(\boldsymbol{y},\boldsymbol{c}) \cdot q_{\text{insert}}(\boldsymbol{x}\leftarrow\boldsymbol{y})}{\rho(\boldsymbol{x},\boldsymbol{c})} \end{aligned} By the way, the above acceptance rates are missing the \min(1, \alpha) operation, but if our random number is sampled from U[0,1], adding this operation or not does not affect the result. Simply put, the acceptance rate means that if a fine-tuning operation increases \rho(\boldsymbol{x}, \boldsymbol{c}), it is very likely to be accepted; however, even if it decreases \rho(\boldsymbol{x}, \boldsymbol{c}), there is still a certain chance it will be accepted. Whether for random sampling or finding the maximum (simulated annealing), this randomness is very important; it is the key to jumping out of local optima.
The transition probabilities based on "insert," "delete," and "replace," combined with the MH sampling acceptance rate, essentially simulate the repeated polishing in our writing process: make a change, then see whether to keep it; keep good changes as much as possible, and avoid keeping bad ones.
Defining the Goal
As the final step of preparation, let’s discuss how to determine the indicator \rho(\boldsymbol{x}, \boldsymbol{c}). CGMH conducted three types of experiments: sentence construction from words, unsupervised sentence rewriting, and unsupervised sentence error correction. Their sampling processes are the same; the difference lies in \rho(\boldsymbol{x}, \boldsymbol{c}). For sentence construction, the constraint is a hard constraint: \rho(\boldsymbol{x}, \boldsymbol{c}) = p(\boldsymbol{x})\cdot \chi(\boldsymbol{x}, \boldsymbol{c}) where \boldsymbol{c} is the given set of words, and \chi(\boldsymbol{x}, \boldsymbol{c}) is 1 only when sentence \boldsymbol{x} contains all words in \boldsymbol{c}, and 0 otherwise. In implementation, we can record the positions of these words and ensure they are not selected during "replace" and "delete" operations. For unsupervised sentence rewriting and error correction, \boldsymbol{c} is the input sentence, and \chi(\boldsymbol{x}, \boldsymbol{c}) is replaced by some similarity indicator \text{sim}(\boldsymbol{x}, \boldsymbol{c}). Please refer to the original paper for specific settings.
Another point worth discussing is the choice of p(\boldsymbol{x}), which represents sentence fluency and is usually a language model: p(\boldsymbol{x}) = \prod_{t=1}^l p(x_t|\boldsymbol{x}_{< t}) However, directly using a language model tends to favor generating very short sentences, because generally, the longer the sentence, the lower the probability. To encourage generating longer sentences, it is suggested to add a power adjustment, changing it to p^{\gamma}(\boldsymbol{x}), where \gamma is a number slightly less than 1.
Experimental Results
With everything ready, we can proceed with the experiments. Here, the sentence construction task is demonstrated. To stay as consistent as possible with the method introduced in CGMH, only a forward language model is used, without an MLM model. The language model used is Huawei’s open-source Chinese GPT base model. The reference code is shared at:
Github Link: https://github.com/bojone/unsupervised-text-generation
Effect demonstration (translated from Chinese examples):
Input words: Guangzhou, Food, Opening
Initial state: Guangzhou food opening.
Step 0, insert: Guangzhou Food Festival opening.
Step 4, insert: Guangzhou Food Festival opening ceremony.
Step 11, insert: Guangzhou Food Festival opening month ceremony.
Step 13, delete: Guangzhou Food Festival opening ceremony.
Step 14, replace: Guangzhou Food Festival has opened.
Step 20, delete: Guangzhou Food Festival opening.
Step 50, replace: Guangzhou Food Web opening.
Step 52, insert: Guangzhou Food Web opening ceremony.
Step 54, replace: Guangzhou Food Festival opening ceremony.
Step 55, delete: Guangzhou Food Festival opening.
Step 63, insert: Guangzhou Food Festival opened yesterday.
Step 70, delete: Guangzhou Food Festival opening.
Step 74, insert: Guangzhou Food Festival has opened.
Step 76, delete: Guangzhou Food Festival opening.
Step 84, insert: Guangzhou Food Festival will open.
Step 90, replace: The opening of the Guangzhou Food Festival.
Step 93, insert: The opening ceremony of the Guangzhou Food Festival.
Step 96, delete: Guangzhou Food Festival opening ceremony.
Step 99, replace: Guangzhou Food Festival has opened.
Step 100, insert: Guangzhou’s Food Festival has opened.
Step 101, delete: Guangzhou Food Festival has opened.
Step 105, insert: Guangzhou Food Festival also opened.
Step 106, insert: Guangzhou’s Food Festival also opened.
Step 107, insert: Guangzhou people’s Food Festival also opened.
Step 108, replace: Guangzhou City’s Food Festival also opened.
Step 123, delete: Guangzhou’s Food Festival also opened.
Step 127, replace: Guangzhou’s Food Festival opened again.Input words: Science, Space
Initial state: Science space.
Step 3, insert: Science, space.
Step 5, delete: Science space.
Step 9, insert: Science is space.
Step 11, insert: Science refers to space.
Step 12, delete: Science refers space.
Step 15, delete: Science space.
Step 25, insert: Science space war.
Step 26, delete: Science space.
Step 28, insert: Science is space.
Step 29, delete: Science space.
Step 32, insert: Science space view.
Step 34, delete: Science space.
Step 42, insert: Science, space.
Step 43, replace: Science and space.
Step 44, delete: Science space.
Step 50, insert: Science is space.
Step 55, delete: Science space.
Step 63, insert: Science has space.
Step 65, delete: Science space.
Step 67, insert: Science is space.
Step 68, replace: Science manages space.
Step 69, insert: Science management space.
Step 70, insert: Science management space is large.
Step 71, insert: Scientific management space is large.
Step 73, delete: Science management space is large.
Step 75, delete: Science management space.
Step 78, replace: Science controls space.
Step 84, replace: Science regulates space.
Step 88, insert: Science regulation space is large.
Step 89, insert: The space for scientific regulation is large.
Step 90, insert: The space for scientific regulation is very large.
Step 94, replace: The space for scientific regulation increases.
Step 104, insert: The space for scientific regulation is increasing.
Step 110, replace: The space for scientific regulation will increase.
Step 125, insert: The space for scientific regulation will increase even more.Input words: Delicious, Snacks
Initial state: Delicious snacks.
Step 4, insert: Delicious snacks.
Step 5, delete: Delicious snacks.
Step 6, insert: Delicious snacks for sale.
Step 7, delete: Delicious snacks.
Step 18, insert: I love delicious snacks.
Step 20, replace: Most delicious snacks.
Step 23, replace: I love delicious snacks.
Step 24, replace: Most delicious snacks.
Step 26, replace: There are delicious snacks.
Step 27, delete: Delicious snacks.
Step 29, insert: Delicious snacks.
Step 30, delete: Delicious snacks.
Step 32, insert: Delicious snacks.
Step 33, delete: Delicious snacks.
Step 35, insert: Delicious snacks.
Step 37, replace: Delicious, snacks.
Step 38, replace: Delicious snacks.
Step 40, delete: Delicious snacks.
Step 53, insert: Most delicious snacks.
Step 54, replace: I love delicious snacks.
Step 58, insert: I love delicious snacks, right?
Step 59, replace: I love delicious snacks!
Step 60, delete: I love delicious snacks.
Step 61, delete: Delicious snacks.
Step 63, insert: Delicious, snacks.
Step 64, replace: Delicious snacks.
Step 66, delete: Delicious snacks.
Step 75, insert: Delicious snacks.
Step 76, delete: Delicious snacks.
Step 77, insert: Delicious snacks.
Step 81, delete: Delicious snacks.
Step 84, insert: Delicious snacks.
Step 89, replace: Delicious, snacks.
Step 90, insert: Delicious, snacks.
Step 92, replace: Delicious new snacks.
Step 93, delete: Delicious snacks.
Step 94, delete: Delicious snacks.
Step 96, insert: Delicious, snacks.
Step 98, replace: Delicious snacks.
Step 99, delete: Delicious snacks.
Step 104, insert: Most delicious snacks.
Step 105, insert: The most delicious snacks.
Step 106, delete: Most delicious snacks.
Step 107, delete: Delicious snacks.
Step 124, insert: Most delicious snacks.
Step 125, replace: I love delicious snacks.
Step 126, insert: But I love delicious snacks.
Step 127, replace: And I love delicious snacks.
In these examples, 128 iterations were performed for each sample. Some intermediate steps that did not change the sentence are not shown. Of course, due to the existence of randomness, running the same input repeatedly will usually result in different sentences, as MCMC is essentially a stochastic sampling scheme. These examples show that this is indeed a process of repeated fine-tuning, eventually yielding relatively readable sentences that satisfy the conditions, demonstrating the effectiveness of the CGMH method.
Theoretically, as long as we can write down the target \rho(\boldsymbol{x}, \boldsymbol{c}) we seek, we can apply this entire process to complete corresponding text generation tasks unsupervised (though it may require enough iterations, unlike sentence construction which shows results in about a hundred steps).
Conclusion
This article introduced and briefly implemented a method called "CGMH" that utilizes MCMC for unsupervised constrained text generation. It can be said to simulate the insertion, deletion, and modification operations in the human writing process, making the generation process quite interpretable. It is the first truly practical example in this series. In principle, CGMH encompasses the general process of text generation through discrete optimization. As long as a text generation task can be evaluated with a quantitative metric that does not rely on labels, this method can be attempted for unsupervised generation.
Original Address: https://kexue.fm/archives/8194