【Text via Search】⋅(4) Composing Sentences from Given Words via Insertion, Deletion, and Replacement

【搜出来的文本】⋅（四）通过增、删、改来用词造句 苏剑林 · 2021-02-25 · Machine Learning text generation sampling discrete optimization MCMC

"Composing a sentence from given words" is a classic elementary-school exercise that helps students understand and use vocabulary. From an NLP perspective, it's a sentence-expansion or sentence-completion task, and it actually requires the ability to generate text in an undirected manner. However, mainstream language models today generate text in a single direction (mostly forward, i.e., left-to-right, and occasionally backward, i.e., right-to-left), while the words given in a sentence-composition task need not appear at the start or end of the sentence. This means we cannot directly use a language model to accomplish this task.

In this post we introduce the paper CGMH: Constrained Sentence Generation by Metropolis-Hastings Sampling, which uses MCMC sampling to let unidirectional language models achieve undirected generation. By simulating the human process of writing and revising through insertion, deletion, and replacement operations, it accomplishes unsupervised text generation tasks such as sentence composition from given words.

Problem Setup

Unsupervised text sampling can be done directly with a language model, and what we still need to do is inject some signal $\boldsymbol{c}$ into this sampling process so that it generates the kind of text we expect. In the "Defining the Objective" section of the first article in this series, Text via Search (1): From Text Generation to Search Sampling, we already introduced the guiding philosophy of this series: write down, in quantitative form, the objective we're looking for, then either maximize it or sample from it. more

There's no fixed format for a quantitative objective, but generally speaking, it tends to take a form like $\setCounter{24}$:

\begin{equation}\rho(\boldsymbol{x}, \boldsymbol{c}) = p(\boldsymbol{x})\cdot \text{sim}(\boldsymbol{x}, \boldsymbol{c})\cdot \chi(\boldsymbol{x}, \boldsymbol{c})\end{equation}

Here $\boldsymbol{c}$ is the given condition, and $\boldsymbol{x}$ is the sentence we want to generate; $p(\boldsymbol{x})$ is a fluency score, typically given by a language model, reflecting the requirement that the generated result be a natural sentence; $\text{sim}(\boldsymbol{x}, \boldsymbol{c})$ is a "soft" relevance score measuring some kind of similarity between $\boldsymbol{x}$ and $\boldsymbol{c}$; and $\chi(\boldsymbol{x}, \boldsymbol{c})$ is a "hard" constraint, usually represented by an indicator function that equals 1 when certain conditions are satisfied and 0 otherwise. These three terms need not all appear, nor is the total limited to three terms — this is just one way of thinking about how to design an objective.

In theory, once we have $\rho(\boldsymbol{x},\boldsymbol{c})$, we can construct the conditional probability

\begin{equation}p(\boldsymbol{x}|\boldsymbol{c}) = \frac{\rho(\boldsymbol{x},\boldsymbol{c})}{\sum\limits_{\boldsymbol{x}} \rho(\boldsymbol{x},\boldsymbol{c})}\end{equation}

and then sample from it conditionally. However, directly sampling from $p(\boldsymbol{x}|\boldsymbol{c})$ is usually intractable, which is where the MCMC methods introduced in the second article, Text via Search (2): From MCMC to Simulated Annealing, come in handy — they let us sample from $p(\boldsymbol{x}|\boldsymbol{c})$ while only ever needing to know $\rho(\boldsymbol{x},\boldsymbol{c})$.

Insertion, Deletion, Replacement

We'll mainly use MH sampling from the MCMC toolbox, and constructing an MH sampler requires a prior transition probability $q(\boldsymbol{x}\leftarrow\boldsymbol{y})$. The transition probability describes the probability of modifying one sample into another. In theory, almost any transition probability is acceptable, but from the "Analysis and Reflection" section of Text via Search (2): From MCMC to Simulated Annealing, we know that the effectiveness of MH sampling relies on each step's transition probability making a "small tweak" to the current sample rather than a "drastic change." So the design of the transition probability here needs to follow the same principle.

Throughout this series, a "sample" refers to the sentence we want to generate, and we can treat the "word" as the basic unit of a sentence. So the fine-tuning operation on a sentence can be designed to act on a single word at a time, comprising three types: insert, delete, and replace.

Insert: insert a new word at some position in the sentence;
Delete: delete some word from the sentence;
Replace: replace some word in the sentence with another word.

Note that these three operations come in inverse pairs: insert and delete are mutual inverses, and replace is its own inverse. Including the inverse operations is essential, because the acceptance-rate formula 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)$, which requires that both $q(\boldsymbol{x}\leftarrow\boldsymbol{y}) > 0$ and $q(\boldsymbol{y}\leftarrow\boldsymbol{x}) > 0$ — i.e., the probability of transforming the original sentence into the new sentence, and the probability of transforming the new sentence back into the original — be nonzero in order for the acceptance rate to be computed sensibly. So we need to define the transition probability for every operation together with its inverse.

Mathematically, this is also required for the transition probability to have a unique stationary distribution. As we discussed in Text via Search (2): From MCMC to Simulated Annealing, the condition for a unique stationary distribution is that any two states be connected — meaning it must be possible to gradually transform any sentence into any other sentence. Clearly this would be impossible without inverse operations.

Transition Probability

Now that we have three kinds of fine-tuning operations — insert, delete, replace — we first need to define the probabilities $p_{\text{insert}},p_{\text{delete}},p_{\text{replace}}$ with which each occurs. Since a properly defined MCMC method will eventually converge to the same stationary distribution regardless, the specific values of these three probabilities have little effect on the final result; for simplicity we can just set $p_{\text{insert}} = p_{\text{delete}} = p_{\text{replace}} = 1/3$. Next we define the transition probability for each operation step by step.

The first thing to define is the transition probability for "replace." Suppose the current sentence is $\boldsymbol{x}=(x_1, x_2, \cdots, x_l)$. We randomly pick a position $i$ from $1,2,\cdots,l$, then draw a new word $y$ from the probability distribution

\begin{equation}p(y|\boldsymbol{x}_{-i})=\frac{p(x_1,\dots,x_{i-1},y,x_{i+1},\cdots,x_l)}{\sum\limits_y p(x_1,\dots,x_{i-1},y,x_{i+1},\cdots,x_l)}\end{equation}

and let $\boldsymbol{y}=(x_1,\dots,x_{i-1},y,x_{i+1},\cdots,x_l)$ be the fine-tuned sentence, where $p(x_1, x_2, \cdots, x_l)$ is the sentence probability given by the language model. This gives us the transition probability $q_{\text{replace}}(\boldsymbol{y}\leftarrow\boldsymbol{x})$ for "replace."

Readers who've read Text via Search (3): Text Sampling Based on BERT will immediately recognize that $p(y|\boldsymbol{x}_{-i})$ is essentially BERT's MLM model. But CGMH predates the release of BERT, so at the time there was presumably no concept of MLM yet — only unidirectional language models existed. If we were to compute $p(y|\boldsymbol{x}_{-i})$ using a unidirectional language model according to the formula above, that would mean computing the probability of $|V|$ different sentences (enumerating every word in the vocabulary at position $i$), which is fairly expensive. To address this, the authors came up with a trick: first use language models to filter out low-probability candidates. Specifically, they use a forward language model $\stackrel{\rightarrow}{p}(y|x_1,x_2,\cdots,x_{i-1})$ and a backward language model $\stackrel{\leftarrow}{p}(y|x_l,x_{l-1},\cdots,x_{i+1})$ to each predict the word distribution at position $i$, and then use

\begin{equation}\min\big(\stackrel{\rightarrow}{p}(y|x_1,x_2,\cdots,x_{i-1}),\, \stackrel{\leftarrow}{p}(y|x_l,x_{l-1},\cdots,x_{i+1})\big)\end{equation}

as a scoring criterion, keeping only the top $K$ words with the highest scores as candidates. This way we only need to compute the probability of $K$ sentences, reducing the computational cost. Again, this criterion isn't strictly fixed — for instance, in many cases when we only have a forward language model, it's perfectly fine to just use $\stackrel{\rightarrow}{p}(y|x_1,x_2,\cdots,x_{i-1})$ directly as the filtering criterion.

With $q_{\text{replace}}(\boldsymbol{y}\leftarrow\boldsymbol{x})$ in hand, defining $q_{\text{insert}}(\boldsymbol{y}\leftarrow\boldsymbol{x})$ for the "insert" operation is also easy, since it can be treated as a variant of "replace." Let $\boldsymbol{x}=(x_1, x_2, \cdots, x_l)$; randomly pick a position $i$ from $1,2,\cdots,l,l+1$, insert an arbitrary new word $\tilde{x}$ between $x_{i-1},x_i$ to get $\tilde{\boldsymbol{x}} = (x_1,\dots,x_{i-1},\tilde{x},x_{i},\cdots,x_l)$, and then, starting from $\tilde{\boldsymbol{x}}$ and using $i$ as the sampling position, compute $q_{\text{replace}}(\boldsymbol{y}\leftarrow\tilde{\boldsymbol{x}})$ as $q_{\text{insert}}(\boldsymbol{y}\leftarrow\boldsymbol{x})$.

Finally, the "delete" operation is the simplest. Let $\boldsymbol{x}=(x_1, x_2, \cdots, x_l)$; randomly pick a position $i$ from $1,2,\cdots,l$, then deleting the word at that position gives $\boldsymbol{y} = (x_1,\dots,x_{i-1},x_{i+1},\cdots,x_l)$, and we simply set $q_{\text{delete}}(\boldsymbol{y}\leftarrow\boldsymbol{x})=1$.

Acceptance Probability

We've now defined the transition probability, which is essentially the action space of the fine-tuning moves we make on the sentence at each step. The transition probability defined above is independent of the task background — that is, it doesn't depend on the conditional information $\boldsymbol{c}$, only on an unsupervised language model. The task-specific information is encoded in the quantitative measure $\rho(\boldsymbol{x},\boldsymbol{c})$, which affects the final result through the acceptance rate:

\begin{equation}\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}\end{equation}

By the way, the acceptance rate above is technically missing a $\min(1,\alpha)$ operation, but as long as our random number is drawn from $U[0,1]$, including or omitting that operation doesn't change the result. In short, this acceptance rate means that if a fine-tuning operation increases $\rho(\boldsymbol{x},\boldsymbol{c})$, it's very likely to be accepted; but even if it decreases $\rho(\boldsymbol{x},\boldsymbol{c})$, there's still some chance of being accepted. Whether we're doing plain sampling or seeking a maximum (simulated annealing), this randomness is crucial — it's the key to escaping local optima.

Combined with the acceptance rate of MH sampling, the transition probability built from "insert," "delete," and "replace" operations essentially simulates the process of repeated revision during writing: make a tweak, then decide whether to keep it — good tweaks tend to be kept, bad ones tend to be discarded.

Defining the Objective

As the last piece of preparatory work, let's discuss how to determine the criterion $\rho(\boldsymbol{x},\boldsymbol{c})$. CGMH runs three kinds of experiments: sentence composition from given words, unsupervised sentence rewriting, and unsupervised sentence correction. The sampling process is identical across all three — the only difference lies in $\rho(\boldsymbol{x},\boldsymbol{c})$. For sentence composition, the constraint is a hard constraint, namely

\begin{equation}\rho(\boldsymbol{x}, \boldsymbol{c}) = p(\boldsymbol{x})\cdot \chi(\boldsymbol{x}, \boldsymbol{c})\end{equation}

where $\boldsymbol{c}$ is the given set of words, and $\chi(\boldsymbol{x}, \boldsymbol{c})$ equals 1 only when the sentence $\boldsymbol{x}$ contains all the words in $\boldsymbol{c}$, and 0 otherwise. In implementation, we can simply record the positions of these words in advance, and make sure the "replace" and "delete" operations never select those positions. For unsupervised sentence rewriting and unsupervised sentence correction, $\boldsymbol{c}$ is the input sentence, and $\chi(\boldsymbol{x}, \boldsymbol{c})$ is replaced with some similarity measure $\text{sim}(\boldsymbol{x}, \boldsymbol{c})$ — see the original paper for the specific setup.

Also worth discussing here is the choice of $p(\boldsymbol{x})$, which represents the fluency of the sentence and is typically just a language model:

\begin{equation}p(\boldsymbol{x}) = \prod_{t=1}^l p(x_t|\boldsymbol{x}_{< t})\end{equation}

However, using the language model directly tends to favor generating very short sentences, since longer sentences generally have lower probability. If we want to encourage longer sentences, it's advisable to add a power adjustment, turning it into $p^{\gamma}(\boldsymbol{x})$, where $\gamma$ is a number slightly less than 1.

Experimental Results

With everything in place, we can run the experiment. Here we demonstrate the sentence-composition-from-given-words task. To stay as close as possible to the method described in CGMH, we use only a forward language model here, without an MLM model. The language model used is Huawei's open-source Chinese GPT-base model (see here). The reference code is shared at:

GitHub link: https://github.com/bojone/unsupervised-text-generation

Demo output:

Input words: Guangzhou, cuisine, opening
Initial state: 广州美食开幕。
Step 0, execute insert, output: 广州美食节开幕。
Step 4, execute insert, output: 广州美食节开幕式。
Step 11, execute insert, output: 广州美食节开幕月式。
Step 13, execute delete, output: 广州美食节开幕式。
Step 14, execute replace, output: 广州美食节开幕了。
Step 20, execute delete, output: 广州美食节开幕。
Step 50, execute replace, output: 广州美食网开幕。
Step 52, execute insert, output: 广州美食网开幕式。
Step 54, execute replace, output: 广州美食节开幕式。
Step 55, execute delete, output: 广州美食节开幕。
Step 63, execute insert, output: 广州美食节昨开幕。
Step 70, execute delete, output: 广州美食节开幕。
Step 74, execute insert, output: 广州美食节开幕了。
Step 76, execute delete, output: 广州美食节开幕。
Step 84, execute insert, output: 广州美食节将开幕。
Step 90, execute replace, output: 广州美食节的开幕。
Step 93, execute insert, output: 广州美食节的开幕式。
Step 96, execute delete, output: 广州美食节开幕式。
Step 99, execute replace, output: 广州美食节开幕了。
Step 100, execute insert, output: 广州的美食节开幕了。
Step 101, execute delete, output: 广州美食节开幕了。
Step 105, execute insert, output: 广州美食节也开幕了。
Step 106, execute insert, output: 广州的美食节也开幕了。
Step 107, execute insert, output: 广州人的美食节也开幕了。
Step 108, execute replace, output: 广州市的美食节也开幕了。
Step 123, execute delete, output: 广州的美食节也开幕了。
Step 127, execute replace, output: 广州的美食节又开幕了。

Input words: science, space
Initial state: 科学空间。
Step 3, execute insert, output: 科学，空间。
Step 5, execute delete, output: 科学空间。
Step 9, execute insert, output: 科学是空间。
Step 11, execute insert, output: 科学是指空间。
Step 12, execute delete, output: 科学指空间。
Step 15, execute delete, output: 科学空间。
Step 25, execute insert, output: 科学空间战。
Step 26, execute delete, output: 科学空间。
Step 28, execute insert, output: 科学是空间。
Step 29, execute delete, output: 科学空间。
Step 32, execute insert, output: 科学空间观。
Step 34, execute delete, output: 科学空间。
Step 42, execute insert, output: 科学，空间。
Step 43, execute replace, output: 科学与空间。
Step 44, execute delete, output: 科学空间。
Step 50, execute insert, output: 科学是空间。
Step 55, execute delete, output: 科学空间。
Step 63, execute insert, output: 科学有空间。
Step 65, execute delete, output: 科学空间。
Step 67, execute insert, output: 科学是空间。
Step 68, execute replace, output: 科学管空间。
Step 69, execute insert, output: 科学管理空间。
Step 70, execute insert, output: 科学管理空间大。
Step 71, execute insert, output: 科学的管理空间大。
Step 73, execute delete, output: 科学管理空间大。
Step 75, execute delete, output: 科学管理空间。
Step 78, execute replace, output: 科学管控空间。
Step 84, execute replace, output: 科学调控空间。
Step 88, execute insert, output: 科学调控空间大。
Step 89, execute insert, output: 科学调控的空间大。
Step 90, execute insert, output: 科学调控的空间很大。
Step 94, execute replace, output: 科学调控的空间加大。
Step 104, execute insert, output: 科学调控的空间在加大。
Step 110, execute replace, output: 科学调控的空间将加大。
Step 125, execute insert, output: 科学调控的空间将更加大。

Input words: delicious, snacks
Initial state: 好吃零食。
Step 4, execute insert, output: 好吃的零食。
Step 5, execute delete, output: 好吃零食。
Step 6, execute insert, output: 好吃零食卖。
Step 7, execute delete, output: 好吃零食。
Step 18, execute insert, output: 我好吃零食。
Step 20, execute replace, output: 最好吃零食。
Step 23, execute replace, output: 我好吃零食。
Step 24, execute replace, output: 最好吃零食。
Step 26, execute replace, output: 有好吃零食。
Step 27, execute delete, output: 好吃零食。
Step 29, execute insert, output: 好吃的零食。
Step 30, execute delete, output: 好吃零食。
Step 32, execute insert, output: 好吃的零食。
Step 33, execute delete, output: 好吃零食。
Step 35, execute insert, output: 好吃的零食。
Step 37, execute replace, output: 好吃，零食。
Step 38, execute replace, output: 好吃的零食。
Step 40, execute delete, output: 好吃零食。
Step 53, execute insert, output: 最好吃零食。
Step 54, execute replace, output: 我好吃零食。
Step 58, execute insert, output: 我好吃零食嘛。
Step 59, execute replace, output: 我好吃零食！。
Step 60, execute delete, output: 我好吃零食。
Step 61, execute delete, output: 好吃零食。
Step 63, execute insert, output: 好吃, 零食。
Step 64, execute replace, output: 好吃的零食。
Step 66, execute delete, output: 好吃零食。
Step 75, execute insert, output: 好吃的零食。
Step 76, execute delete, output: 好吃零食。
Step 77, execute insert, output: 好吃的零食。
Step 81, execute delete, output: 好吃零食。
Step 84, execute insert, output: 好吃的零食。
Step 89, execute replace, output: 好吃，零食。
Step 90, execute insert, output: 好吃的，零食。
Step 92, execute replace, output: 好吃的新零食。
Step 93, execute delete, output: 好吃的零食。
Step 94, execute delete, output: 好吃零食。
Step 96, execute insert, output: 好吃，零食。
Step 98, execute replace, output: 好吃的零食。
Step 99, execute delete, output: 好吃零食。
Step 104, execute insert, output: 最好吃零食。
Step 105, execute insert, output: 最好吃的零食。
Step 106, execute delete, output: 最好吃零食。
Step 107, execute delete, output: 好吃零食。
Step 124, execute insert, output: 最好吃零食。
Step 125, execute replace, output: 我好吃零食。
Step 126, execute insert, output: 但我好吃零食。
Step 127, execute replace, output: 而我好吃零食。

Each sample here went through 128 iterations; intermediate steps where the sentence wasn't modified are omitted from the display. Of course, due to the randomness involved, re-running the same input will typically produce different sentences, since MCMC is fundamentally a stochastic sampling scheme. These examples show that this genuinely is a process of repeatedly fine-tuning a sentence, and it ultimately produces reasonably readable sentences that satisfy the given conditions — demonstrating the effectiveness of the CGMH method.

In principle, as long as we can write down the objective $\rho(\boldsymbol{x},\boldsymbol{c})$ we're seeking, we can apply this entire process to accomplish the corresponding text generation task in an unsupervised way (though it may require enough iterations — unlike sentence composition, which shows results after just a hundred or so steps).

Summary

This post introduced and briefly reproduced a method called "CGMH" for unsupervised, constrained text generation via MCMC. It can be said to simulate the insertion, deletion, and replacement operations of the human writing process, making the generation process quite interpretable — this is the first genuinely practical example in this series. In principle, CGMH already embodies the general procedure for text generation via discrete optimization: as long as a given text generation task can be expressed as a quantitative evaluation criterion that doesn't rely on labels, this method can be applied for unsupervised generation.