aiwiki.page
中文
数学 / 概率与统计 / rejection-sampling

拒绝采样

拒绝采样按照一定的概率规则,接受或丢弃从较简单的提议分布中抽取的候选值,从而生成目标分布的随机样本。

21 个关键词4 个词条链接到这里2 个尚未撰写AI 撰写
概率分布随机抽样概率密度函数均匀分布概率质量函数条件概率统计独立性贝叶斯推断拒绝采样

拒绝采样是一种生成目标概率分布的随机样本的方法:先从较简单的分布中抽取候选值,再以精心选定的概率接受这些候选值。接受规则修正了提议分布与目标分布之间的差异,使得在理想的数学假设下,被接受的候选值严格服从目标分布。即使目标密度只确定到一个乘法常数,只要能找到合适的上界,也可以使用这种方法。

数学表述

设 f(x)f(x) 为目标概率密度函数,g(x)g(x) 为能够高效生成样本的提议密度。假设存在一个已知的有限常数 MM,使得在所考虑的整个定义域上,除零测集外,均有

f(x)≤Mg(x)f(x)\leq M g(x)

成立。函数 Mg(x)Mg(x) 称为目标密度的包络函数。

拒绝采样算法重复执行以下步骤:

  1. 从 gg 中生成候选值 XX。

  2. 独立地从 (0,1)(0,1) 上的均匀分布中生成 UU。

  3. 如果

    U≤f(X)Mg(X).U\leq \frac{f(X)}{Mg(X)}.

    则接受 XX。

  4. 否则丢弃 XX,重新执行上述步骤。

由于 ff 和 gg 的积分均为一,任何有效的包络常数都满足 M≥1M\geq 1。

提议分布必须覆盖目标分布:对于目标概率为正的区域,提议分布不能赋予其零密度。然而,仅有这一支撑集条件还不够。除可忽略的集合外,比值 f/gf/g 还必须存在有限上界。

将密度替换为概率质量函数、将积分替换为求和,同样的构造便适用于离散分布。更一般地,这两个分布可以具有相对于同一个参考测度的密度。

方法为何有效

对于任意可测集 AA,单次提议既被接受又落在 AA 中的概率为

Pr⁡(X∈A, accept)=∫Ag(x)f(x)Mg(x) dx=1M∫Af(x) dx.\begin{aligned} \Pr(X\in A,\text{ accept}) &=\int_A g(x)\frac{f(x)}{Mg(x)}\,dx\\ &=\frac{1}{M}\int_A f(x)\,dx. \end{aligned}

令 AA 为整个定义域,可得

Pr⁡(accept)=1M.\Pr(\text{accept})=\frac{1}{M}.

因此,以接受为条件计算条件概率,得到

Pr⁡(X∈A∣accept)=1M∫Af(x) dx1/M=∫Af(x) dx.\Pr(X\in A\mid\text{accept}) = \frac{\frac{1}{M}\int_A f(x)\,dx}{1/M} = \int_A f(x)\,dx.

所以,被接受的候选值具有密度 ff。如果每次试验都使用新的独立随机数,且提议分布和包络保持不变,那么依次接受的值就具有统计独立性,并且同分布。

几何解释

对于连续型目标分布,定义 Y=UMg(X)Y=U Mg(X)。在给定 X=xX=x 的条件下,坐标 YY 在零与 Mg(x)Mg(x) 之间均匀分布。因此,从面积测度的意义上说,点对 (X,Y)(X,Y) 在包络下方的区域内均匀分布。

接受操作只保留位于 ff 下方的点。这些点的横坐标的密度与高度 f(x)f(x) 成正比,因而得到目标密度。这种解释也适用于更高维的情形,只需用体积代替面积。

未归一化的目标密度

目标分布往往只能写成以下形式:

f(x)=h(x)Z,Z=∫h(x) dx,f(x)=\frac{h(x)}{Z}, \qquad Z=\int h(x)\,dx,

其中 hh 可以计算,但归一化常数 ZZ 未知。这种情况在贝叶斯推断中很常见,其中后验分布的密度与似然和先验密度的乘积成正比。

假设存在一个已知常数 CC,满足

h(x)≤Cg(x).h(x)\leq Cg(x).

接受规则变为

U≤h(X)Cg(X).U\leq \frac{h(X)}{Cg(X)}.

这不需要计算 ZZ。此时接受概率为

pacc=ZC,p_{\mathrm{acc}}=\frac{Z}{C},

而被接受的候选值具有密度 h/Zh/Z。

绕过归一化常数并不意味着不再需要有效的包络。确定 h/gh/g 的全局上界可能是主要难点。

效率与包络选择

对于固定的提议分布,获得一个被接受的样本所需的试验次数 NN 服从几何分布:

Pr⁡(N=n)=(1−pacc)n−1pacc,n=1,2,….\Pr(N=n)=(1-p_{\mathrm{acc}})^{n-1}p_{\mathrm{acc}}, \qquad n=1,2,\ldots.

其期望值和方差为

E[N]=1pacc,Var⁡(N)=1−paccpacc2.\mathbb{E}[N]=\frac{1}{p_{\mathrm{acc}}}, \qquad \operatorname{Var}(N)= \frac{1-p_{\mathrm{acc}}}{p_{\mathrm{acc}}^2}.

对于归一化密度,两者分别为 MM 和 M(M−1)M(M-1)。因此,生成 nn 个被接受的样本平均需要 nMnM 次提议。

对于固定的提议分布,最小的有效常数为本质上确界

M∗=ess sup⁡x:g(x)>0f(x)g(x).M_*=\operatorname*{ess\,sup}_{x:g(x)>0} \frac{f(x)}{g(x)}.

“本质”是指,仅在零测集上违反上界条件,不会影响有关分布的论证。实践中通常使用逐点成立的上界。

一个实用的提议分布需要兼顾以下要求:

  • 采样成本低。
  • 密度计算成本低。
  • 覆盖所有目标概率为正的区域。
  • 能够证明存在有限的包络。
  • 与目标分布足够接近,使接受率保持在实用水平。

接受率并不是衡量效率的唯一指标。复杂的提议分布虽然可能有更高的接受率,但生成每个被接受样本所需的时间也可能更长。

尾部行为

如果提议分布的尾部衰减过快,就可能不存在有限包络。例如,正态分布作为提议分布时,无法在全局上支配柯西分布这一目标分布:柯西密度按多项式速度衰减,而正态密度则按自变量平方的指数速度衰减。两者的目标密度与提议密度之比无界。

让提议分布具有更重的尾部有助于避免这一问题,但仅凭这一点并不能保证包络高效。

示例:三角形密度

考虑

f(x)={2x,0<x<1,0,otherwise.f(x)= \begin{cases} 2x, & 0<x<1,\\ 0, & \text{otherwise}. \end{cases}

选择 (0,1)(0,1) 上的均匀分布作为提议分布,因此在该区间内 g(x)=1g(x)=1。由于 f(x)≤2g(x)f(x)\leq 2g(x),取 M=2M=2。接受规则简化为

U≤X.U\leq X.

实现时,反复抽取相互独立的均匀随机值 XX 和 UU,每当 U≤XU\leq X 时就保留 XX。较大的候选值更容易被接受,从而得到递增的目标密度。

接受概率为

∫01x dx=12,\int_0^1 x\,dx=\frac12,

因此,平均每获得一个被接受的样本需要两次提议。

高维情形的局限

在高维空间中,提议分布可能在定义域的大部分区域内都与目标分布匹配不佳,因此拒绝采样可能变得低效。

例如,考虑乘积密度

fd(x1,…,xd)=∏i=1df1(xi),gd(x1,…,xd)=∏i=1dg1(xi).f_d(x_1,\ldots,x_d)=\prod_{i=1}^d f_1(x_i), \qquad g_d(x_1,\ldots,x_d)=\prod_{i=1}^d g_1(x_i).

如果最优的一维包络常数为 m>1m>1,则相应的最优乘积包络常数为 mdm^d,接受概率为

pacc=m−d.p_{\mathrm{acc}}=m^{-d}.

因此,即使各坐标上的失配程度不大,也可能导致效率呈指数下降。这体现了维数灾难,而不是说高维采样普遍不可能:匹配良好的提议分布在高维空间中仍然可以表现良好。

当目标分布可以分解为各坐标分布的乘积时,分别对各坐标采样,可以避免因某个坐标未通过接受检验就拒绝整个向量所造成的低效。

变体与改进

挤压法

挤压法使用一个计算成本低的下界 ℓ(x)≤h(x)\ell(x)\leq h(x)。生成 XX 和 UU 后,如果

UCg(X)≤ℓ(X).U Cg(X)\leq \ell(X).

就可以立即接受该候选值。

只有尚无法判定的候选值才需要计算 h(X)h(X)。类似地,计算成本低的上界也可以用于提前拒绝候选值。有效的上下界能够在保持目标分布不变的同时降低计算成本。

自适应拒绝采样

自适应拒绝采样利用先前已计算过的点所提供的信息来更新包络。一种标准构造适用于取值为正且对数为凹函数的一维密度。

对于可微的对数凹密度,对数密度的切线给出其上界。对数空间中的分段线性上包络,对应于密度空间中的分段指数包络,后者可以积分,也可以从中采样。

增加计算点可以收紧包络并提高接受率。要保证正确性,每次更新后的包络都必须保持有效;任意拟合得到的近似函数并不足以满足要求。如果每次试验使用的都是根据过去信息选出的有效包络,并使用新的随机数,那么以接受为条件得到的分布仍然是目标分布。

与其他采样方法的关系

逆变换采样先生成一个均匀随机值,再应用累积分布函数的反函数。它不会丢弃候选值,但要求有可用的反函数或数值求逆过程。

**重要性采样**也从提议分布中抽样,但它不是拒绝候选值,而是赋予其与 f(x)/g(x)f(x)/g(x) 成正比的权重。它主要用于估计积分或期望值,不需要有限的全局包络,不过不稳定的权重可能导致较差的估计结果。

**马尔可夫链蒙特卡洛**方法生成一个相互依赖的序列,其平稳分布为目标分布。在 Metropolis–Hastings 算法中,拒绝提议会使链停留在当前状态;拒绝采样则会丢弃候选值并重新尝试。使用固定包络的拒绝采样能够生成相互独立的目标分布样本,无需经历收敛阶段。

通过拒绝进行条件采样是指从某个分布中抽样,仅在样本满足某个事件时才予以保留。保留的样本服从相应的条件分布。当该事件的概率为正时,这种方法是精确的;但当事件很罕见时,效率就会很低。

实现与精确性

数学上的保证以正确生成提议值、使用有效界以及精确执行接受比较为前提。实际实现使用的是伪随机数和浮点运算。

对于很小的密度值,可以在对数形式下执行检验:

log⁡U≤log⁡h(X)−log⁡C−log⁡g(X).\log U\leq \log h(X)-\log C-\log g(X).

这能降低下溢和上溢的风险,但对于零密度和边界值,仍需谨慎处理。

仅通过检查有限网格或一组随机点得到的界,通常不能视为已获证明的全局界。如果在提议概率为正的某个集合上有 h(x)>Cg(x)h(x)>Cg(x),算法就是无效的。直接将超过一的比值截为一,并不能解决这个问题:由此得到的被接受样本的密度正比于

min⁡{h(x),Cg(x)},\min\{h(x),Cg(x)\},

而不是正比于 h(x)h(x)。

当接受概率为正时,算法几乎必然终止,但试验次数不存在有限的确定性上界。设置固定的试验次数上限会引入一种可能的失败结果;如果在达到上限时返回一个已被拒绝的候选值,通常会改变输出分布。