拒绝采样

接收-拒绝算法是利用符合某个分布的函数g去模拟目标概率密度函数f，且f/g是有界的，标准的接收-拒绝算法为：

• 从g中生成样本X_{i}
• 如果U_{i}\leq f(X_{i})/g(X_{i})，则接收X_{i}为函数的采样点
• 如果不满足上述条件，则i+1

来源：

G Casella, CP Robert, MT Wells.(2004).Generalized Accept–Reject sampling schemes. Lecture Notes-Monograph Series(45):342-347

例子：

下面这张图很好地阐释了拒绝采样的基本思想。假设我们相对PDF为p(x)的函数进行采集，但是由于种种原因（例如这个函数很复杂），对其进行采样时相对困难的。但是，另外一个PDF（概率密度函数）为q(x)的函数则相对容易采样，例如其就是一个均匀分布。那么，当我们将q(x)与一个常数M相乘之后，可以实现下图所示之关系，即Mq(x)将p(x)完全罩住。

然后重复如下步骤，直到获得m个被接受的采样点：

• 从q(x)中获得一个随机采样点x(i)
• 对于X_{i}计算接受概率\alpha =\frac{p(x_{i})}{Mq(x_{i})}
• 从正态分布(0,1)中随机生成一个值，用u表示
• 如果\alpha \geq u，则接受X_{i}作为一个来自p(x)的采样值，否则就拒绝X_{i}并回到第一步

基于蒙特卡洛思想的拒绝采样方法在机器学习技术中占据着非常重要的地方，因为这些采样方法可以作为很多模型参数估计的基础。

发展历史

描述

随机变量抽样的基本原理是由Von Neumann在1951年完成的。1954年，Kahn对Von Neumann的理论予以系统化并加以扩充。此后，在抽样的基本原理方面几乎没有什么太大的突破，而主要是对一些分布类和重要的分布设计更好的抽样方法。产生这一现象的原因在于，给出随机变量抽样的一般原理固然重要，可是，将一般原理应用于若干重要分布的随机变量抽样中，给出理想的抽样方法同样很重要，从困难程度说，后者有时比前者还困难。

主要事件

发展分析

瓶颈

它的一个瓶颈涉及到采样效率的问题。参考分布其实离目标分布还有一定距离，这样在采样过程中被拒绝的点就会更多，这种开销其实相当浪费。从图形上来看就是包裹的越紧实越好。但是这种情况的参考分布往往又不那么容易得到。

未来发展方向

考虑用分布式计算机计算采样点

Contributor: Peng Jiang