开通VIP，畅享免费电子书等14项超值服
首页
好书
留言交流
下载APP
联系客服
2018.02.08
全球人工智能
MCMC介绍
MarkovChainMonteCarlo简称MCMC，是一个抽样方法，用于解决难以直接抽样的分布的随机抽样模拟问题。
在基础概率课我们有学过，已知一个概率分布函数F(X)，那么用电脑产生服从Uniform分布的随机数U，代入，那么就是服从F(X)的随机变量。这个方法在金融领域使用很广，即MonteCarloSimulation：通过模拟股票价格来计算期权价格。当然，这个方法很重要的一个假设是，已知概率分布函数。但很多情况下我们并没有方法得到概率分布和其反函数，因此需要其他手段。
MCMC通常用于解决高维度的积分和最优化问题，这两种问题也是机器学习、物理、统计、计量等领域的基础。比如：
1、贝叶斯推论和学习，给定未知变量x和y，贝叶斯统计主要需计算以下积分：
2、统计力学，用概率理论来总结一个力学系统的平均行为。。。在计算中有运用类似统计推论里计算标准化常数的方法。
3、最优化，最小化或最大化目标函数
4、带有惩罚函数的似然模型选择（Penalizedlikelihoodmodelselection），分为两个步骤，一，对每一个模型计算极大似然估计参数。然后用惩罚项（如AIC，BIC）来选择复杂度和拟合度都较好的模型。
MonteCarlo原理
依据给定的目标概率分布（高维度的），产生独立同分布的样本，利用产生的样本可以对该分布进行离散式近似，其中是xi的狄拉克δ函數。然后就可以用这个近似的分布函数计算各种积分。但是，很多分布是难以直接取样的，需要借助一些方法，就是用可以直接抽样的较为简单的分布作为依据（proposaldistribution）。如rejectionsampling,importancesampling和MCMC。
狄拉克δ函數delta-Dirac，它在除x以外的点上都等于零，且其在整个定义域上的积分等于1。是一种连续函数的表达式，若用离散函数来表达的话，就是
可以证明，如此这般，acceptedx服从p(x)。
用python对p(x)为标准正态分布作了个实验（code在文末）
目标分布p(x)，参考分布q(x)，且p(x)=w(x)q(x)，w(x)称为重要性权重。比如要计算
咋看之下很奇怪，但是其实是用于应对极端情况问题的抽样，因此很适合用在金融领域。比如我们已知某风险因子（riskfactor）服从p(X)，然后根据风险因子计算的风险值f(X)只在X很大的时候才有值，其他时候均为0，即
下面是两个拓展：
标准化常数（Normalizingconstant）：就是使概率函数变为概率密度函数的常数，比如
不过即使有上述几个拓展，有的时候还是很难得到目标分布的良好估计。因此，我们需要更加英霸的技术，基于马尔科夫链。
是我觉得目前来看缩写最好记的方法，值得一学。
简而言之，就是用马尔科夫链方法来抽样。本文一贯的假设是目标分布p(x)难以直接抽样，但是我们对他的常数倍了如指掌（原文是“canevaluatep(x)uptoanormalisingconstant”）
马尔科夫链
首先，xi是离散的随机序列（stochasticprocess），而且在每个时刻只有s个可能的值（state）。那么，这个随机序列若满足以下条件就可以称为马尔科夫链：
比如说下图的关系就可以用
来表示
T需要满足的条件是：
另外，还有一个p(x)是可收敛分布的充分条件（非必要）是
用互联网来具象化上述两个条件的重要意义：第一个条件说明我们从任意一个网页出发都可以访问其他任何网页，而且在任何一个网页都必须可以到其他网页，而不是死循环。例如谷歌的PageRank算法就是定义T=L+E，其中L矩阵的各元素表示从一个网页到另一个网页的链接数，E是一个均匀随机数矩阵，用于满足不可化简性和排除死循环（再次的网站也要有正的概率可以摆在搜索排行前面，虽然概率很低）。
MCMC的目的就是用MarkovChain收敛于p(x)这一性质来抽样，即不管一开始抽取的样本服从什么分布，只要用了恰当的转换矩阵，经过多次转换后之后抽取的眼本就会服从目标分布。概念说起来很简单，但是转换矩阵的不同选择就形成了不同的算法。
在X是连续变量的情况下，转换矩阵T变为核函数积分形式：
，
MetropolisHastingAlgorithm
最出名的算法叫做MetropolisHastingAlgorithm（MH）：很多其他实用的MCMC算法究其根本都是MH算法的延伸。
个人在stackexchange上看到一个很形象的比喻：假设你目前在一片高低不平的山地上，你此行的目的是在海拔越高的地方停留越久（p(x)大的时候，样本里x就多）。你的方法是随便指一个新的地方，如果这个地方的海拔更高，那么就移动过去；但如果这个地方的海拔比当前低，你就抛一个不均匀的硬币决定是否过去，而硬币的不均匀程度相当于新海拔和当前海拔的比例。也即新海拔若是当前海拔的一半，你就只有1/2的概率会过去。MH算法中q(x*|x)就是按照一定的规律指出一个新方向，A(x,x*)就是计算相对高度。
用python实现结果如下：
MH算法很简单，但是对q(x*|x)的选择非常关键。而且其他不同的算法也主要是对q的不同选择。
MH算法的转换核(transitionkernel)是
其中
这个转换核满足平衡条件
转换核就是前面的T在连续情况下
可以证明，通过MH算法得到的样本就是近似服从目标分布p(x)的样本：
证明：
因此，MH的转换核满足平衡条件，所以抽样得到的样本将会趋向于p(x)。
因为算法内部有拒绝的设定，所以不存在死循环（即每一次产生一个新的proposalx*，都有机会移动到该值上）。为了证明MH算法不存在可简化性，需要证明在有限步内x的每一个取值都有正的概率。
MH算法有两个简易的特例：IndependentSampler和MetropolisAlgorithm。
另外，MH算法有几个重要性质：
------------------接下去就是MCMC如何解决具体问题-----------------
效果如图：
MCMC还有一个优点就是可以结合多种抽样器于一个混合的（mixture）或循环的（cycle）抽样器。即若K1和K2是具有相同收敛分布p的核，那么循环核K1K2和混搭核vK1+(1-v)K2,
混搭核可以通过一个总体参考分布先探索可能的取值范围，然后再针对不同的抽样器选用不同的参考函数来探索目标分布的性质。这对于有很多极值的目标分布很有效。
有时联合分布比边缘分布好抽样，所以可以先通过联合分布得到样本，然后忽略掉作为辅助的变量。下面介绍两种。
所以
条件概率分布为
算法就是基于当前步得到的samplexi，先在0到p(xi)之间均匀抽样一个u，然后在p(x)>u的区域A内均匀抽样一个x。
给定一类模型集合M，我们将构建遍历马尔科夫链(ergodicmarkovchina)，使得其收敛分布为p(m,xm)。可以实现模拟不同维度的分布。
遍历马尔科夫链：若马尔科夫链上的每一个状态（state）都是可遍历的，那么这个MC就是一个EMC，其实就是具有不可化简性，可以从任何状态到达任何状态。
希望找到一个界限，使得在该步以后MC基本收敛。
在抽样过程中根据抽取的样本调整参考分布，不过目前的研究都没有显著效果
适用于连续型数据分析，例如信号等。
主要应用在高维度模型，大数据。
----------------------------------以下是附录----------------------------------