[Bayes] What is Sampling
Ref: http://blog.csdn.net/xianlingmao/article/details/7768833
通常,我们会遇到很多问题无法用分析的方法来求得精确解,例如由于式子特别,真的解不出来;
一般遇到这种情况,人们经常会采用一些方法去得到近似解,已经近似程度。
本文要谈的随机模拟就是这么一类近似求解的方法。
它的诞生虽然最早可以追溯到18xx年法国数学家蒲松的投针问题(用模拟的方法来求解\pi的问题),但是真正的大规模应用还是被用来解决二战时候美国生产原子弹所碰到的各种难以解决的问题而提出的蒙特卡洛方法(Monte Carlo),从此一发不可收拾。
一. 随机模拟的基本思想
其基本思路就是要把待解决的问题转化为一种可以通过某种采样方法可以解决的问题,至于怎么转化,还是挺有创造性,没有定法。
因此,随机模拟方法的核心就是:如何对一个概率分布得到样本,即抽样(sampling)。
二. 常见的抽样方法
2.0 直接抽样法
略。
2.1 接受-拒绝抽样(Acceptance-Rejection sampling)
又简称拒绝抽样,直观地理解,为了得到一个分布的样本,我们通过某种机制得到了很多的初步样本,然后其中一部分初步样本会被作为有效的样本(即要抽取的分布的样本),一部分初步样本会被认为是无效样本舍弃掉。
这个算法的基本思想是:我们需要对一个分布f(x)进行采样,但是却很难直接进行采样,所以我们想通过另外一个容易采样的分布g(x)的样本,用某种机制去除掉一些样本,从而使得剩下的样本就是来自与所求分布f(x)的样本。
2.2 重要性抽样(Importance sampling)
重要性采样 和 蒙特卡洛积分 密切相关。
给每个样本赋予了一个权重,g(xi)大意味着概率大,那么N里面含有这样的样本xi就多,即这些样本的权重大,所以称为重要性抽样。
2.3 MCMC抽样方法
无论是拒绝抽样还是重要性采样,都是属于独立采样,即样本与样本之间是独立无关的,这样的采样效率比较低,如拒绝采样,所抽取的样本中有很大部分是无效的,这样效率就比较低。
MCMC方法是关联采样,即下一个样本与这个样本有关系,从而使得采样效率高。
MCMC方法的基本思想是:通过构建一个markov chain使得该markov chain的稳定分布是我们所要采样的分布f(x)。
当markov chain达到稳定状态,那么来自这个chain的每个样本都是f(x)的样本,从而实现抽样的目的。
这里存在一个核心问题,如何构建满足要求的markov chain?
A). Metropolis-Hasting算法
见:[Bayes] dchisq: Metropolis-Hastings Algorithm
B). Gibbs采样算法
暂略。
当然无论是metropolis-hasting算法还是gibbs算法,都有一个burn in的过程,在burn in过程中产生的样本都需要被舍弃。
可以证明Gibbs算法是metropolis-hasting算法的一个特例,即比率\alpha(x,y) = 1的一个特列。具体证明,此处略。
最新文章
- 在C#中调用EXE文件
- TestNG测试报告美化buid.xml配置
- localStorage兼容ie6/7 用addBehavior 实现
- centos下安装nginx和php-fpm
- Nginx源码安装及调优配置
- 创建型模式——Abstract Factory
- java取随机数
- fmt:formatDate标签的输出格式
- Codeforces 713 C Sonya and Problem Wihtout a Legend
- Css实现透明效果,兼容IE8
- libeXosip2(2-1) -- eXosip2 configuration API
- Mplayer ARM平台下交叉编译
- MongoDB数据库索引
- 071、如何定制calico网络的IP池(2019-04-16 周二)
- DateTime?,也是一种类型,代表DateTime或NULL两种类型,在处理空时间时比较有用
- 虚拟化之kvm --(vnc控制台)
- mapper.xml中转义
- 设计模式 笔记 桥接模式 Bridge
- ubuntu编译centos7部署大象医生 dr-elephant
- ES6重点--笔记(转)