第十七章：Monte Carlo Methods

17. Monte Carlo Methods

随机算法：随机算法可以粗略地分为两类：拉斯维加斯算法（Las Vegas algorithms）和蒙特卡洛算法（Monte Carlo algorithms）。

拉斯维加斯算法（Las Vegas algorithms）：总是精确地返回一个正确答案（或者返回算法失败）。 该方法通常需要占用随机量的计算资源（一般指内存或运行时间）。

蒙特卡洛算法（Monte Carlo algorithms）：蒙特卡罗方法返回的答案具有随机大小的错误。

花费更多的计算资源（通常包括内存和运行时间）可以减少这种错误。 在任意固定的计算资源下， 蒙特卡罗算法可以得到一个近似解。

为什么要sampling？：1.有时我们使用它加速一些很费时却易于处理的求和估计；2.有时我们用sampling去近似一个难以处理的求和或积分；3.还有一些时候，sampling就是我们的目标，例如我们想训练一个可以从训练分布采样的模型。

蒙特卡洛采样的基础（Basics of Monte Carlo Sampling）：当求和和积分不能直接计算时，我们使用下面的idea：将求和和积分视作某个分布的期望：$s=∑xp(x)f(x)=E_p[f(x)]$或者$s=∫p(x)f(x)dx=E_p[f(x)]$，然后用平均值去估计它：$\hat{s_n} = \frac{1}{n}\sum{i=1}^{n}f(x^{(i)})$

重要性采样（Importance Sampling）：p(x)f(x)重写成：$p(x)f(x) = q(x)\frac{p(x)f(x)}{q(x)}$，于是，蒙特卡洛Sampling可以转换成重要性Sampling，即从$\hat{s_p} = \frac{1}{n}\sum_{i=1,x^{(i)}\sim p}^{n}f(x^{(i)})$转换成$\hat{s_q} = \frac{1}{n}\sum_{i=1,x^{(i)}\sim q}^{n}\frac {p(x^{(i)})f(x^{(i)})}{q(x^{(i)})}=\frac{1}{n}\sum_{i=1,x^{(i)}\sim q}^{n}w(x^{(i)})f(x^{(i)})$。其中可以把$w(x)=\frac{p(x)}{q(x)}$称为重要性权重（importance weight）

马尔科夫链蒙特卡洛方法：在深度学习的内容中，有时候需要从目标分布$p_{model}(x)$中精确采样或者一个好的（方差较小的）重要采样分布q(x)，但是又有很多时候不能直接采样，比如使用无向图模型的时候。使用MCMC方法有一个前提：所有的可能状态的概率不能为0，即不可化简性（Irreducibility）。无向图使用的基于能量的模型（Energy Based Model， EBM）保证了这一点。 马尔科夫链（Markov Chain）的核心思想：从某个可取任意值的状态x出发。

随着时间的推移，我们随机地反复更新状态x。最终x成为了一个从近似p(x)中抽出的样本。在正式的定义中，马尔科夫链由一个随机状态x和一个转移分布$T(x′∣x)$定义而成，$T(x′∣x)$是一个概率分布，说明了给定状态x的情况下随机地转移到x′的概率。

运行一个马尔科夫链意味着根据转移分布$T(x′∣x)$采出的值x′来更新状态x。运行马尔科夫链直到它达到均衡分布的过程通常被称为马尔科夫链的磨合过程（burnining）。

mcmc方法抽样的两个连续的样本之间会高度相关，如果我们想要得到完全独立的样本，那么我们可以同时并行地运行多个马尔科夫链。深度学习的从业者们通常选取的马尔科夫链的数目和小批量中的样本数相近，然后从这些固定的马尔科夫链集合中抽取所需要的样本。

马尔科夫链的数目通常选为100。 还有另一个难点是我们无法预先知道马尔可夫链需要运行多少步才能到达均衡分布。 这段时间通常被称为混合时间（mixing time）。

吉布斯采样（Gibbs Sampling）：其中在基于能量的模型中从T(x′∣x)采样是通过选择一个变量$x_i$，然后从$p_{model}$中该点关于在无向图G（定义了基于能量的模型结构）中邻接点的条件分布中采样。

只要一些变量在给定相邻变量时是条件独立的，那么这些变量就可以被同时采样。

这章可以参考之前的另一篇关于MCMC的笔记，或者直接参考An Introduction to MCMC for Machine Learning，这里是中文简易翻译版。