前面转载过一篇文章MCMC和Gibbs Sampling,文中详细介绍了MCMC算法及其证明.本文用几个简单的例子再来理解一下MCMC.

假设有一个抽样任务,变量X取值的样本空间为\{1,2,3\},且取1,2,3三个值的概率分别为\frac{1}{2},\frac{1}{4},\frac{1}{4}。那么这时候你要如何从这个分布中进行采样?

我想大多数人自己都写过这样简单的程序,首先根据各离散取值的概率大小把[0,1]区间划分为[0,0.5],[0,5,0.75],[0.75,1]这三个区间,再通过计算机产生[0,1]之间的伪随机数,根据伪随机数的落点即可完成一次采样。
image.png

现在把问题改为二维的,每个维度上的取值和概率同上,我们可以把二维平面按比例切分,然后产生两个[0,1]之间的伪随机数,根据这两个伪随机数的落点进行采样:
image.png

你可能已经看出来了,随着维度的增加抽样的复杂度是程指数增加的.假设我们有100维的数据,每个维度有10个取值,那么概率空间的大小为10^{100},作为对比,已知宇宙的基本粒子大约有10^{87}个。

上面例子取值是离散的,但如果分布P(x)是连续的,我们无法直接对概率进行"分段",聪明的你可能会想到,我们可以已固定长度进行"分段",P(x)的积分就是这段出现的概率.不幸的是,并不是所有的函数都可以计算积分,而且已固定长度进行"分段",同样有"维数灾难"的问题.

如果仔细观察"等距计算"的结果,就会发现绝大多数点算出的概率都很小,而少部分点的概率非常大。而如果我们忽略大多数概率小的点,只计算概率大的那小部分点,对最后数学期望的结果影响非常小。这是MCMC思路的直观部分。


参考:
https://www.zhihu.com/question/60437632

posted @ 2019-01-01 15:05:47
评论加载中...

发表评论