算法学习系列（MCMC）：MCMC采样

如果假定我们可以得到我们需要采样样本的平稳分布所对应的马尔科夫链状态转移矩阵，那么我们就可以用马尔科夫链采样得到我们需要的样本集，进而进行蒙特卡罗模拟。但是一个重要的问题是，随意给定一个平稳分布 π ,如何得到它所对应的马尔科夫链状态转移矩阵 P 呢？这是个大问题。我们绕了一圈似乎还是没有解决任意概率分布采样样本集的问题。

概率图模型中最常用的采样技术就是马尔可夫链蒙特卡洛方法（MCMC）。

MCMC 一般算法

算法基本思想

先设法构造一条马尔可夫链，使其收敛至平稳分布恰好为 ，然后通过这条马尔可夫链然后产生符合 分布的样本。最后通过这些样本来进行估计。

MCMC采样算法

由于一般情况下，目标平稳分布π(x)π(x)和某一个马尔科夫链状态转移矩阵QQ不满足细致平稳条件，即

我们可以对上式做一个改造，使细致平稳条件成立。方法是引入一个 α( i , j ) ，使上式可以取等号，即：

什么样的 α( i , j ) 可以使等式成立呢？其实很简单，只要满足下两式即可：

这样，我们就得到了我们的分布 π(x) 对应的马尔科夫链状态转移矩阵 P，满足：

α( i , j ) 我们有一般称之为接受率。(取值在[0,1]之间，可以理解为一个概率值。)

也就是说，我们的目标矩阵 P 可以通过任意一个马尔科夫链状态转移矩阵 Q 乘以 α( i , j ) 得到。α( i , j )我们一般称之为接受率。即目标矩阵 P 可以通过任意一个马尔科夫链状态转移矩阵 Q 以一定的接受率获得。

这个很像我们在之前讲到的接受-拒绝采样，那里是以一个常用分布通过一定的接受-拒绝概率得到一个非常见分布，这里是以一个常见的马尔科夫链状态转移矩阵 Q 通过一定的接受-拒绝概率得到目标转移矩阵 P ,两者的解决问题思路是类似的。

现在我们来总结下MCMC的采样过程：

上面这个过程基本上就是MCMC采样的完整采样理论了，这个算法存在一些问题，后面会提及

在介绍Metropolis- Hastings算法之前首先介绍以下Metropolis采样算法。

Metropolis采样算法

Metropolis算法的原理

从一个已知的形式较为简单的分布中采样，并以一定的概率接受这个样本作为目标分布的近似样本。

假设需要从目标概率密度函数 p(θ) 中进行采样，同时，θ满足 −∞<θ<∞ 。Metropolis采样算法根据马尔可夫链去生成一个序列：

                                                    

其中，表示的是马尔可夫链在第 t代时的状态。

在Metropolis采样算法的过程中，首先初始化状态值  ，然后利用一个已知的分布 生成一个新的候选状态 ，随后根据一定的概率 a 选择接受这个新值，或者拒绝这个新值，在Metropolis采样算法中，概率为：

                                 
这样的过程一直持续到采样过程的收敛，当收敛以后，样本即为目标分布 p(θ) 中的样本。

Metropolis算法的流程

基于以上的分析，可以总结出如下的Metropolis采样算法的流程：

Metropolis算法的解释

要证明Metropolis采样算法的正确性，最重要的是要证明构造的马尔可夫过程满足如上的细致平稳条件，即：

                                                               

对于上面所述的过程，分布为，从状态 i 转移到状态 j 的转移概率为：

                                                             

对于选择该已知的分布，在Metropolis采样算法中，要求该已知的分布必须是对称的，即 ，即

 

                                                  

常用的符合对称的分布主要有：正态分布，柯西分布以及均匀分布等。

接下来，需要证明在Metropolis采样算法中构造的马尔可夫链满足细致平稳条件：

                                             

因此，通过以上的方法构造出来的马尔可夫链是满足细致平稳条件的。

Metropolis算法要求已知的条件分布必须是对称的，而一般的MCMC采样算法问题存在于上面第三步的 c 步骤。由于   可能非常的小，比如0.1，导致我们大部分的采样值都被拒绝转移，采样效率很低。使得马氏链遍历所有的状态空间要花费太长的时间，收敛到平稳分布 p(x) 的速度太慢这时，就轮到我们的M-H采样出场了。

Metropolis - Hastings算法

因此我们的接受率可以做如下改进，即：

 

很容易验证：

MH算法流程

                                

Gibbs采样

MH算法不仅适用于一维的情况，也适用于高维的情况，但是对于高维的情况存在问题，一是接受率的存在，计算量大。并且由于接受率的原因导致算法收敛时间变长。二是有些高维数据，特征的条件概率分布好求，但是特征的联合分布不好求。

细致平稳条件（Gibbs采样原理）

 

在M-H采样中我们通过引入接受率使细致平稳条件满足。现在我们换一个思路。

Gibbs算法流程