蒙特卡罗方法

  2019-10-12 


采样与蒙特卡罗方法

为什么要采样?比如假设我们要计算积分$\int_a^bh(x)dx$,我们需要枚举$x∈[a,b]$,这是非常困难的;又比如使用mini-batch进行模型训练的时候需要采样

蒙特卡罗采样的思想就是在这种很难进行枚举的时候,使用采样来近似它。这种想法把和或者积分视作某分布下的期望,然后通过估计对应的平均值来近似这个期望(也就是说把原函数$h(x)$分解成某个函数与概率密度函数$p(x)$的乘积,即$f(x)$在$p(x)$分布上的均值)

从样本集中抽取$n$个样本$(x_1,\cdots,x_n)~p(x)$(同期望证明略,使用大数定理可证得)来近似之,则

蒙特卡罗方法是一种随机模拟技术

马尔科夫链蒙特卡罗方法(MCMC)

Markov Chain Monte Carlo

马尔科夫链是随机过程中的重要角色,不多赘述

马尔科夫过程各态遍历性需要满足:①非周期 ②不可约

非周期即存在某个取值从它出发转移回自身所需要的转移次数总是整数$d(>1)$的倍数,使得能够“连续”转移,这保证了马尔科夫过程的连续性,否则必须走特定步长(即周期)才能转移,使得马尔科夫过程不连续

不可约即为任意两个取值之间总是能以非零的概率相互转移

若马尔科夫过程是各态遍历的,无论初始值为何,随机变量的最终取值分布会收敛于一个唯一的平稳分布$\pi^*$

意味着马尔科夫过程经过多次转以后,随机变量的分布会一直逼近该平稳分布

可以从这个角度证明:

可见这个过程将导致$P$中不为1的特征值全部衰减到0,因此该过程就收敛到平稳分布

得到一个特征向量方程,收敛之后的$\pi^*$是特征值为1所对应的特征向量

于是就可以利用马尔科夫链来进行蒙特卡罗估计,这类算法被称为马尔科夫链蒙特卡罗方法(MCMC)

由于要保证各态遍历性,于是MCMC方法最适用于基于能量的模型(见上一篇笔记)

马尔科夫链的磨合过程:运行马尔科夫过程直到收敛

马尔科夫过程中的混合时间:在未收敛前的那段时间

连续的马尔科夫链也叫哈里斯链

难以预测马尔科夫链是否收敛,目前方法:

①看$P$的特征值是否趋近于0 (但通常$P^t$计算难度极大,难以表示)

②启发式方法(手动检查样本;衡量样本间的相关性)

但注意一个问题:在一个马尔科夫链的一个抽样序列无法完全表达均衡分布!

因为在一个马尔科夫链达到平稳状态后,两个连续样本之间会高度相关。(在马尔科夫过程平稳后,$P$使得每次转移使得样本的分布不变,但是$P$会改变每一次转移后的样本的形态,但同一时间下的样本形态是高度相关的)

解决办法之一是间隔抽样,另一个是使用多条马尔科夫链,每个样本从不同的马尔科夫链抽样,在深度学习中的通用实践是选取的马尔科夫链数目和小批量中的样本数相近。

如何采样?(采样方法)

对于$uniform(0,1)$,我们可以使用线性同余发生器算法LCG:$R=(A*R+B)\%M$,推导略

对于常见的概率分布,可以使用逆采样方法,将其他概率分布映射到$uniform(0,1)$,推导略(大体思路是将CDF的反函数代入$uniform(0,1)$的概率密度函数)

这需要是常见概率分布,因为必须要求累计概率分布CDF可以求逆,所以

对于非常见概率分布,可以使用接受—拒绝采样,但对MCMC使用接受—拒绝采样效果并不好

(以上的采样方法可以以后单独写篇笔记)

那MCMC该如何采样呢?我们需要采样目标概率分布$p(x)$,而目标概率分布是由转移概率决定的,所以也就是说我们要构造一个转移概率矩阵$P$,使得$p(x)$恰好是我们想要的目标概率分布

Metropolis Hasting采样

为了满足能够构造一个转移概率矩阵$P$,使得$p(x)$恰好是我们想要的目标概率分布,我们设定马尔科夫链满足细致平稳条件

若满足,则马尔科夫链为平稳分布。

细致平稳条件可理解为从$i$状态转移到$j$状态的付出消耗与从$j$转移回$i$的吸收消耗相同,所以状态$i$上的概率质量$\pi(i)$是稳定的。

那么一般情况下

$Q$为转移矩阵,$q$为转移概率。为了强行让它相等,即满足细致平稳条件,则设计一个$\alpha$(称作跳转的接受率)使得$\alpha(i,j)=p(j)q(j,i),\alpha(j,i)=p(i)q(i,j)$(对称性)

$\hat{Q}(i,j)=q(i,j)\alpha(i,j),\hat{Q}(j,i)=q(j,i)\alpha(j,i)$

$q$称为提议概率,$Q$称为提议转移矩阵,自己选择一种简单的分布即可

于是原来的转移矩阵$Q$变成了现在可以保证细致平稳条件的转移矩阵$\hat{Q}$,此转移矩阵的平稳分布就是$p(x)$了

以上称为Metropolis抽样

那么$\alpha$该如何更好地取值呢?太小的话会导致拒绝率太高,收敛速度太慢。发现如果在等式两边同时扩大相同的倍数,等式依然成立,于是想到将等式两边同比例放大使得最大的一边放大到1(概率最大为1),即

(这里的推导:当$\alpha(i,j)>\alpha(j,i),则\alpha(i,j)先到1,\alpha^(j,i)=\frac{1}{\alpha(i,j)}·\alpha(j,i)<1$ *缩放

当$\alpha(j,i)>\alpha(i,j),则\alpha(j,i)先到1,\alpha^(i,j)=\frac{\alpha(i,j)}{\alpha(j,i)}$ *缩放

整合上两式记得上面的等式)

于是$p(x)$是目标平稳概率分布,自设已知;$q(x)$为提议概率分布,自设已知,那么就可以求出转移概率$\alpha$了

从$uniform(0,1)$中采样$u$,如果$u<\alpha(i,j)$,(相当于在拒绝采样中,随机采样点落入函数范围内),则该跳转成功,否则该跳转失败,以此迭代(这里使用接受-拒绝采样算法的思想,用提议转移矩阵$Q$去求得转移矩阵$\hat{Q}$)

这就是Metropolis Hasting采样算法

算法如下:

0

Gibbs采样(深度学习中的最佳选择)

针对高维的情形,发现在高维情况下自然成立一个式子使得细致平稳条件成立,也就可以不拒绝,使得收敛迅速。Gibbs采样每一步都只更新变量的一个小部分

对平面上任意两点$X,Y$

0

0


且听风吟