MCMC之蒙特卡罗方法
马尔可夫链蒙克卡罗(Markov Chain Monte Carlo,MCMC)是一种随机采样方法，在机器学习、深度学习及自然语言处理等领域都有广泛的应用，是很多复杂算法求解的基础，例如受限玻尔兹曼机(RBM)便是用MCMC来做一些复杂算法的近似求解。在具体讲解什么是MCMC之前，我们先看看MCMC可以解决什么样的问题，为什么需要MCMC方法。
2. 为什么需要MCMC?
累积分布函数如下所示
上面针对连续分布采样有两个假设前提：一是概率密度函数可积；二是累积分布函数有反函数。但是上述假设前提不成立怎么办？此时便需要用到下面介绍的MCMC。
3.蒙特卡罗方法
我们首先介绍MCMC中的蒙特卡罗(Monte Carlo)方法，蒙特卡罗是一种随机模拟的方法，最初的蒙特卡罗方法是用来求解积分问题，比如
虽然上面的方法可以求解近似值，但它隐含一个假设，即x在[a,b]之间是均匀分布的。而大多数情况下，x在[a,b]之间不是均匀分布的，如果继续用上面的方法，模拟求出的结果很可能和结果相差甚远，那怎么解决这个问题呢？如果我们可以得到x在[a,b]的概率分布函数p(x)，那么我们的定积分求和可以转换为
也就是说，最上面的均匀分布可以作为一般概率分布函数p(x)在均匀分布时候的特例，那么现在问题便转换为如何求出x的分布p(x)对应的若干个样本上来。
4.概率分布采样
上面讲到蒙特卡罗方法的关键是得到x的概率分布p(x)，如果求出了x的概率分布，便可以基于这个概率分布去采样n个x的样本集，然后带入蒙特卡罗求和的方程式便可以求解。当然，上面的关键问题还没有解决，即如何基于概率分布去采样n个x的样本集。
对于常见的均匀分布uniform(0,1)是非常容易采集样本的，一般通过线性同余发生器便可以很方便的生成(0,1)之间的伪随机数样本。对于常见的概率分布，无论是离散的分布还是连续的分布，都可以通过uniform(0,1)的样本转换得到。比如二维正态分布的样本(Z1,Z2)，可以通过独立采样得到uniform(0,1)样本对(X1,X2)进行转换得到，转换方程式如下所示
其他的一些常见的连续分布，比如t分布,F分布,Beta分布,Gamma分布等，都可以通过类似的方式从uniform(0,1)得到的样本转换得到。不过很多时候，我们x的概率分布不是常见的分布，这意味着我们无法方便的得到这些概率分布的样本集，那这个问题怎么解决呢？
5.接受-拒绝采样
对于概率分布不是常见的分布，一个可行的方法是采用接受-拒绝采样来得到该分布的样本。既然p(x)太复杂在程序中没法直接采样，那么我们设定一个可采样的分布q(x)，比如高斯分布，然后按照一定的方法拒绝某些样本，以达到接近p(x)分布的目的，其中q(x)叫做建议分布(proposal distribution)。
6.蒙特卡罗方法总结
使用接受-拒绝采样，可以解决一些概率分布不是常见分布的情况，然后得到采样集，最后用蒙特卡罗方法求和。但是接受-拒绝采样只能部分满足我们的情况，在很多时候我们还是很难得到概率分布的样本集，比如
- 对于一些二维分布(x,y)，有些时候只能得到条件概率分布p(x|y)和p(y|x)，却很难得到二维分布p(x,y)，这时便无法采用接受拒绝采样得到其样本集。
- 对于一些高维的复杂分布p(x1,x2,x3,...,xn)，得到合适的q(x)和k非常困难。
从上面可以看出，要将蒙特卡罗方法作为通用的采样模拟求和方法，必须解决如何方便得到各种复杂概率分布的对应采样样本的问题。下篇文章，我们将通过介绍马尔可夫链，来帮助我们找到这些复杂概率分布所对应的采样样本集。