Recently, I have started a new endeavor: performing text generation tasks based on the idea of discrete optimization. Simply put, this involves quantitatively writing down the objective of the text we want to generate, constructing a distribution, and then searching for the maximum point of this distribution or sampling from it. This process usually does not require training on labeled data. Since language is discrete, continuous function optimization methods like gradient descent are not applicable. Furthermore, because these distributions often do not have a form that is easy to sample from directly, direct sampling is infeasible. Therefore, specially designed sampling algorithms are required, such as Rejection Sampling, MCMC (Markov Chain Monte Carlo), MH Sampling (Metropolis-Hastings Sampling), Gibbs Sampling, and so on.
Some readers might find this familiar, as if returning to those headache-inducing years of learning LDA (Latent Dirichlet Allocation). Indeed, the aforementioned sampling algorithms are essential foundations for understanding LDA models. In this article, we will review these various sampling algorithms, which will appear in the rich text generation applications to be introduced later.
Defining the Goal
In many cases, we need to generate target text \boldsymbol{x} based on specific information \boldsymbol{c}. In mathematical terms, this is a conditional language model p(\boldsymbol{x}|\boldsymbol{c}). However, we often cannot obtain enough corpora of pairs (\boldsymbol{x}, \boldsymbol{c}) to directly train a conditional language model via supervised learning. Instead, we can only train an unconditional language model p(\boldsymbol{x}), but we can manually design an indicator to quantitatively describe the connection between \boldsymbol{x} and \boldsymbol{c}. In this situation, how to perform conditional text generation based on the unconditional language model p(\boldsymbol{x}) and the relationship between \boldsymbol{x} and \boldsymbol{c} becomes our object of study. We can call this “Constrained Text Generation.”
For example, in sentence generation using keywords, \boldsymbol{c} is the set of keywords. We can define an indicator function: \chi(\boldsymbol{x}, \boldsymbol{c})=\left\{\begin{aligned}&1,\,\,\text{if } \boldsymbol{x} \text{ contains the keyword set } \boldsymbol{c} \\ &0,\,\,\text{if } \boldsymbol{x} \text{ does not contain the keyword set } \boldsymbol{c}\end{aligned}\right. Then define: \rho(\boldsymbol{x}, \boldsymbol{c}) = p(\boldsymbol{x})\chi(\boldsymbol{x}, \boldsymbol{c}) Here, p(\boldsymbol{x}) ensures the fluency of the generated sentence, and \chi(\boldsymbol{x}, \boldsymbol{c}) ensures that the generated sentence contains the required keywords. The problem then becomes a maximization operation \mathop{\text{argmax}}\limits_{\boldsymbol{x}} \rho(\boldsymbol{x}, \boldsymbol{c}) or a sampling operation \boldsymbol{x}\sim \rho(\boldsymbol{x}, \boldsymbol{c}). Of course, \rho(\boldsymbol{x}, \boldsymbol{c}) here is not yet a probability distribution; it becomes a true probability distribution only after normalization: \frac{\rho(\boldsymbol{x}, \boldsymbol{c})}{\sum\limits_{\boldsymbol{x}}\rho(\boldsymbol{x}, \boldsymbol{c})} = \frac{p(\boldsymbol{x})\chi(\boldsymbol{x}, \boldsymbol{c})}{\sum\limits_{\boldsymbol{x}}p(\boldsymbol{x})\chi(\boldsymbol{x}, \boldsymbol{c})} However, the denominator is usually difficult to calculate explicitly. This means that for the distribution we wish to sample from, we only know that it is proportional to some function \rho(\boldsymbol{x}, \boldsymbol{c}), without knowing the exact expression of the distribution.
Similar examples are not uncommon, such as text summarization. What is text summarization? Essentially, it is using fewer words \boldsymbol{x} to express the same meaning as the original text \boldsymbol{c} as much as possible. In this case, we can define: \rho(\boldsymbol{x}, \boldsymbol{c}) = p(\boldsymbol{x})\cdot \text{sim}(\boldsymbol{x}, \boldsymbol{c})\cdot \chi(\boldsymbol{x}, \boldsymbol{c}) Where \text{sim}(\boldsymbol{x}, \boldsymbol{c}) is some text similarity function, and \chi(\boldsymbol{x}, \boldsymbol{c}) is an indicator function for length—i.e., it is 1 if the length of \boldsymbol{x} is within a certain range (which may depend on \boldsymbol{c}), and 0 otherwise. Here again, we obtain an unnormalized probability distribution \rho(\boldsymbol{x}, \boldsymbol{c}) that needs to be maximized or sampled from. Clearly, this objective means we want to obtain a piece of text that is as semantically similar to the original as possible and satisfies certain length constraints—which is exactly the purpose of a summary. Therefore, the core starting point of this approach is: we must quantitatively clarify the target we want to generate, and then proceed to the next step.
Difficulty Analysis
Setting aside the background for a moment, the problem we face is that we have a distribution p(\boldsymbol{x}) where we only know p(\boldsymbol{x})\propto \rho(\boldsymbol{x}), i.e., p(\boldsymbol{x}) = \frac{\rho(\boldsymbol{x})}{\sum\limits_{\boldsymbol{x}} \rho(\boldsymbol{x})} and we cannot explicitly calculate the denominator. In this series of articles, \boldsymbol{x} represents text, which is a sequence of discrete elements, but the subsequent inferences also apply to scenarios where \boldsymbol{x} is a continuous vector. Now we want to search for the maximum position \mathop{\text{argmax}}\limits_{\boldsymbol{x}} p(\boldsymbol{x}) or perform sampling \boldsymbol{x}\sim p(\boldsymbol{x}). As we will see later, searching for the maximum can actually be viewed as a special case of sampling, so we are primarily concerned with sampling methods.
As mentioned earlier, the reason we need to design special algorithms for sampling is that direct sampling from p(\boldsymbol{x}) is difficult. We need to understand where the difficulty lies to truly appreciate the key aspects of the sampling algorithms designed later. Where is the difficulty? If the candidate space for \boldsymbol{x} is small—even if there are 1 million candidates—we could calculate every p(\boldsymbol{x}) and then proceed with standard categorical sampling. However, the candidate space for \boldsymbol{x} is generally far beyond 1 million. For instance, if \boldsymbol{x} has 10 components and each component has 10,000 choices (corresponding to vocabulary size), then the total number of permutations is 10^{40}. It is impossible to pre-calculate the probability of every permutation and sample accordingly.
What can be done? As the saying goes, “A journey of a thousand miles begins with a single step.” We can only take it one step at a time. That is to say, if I cannot directly implement a “1 out of 10^{40}” selection, can I perform ten “1 out of 10^4” selections? This corresponds to so-called “autoregressive generation”: p(\boldsymbol{x})=p(x_1) p(x_2|x_1) p(x_3|x_1, x_2) \cdots p(x_n|x_1,\cdots,x_{n-1}) = \prod_{t=1}^n p(x_t|\boldsymbol{x}_{< t}) In this way, we can first sample x_1 from p(x_1), then sample x_2 from p(x_2|x_1), and recurse. However, autoregressive generation only corresponds to unconditional language models or supervised Seq2Seq models. If we wish to add constraints to the generation process of an unconditional language model as in the previous examples, the resulting model is no longer autoregressive, and thus cannot be sampled using such recursion.
Therefore, we inevitably need the various sampling algorithms introduced later. They also follow the “step-by-step” philosophy, but the distribution forms they use are more general.
Importance Sampling
In articles such as "Optimization from the Perspective of Sampling: A Unified View of Differentiable and Non-Differentiable Optimization" and "How to Partition a Validation Set Closer to the Test Set?", we introduced the concept of “Importance Sampling.” That is, if we want to estimate the expectation \mathbb{E}_{\boldsymbol{x}\sim p(\boldsymbol{x})}[f(\boldsymbol{x})], but p(\boldsymbol{x}) is not a distribution that is easy to sample from, we can find a distribution q(\boldsymbol{x}) that is close to p(\boldsymbol{x}) and easy to sample from. Then, according to the following transformation: \mathbb{E}_{\boldsymbol{x}\sim p(\boldsymbol{x})}[f(\boldsymbol{x})] = \sum_{\boldsymbol{x}} p(\boldsymbol{x}) f(\boldsymbol{x}) = \sum_{\boldsymbol{x}} q(\boldsymbol{x})\frac{p(\boldsymbol{x})}{q(\boldsymbol{x})}f(\boldsymbol{x}) = \mathbb{E}_{\boldsymbol{x}\sim q(\boldsymbol{x})}\left[\frac{p(\boldsymbol{x})}{q(\boldsymbol{x})}f(\boldsymbol{x})\right] the problem is converted to sampling from q(\boldsymbol{x}) to calculate the expectation of \frac{p(\boldsymbol{x})}{q(\boldsymbol{x})}f(\boldsymbol{x}). This means weighting each sample by \frac{p(\boldsymbol{x})}{q(\boldsymbol{x})}, which is why it is called Importance Sampling. If we only know p(\boldsymbol{x})\propto \rho(\boldsymbol{x}), importance sampling is still possible because: 1 = \sum_{\boldsymbol{x}} p(\boldsymbol{x}) = \sum_{\boldsymbol{x}} q(\boldsymbol{x})\frac{p(\boldsymbol{x})}{q(\boldsymbol{x})} = \mathbb{E}_{\boldsymbol{x}\sim q(\boldsymbol{x})}\left[\frac{p(\boldsymbol{x})}{q(\boldsymbol{x})}\right] Therefore: \mathbb{E}_{\boldsymbol{x}\sim q(\boldsymbol{x})}\left[\frac{p(\boldsymbol{x})}{q(\boldsymbol{x})}f(\boldsymbol{x})\right] = \mathbb{E}_{\boldsymbol{x}\sim q(\boldsymbol{x})}\left[\frac{p(\boldsymbol{x}) / q(\boldsymbol{x})}{\mathbb{E}_{\boldsymbol{x}\sim q(\boldsymbol{x})}[p(\boldsymbol{x}) / q(\boldsymbol{x})]}f(\boldsymbol{x})\right] In this way, we find that the above formula only depends on the relative values of p(\boldsymbol{x}), not its absolute values. Thus, replacing p(\boldsymbol{x}) with \rho(\boldsymbol{x}) (which is proportional to it) is also feasible, ultimately simplifying to: \mathbb{E}_{\boldsymbol{x}\sim p(\boldsymbol{x})}[f(\boldsymbol{x})] \approx \frac{\sum\limits_{i=1}^N \rho(\boldsymbol{x}_i) / q(\boldsymbol{x}_i) \cdot f(\boldsymbol{x}_i)}{\sum\limits_{i=1}^N \rho(\boldsymbol{x}_i) / q(\boldsymbol{x}_i)},\quad \boldsymbol{x}_1,\cdots,\boldsymbol{x}_N\sim q(\boldsymbol{x})
Rejection Sampling
The importance sampling in the previous section achieves the conversion of an expectation over a complex distribution into an expectation over a simple distribution. However, this is not our true goal. What we want to achieve is to sample actual instances from the distribution p(\boldsymbol{x}), rather than estimating some expectation. The idea remains similar to importance sampling: introduce a distribution q(\boldsymbol{x}) that is easy to sample from, and then randomly filter out certain samples so that the remaining samples follow the distribution p(\boldsymbol{x}).
Specifically, assume there is a function \alpha(\boldsymbol{x})\in [0, 1]. We perform sampling according to the following process, known as Rejection Sampling:
Rejection Sampling: Sample a candidate \boldsymbol{x} from q(\boldsymbol{x}). Sample a random number \varepsilon from U[0,1]. If \varepsilon \leq \alpha(\boldsymbol{x}), accept the sample; otherwise, reject it and restart the process.
So, what is the true probability distribution of the samples \boldsymbol{x} obtained this way? It is not difficult to derive. Since the probability of a sample \boldsymbol{x} being retained is \alpha(\boldsymbol{x}), its relative probability is q(\boldsymbol{x})\alpha(\boldsymbol{x}). We only need to re-normalize it: \frac{q(\boldsymbol{x})\alpha(\boldsymbol{x})}{\sum\limits_{\boldsymbol{x}} q(\boldsymbol{x})\alpha(\boldsymbol{x})} to get the true probability distribution corresponding to rejection sampling. From this form, we can also see that multiplying the acceptance rate by a constant between 0 and 1 does not change the distribution corresponding to rejection sampling.
This process suggests that rejection sampling allows us to sample from a distribution proportional to q(\boldsymbol{x})\alpha(\boldsymbol{x}). Given p(\boldsymbol{x})=q(\boldsymbol{x})\frac{p(\boldsymbol{x})}{q(\boldsymbol{x})}, we can let \alpha(\boldsymbol{x})=\frac{p(\boldsymbol{x})}{q(\boldsymbol{x})} serve as the acceptance probability to perform rejection sampling starting from q(\boldsymbol{x}). The result is equivalent to sampling from p(\boldsymbol{x}). Of course, it is not quite that simple; according to the normalization property of probability, unless q(\boldsymbol{x}) is identical to p(\boldsymbol{x}), \frac{p(\boldsymbol{x})}{q(\boldsymbol{x})} cannot always be within [0, 1]. But this does not matter; as long as \frac{p(\boldsymbol{x})}{q(\boldsymbol{x})} has an upper bound, we can choose a sufficiently large constant M such that \frac{p(\boldsymbol{x})}{q(\boldsymbol{x})\cdot M}\in [0, 1]. In this case, using \alpha(\boldsymbol{x})=\frac{p(\boldsymbol{x})}{q(\boldsymbol{x})\cdot M} as the acceptance probability works. As we just said, multiplying by a constant does not affect the distribution. In other words, this process also does not depend on a perfectly accurate p(\boldsymbol{x}); p(\boldsymbol{x}) can be replaced by \rho(\boldsymbol{x}).
Regarding the acceptance rate \alpha(\boldsymbol{x}), although theoretically it only needs to be \alpha(\boldsymbol{x})\in[0, 1], in practice it is best if \max\limits_{\boldsymbol{x}}\alpha(\boldsymbol{x}) = 1. This is because an excessively low acceptance rate leads to too many rejections (almost every sample is rejected), making sampling efficiency too low and the cost of generating a reasonable sample too high. Similarly, although the theoretical requirement for q(\boldsymbol{x}) is only that it is easy to sample from and that \frac{p(\boldsymbol{x})}{q(\boldsymbol{x})} has an upper bound, in practice q(\boldsymbol{x}) and p(\boldsymbol{x}) should be as similar as possible. Otherwise, it may still result in an acceptance rate so low that the sampling cost becomes unacceptable. Thus, while rejection sampling seems to provide a scheme for sampling from almost any distribution p(\boldsymbol{x}), the design of the approximate distribution q(\boldsymbol{x}) remains a significant challenge in practical applications.
Summary
Starting with this article, we have opened a new series attempting to complete certain text generation tasks (constrained text generation) from the perspective of discrete optimization. It works by determining a quantitative evaluation target and then maximizing this target or sampling from it to obtain the desired output, without requiring labeled data to supervise the training of a new model. In this process, the tools used are primarily sampling algorithms. This article first introduced the very basic Importance Sampling and Rejection Sampling. We will continue to improve this series in the future; please stay tuned.