In the previous article, we introduced the concept of "constrained text generation," pointing out that certain conditional text generation tasks can be completed in an unsupervised manner by quantifying objectives and sampling from them. At the same time, the previous article introduced "Importance Sampling" and "Rejection Sampling," noting that for high-dimensional spaces, the easy-to-sample distributions they rely on are often difficult to design, making it hard for them to meet our sampling needs.
At this point, we need to introduce one of the most important algorithms in the sampling world: the Markov Chain Monte Carlo (MCMC) method. It combines Markov chains with Monte Carlo methods, making it possible (at least theoretically) to sample from many high-dimensional distributions. It is also one of the fundamental algorithms for the constrained text generation applications we will introduce later. This article attempts to provide a basic introduction to it.
Markov Chain
A Markov chain is essentially a "memoryless" random walk process. It is based on a transition probability p(\boldsymbol{y}\leftarrow\boldsymbol{x}). Starting from an initial state \boldsymbol{x}_0, each step randomly selects the next state through this transition probability, forming a sequence of random states \boldsymbol{x}_0, \boldsymbol{x}_1, \boldsymbol{x}_2, \dots, \boldsymbol{x}_t, \dots. We wish to examine the distribution followed by \boldsymbol{x}_t for a sufficiently large number of steps t, which is the "stationary distribution" of the Markov chain.
Assuming the distribution followed by \boldsymbol{x}_t is p^{(t)}(\boldsymbol{x}_t), then the distribution followed by \boldsymbol{x}_{t+1} is: p^{(t+1)}(\boldsymbol{x}_{t+1}) = \sum_{\boldsymbol{x}_t} p(\boldsymbol{x}_{t+1} \leftarrow \boldsymbol{x}_t)p^{(t)}(\boldsymbol{x}_t) If equilibrium has been reached, then we should have p^{(t+1)}=p^{(t)}. Therefore, if p(\boldsymbol{x}) is the stationary distribution, it satisfies: p(\boldsymbol{y}) = \sum_{\boldsymbol{x}} p(\boldsymbol{y} \leftarrow \boldsymbol{x})p(\boldsymbol{x}) \label{eq:stable} In other words, the stationary distribution is a non-zero solution to the above equation regarding p(\boldsymbol{x}).
A question that needs to be answered is: Is the non-zero solution to the above equation unique? The answer to this question determines whether the stationary distribution of the Markov chain depends on the initial state \boldsymbol{x}_0. Unfortunately, the answer is not necessarily. Simply put, the condition for a unique non-zero solution is that any two states of the Markov chain are connected. Specifically, for any two states \boldsymbol{x}, \boldsymbol{y}, there exists a chain of states \boldsymbol{x}=\boldsymbol{x}_0, \boldsymbol{x}_1, \dots, \boldsymbol{x}_{n-1}, \boldsymbol{x}_n=\boldsymbol{y} such that: \begin{aligned} &p(\boldsymbol{x}_{1} \leftarrow \boldsymbol{x}_0) > 0 \\ &p(\boldsymbol{x}_{2} \leftarrow \boldsymbol{x}_1) > 0 \\ &\qquad\vdots \\ &p(\boldsymbol{x}_{n} \leftarrow \boldsymbol{x}_{n-1}) > 0 \end{aligned} Plainly speaking, the probability of jumping from state \boldsymbol{x} to \boldsymbol{y} (not necessarily in one step, but possibly multiple steps) must be greater than 0. This criterion is not hard to understand; a figurative analogy is that the condition for a unique stationary distribution is that the Markov chain cannot have "islands." Otherwise, if \boldsymbol{x}_0 is inside an island, it will wander within that island forever; if \boldsymbol{x}_0 is outside the island, it will stay outside forever. Thus, different initial states would lead to different stationary distributions.
Detailed Balance
Since a Markov chain has a stationary distribution, and constructing a Markov chain only requires a transition matrix, if we can construct an easy-to-sample transition matrix whose stationary distribution is exactly the distribution p(\boldsymbol{x}) we want to sample from, then after iterating for enough steps, wouldn’t it be equivalent to sampling from p(\boldsymbol{x})? This is the idea behind all MCMC methods. Of course, Markov chains often require many iterations to reach stationarity, so sampling is often time-consuming. However, even so, the sampling process can eventually be completed within a finite cost, making it practical in many cases.
Assuming MCMC is feasible, the key is how to construct a transition probability p(\boldsymbol{y}\leftarrow\boldsymbol{x}) such that its stationary distribution is our given distribution p(\boldsymbol{x}). Also, as introduced in the previous article, we often only know \rho(\boldsymbol{x}), which is proportional to p(\boldsymbol{x}), but we do not know the normalization factor. Therefore, the process of constructing p(\boldsymbol{y}\leftarrow\boldsymbol{x}) cannot rely on the normalization factor of p(\boldsymbol{x}).
To this end, we need to use the "Detailed Balance Condition":
Detailed Balance Condition If the distribution p(\boldsymbol{x}) and the transition probability p(\boldsymbol{y}\leftarrow\boldsymbol{x}) satisfy the identity: p(\boldsymbol{y}\leftarrow\boldsymbol{x})p(\boldsymbol{x})=p(\boldsymbol{x}\leftarrow\boldsymbol{y})p(\boldsymbol{y}) then p(\boldsymbol{x}) is the stationary distribution of p(\boldsymbol{y}\leftarrow\boldsymbol{x}).
The name sounds sophisticated, but it is actually very easy to prove. By summing both sides over \boldsymbol{x}, we immediately obtain Equation [eq:stable]. Satisfying Equation [eq:stable] indicates that p(\boldsymbol{x}) is the stationary distribution of p(\boldsymbol{y}\leftarrow\boldsymbol{x}). The "Detailed Balance Condition" is a sufficient condition for determining a stationary distribution, but not a necessary one. Its value lies in providing a convenient way to construct transition probabilities for any distribution.
Transition Probability
Given a stationary distribution p(\boldsymbol{x}) and any reference transition probability q(\boldsymbol{y}\leftarrow\boldsymbol{x}), if it satisfies the detailed balance condition, then everything is fine, and we can directly use q(\boldsymbol{y}\leftarrow\boldsymbol{x}) as the final probability. If it does not satisfy it, let \alpha(\boldsymbol{x}\leftarrow\boldsymbol{y})=q(\boldsymbol{y}\leftarrow\boldsymbol{x})p(\boldsymbol{x}). Then the following identity obviously holds: \underbrace{\alpha(\boldsymbol{y}\leftarrow\boldsymbol{x})q(\boldsymbol{y}\leftarrow\boldsymbol{x})}_{\tilde{q}(\boldsymbol{y}\leftarrow\boldsymbol{x})}p(\boldsymbol{x})=\underbrace{\alpha(\boldsymbol{x}\leftarrow\boldsymbol{y})q(\boldsymbol{x}\leftarrow\boldsymbol{y})}_{\tilde{q}(\boldsymbol{x}\leftarrow\boldsymbol{y})}p(\boldsymbol{y}) \label{eq:feihua} In fact, this identity is almost trivial; it is equivalent to saying "although a \neq b, ab = ba always holds." But this "trivial" identity gives us an inspiration: if we use \tilde{q}(\boldsymbol{y}\leftarrow\boldsymbol{x}) as the transition probability, wouldn’t the corresponding stationary distribution be p(\boldsymbol{x})?
Actually, it’s not that simple, because the \tilde{q}(\boldsymbol{y}\leftarrow\boldsymbol{x}) constructed this way is usually not normalized. Not being normalized means it is not a valid transition probability itself, and thus there is no stationary distribution to speak of. Note that to perform sampling, we might not need to know the normalization factor, but for the theoretical distribution, we need to ensure normalization holds. Some readers might think: can I just manually divide by a normalization factor? No, because after dividing by the normalization factor, the detailed balance condition might no longer hold, and even Equation [eq:stable] might fail. I have consulted many introductory materials, and many do not clarify this issue, simply saying to use \tilde{q}(\boldsymbol{y}\leftarrow\boldsymbol{x}) as the transition probability, which confused me for a long time.
In fact, the MCMC method does not normalize \tilde{q}(\boldsymbol{y}\leftarrow\boldsymbol{x}) at all. Instead, it transfers all the remaining probability to the state itself. In mathematical terms, the transition probability it actually uses is: p(\boldsymbol{y}\leftarrow\boldsymbol{x})=\tilde{q}(\boldsymbol{y}\leftarrow\boldsymbol{x}) + \left(1 - \sum_{\boldsymbol{y}} \tilde{q}(\boldsymbol{y}\leftarrow\boldsymbol{x})\right)\delta(\boldsymbol{y}\leftarrow\boldsymbol{x}) where \delta(\boldsymbol{y}\leftarrow\boldsymbol{x}) = \left\{\begin{aligned}1, \boldsymbol{y}=\boldsymbol{x} \\ 0, \boldsymbol{y}\neq \boldsymbol{x}\end{aligned}\right., representing the transition probability of staying in the same state (i.e., "never changing"). Therefore, the definition of p(\boldsymbol{y}\leftarrow\boldsymbol{x}) simply stacks all the excess probability onto the "no change" operation, so it clearly satisfies normalization. As for the detailed balance condition, it can be verified by substitution; it is also satisfied, mainly because for any p(\boldsymbol{x}) and f(\boldsymbol{x},\boldsymbol{y}), the following identity always holds: f(\boldsymbol{x},\boldsymbol{y})\delta(\boldsymbol{y}\leftarrow \boldsymbol{x})p(\boldsymbol{x})=f(\boldsymbol{y},\boldsymbol{x})\delta(\boldsymbol{x}\leftarrow \boldsymbol{y})p(\boldsymbol{y}) Thus, p(\boldsymbol{y}\leftarrow\boldsymbol{x}) is the true transition probability we seek. If the state space is finite, the transition probability corresponds to a finite matrix. The above result essentially says that "normalization can be completed by adjusting the diagonal elements of the transition matrix without affecting the validity of the detailed balance condition."
MCMC Method
How do we implement sampling from the aforementioned p(\boldsymbol{y}\leftarrow\boldsymbol{x})? It’s simple: first implement sampling from \tilde{q}(\boldsymbol{y}\leftarrow\boldsymbol{x}), and if the condition for sampling from \tilde{q}(\boldsymbol{y}\leftarrow\boldsymbol{x}) is not met, then stay unchanged. Since \tilde{q}(\boldsymbol{y}\leftarrow\boldsymbol{x})=\alpha(\boldsymbol{y}\leftarrow\boldsymbol{x})q(\boldsymbol{y}\leftarrow\boldsymbol{x}), and we assume sampling from q(\boldsymbol{y}\leftarrow\boldsymbol{x}) is easy, then recalling the rejection sampling introduced in the previous article, we can further sample an \varepsilon\sim U[0,1] and use \alpha(\boldsymbol{y}\leftarrow\boldsymbol{x}) < \varepsilon to decide whether to accept the sampled \boldsymbol{y}. In summary, we get the following MCMC sampling process:
Metropolis Sampling
Initial state is \boldsymbol{x}_0, and the state at time t is \boldsymbol{x}_t.
Sample \boldsymbol{x}_{t+1} through the following process:
Sample \boldsymbol{y}\sim q(\boldsymbol{y}\leftarrow\boldsymbol{x}_t);
Sample \varepsilon\sim U[0,1];
Calculate \alpha(\boldsymbol{y}\leftarrow\boldsymbol{x}_t)=q(\boldsymbol{x}_t\leftarrow\boldsymbol{y})p(\boldsymbol{y});
If \varepsilon \leq \alpha(\boldsymbol{y}\leftarrow\boldsymbol{x}_t), then \boldsymbol{x}_{t+1} = \boldsymbol{y}, otherwise \boldsymbol{x}_{t+1}=\boldsymbol{x}_t.
This is the sampling algorithm proposed by Metropolis in 1953, generally called the Metropolis algorithm, or simply the MCMC method. It requires knowing the exact expression of p(\boldsymbol{x}) and an easy-to-sample transition probability q(\boldsymbol{y}\leftarrow\boldsymbol{x}). After iterating for enough steps according to the above process, the resulting \boldsymbol{x}_t can be considered a sample from p(\boldsymbol{x}). The number of steps required depends on the specific choices of p(\boldsymbol{x}) and q(\boldsymbol{y}\leftarrow\boldsymbol{x}); generally, it can only be determined based on experimental results, as there is no unified standard.
Some readers might think: isn’t this just ordinary rejection sampling? Where is the part about "stacking all the excess probability onto the ’no change’ operation"? In fact, it is slightly different from ordinary rejection sampling. In ordinary rejection sampling, if \varepsilon > \alpha(\boldsymbol{y}\leftarrow\boldsymbol{x}), steps 1, 2, and 3 are repeated until a \boldsymbol{y} satisfying \varepsilon \leq \alpha(\boldsymbol{y}\leftarrow\boldsymbol{x}) is sampled, and then \boldsymbol{x}_{t+1} = \boldsymbol{y}. In the sampling process above, if \varepsilon > \alpha(\boldsymbol{y}\leftarrow\boldsymbol{x}), we directly set \boldsymbol{x}_{t+1} = \boldsymbol{x}_t, and the next sample will be \boldsymbol{x}_{t+2}. If we assume the distribution becomes stationary starting from time T, then \{\boldsymbol{x}_t\}_{t=T}^{\infty} are all samples from p(\boldsymbol{x}) (identically distributed but not independent). Obviously, the two different rejection methods affect the final distribution of \{\boldsymbol{x}_t\}_{t=T}^{\infty}.
Furthermore, it is worth pointing out that although in this series of articles we deal with \boldsymbol{x} as a discrete object, the same conclusions apply to the sampling of continuous objects. One only needs to replace the summation with an integral over the probability density in the previous derivations; there is no substantial difference.
MH Sampling
The Metropolis sampling described above is already usable in many scenarios, but it is not perfect. First, as mentioned, Metropolis sampling requires knowing the exact expression of p(\boldsymbol{x}), which is difficult to achieve in many tasks. Second, the acceptance rate \alpha(\boldsymbol{y}\leftarrow\boldsymbol{x}) is often too small, leading to long periods of "staying in place," which makes the time to reach stationarity too long. Fortunately, there is a simple trick that can solve both problems simultaneously.
The trick is to use the following expression as the acceptance rate: \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) This acceptance rate also originates from identity [eq:feihua]. For the acceptance rate, our only requirement is that it is between 0 and 1; furthermore, the closer it is to 1, the better. To this end, we can divide the acceptance rates on both sides of identity [eq:feihua] by \max(\alpha(\boldsymbol{y}\leftarrow\boldsymbol{x}), \alpha(\boldsymbol{x}\leftarrow\boldsymbol{y})). In this way, one of them becomes 1, and the other is no greater than 1 and is amplified. After simplification, we get \mathcal{A}(\boldsymbol{y}\leftarrow\boldsymbol{x}). Quite cleverly, \mathcal{A}(\boldsymbol{y}\leftarrow\boldsymbol{x}) now only depends on the relative values of p(\boldsymbol{y}), so we don’t need to calculate its normalization factor.
Thus, we obtain the improved version of the Metropolis sampling algorithm, the famous Metropolis-Hastings Sampling (MH Sampling):
Metropolis-Hastings Sampling
Initial state is \boldsymbol{x}_0, and the state at time t is \boldsymbol{x}_t.
Sample \boldsymbol{x}_{t+1} through the following process:
Sample \boldsymbol{y}\sim q(\boldsymbol{y}\leftarrow\boldsymbol{x}_t);
Sample \varepsilon\sim U[0,1];
Calculate \mathcal{A}(\boldsymbol{y}\leftarrow\boldsymbol{x}_t) = \min\left(1, \frac{q(\boldsymbol{x}_t\leftarrow\boldsymbol{y})p(\boldsymbol{y})}{q(\boldsymbol{y}\leftarrow\boldsymbol{x}_t)p(\boldsymbol{x}_t)}\right);
If \varepsilon \leq \mathcal{A}(\boldsymbol{y}\leftarrow\boldsymbol{x}_t), then \boldsymbol{x}_{t+1} = \boldsymbol{y}, otherwise \boldsymbol{x}_{t+1}=\boldsymbol{x}_t.
Analysis and Thinking
In the previous article, we pointed out that sampling directly from p(\boldsymbol{x}) is very difficult. Even with rejection sampling, if the dimension of \boldsymbol{x} is too high, the acceptance rate after sampling from the approximate distribution q(\boldsymbol{x}) is usually very low, making rejection sampling extremely inefficient and unusable. A natural question arises:
In the MCMC method, we also sample from a transition probability q(\boldsymbol{y}\leftarrow \boldsymbol{x}) and also have an acceptance probability \mathcal{A}(\boldsymbol{y}\leftarrow \boldsymbol{x}). Why is MCMC practical while ordinary rejection sampling is not?
In fact, for direct rejection sampling, it must sample the entire high-dimensional sequence directly from the approximate distribution q(\boldsymbol{x}). If q(\boldsymbol{x}) differs significantly from the exact p(\boldsymbol{x}), the acceptance probability often decays exponentially, resulting in an extremely low acceptance rate. For the MCMC method, we do not have many restrictions on the form of q(\boldsymbol{y}\leftarrow \boldsymbol{x}), so we can appropriately design q(\boldsymbol{y}\leftarrow \boldsymbol{x}) such that the probability distribution is concentrated only on those \boldsymbol{y} that are similar to \boldsymbol{x}. In other words, q(\boldsymbol{y}\leftarrow \boldsymbol{x}) is non-zero only when \boldsymbol{y} is very similar to \boldsymbol{x}. Consequently, the result of sampling from q(\boldsymbol{y}\leftarrow \boldsymbol{x}) has only small differences from the input \boldsymbol{x}. When the change is small, the acceptance rate tends to be higher, making rejection sampling possible.
So, simply put, the MCMC method converts "directly generating \boldsymbol{x}" into a gradual process of "starting from \boldsymbol{x}_0, repeatedly fine-tuning and polishing it until an \boldsymbol{x} that meets the conditions is generated," making it effective. This is consistent with the "step-by-step" idea mentioned in the previous article.
Next, we will introduce two examples of MH sampling: Gibbs sampling and Simulated Annealing. Both embody this fine-tuning and gradual idea of MCMC.
Gibbs Sampling
Suppose \boldsymbol{x}=(x_1, x_2, \dots, x_l) is a sequence of length l. Gibbs sampling adjusts only one element at a time. Specifically, Gibbs sampling defines the reference transition probability as (strictly speaking, it should be divided by l, but constants do not change the result, so it is omitted): q(\boldsymbol{x}_{[x_i=y]}\leftarrow \boldsymbol{x}) = p(y|\boldsymbol{x}_{-i})\triangleq\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)} where \boldsymbol{x}_{[x_i=y]} is the sequence after replacing the i-th position of \boldsymbol{x} with y. This means it uses the distribution p(\boldsymbol{x}) itself to construct p(y|\boldsymbol{x}_{-i}) as the transition probability. Each time, it randomly selects a position i from 1, 2, \dots, l, and then replaces the element at position i with a result sampled from the distribution p(y|\boldsymbol{x}_{-i}). Even better, we can prove that in this case, the acceptance probability is always 1: \begin{aligned} \mathcal{A}(\boldsymbol{x}_{[x_i=y]}\leftarrow \boldsymbol{x}) =&\, \min\left(1, \frac{p(x_i|\boldsymbol{x}_{-i})p(\boldsymbol{x}_{[x_i=y]})}{p(y|\boldsymbol{x}_{-i})p(\boldsymbol{x})}\right) \\ =&\, \min\left(1, \frac{p(x_i|\boldsymbol{x}_{-i})p(y|\boldsymbol{x}_{-i})p(\boldsymbol{x}_{-i})}{p(y|\boldsymbol{x}_{-i})p(x_i|\boldsymbol{x}_{-i})p(\boldsymbol{x}_{-i})}\right)\\ =&\, \min\left(1, 1\right)\\ =&\,1 \end{aligned} From this, we can construct the following Gibbs sampling process:
Gibbs Sampling
Initial state is \boldsymbol{x}_0=(x_{0,1},x_{0,2},\cdots,x_{0,l}), and the state at time t is \boldsymbol{x}_t=(x_{t,1},x_{t,2},\cdots,x_{t,l}).
Sample \boldsymbol{x}_{t+1} through the following process:
Uniformly sample an i from 1, 2, \dots, l;
Calculate p(y|\boldsymbol{x}_{t,-i})=\frac{p(x_{t,1},\dots,x_{t,i-1},y,x_{t,i+1},\cdots,x_{t,l})}{\sum\limits_y p(x_{t,1},\dots,x_{t,i-1},y,x_{t,i+1},\cdots,x_{t,l})};
Sample y\sim p(y|\boldsymbol{x}_{t,-i});
\boldsymbol{x}_{t+1} = {\boldsymbol{x}_t}_{[x_{t,i}=y]} (i.e., replace the i-th position of \boldsymbol{x}_t with y to get \boldsymbol{x}_{t+1}).
Simulated Annealing
Another example is the Simulated Annealing algorithm. In the previous article, we mentioned that maximizing an objective can also be seen as random sampling from that objective, and the result corresponds to the simulated annealing algorithm.
First, let the function we want to maximize be f(\boldsymbol{x}), and assume there exists some constant T > 0 such that for any 0 < \tau \leq T: \sum_{\boldsymbol{x}} e^{f(\boldsymbol{x})/\tau} < \infty The physical meaning of \tau here is temperature. This assumption seems like an additional constraint, but in fact, simulated annealing is only suitable for scenarios that satisfy this condition. Since this condition is met, we can construct the distribution: p_{\tau}(\boldsymbol{x}) = \frac{e^{f(\boldsymbol{x})/\tau}}{\sum\limits_{\boldsymbol{x}} e^{f(\boldsymbol{x})/\tau}} Assuming the maximum point is unique, as \tau\to 0, p_{\tau}(\boldsymbol{x}) will degenerate into a one-hot distribution, where only the probability of the maximum point is 1. If we sample from p_{\tau}(\boldsymbol{x}), the result will be the maximum point. Even if \tau > 0, the probability of the maximum point is still the highest, so sampling from p_{\tau}(\boldsymbol{x}) will show a trend towards the maximum point. Therefore, we can first fix the temperature \tau, construct a stochastic process for MH sampling from p_{\tau}(\boldsymbol{x}), and then slowly lower \tau. The final convergence result will be near the maximum point. This is the so-called "simulated annealing."
To perform MH sampling, we need to construct a transition matrix. The choice for simulated annealing is relatively simple: design a fixed number of \boldsymbol{y} as candidates for the new \boldsymbol{x} based on the current state \boldsymbol{x} (this step is usually called "mutation," often just a simple modification of \boldsymbol{x} to get \boldsymbol{y}), and then q(\boldsymbol{y}\leftarrow \boldsymbol{x}) is a uniform random selection from the candidates. Since it is uniform, q(\boldsymbol{y}\leftarrow \boldsymbol{x}) is a constant, and q(\boldsymbol{y}\leftarrow \boldsymbol{x})=q(\boldsymbol{x}\leftarrow \boldsymbol{y}), so we have: \mathcal{A}(\boldsymbol{y}\leftarrow\boldsymbol{x}) = \min\left(1, \frac{q(\boldsymbol{x}\leftarrow\boldsymbol{y})p_{\tau}(\boldsymbol{y})}{q(\boldsymbol{y}\leftarrow\boldsymbol{x})p_{\tau}(\boldsymbol{x})}\right) = \min\left(1, e^{[f(\boldsymbol{y}) - f(\boldsymbol{x})]/\tau}\right) Thus, simulated annealing is a search strategy: if f(\boldsymbol{y}) \geq f(\boldsymbol{x}), then update \boldsymbol{x}=\boldsymbol{y}; even if not, there is still a certain probability to update \boldsymbol{x}=\boldsymbol{y}. Throughout the search process, we slowly perform annealing (\tau slowly approaches 0). Under an appropriate annealing strategy, simulated annealing almost always finds the maximum point. Of course, how to formulate an "appropriate" annealing strategy for a specific problem is another question worth considering.
Simulated Annealing
Initial state is \boldsymbol{x}_0, initial temperature is \tau_0, and the temperature decreases according to a pre-formulated strategy. At time t, the state is \boldsymbol{x}_t and the temperature is \tau_t.
Sample \boldsymbol{x}_{t+1} through the following process:
Sample \boldsymbol{y}\sim q(\boldsymbol{y}\leftarrow\boldsymbol{x}_t);
Sample \varepsilon\sim U[0,1];
Calculate \mathcal{A}(\boldsymbol{y}\leftarrow\boldsymbol{x}_t) = \min\left(1, e^{[f(\boldsymbol{y}) - f(\boldsymbol{x}_t)]/\tau_t}\right);
If \varepsilon\leq \mathcal{A}(\boldsymbol{y}\leftarrow\boldsymbol{x}_t), then \boldsymbol{x}_{t+1} = \boldsymbol{y}, otherwise \boldsymbol{x}_{t+1}=\boldsymbol{x}_t.
If we modify this slightly and change the acceptance strategy to "accept if f(\boldsymbol{y}) \geq f(\boldsymbol{x}_t), otherwise reject," it becomes the simpler "Hill Climbing" method. Obviously, hill climbing has a clearer goal and may converge faster in the early stages, but once it falls into a local maximum, it usually cannot jump out. The final convergence result is not as good as simulated annealing. Of course, the effect of hill climbing can be improved by repeating experiments with different initial values. The choice of algorithm depends on the specific problem.
Summary
This article continues to introduce the basic sampling algorithm required for "constrained text generation"—the MCMC method. After repeated revisions, I have finally written an introduction to the MCMC method that I find satisfactory. The main difference is that it answers some detailed questions not mentioned in common MCMC tutorials. The introduction to basic algorithms ends here. Starting from the next article, we will gradually introduce how to apply these seemingly dry sampling algorithms to vivid and specific text generation tasks.
Original address: https://kexue.fm/archives/8084