专栏首页机器学习算法工程师随机采样方法——蒙特卡罗方法

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

作者: 刘建平

编辑:祝鑫泉

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

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

前 言

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

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

01

MCMC概述

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

02

蒙特卡罗方法引入

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

如果我们很难求解出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)对应的若干个样本上来。

03

条概率分布采样

上一节我们讲到蒙特卡罗方法的关键是得到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的概率分布不是常见的分布,这意味着我们没法方便的得到这些非常见的概率分布的样本集。那这个问题怎么解决呢?

04

接受—拒绝采样

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

具体采用过程如下,设定一个方便采样的常用概率分布函数 q(x),以及一个常量 k,使得 p(x) 总在 kq(x) 的下方。如上图。

首先,采样得到q(x)的一个样本z0,采样方法如第三节。然后,从均匀分布(0,kq(z0))中采样得到一个值u。如果u落在了上图中的灰色区域,则拒绝这次抽样,否则接受这个样本z0。重复以上过程得到n个接受的样本z0,z1,...zn−1,则最后的蒙特卡罗方法求解结果为:

整个过程中,我们通过一系列的接受拒绝决策来达到用q(x)模拟p(x)概率分布的目的。

05

蒙特卡罗方法小结

使用接受-拒绝采样,我们可以解决一些概率分布不是常见的分布的时候,得到其采样集并用蒙特卡罗方法求和的目的。但是接受-拒绝采样也只能部分满足我们的需求,在很多时候我们还是很难得到我们的概率分布的样本集。比如:

1)对于一些二维分布p(x,y),有时候我们只能得到条件分布p(x|y)和p(y|x)和,却很难得到二维分布p(x,y)一般形式,这时我们无法用接受-拒绝采样得到其样本集。

2)对于一些高维的复杂非常见分布p(x1,x2,...,xn),我们要找到一个合适的q(x)和k非常困难。

从上面可以看出,要想将蒙特卡罗方法作为一个通用的采样模拟求和的方法,必须解决如何方便得到各种复杂概率分布的对应的采样样本集的问题。而我们下一篇要讲到的马尔科夫链就是帮助找到这些复杂概率分布的对应的采样样本集的白衣骑士。下一篇我们来总结马尔科夫链的原理。

本文分享自微信公众号 - 机器学习算法工程师(Jeemy110)

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2018-08-01

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 机器学习中的数据不平衡解决方案大全

    在机器学习任务中,我们经常会遇到这种困扰:数据不平衡问题。 数据不平衡问题主要存在于有监督机器学习任务中。当遇到不平衡数据时,以总体分类准确率为学...

    机器学习算法工程师
  • 朴素贝叶斯算法详解(1)

    1. 引言   朴素贝叶斯算法(Naive Bayes)是机器学习中常见的基本算法之一,主要用来做分类任务的。它是基于贝叶斯定理与条件独立性假设的分类方法。...

    机器学习算法工程师
  • 机器学习从零开始系列连载(1)——基本概念

    作者:张 磊 编辑:赵一帆 本周内容: 1. 一些基本概念 1.1 生成式模型与判别式模型 1.2 参数学习与非参学习 1....

    机器学习算法工程师
  • LeetCode 965 Univalued Binary Tree

    判断二叉树是否是 唯一二叉树. 当树中所有节点的值都一样时,我们认为他是一颗 唯一二叉树。

    一份执着✘
  • python之platform模块

    python中,platform模块给我们提供了很多方法去获取操作系统的信息 如:

    菲宇
  • MCMC原理解析(马尔科夫链蒙特卡洛方法)

    马尔科夫链蒙特卡洛方法(Markov Chain Monte Carlo),简称MCMC,MCMC算法的核心思想是我们已知一个概率密度函数,需要从这个...

    种花家的奋斗兔
  • 开源流媒体服务器SRS学习笔记(4) - Cluster集群方案

    单台服务器做直播,总归有单点风险,利用SRS的Forward机制 + Edge Server设计,可以很容易搭建一个大规模的高可用集群,示意图如下

    菩提树下的杨过
  • 写给开发者的机器学习指南(九)

    正如你所看到的,最高的权重给予了几乎立即得到电子邮件回复的电子邮件,而最低权重给予具有非常长的时间范围的电子邮件。这允许具有非常低频率的电子邮件仍然基于它们被发...

    哒呵呵
  • 加州大学正研发新型全息技术,可欺骗大脑和改变记忆

    VRPinea
  • Spring Boot项目启动和添加新的跳转页面

    Spring Boot 是由 Pivotal 团队提供的全新框架,默认配置了很多框架的使用方式,就像 Maven 整合了所有的 Jar 包,Spring Boo...

    王小婷

扫码关注云+社区

领取腾讯云代金券