拒绝性采样：从通俗解释到深入推导及其在大模型中的应用

拒绝性采样（Rejection Sampling）是一种在统计学和机器学习中常用的采样方法，尤其在生成模型、强化学习等领域中有着广泛的应用。它的核心目标是帮助我们从一个复杂的分布中获取样本，尤其是在直接采样比较困难的情况下。本文将从通俗的解释开始，逐步深入到数学原理和推导，最后结合大模型中的实际应用，详细探讨拒绝性采样的原理和重要性。

---

什么是拒绝性采样？通俗解释

拒绝性采样是一种从目标分布中获取样本的方法，特别适用于目标分布 ( $p(x)$ ) 难以直接采样的情况。它的基本思路是：通过从一个容易采样的分布（称为建议分布 ( $q(x)$ )）中采样，然后根据一定的概率接受或拒绝这些样本，最终得到的样本近似于目标分布 ( $p(x)$ )。

用通俗的例子来理解

---

例子 1：钓鱼选鱼

假设你想钓一种特定的鱼（比如鲈鱼），但你只有一个普通的鱼竿，能钓到湖里各种各样的鱼，包括鲈鱼、鲤鱼、鲶鱼等等。你每次钓上一条鱼后，会检查它是不是鲈鱼：

• 如果是鲈鱼，你就保留这条鱼（接受）。
• 如果不是鲈鱼，你就把它放回湖里（拒绝）。

通过不断重复这个过程，你最终留下来的鱼就都是鲈鱼。这个过程就是拒绝性采样的核心思想：

• 普通的鱼竿对应于建议分布 ( $q(x)$ )（容易采样，钓到各种鱼）。
• 鲈鱼对应于目标分布 ( $p(x)$ )（你想要的特定鱼，难以直接只钓到它）。
• 检查是否是鲈鱼的过程对应于接受或拒绝的概率。

---

例子 2：抽奖挑奖品

假设你参加一个抽奖活动，想抽中一个特定的奖品（比如一台游戏机），但奖池里有很多不同的奖品（游戏机、玩具、零食等等），你只能随机抽一次奖券。你每次抽到一张奖券后，会检查它对应的奖品：

• 如果是游戏机，你就保留这张奖券（接受）。
• 如果不是游戏机（比如抽到零食），你就把它扔掉（拒绝），然后再抽一张。

通过不断重复这个过程，你最终留下的奖券都会是游戏机的。这个过程就是拒绝性采样的核心思想：

• 随机抽奖对应于建议分布 ( $q(x)$ )（容易采样，各种奖品都有可能）。
• 游戏机对应于目标分布 ( $p(x)$ )（你想要的特定奖品，难以直接抽到）。
• 检查是否是游戏机的过程对应于接受或拒绝的概率。

---

这两个例子都尽量贴近日常生活，直观地展示了拒绝性采样的逻辑：从一个容易获取的“大集合”中不断挑选，直到留下符合“目标”的部分。

---

拒绝性采样的数学原理

现在，我们用数学语言更严谨地描述拒绝性采样的过程。假设我们有一个目标分布 ( $p(x)$ )，但直接从 ( $p(x)$ ) 采样很困难。我们需要选择一个建议分布 ( $q(x)$ )，满足以下两个条件：

1. ( $q(x)$ ) 是一个容易采样的分布。
2. 存在一个常数 ( $M$ )，使得对于所有的 ( $x$ )，有：
   $$p(x)\le Mq(x)$$
   也就是说，( $Mq(x)$ ) 是 ( $p(x)$ ) 的一个上界。

拒绝性采样的步骤

拒绝性采样的具体步骤如下：

1. 从建议分布 ( $q(x)$ ) 中采样一个点 ( $x$ )。
2. 从均匀分布 ( $U(0,1)$ ) 中采样一个数 ( $u$ )。
3. 计算接受概率：
   $$\frac{p(x)}{Mq(x)}$$
   • 如果 ( $u<\frac{p(x)}{Mq(x)}$ )，则接受 ( $x$ )。
   • 否则，拒绝 ( $x$ )。

通过不断重复这个过程，接受的样本 ( $x$ ) 将近似于来自目标分布 ( $p(x)$ )。

---

为什么拒绝性采样有效？数学推导

为了理解拒绝性采样为什么有效，我们需要证明最终接受的样本分布确实是 ( $p(x)$ )。以下是详细的推导。

接受概率的意义

假设我们从 ( $q(x)$) 中采样一个点 ( $x$ )。根据拒绝性采样的规则，接受 ( $x$ ) 的概率是：
$$P(\text{accept}|x)=\frac{p(x)}{Mq(x)}$$
这意味着：

• 在 ( $p(x)$ ) 较高的区域，接受概率 ( $\frac{p(x)}{Mq(x)}$ ) 较大，( $x$ ) 更容易被接受。
• 在 ( $p(x)$ ) 较低的区域，接受概率较小，( $x$ ) 更容易被拒绝。

最终，接受的样本会更倾向于来自 ( $p(x)$ ) 高的区域，从而近似于 ( $p(x)$ )。

接受样本的分布

我们来推导接受样本的分布。假设 ( $x$ ) 是从 ( $q(x)$ ) 中采样的，那么接受 ( $x$ ) 的联合概率是：
$$q(x)\cdot P(\text{accept}|x)=q(x)\cdot \frac{p(x)}{Mq(x)}=\frac{p(x)}{M}$$
由于 ( $M$ ) 是一个常数，接受样本的分布为：
$$\frac{p(x)}{M}$$
为了得到归一化的概率分布，我们需要计算接受的总概率（即接受率）。接受率 ( $P(\text{accept})$ ) 是：
$$P(\text{accept})=\int q(x)\cdot \frac{p(x)}{Mq(x)}dx=\int \frac{p(x)}{M}dx=\frac{1}{M}$$
因此，归一化后的接受样本分布为：
$$\frac{\frac{p(x)}{M}}{\frac{1}{M}}=p(x)$$
这证明了拒绝性采样最终得到的样本分布确实是目标分布 ( $p(x)$ )。

---

拒绝性采样的效率问题

拒绝性采样的效率取决于建议分布 ( $q(x)$ ) 和常数 ( $M$ ) 的选择：

• 如果 ( $M$ ) 太大，接受率 ( $P(\text{accept})=\frac{1}{M}$ ) 会很低，大部分样本会被拒绝，导致效率低下。
• 如果 ( $M$ ) 太小，可能不满足 ( $p(x)\le Mq(x)$ ) 的条件，算法会失效。

因此，在实际应用中，选择一个合适的 ( $q(x)$ ) 和 ( $M$ ) 非常重要。理想情况下，( $q(x)$ ) 应该尽可能接近 ( $p(x)$ )，以减少拒绝率。

---

拒绝性采样在大模型中的应用

拒绝性采样不仅在理论上重要，在实际的大模型训练中也有着广泛的应用，尤其是在生成高质量训练数据的场景中。以下我们以一段技术报告为例，探讨拒绝性采样在大模型中的具体应用。

技术报告描述

2.3.3. Rejection Sampling and Supervised Fine-Tuning
When reasoning-oriented RL converges, we utilize the resulting checkpoint to collect SFT
(Supervised Fine-Tuning) data for the subsequent round. Unlike the initial cold-start data, which
primarily focuses on reasoning, this stage incorporates data from other domains to enhance the
model’s capabilities in writing, role-playing, and other general-purpose tasks. Specifically, we
generate the data and fine-tune the model as described below.
Reasoning data We curate reasoning prompts and generate reasoning trajectories by performing rejection sampling from the checkpoint from the above RL training. In the previous stage,
we only included data that could be evaluated using rule-based rewards. However, in this stage,
we expand the dataset by incorporating additional data, some of which use a generative reward
model by feeding the ground-truth and model predictions into DeepSeek-V3 for judgment.
Additionally, because the model output is sometimes chaotic and difficult to read, we have
filtered out chain-of-thought with mixed languages, long parapraphs, and code blocks. For
each prompt, we sample multiple responses and retain only the correct ones. In total, we collect
about 600k reasoning related training samples.
Source: https://arxiv.org/pdf/2501.12948

在一份技术报告中，提到在推理导向的强化学习（RL）收敛后，利用得到的模型检查点（checkpoint）来收集监督微调（SFT）数据。与初始阶段的冷启动数据主要关注推理不同，这个阶段纳入了其他领域的数据，以增强模型在写作、角色扮演和其他通用任务中的能力。

具体来说，在生成推理数据时，他们从 RL 训练的检查点中进行拒绝性采样。之前的阶段只包括可以使用基于规则的奖励进行评估的数据，但在这个阶段，他们通过纳入额外的数据来扩展数据集，其中一些数据使用生成奖励模型，通过将 ground-truth 和模型预测输入 DeepSeek-V3 进行判断。

此外，由于模型输出有时杂乱无章且难以阅读，他们过滤掉了混合语言、长段落和代码块的思维链。对于每个提示，他们采样多个响应并仅保留正确的响应。总共收集了约 600k 个与推理相关的训练样本。

---

拒绝性采样在大模型中的具体应用

从技术报告的描述中，我们可以看到拒绝性采样在大模型训练中的核心作用：通过从模型的输出中选择高质量的样本，用于后续的监督微调。具体来说：

• 模型的输出分布可以看作建议分布 ( $q(x)$ )。
• 目标分布 ( $p(x)$ ) 是正确响应的分布（即符合要求的推理轨迹）。
• 通过拒绝性采样，他们从 ( $q(x)$ ) 中采样响应 ( $x$ )，然后根据某个接受准则（比如是否正确）来决定是否保留 ( $x$ )。

数学视角

假设模型的输出分布为 ( $q(x)$ )，而我们希望的正确响应的分布为 ( $p(x)$ )。在拒绝性采样中：

1. 从 ( $q(x)$ ) 中采样一个响应 ( $x$ )。
2. 使用一个接受准则（比如是否正确）来决定是否接受 ( $x$ )。
3. 如果接受准则与 ( $p(x)$ ) 成正比，那么接受的样本将近似于来自 ( $p(x)$ )。

在技术报告中，他们通过判断模型的预测是否正确来决定是否接受样本。这可以看作是 ( $p(x)$ ) 是正确响应的分布，而 ( $q(x)$ ) 是模型的输出分布。通过拒绝性采样，他们能够从模型的输出中选择出正确的响应，用于后续的微调。

实际操作

在实际操作中，他们对每个提示采样多个响应，然后使用规则（如是否正确、是否包含杂乱内容）来筛选样本。例如：

• 过滤掉混合语言、长段落和代码块的响应。
• 只保留正确的推理轨迹。

最终，他们收集了约 600k 个高质量的推理相关训练样本，用于微调模型。

---

拒绝性采样的优势

拒绝性采样在大模型中的应用有以下优势：

1. 数据质量提升：即使模型的输出不完美，通过拒绝性采样，可以从中提取出有用的、正确的数据。
2. 灵活性：拒绝性采样可以结合多种接受准则（如规则判断、生成奖励模型等），适应不同的任务需求。
3. 数据扩展：在数据稀缺或标注成本高的情况下，拒绝性采样能够从模型的输出中生成高质量的训练数据。

---

总结

拒绝性采样是一种强大的采样方法，可以帮助我们从复杂的分布中获取样本，尤其是在直接采样困难的情况下。其核心思想是通过从建议分布中采样，然后根据一定的概率接受或拒绝样本，最终得到的样本近似于目标分布。通过数学推导，我们证明了拒绝性采样能够正确地生成目标分布的样本。

在大模型的训练中，拒绝性采样被广泛用于生成高质量的训练数据。通过从模型的输出中选择正确的响应，可以提高后续微调的效果。这种方法在数据稀缺或标注成本高的场景中尤为重要。

希望本文能够帮助读者更好地理解拒绝性采样的原理及其在大模型中的应用。如果你对拒绝性采样的具体实现或更多应用场景有兴趣，欢迎留言讨论！

后记

2025年2月24日13点44分于上海，在Grok 3大模型辅助下完成。