随机采样方法

  当知道某个模型的概率分布的时候,常常想产生这种概率分布的样本,甚至某些复杂的分布模型,也可以根据这种方式产生大规模样本考察其数学期望等特性,所以随机采样算是一个十分重要的算法。本人最初还是看LDA算法的时候,最初接触到这个Gibbs采样,当初看的也是云里雾里的,乘着这次看徐亦达老师的视频,对随机采样的常见算法做一个归纳整理,包括一些简单的采样方式以及MCMC(Markov Chain Monte Carlo)采样。

一、逆CDF采样

  对某个分布的CDF曲线(累积分布函数),在Y轴[0,1]的区间上做均匀采样,然后其在曲线上相同y的点映射到X轴(inverse CDF),即为所采样本。
  但是不是所有分布的inverse CDF都能得到的,所以这种采样方式不太通用。
逆CDF采样

二、接受-拒绝采样(Rejection Sampling)

  基本思路就是用一个简单易于抽样的分布类型q(x),乘以一个大于1的常数值M,使其完全包络待采样分布类型p(x)的PDF(概率密度函数),然后按照Mq(x)进行采样,同时还进行一个选择系数$U~Uniform[0,1]$采样,然后当$Y=Mq(x)U\lt p(x)$的时候,此时采样点被p(x)分布所包围,则接受之,否则拒绝之。
  这种方法确实能进行有效采样,但是主要问题是效率不高,p(x)和q(x)两者的分布越接近,采样效率才会越高,但实际上往往比较难寻十分合适的q(x)。对此有个改进,叫做Adaptive Rejection Sampling(ARS采样),就是让包络分布尽可能的贴近目的采样函数,比较复杂,且前提条件是$log(p(x))$是凸函数的时候才可以用。
接收拒绝采样

三、重要性采样(Importance Sampling)

  这个采样,感觉主要是用来计算数学期望的,而不是用来真正产生符合原分布的单个样本的。就是原分布f(x)比较难积分且难以采样,那么就无法用积分或者用大数定理采样来估算数学期望,这时候就引入一个辅助的分布q(x)来采样,然后相应的$\frac{f(x)}{q(x)}$就作为了这个采样点对最终数学期望贡献率的权重了,所以叫做重要性采样。
  怎么感觉重要性采样的重要性不大咧~

四、MCMC采样

  说道MCMC采样,就不得不说到马尔科夫链了,其假设了某个随机序列当前的输出,只跟其前N-1个输出相关,叫做N阶马尔科夫链。对于1阶马尔科夫链:
$$ P(Xt|X{t-1},X_{t-2},…,X_1) = P(Xt|X{t-1})$$
  马尔科夫链最Amazoning的,是对于有限的状态空间,其各个状态的转移概率是固定与t无关的(转移矩阵P),且任意两个状态是连通的,那么在较长时间后,马尔科夫过程逐渐处于稳定状态,且与初始状态无关,而且这个稳定状态是唯一固定的。而如果能够让这个马尔科夫链的稳定状态恰好是我们所需要采样的f(x)的分布,那么一旦马尔科夫链稳定之后,其所有的输出序列都是我们想要的采样样本了!

4.1 M-H(Metropolis Hastings)采样

  假设需要采样的分布为f(x),那么需要找到一个分布k(x),使得f(x)k(y|x)=f(y)k(x|y),就是x->y与y->x的转换概率是相同的,叫做细致平稳条件(detail balance),是马尔科夫链平稳的必要条件。所以M-H采样方法,就是要设法找到这个k来实现细致平稳,让马氏链最终收敛后不断产生需要的采样。
  对于M-H中的接受率$\alpha$的表达如下
$$\alpha=min{1,\frac{f(y)q(x|y)}{f(x)q(y|x)}}$$
  初看来会比较的费解,具体可以查看参考文献,其实是在保持细致平稳条件下提交接受率,以方便马尔科夫链快速收敛而操作的。
  所以需要看清楚的是,上文的f(x)q(x|y)通常条件下不满足细致平稳条件,而需要添加一个$\alpha$的接受率之后,$f(x)q(y|x)\alpha’(y|x)$以及和$f(y)q(x|y)\alpha’(x|y)$才是马氏平稳的。而最终采样的时候只看见一个$\alpha$,其实是保持细致平稳增加接受率化简后的结果,然后从$Uniform~(0,1)$中随机采样然后跟接受率比较,判断是否转移到备选点还是停留在远点不转移(但无论如何都是被接受的有效采样点)。
  采样过程摘录如下:
MCMC Metropolis Hastings采样过程

4.2 Gibbs采样

  首先结论上,Gibbs采样其实是M-H采样的一个特例,就是让其接收率$\alpha$=1最高时候的一种特殊情况,这样在多维度采样的时候,采样效率要高的多。考虑二位MCMC采样,设位于x=x1直线上的两点A(x1,y1)和B(x1,y2),那么从A转移到B和从B转移到A的概率(就是沿着X轴转移)描述如下:
$$p(x1,y1)p(y2|x1)=p(x1)p(y1|x1)p(y2|x1)$$
$$p(x1,y2)p(y1|x1)=p(x1)p(y2|x1)p(y1|x1)$$
  因此
$$p(x1,y1)p(y2|x1)==p(x1,y2)p(y1,x1)$$
  可以得到
$$p(A)p(y2|x1)==p(B)p(y1,x1)$$
  就是在X轴上的任意转移,都满足细致平稳条件,而且这个时候的接受率$\alpha$=1。
  这种情况也可以推广到多维分布,只需要沿着某一个坐标轴${xi}$上做转移,定义$Xi^{-1}=(x1,x2,…,xi-1,xi+1,…,xn)$,那么其转移概率为$p(xi|Xi^{-1})$。

本文完!

参考