拒绝采样

拒绝采样通过从一个更简单的包络分布中提出样本，并以目标密度与包络密度之比的概率接受每个提议，从而从目标密度中抽取精确样本，其余的则被丢弃。

Definition

拒绝采样是一种蒙特卡洛技术，它从一个在常数因子内支配目标密度的提议密度中生成候选样本，然后以等于目标密度与边界密度之比的概率接受该候选样本，从而产生与目标密度精确分布的接受值。

Scope

本主题涵盖了基本的接受-拒绝算法及其正确性、包络和边界常数在确定效率中的作用、用于避免昂贵密度评估的挤压技术，以及用于对数凹密度的自适应构造（如自适应拒绝采样）。它与马尔可夫链方法中的接受步骤相关联。

Core questions

• 为什么接受的候选样本精确地按照目标密度分布？
• 边界常数如何控制每个接受样本所需的提议数量的期望值？
• 挤压函数如何减少昂贵的密度评估次数？
• 如何为对数凹密度自动构建和改进包络？

Key concepts

• 包络分布
• 边界常数
• 接受概率
• 挤压函数
• 对数凹性

Key theories

接受-拒绝原理

如果一个提议密度乘以一个常数在所有地方都支配目标密度，那么以等于目标密度与边界密度之比的概率接受提议会产生精确的目标样本；接受概率等于边界常数的倒数。

自适应拒绝采样

对于对数凹密度，由切线和弦构建的分段指数包络可以在每个被拒绝点进行细化，从而使接受率趋向于一，而无需归一化常数。

Clinical relevance

拒绝采样从仅在常数因子内已知的密度中生成变量，这在贝叶斯计算中经常出现；特别是自适应拒绝采样为许多吉布斯采样器提供了全条件抽样，使其成为实际后验模拟的基本组成部分。

History

冯·诺依曼在蒙特卡洛计算的早期描述了接受-拒绝思想；后来的工作推广了包络，增加了挤压步骤以提高效率，并开发了自适应方案，可以自动收紧贝叶斯采样中使用的对数凹目标的包络。

Key figures

• John von Neumann
• Luc Devroye
• Walter Gilks
• Christian P. Robert

Seminal works

• devroye1986
• gilks1992

Frequently asked questions

什么使拒绝采样高效或低效？

效率取决于缩放后的包络与目标密度拟合的紧密程度。松散的包络意味着大的边界常数和许多被拒绝的提议；在高维情况下，接受率可能会变得不切实际地小。

当归一化常数未知时，为什么拒绝采样有用？

该方法只需要目标密度在乘法常数内的信息，因为该常数被吸收到边界常数中。这就是为什么它与贝叶斯后验自然结合的原因，贝叶斯后验通常仅在其归一化因子内已知。