社区首页 >专栏 >随机采样方法——蒙特卡罗方法

随机采样方法——蒙特卡罗方法

机器学习算法工程师

发布于 2018-08-17 09:18:26

2.9K0

文章被收录于专栏：机器学习算法工程师机器学习算法工程师

作者：刘建平

编辑：祝鑫泉

授权转发自：刘建平《MCMC(一)蒙特卡罗方法》

地址:http://www.cnblogs.com/pinard/p/6625739.html

前言

作为一种随机采样方法，马尔科夫链蒙特卡罗（Markov Chain Monte Carlo，以下简称MCMC）在机器学习,深度学习以及自然语言处理等领域都有广泛的应用，是很多复杂算法求解的基础。 章节目录

MCMC概述
蒙特卡罗方法引入
概率分布采样
接受—拒绝采样
蒙特卡罗方法小结

MCMC概述

从名字我们可以看出，MCMC由两个MC组成，即蒙特卡罗方法（Monte Carlo Simulation，简称MC）和马尔科夫链（Markov Chain ，也简称MC）。要弄懂MCMC的原理我们首先得搞清楚蒙特卡罗方法和马尔科夫链的原理。我们将用三篇来完整学习MCMC。在本篇，我们关注于蒙特卡罗方法。

蒙特卡罗方法引入

蒙特卡罗原来是一个赌场的名称，用它作为名字大概是因为蒙特卡罗方法是一种随机模拟的方法，这很像赌博场里面的扔骰子的过程。最早的蒙特卡罗方法都是为了求解一些不太好求解的求和或者积分问题。比如积分：

如果我们很难求解出f(x)的原函数，那么这个积分比较难求解。当然我们可以通过蒙特卡罗方法来模拟求解近似值。如何模拟呢？假设我们函数图像如下图:

则一个简单的近似求解方法是在[a,b]之间随机的采样一个点。比如x0,然后用f(x0)代表在[a,b]区间上所有的f(x)的值。那么上面的定积分的近似求解为:

当然，用一个值代表[a,b]区间上所有的f(x)的值，这个假设太粗糙。那么我们可以采样[a,b]区间的n个值：x0,x1,...xn−1,用它们的均值来代表[a,b]区间上所有的f(x)的值。这样我们上面的定积分的近似求解为:

虽然上面的方法可以一定程度上求解出近似的解，但是它隐含了一个假定，即x在[a,b]之间是均匀分布的，而绝大部分情况，x在[a,b]之间不是均匀分布的。如果我们用上面的方法，则模拟求出的结果很可能和真实值相差甚远。

怎么解决这个问题呢？如果我们可以得到x在[a,b]的概率分布函数p(x)，那么我们的定积分求和可以这样进行：

上式最右边的这个形式就是蒙特卡罗方法的一般形式。当然这里是连续函数形式的蒙特卡罗方法，但是在离散时一样成立。

可以看出，最上面我们假设x在[a,b]之间是均匀分布的时候，p(xi)=1/(b−a)，带入我们有概率分布的蒙特卡罗积分的上式，可以得到：

也就是说，我们最上面的均匀分布也可以作为一般概率分布函数p(x)在均匀分布时候的特例。那么我们现在的问题转到了如何求出x的分布p(x)对应的若干个样本上来。

条概率分布采样

上一节我们讲到蒙特卡罗方法的关键是得到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)得到的采样样本转化得到。在python的numpy，scikit-learn等类库中，都有生成这些常用分布样本的函数可以使用。

不过很多时候，我们的x的概率分布不是常见的分布，这意味着我们没法方便的得到这些非常见的概率分布的样本集。那这个问题怎么解决呢？

接受—拒绝采样

对于概率分布不是常见的分布，一个可行的办法是采用接受-拒绝采样来得到该分布的样本。既然 p(x) 太复杂在程序中没法直接采样，那么我设定一个程序可采样的分布 q(x) 比如高斯分布，然后按照一定的方法拒绝某些样本，以达到接近 p(x) 分布的目的，其中q(x)叫做 proposal distribution。