MCMC是一种随机采样方法，用来处理一些复杂运算的近似求解。在HMM、LDA等模型中都有重要应用。
上一篇 MCMC详解1——蒙特卡洛方法

---

上一篇总结了求解复杂函数的积分问题，通过蒙特卡洛方法转化为了采集符合概率密度分布的样本求均值的问题，然后总结了拒绝-接受采样方法，但是该方法有个弊端，高纬度数据难以采样以及效率问题。本篇总结MCMC采样方法来解决这两个问题。

1，马尔科夫链模型

马尔科夫链的定义本身比较简单：某一时刻的状态转移概率只依赖与前一时刻。数学语言描述如下：
假设序列的状态为$...,X_{t-1},X_t,X_{t+1},...$那么在$t+1$时刻的状态概率只依赖与$t$时刻：
$$P(X_{t+1}|...,X_{t-2},X_{t-1},X_t)=P(X_{t+1}|X_t)$$

既然某一时刻状态转移的概率只依赖于它的前一个状态，那么我们只要能求出系统中任意两个状态之间的转换概率，这个马尔科夫链的模型就定下来了，转移概率组成的矩阵P，我们称为状态转移矩阵。

那么马尔科夫链的转移矩阵与蒙特卡洛方法所需要的概率分布什么关系呢？ 这要从马尔科夫链的状态转移矩阵的性质讲起。

1.1 马尔科夫链转移矩阵的性质

1）不同的初始状态经过多次P状态转移后，保持稳定不变相同状态。即不同的初始概率分布样本经过多次转移矩阵后会稳定到同一个概率分布。

比如，P=[[0.9,0.075,0.025],[0.15,0.8,0.05],[0.25,0.25,0.5]]，初始状态[[0.3,0.4,0.3]]或者[[0.7,0.1,0.2]]在经过多次状态转移以后的结果都是[[ 0.625 0.3125 0.0625]]

那么重点来了：如果我们得到这个稳定概率分布对应的马尔科夫模型的状态转移矩阵P，则我们可以用任意的概率分布样本开始，带入马尔科夫模型，经过一系列的转换，就可以得到符合我们对应稳定概率分布的样本。

2）同时对于一个确定的状态转移矩阵P，它的n次幂$P^n$，当n大于一定值的时候，也是稳定不变的。同时这个稳定的分布与1）所述的分布是一致的。

比如：还是上面的例子，$p^n$在n足够大的时候，该矩阵的每一行都是[[ 0.625 0.3125 0.0625]]

总结一下马尔科夫链转移矩阵的性质如下：
1）状态转移矩阵p，它的n次幂，将会稳定下来。矩阵的每一行都是稳定的序列，所以其只与j相关

$$li{m}_{n\to \infty }{P}^n=\begin{array}{c}\left(\begin{array}{cccccc}\pi (1)& \pi (2)& ...& \pi (j)& ...& \\ \pi (1)& \pi (2)& ...& \pi (j)& ...& \\ ...& ...& ...& ...& ...& \\ \pi (1)& \pi (2)& ...& \pi (j)& ...& \end{array}\right)\end{array}$$$$li{m}_{n\to \infty }{P}_{ij}^n=\pi (j)$$

将矩阵P看作是$\pi$的组合：
$$\pi (j)=\sum _{i=0}^{\infty }\pi (i)P_{ij}$$
$\pi$是方程$\pi P=\pi$的唯一非负解，通常称为马尔科夫链的平稳分布,其中：
$$\begin{gathered} \pi =[\pi (1),\pi (2),...,\pi (j),...], \\ \sum _{i=0}^{\infty }\pi (i)=1 \end{gathered}$$

1.2 马尔科夫链的采样思路

假设我们任意概率分布式$p_0(x)$，经过n次马尔科夫状态转移后是$p_n(x)$，之后是平稳分布：
$${\pi }_n(x)={\pi }_{n+1}(x)={\pi }_{n+2}(x)=...=\pi (x)$$
对于每个${\pi }_i(x)$我们有：
$${\pi }_i(x)={\pi }_{i-1}(x)P={\pi }_{i-2}(x)P^2={\pi }_0(x)P^i$$

现在我们来描述采样过程： 首先基于任何初始分布比如均匀分布、高斯分布$p_0(x)$等采样得到状态值$x_0$，然后基于条件概率$p(x|x_0)$采样状态值$x_1$，一致进行下去，当状态转移达到一定的次数n，达到平稳，此时再次采样得到m个样本 ，即是符合我们的平稳分布的对应样本集。然后就可以用来做蒙特卡洛模拟求和了。

注：采样过程中有几个地方要解释
1）什么是条件概率$p(x|x_0)$？p是状态转移概率，基于每个状态x0，都有相应的转移概率，可以认为$p(x|x_0)$就是矩阵p的某一行。

2）每一步是怎么采样的？假设我们初始状态[0.1,0.8]两个，选取均匀采样，采样结果为两个状态中的某一个，比如状态1为0.1，此时，根据转移矩阵p = [[0.4,0.6],[0.3,0.7]]中状态1的条件概率$p(x|x_0)$，即状态1情况下的其他状态的转移概率，进行采样，此时较大的概率（0.6）选取状态2，那么这一步采集了一个样本，相当于完成了一次状态转移，因为此时样本的概率分布已经经过P改变，不再是均匀分布，依次采样，在第n次后，分布平稳，再次采集m个样本，就是我们需要的符合分布的样本集。

3）整个过程本身，并没有改变状态内容，只是改变了状态分布，这里的状态，理解成坐标也没问题。

到此为止，我们知道，获得马尔科夫链的转移矩阵，就能得到我们需要的样本集，甚至我们也知道了采样方法。但是如何根据我们知道的平稳分布p(z)得到马尔科夫状态转移矩阵呢？这个问题还是没有解决这里就用到MCMC采样，以及其改进版M-H采样和Gibbs采样。

1.3 MCMC采样

马尔科夫链的细致平稳条件：我们知道非周期马尔科夫链经过多次转移后，变得平稳：
$$\pi (i)P(i,j)=\pi (j)P(j,i)$$

矩阵表示为：
$$\pi P=\pi$$

从以上公式可以看到，只要我们找到了可以使概率分布$\pi (x)$满足该细致平稳分布的矩阵即可，这里就是一条寻找状态转移矩阵P的思路。

但是一般情况下，目标平稳分布$\pi (x)$，随便找个马尔科夫转移矩阵是不满足以上条件的：
$$\pi (i)Q(i,j)\ne \pi (j)Q(j,i)$$
怎么办呢？我们需要对上述公式进行改造:
$$\begin{gathered} \pi (i)Q(i,j)\alpha (i,j)=\pi (j)Q(j,i)\alpha (j,i) \\ \alpha (i,j)=\pi (j)Q(j,i) \\ \alpha (j,i)=\pi (i)Q(i,j) \end{gathered}$$
这样我们就得到分布p对应的马尔科夫状态转移矩阵P了！！！
$$P(i,j)=Q(i,j)\alpha (i,j)$$

我们的目标矩阵p可以通过任意的马尔科夫状态转移矩阵Q，乘以alpha获得，这里可以将alpha理解为接受率，可以类比拒绝-接受采样中的方法。那里是常见分布通过一定的拒绝-接受得到一个非常见分布，这里是一个常见的马尔科夫链状态转移矩阵Q通过一定的拒绝接受概率得到目标转移矩阵，通过这种方法，得到P（的分布）。

MCMC的采样过程如下：
1）输入我们任意选定的马尔科夫链状态转移矩阵Q，平稳分布$\pi (x)$,设定状态转移次数$n1$,需要的样本个数$n2$
2）从任意的概率分布找那个采样得到初始状态值$x_0$
3）for t=0 to n_1 + n_2 -1:
a）从条件概率分布$Q(x|x_t)$中采样的得到样本$x_{\ast }$
b）从均匀分布采样$u\sim uniform[0,1]$
c）如果$u<\alpha (x_t,x_{\ast })=\pi (x_{\ast })Q(x_{\ast },x_t)$，则接受转移$x_t\to x_{\ast }$，即$x_{t+1}=x_{\ast }$
d)否则不接受转移，即$x_{t+1}=x_t$
最后得到我们需要的平稳分布对应的样本集$(x_{n_1},x_{n_1+1},...,x_{n_1+n_2-1})$

以上过程已经解决了样本集采样问题，有了完整的理论，但是距离实际应用还有距离，因为在接受概率alpha可能非常小，采样值容易拒绝转移，效率低，难收敛。

1.4 M-H采样

M-H采样是Metropolis-Hastings采样的简称，这个算法首先由Metropolis提出，被Hastings改进，因此被称之为Metropolis-Hastings采样或M-H采样。

MCMC采样讲到效率问题，其根本是$\alpha$这个接受概率可能太小，导致采样效率低。
$$\pi (i)Q(i,j)\alpha (i,j)=\pi (j)Q(j,i)\alpha (j,i)$$

假设$\alpha (i,j)=0.1,\alpha (j,i)=0.2$
$$\pi (i)P(i,j)\ast 0.1=\pi (j)P(j,i)\ast 0.2$$

同时扩大5倍，等式仍然成立
$$\pi (i)P(i,j)\ast 0.5=\pi (j)P(j,i)\ast 1$$

我们的目的是让等式成立就行，所以，这里进行了一下改进,将alpha进行归一化:
α ( i , j ) = m i n { π ( j ) Q ( j , i ) π ( i ) Q ( i , j ) , 1 } \alpha(i,j)=min\{\frac{\pi(j)Q(j,i)}{\pi(i)Q(i,j)},1\} α(i,j)=min{π(i)Q(i,j)π(j)Q(j,i)​,1}

M-H的采样过程如下：
1）输入我们任意选定的马尔科夫链状态转移矩阵Q，平稳分布$\pi (x)$,设定状态转移次数$n1$,需要的样本个数$n2$
2）从任意的概率分布找那个采样得到初始状态值$x_0$
3）for t=0 to n_1 + n_2 -1:
a）从条件概率分布$Q(x|x_t)$中采样的得到样本$x_{\ast }$
b）从均匀分布采样$u\sim uniform[0,1]$
c）如果 u < α ( x t , x ∗ ) = m i n { π ( j ) Q ( j , i ) π ( i ) Q ( i , j ) , 1 } u<\alpha(x_t,x_*)=min\{\frac{\pi(j)Q(j,i)}{\pi(i)Q(i,j)},1\} u<α(xt​,x∗​)=min{π(i)Q(i,j)π(j)Q(j,i)​,1}，则接受转移$x_t\to x_{\ast }$，即$x_{t+1}=x_{\ast }$
d)否则不接受转移，即$x_{t+1}=x_t$
最后得到我们需要的平稳分布对应的样本集$(x_{n_1},x_{n_1+1},...,x_{n_1+n_2-1})$

# 在例子里，我们的目标平稳分布是一个均值3，标准差2的正态分布，
# 选择的马尔可夫链状态转移矩阵Q(i,j)的条件转移概率是以i为均值,方差1的正态分布在位置j的值。
# 这个例子仅仅用来让大家加深对M-H采样过程的理解。毕竟一个普通的一维正态分布用不着去用M-H采样来获得样本。
import random
from scipy.stats import norm
import matplotlib.pyplot as plt


def norm_dist_prob(theta):
    y = norm.pdf(theta, loc=3, scale=2)#均值为3、方差为2的高斯分布的概率密度函数，返回其在theta处的值。
    return y

T = 5000                                #采样次数
pi = [0 for i in range(T)]              #每次采样的结果
sigma = 1                               #转移矩阵分布参数
t = 0                                   #采样次数初始化
while t < T-1:
    t = t + 1
    # rvs 产生服从指定分布的随机数
    pi_star = norm.rvs(loc=pi[t - 1], scale=sigma, size=1, random_state=None)   #根据转移矩阵进行采样
    alpha = min(1, (norm_dist_prob(pi_star[0]) / norm_dist_prob(pi[t - 1])))    #计算拒绝-接受参数,Q相同，这里忽略

    u = random.uniform(0, 1)
    if u < alpha:
        pi[t] = pi_star[0]              # 接受
    else:
        pi[t] = pi[t - 1]               # 拒绝

plt.scatter(pi, norm.pdf(pi, loc=3, scale=2))
num_bins = 50
plt.hist(pi, num_bins, normed=1, facecolor='red', alpha=0.7)
plt.show()

M-H采样解决了使用蒙特卡洛方法需要的任意概率分布样本集的问题，得到了广泛的应用。

但是仍然面临着两大难题：
1）还是拒绝概率问题，如果特征非常多，那么算法效率是比较低的，是否能做到不拒绝的转移方法？
2）当特征很多的时候，我们很难求出目标的联合分布，但是可以方便求出各特征之间的条件概率分布（每次采样按照一个维度采），是否能在只具备各维度之间条件概率分布的情况下采样呢？

1.5 Gibbs采样

上一节提到多维数据分布的采样难题，本节来解决：

在M-H中使用接受率使细致平稳条件满足，现在换一个思路：

从二维数据分布开始，假设$p_1(x_1,x_2)$是一个二维联合数据分布，假设有两个点，$A(x_1^{(1)},x_2^{(1)})$,$B(x_1^{(1)},x_2^{(2)})$,则$\pi (A)\pi (x_2^{(2)}|x_1^{(1)})=\pi (B)\pi (x_2^{(1)}|x_1^{(1)})$为什么呢？
$$\begin{gathered} \pi (x_1^{(1)},x_2^{(1)})\pi (x_2^{(2)}|x_1^{(1)})=\pi (x_1^{(1)})\pi (x_2^{(1)}|\pi (x_1^{(1)})\pi (x_2^{(2)}|x_1^{(1)}) \\ \pi (x_1^{(1)},x_2^{(2)})\pi (x_2^{(1)}|x_1^{(1)})=\pi (x_1^{(1)})\pi (x_2^{(2)}|\pi (x_1^{(1)})\pi (x_2^{(1)}|x_1^{(1)}) \end{gathered}$$
上式右边相等，所以等式成立。
$$\pi (A)\pi (x_2^{(2)}|x_1^{(1)})=\pi (B)\pi (x_2^{(1)}|x_1^{(1)})$$

$P_i(A)$表示A点两个特征的联合分布，$p_i（x_2^{(2)}|x_1^{(1)}）$为$x_1^{(1)}$条件下的分布。

现在$x_1=x_1^{(1)}$这条直线上（看作是特征维度1在某个具体特征值上），在如果把条件概率分布$\pi (x_2|x_1^{(1)})$看作是马尔科夫链的状态转移概率，则任意两个点之间的转移满足细致平稳条件，同理，在$x_2=x_2^{(1)}$这个轴上也成立。基于以上发现，我们可以构造分布$\pi (x_1,x_2)$的马尔科夫链的状态转移矩阵P。
$$\begin{gathered} P(A\to B)=\pi (x_2^{(B)}|x_1^{(1)})if{x}_1^{(A)}=x_1^{(B)}=x_1^{(1)} \\ P(A\to C)=\pi (x_1^{(C)}|x_2^{(1)})if{x}_2^{(A)}=x_2^{(C)}=x_2^{(1)} \\ P(A\to D)=0else \end{gathered}$$

有了上面这个状态转移矩阵，我们很容易验证平面上的任意两点E,F满足细致平稳条件：
$$\pi (E)P(E\to F)=\pi (F)P(F\to E)$$

我们来看下Gibbs二维采样的步骤：
1）输入平稳分布$\pi (x_1,x_2)$设定状态转移次数阈值$n_1$，需要的样本个数$n_2$
2）随机初始化初始状态$x_1^{(0)}$和$x_2^{(0)}$
3）for t=0 to n1+n2-1:
a）从条件概率分布$P(x_2|x_1^{(t)})$中采样得到样本$x_2^{t+1}$
b) 从条件概率分布$P(x_1|x_2^{(t+1)})$中采样得到样本$x_1^{t+1}$
样本集 { ( x 1 ( n 1 ) , x 2 ( n 1 ) ) , ( x 1 ( n 1 + 1 ) , x 2 ( n 1 + 1 ) ) , . . . , ( x 1 ( n 1 + 2 ) , x 2 ( n 1 + 2 ) ) } \{(x_1^{(n_1)},x_2^{(n_1)}),(x_1^{(n_1+1)},x_2^{(n_1+1)}),...,(x_1^{(n_1+2)},x_2^{(n_1+2)})\} {(x1(n1​)​,x2(n1​)​),(x1(n1​+1)​,x2(n1​+1)​),...,(x1(n1​+2)​,x2(n1​+2)​)}即我们要的平稳分布对应的样本集。

采样过程是通过轮换改变坐标轴实现的，当然这不是必须的，但是一般是这样做。以上过程亦可以推广到多维Gibbs采样。

例子：
假设我们要采样的是一个二维正太分布$Normal(u,\Sigma )$,其中
$$u=(u_1,u_2)=(5,-1)$$$$\Sigma =\begin{array}{c}\left(\begin{array}{cc}{\sigma }_1^2& \rho {\sigma }_1{\sigma }_2\\ \rho {\sigma }_1{\sigma }_2& {\sigma }_2^2\end{array}\right)\end{array}=\begin{array}{c}\left(\begin{array}{cc}1& 1\\ 1& 4\end{array}\right)\end{array}$$
状态转移条件分布为：
$$\begin{gathered} P(x_2|x_1)=Norm(u+\rho {\sigma }_1/{\sigma }_2(x_2-u_2),(1-{\rho }^2){\sigma }_1^2) \\ P(x_1|x_2)=Norm(u+\rho {\sigma }_2/{\sigma }_1(x_1-u_1),(1-{\rho }^2){\sigma }_2^2) \end{gathered}$$

import random
import math
import matplotlib.pyplot as plt
from mpl_toolkits.mplot3d import Axes3D
from scipy.stats import multivariate_normal

samplesource = multivariate_normal(mean=[5,-1], cov=[[1,0.5],[0.5,2]])
#条件概率分布采样函数
def p_ygivenx(x, m1, m2, s1, s2):
    return (random.normalvariate(m2 + rho * s2 / s1 * (x - m1), math.sqrt(1 - rho ** 2) * s2))

def p_xgiveny(y, m1, m2, s1, s2):
    return (random.normalvariate(m1 + rho * s1 / s2 * (y - m2), math.sqrt(1 - rho ** 2) * s1))

N = 5000                                    #采样次数
K = 20
x_res = []                                  #采样样本x维度
y_res = []                                  #采样样本y维度
z_res = []                                  #采样样本z维度
m1 = 5                                      #均值u1
m2 = -1                                     #均值u2
s1 = 1                                      #方差s1
s2 = 2                                      #方差s2

rho = 0.5                                   #参数设置
y = m2

for i in range(N):
    for j in range(K):
        x = p_xgiveny(y, m1, m2, s1, s2)    #x轴根据条件概率采样
        y = p_ygivenx(x, m1, m2, s1, s2)    #y轴根据条件概率采样
        z = samplesource.pdf([x,y])         #z轴根据条件概率采样
        x_res.append(x)
        y_res.append(y)
        z_res.append(z)

num_bins = 50
plt.hist(x_res, num_bins, normed=1, facecolor='green', alpha=0.5)
plt.hist(y_res, num_bins, normed=1, facecolor='red', alpha=0.5)
plt.title('Histogram')
plt.show()

# 样本生成的二维正太分布图

fig = plt.figure()
ax = Axes3D(fig, rect=[0, 0, 1, 1], elev=30, azim=20)
ax.scatter(x_res, y_res, z_res,marker='o')
plt.show()

两个维度的采样分布如下：

二维分布如下：

由于Gibbs采样在高维特征时的优势，目前我们通常意义上的MCMC采样都是用的Gibbs采样。当然Gibbs采样是从M-H采样的基础上的进化而来的，同时Gibbs采样要求数据至少有两个维度，一维概率分布的采样是没法用Gibbs采样的,这时M-H采样仍然成立。

Gibbs采样是一种多维数据分布的样本集采样方法，Gibbs的采样理论是基于马尔科夫链的平稳分布条件得到的。具体的，将两点之间相同维度值的条件概率作为两数据点之间的转移概率，进行状态转移计算，轮换坐标轴采样，相应的得到本次转移的采样样本，所以，对于Gibbs采样而言，获取条件概率是必须的。

2，总结

我们来回忆一下整个问题。
1）很多时候，我们对一个分布并不感兴趣，感兴趣的是它的期望，所以我们会对一个连续函数$f(x)$求积分，但是积分需要知道$f(x)$的原函数，可是很多时候原函数很难求的，然后我们想到一个办法，根据x的概率分布函数采样，然后求期望值得到近似结果。——蒙特卡洛方法

2）好了，我们换了一条路，通过对x的概率密度分布函数$p(x)$采样，解决了$f(x)$原函数不好求解的问题，很多时候概率密度分布函数是先验的，比如掷硬币。但是另一个问题，如何采样？最简单的，我们通过一个常见函数$g(x)$覆盖目标函数$p(x)$，先对常见函数采样，然后按照一定的概率接受这个样本。——拒绝-接受采样

3）ok，我们看似解决了整个问题，但是拒绝-接受采样需要先找到一个可行的$g(x)$，在很多时候是比较困难的，而且不能处理多维数据采样问题，很多应用都是多维的。MCMC采样可以解决这个问题。根据MCMC平稳分布条件，我们知道，状态经过n次转移后，其概率分布不在变化，那么很明显，如果我们能得到使得状态能够平稳分布在目标分布$p(x)$的转移概率P，随意初始化样本，经过多次采样，就可以得到$p(x)$分布样本集。——MCMC

4）直接对$p(x)$采样的思路有了，那么如何得到合适的转移矩阵P呢？对任意一个转移矩阵Q添加一个可以使平稳分布成立的$\alpha$因子，我们就能得到想要的转移矩阵P，因此我们得到了MCMC采样方法。——MCMC采样

5）MCMC采样虽然可以完成采样任务，但是效率并不高，因为接受概率$\alpha$因子比较小，在可以转移的两个样本之间$\alpha$因子进行放大，保持等式成立的同时，增加了采样效率。——M-H采样

6）但是，我们还有一个最根本的问题。多维采样怎么处理？以上采样方法，只适合单一维度的函数采样，因为我们很难得到多维数据的联合分布状态转移矩阵，没关系，单一维度一样可以实现多维数据采样，只要我们从一个点的某一个轴开始，按照该参数轴上该点对另一个点的条件概率分布采样，就能得到另一个点的样本，多轴依次轮转，分别得到各个维度的采样值。而且同时我们每一次采样都是接受的，效率也很高。——Gibbs采样

至此，完美实现了概率密度函数$p(x)$采样问题，也顺利解决了积分或者求期望问题。

上一篇 MCMC详解1——蒙特卡洛方法

（本文参考了刘建平老师的博客，加入了一些自己的一些理解，有兴趣的可以去拜读原文）