拒绝采样是一种生成目标概率分布的随机样本的方法:先从较简单的分布中抽取候选值,再以精心选定的概率接受这些候选值。接受规则修正了提议分布与目标分布之间的差异,使得在理想的数学假设下,被接受的候选值严格服从目标分布。即使目标密度只确定到一个乘法常数,只要能找到合适的上界,也可以使用这种方法。
数学表述
设 为目标概率密度函数, 为能够高效生成样本的提议密度。假设存在一个已知的有限常数 ,使得在所考虑的整个定义域上,除零测集外,均有
成立。函数 称为目标密度的包络函数。
拒绝采样算法重复执行以下步骤:
从 中生成候选值 。
独立地从 上的均匀分布中生成 。
如果
则接受 。
否则丢弃 ,重新执行上述步骤。
由于 和 的积分均为一,任何有效的包络常数都满足 。
提议分布必须覆盖目标分布:对于目标概率为正的区域,提议分布不能赋予其零密度。然而,仅有这一支撑集条件还不够。除可忽略的集合外,比值 还必须存在有限上界。
将密度替换为概率质量函数、将积分替换为求和,同样的构造便适用于离散分布。更一般地,这两个分布可以具有相对于同一个参考测度的密度。
方法为何有效
对于任意可测集 ,单次提议既被接受又落在 中的概率为
令 为整个定义域,可得
因此,以接受为条件计算条件概率,得到
所以,被接受的候选值具有密度 。如果每次试验都使用新的独立随机数,且提议分布和包络保持不变,那么依次接受的值就具有统计独立性,并且同分布。
几何解释
对于连续型目标分布,定义 。在给定 的条件下,坐标 在零与 之间均匀分布。因此,从面积测度的意义上说,点对 在包络下方的区域内均匀分布。
接受操作只保留位于 下方的点。这些点的横坐标的密度与高度 成正比,因而得到目标密度。这种解释也适用于更高维的情形,只需用体积代替面积。
未归一化的目标密度
目标分布往往只能写成以下形式:
其中 可以计算,但归一化常数 未知。这种情况在贝叶斯推断中很常见,其中后验分布的密度与似然和先验密度的乘积成正比。
假设存在一个已知常数 ,满足
接受规则变为
这不需要计算 。此时接受概率为
而被接受的候选值具有密度 。
绕过归一化常数并不意味着不再需要有效的包络。确定 的全局上界可能是主要难点。
效率与包络选择
对于固定的提议分布,获得一个被接受的样本所需的试验次数 服从几何分布:
对于归一化密度,两者分别为 和 。因此,生成 个被接受的样本平均需要 次提议。
对于固定的提议分布,最小的有效常数为本质上确界
“本质”是指,仅在零测集上违反上界条件,不会影响有关分布的论证。实践中通常使用逐点成立的上界。
一个实用的提议分布需要兼顾以下要求:
- 采样成本低。
- 密度计算成本低。
- 覆盖所有目标概率为正的区域。
- 能够证明存在有限的包络。
- 与目标分布足够接近,使接受率保持在实用水平。
接受率并不是衡量效率的唯一指标。复杂的提议分布虽然可能有更高的接受率,但生成每个被接受样本所需的时间也可能更长。
尾部行为
如果提议分布的尾部衰减过快,就可能不存在有限包络。例如,正态分布作为提议分布时,无法在全局上支配柯西分布这一目标分布:柯西密度按多项式速度衰减,而正态密度则按自变量平方的指数速度衰减。两者的目标密度与提议密度之比无界。
让提议分布具有更重的尾部有助于避免这一问题,但仅凭这一点并不能保证包络高效。
示例:三角形密度
考虑
选择 上的均匀分布作为提议分布,因此在该区间内 。由于 ,取 。接受规则简化为
实现时,反复抽取相互独立的均匀随机值 和 ,每当 时就保留 。较大的候选值更容易被接受,从而得到递增的目标密度。
接受概率为
因此,平均每获得一个被接受的样本需要两次提议。
高维情形的局限
在高维空间中,提议分布可能在定义域的大部分区域内都与目标分布匹配不佳,因此拒绝采样可能变得低效。
例如,考虑乘积密度
如果最优的一维包络常数为 ,则相应的最优乘积包络常数为 ,接受概率为
因此,即使各坐标上的失配程度不大,也可能导致效率呈指数下降。这体现了维数灾难,而不是说高维采样普遍不可能:匹配良好的提议分布在高维空间中仍然可以表现良好。
当目标分布可以分解为各坐标分布的乘积时,分别对各坐标采样,可以避免因某个坐标未通过接受检验就拒绝整个向量所造成的低效。
变体与改进
挤压法
挤压法使用一个计算成本低的下界 。生成 和 后,如果
就可以立即接受该候选值。
只有尚无法判定的候选值才需要计算 。类似地,计算成本低的上界也可以用于提前拒绝候选值。有效的上下界能够在保持目标分布不变的同时降低计算成本。
自适应拒绝采样
自适应拒绝采样利用先前已计算过的点所提供的信息来更新包络。一种标准构造适用于取值为正且对数为凹函数的一维密度。
对于可微的对数凹密度,对数密度的切线给出其上界。对数空间中的分段线性上包络,对应于密度空间中的分段指数包络,后者可以积分,也可以从中采样。
增加计算点可以收紧包络并提高接受率。要保证正确性,每次更新后的包络都必须保持有效;任意拟合得到的近似函数并不足以满足要求。如果每次试验使用的都是根据过去信息选出的有效包络,并使用新的随机数,那么以接受为条件得到的分布仍然是目标分布。
与其他采样方法的关系
逆变换采样先生成一个均匀随机值,再应用累积分布函数的反函数。它不会丢弃候选值,但要求有可用的反函数或数值求逆过程。
**重要性采样**也从提议分布中抽样,但它不是拒绝候选值,而是赋予其与 成正比的权重。它主要用于估计积分或期望值,不需要有限的全局包络,不过不稳定的权重可能导致较差的估计结果。
**马尔可夫链蒙特卡洛**方法生成一个相互依赖的序列,其平稳分布为目标分布。在 Metropolis–Hastings 算法中,拒绝提议会使链停留在当前状态;拒绝采样则会丢弃候选值并重新尝试。使用固定包络的拒绝采样能够生成相互独立的目标分布样本,无需经历收敛阶段。
通过拒绝进行条件采样是指从某个分布中抽样,仅在样本满足某个事件时才予以保留。保留的样本服从相应的条件分布。当该事件的概率为正时,这种方法是精确的;但当事件很罕见时,效率就会很低。
实现与精确性
数学上的保证以正确生成提议值、使用有效界以及精确执行接受比较为前提。实际实现使用的是伪随机数和浮点运算。
对于很小的密度值,可以在对数形式下执行检验:
这能降低下溢和上溢的风险,但对于零密度和边界值,仍需谨慎处理。
仅通过检查有限网格或一组随机点得到的界,通常不能视为已获证明的全局界。如果在提议概率为正的某个集合上有 ,算法就是无效的。直接将超过一的比值截为一,并不能解决这个问题:由此得到的被接受样本的密度正比于
而不是正比于 。
当接受概率为正时,算法几乎必然终止,但试验次数不存在有限的确定性上界。设置固定的试验次数上限会引入一种可能的失败结果;如果在达到上限时返回一个已被拒绝的候选值,通常会改变输出分布。