马尔可夫蒙特卡洛（MCMC）

1.马尔可夫链(Markov Chain)

随机过程是一组随机变量$X_t$的集合，$t$为整数的时候，就是离散随机过程。马尔可夫过程是指一个满足马尔可夫性质的随机过程。马尔可夫性质是指:$$P(X_{t+1}|X_t,\cdots ,X_1)=P(X_{t+1}|X_t)$$

也就是说，当前随机变量的分布，只与上一个时间的随机变量取值有关系，与之前的取值都是独立的。

1.1 平稳分布

(定义)状态空间：状态空间是指这些随机变量所有取值的集合。例如，下雨和晴天的概率是0.1和0.9，则状态空间就是下雨和晴天。

**状态转移矩阵：**当状态空间大小K是有限的，则状态之间的转移概率可以用一个矩阵$M\in {\mathbb{R}}^{k\times k}$来表示。其中，$M_{ij}$表示从状态$i$转移到状态$j$的概率。例如，从下雨转移到晴天的概率是0.9，从晴天转移到下雨的概率是0.2，从下雨转移到下雨本身的概率是0.1，从晴天转移到晴天本身的概率是0.8。则可表示为一个$2\times 2$的矩阵，为：
$$M=\left[\begin{array}{cc}0.8& 0.2\\ 0.9& 0.1\end{array}\right]$$
于是，如果晴天和下雨本身的初始状态分布$\pi$是:
$$\pi ={\left[\begin{array}{c}0.9\\ 0.1\end{array}\right]}^T$$
则经过一次状态转移就是：
$${\pi }_{new}=\pi M$$
对于${\pi }_{new}$，可以继续进行状态转移。

转移矩阵显然需要满足：
$$\sum _j{M}_{ij}=1$$
也就是每一行是归一化的。因为由原来某种状态转向所有状态的概率之和肯定是1。

（定义）平稳分布: 对于状态转移矩阵为$M$的马尔可夫链，如果存在$\pi$，使得

$$\pi =M\pi$$，则称$\pi$是该马尔可夫链的平稳分布。也就是说，经过一次状态转移后，状态不再发生改变。

对于$M$满足一定条件的马尔可夫链来说，初始状态经过一定时间的状态转移之后，一定会收敛。
$$\pi =\underset{N\to \infty }{\lim }{M}^N\pi$$
也就是说，乘以了一定次数的状态转移矩阵M之后，状态分布就不会变了。注意，这里的状态转移矩阵$M$是需要满足两个条件，为所有状态可遍历性可非周期性。

2.2 细致平稳条件(Detail Balance Condition)

细致平稳条件是马尔可夫收敛的充分条件，保证了马尔可夫链一定会收敛。

(定义）细致平稳条件: 给定一个状态空间中的分布$\pi$，如果转移矩阵为$M$的马尔可夫链满足：
$${\pi }_i{m}_{ij}={\pi }_j{m}_{ji},\forall 1\le i,j\le K$$
则该马尔可夫链在已经一段时间的状态转移之后就一定会收敛到分布$\pi$。

换句话说，如果满足该马尔可夫链的状态转移矩阵满足了上述条件，则$\pi$就是该马尔可夫链的平稳分布，而且一定能够收敛到这个平稳分布。

2.MCMC

MCMC是对某个概率分布进行采样，获得样本的方法，是一种采样方法。对于一个复杂的概率密度分布，我们很难获得其解析的性质，因此采用采样的方式，通过样本来观察这个概率分布的性质。

MCMC是思路是找到一个平稳分布为所需要采样分布的马尔可夫链，其本质是找到一个转移矩阵，确定了平稳分布对应的转移矩阵，就确定了马尔可夫链。

但是，随便一个状态转移矩阵，一般无法满足细致平稳条件。对于某个希望采样的平稳分布$\pi$，对于某一随机状态转移矩阵，并不能保证收敛到到这个平稳分布，也就是：
$${\pi }_i{m}_{ij}\ne {\pi }_j{m}_{ji}$$

2.1 Metropolis-Hastings采样方法

在上面公式的两边同时乘以一个数，则存在这样的数，使得：
$${\pi }_i{m}_{ij}{\alpha }_{ij}={\pi }_i{m}_{ji}{\alpha }_{ji}\forall 1\le i,j\le k$$
此时，M为某个不满足$\pi$对应细致条件的转移矩阵，是任意的转移矩阵，而经过$\alpha$的修正，就满足了细致平稳条件，此时可以令$p_{ij}=m_{ij}{\alpha }_{ij}$，此时$P\in R^{k\times k}$就为一个新的转移矩阵，该矩阵就是满足细致平稳条件的转移矩阵。

这样的数${\alpha }_{ij}$如何找到呢？Metropolis-Hastings方法构造了如下的${\alpha }_{ij}$:
α i j = m i n { π j m j i π j m i j , 1 } \alpha_{ij} = min\{\frac{\pi_jm_{ji}}{\pi_jm_{ij}},1 \} αij​=min{πj​mij​πj​mji​​,1}
如果令${\alpha }_{ij}$等于上式，则可使得调整后的转移矩阵满足$\pi$对应细致平稳条件，推导如下：
π i m i j α i j = π i m i j m i n { 1 , π j m j i π i m i j } = m i n { π i m i j , π j m j i } = π j m j i m i n { π i m i j π j m j i , 1 } = π j m j i α j i \pi_im_{ij}\alpha_{ij} \\ =\pi_im_{ij}min\{1,\frac{\pi_jm_{ji}}{\pi_im_{ij}}\}\\ =min\{\pi_im_{ij},\pi_jm_{ji}\}\\ =\pi_jm_{ji}min\{\frac{\pi_im_{ij}}{\pi_jm_{ji}},1\}\\ =\pi_jm_{ji}\alpha_{ji} πi​mij​αij​=πi​mij​min{1,πi​mij​πj​mji​​}=min{πi​mij​,πj​mji​}=πj​mji​min{πj​mji​πi​mij​​,1}=πj​mji​αji​
故上面所构造的${\alpha }_{ij}$，可以使得细致平稳条件得到满足。

由此，只需要先进行一定次数的随机游走（预烧期）之后，马尔可夫链收敛到平稳分布。然后继续通过随机游走，获得新的样本。由于此时的样本的分布已经是平稳分布，同时也是我们需要采样的分布，获得的样本就属于所需要采样的分布。

此时，马尔可夫链做了两件事请：

• 首先以原本转概率矩阵的概率进行转移
• 然后，在转移的半截腰中，在根据${\alpha }_{ij}$来再次判定是否转移。

因此，${\alpha }_{ij}$可以视作某种接受概率，马尔可夫链进行一次转移之后，以这个接受率判断是否进行这次转移。

那么，如何让${\alpha }_{ij}$发挥作用呢？

1. 当马尔可夫链进行随机游走，就产生了一个新的样本
2. 生成一个0~1上的服从均匀分布的随机数
3. 如果随机数大于${\alpha }_{ij}$，就接受这个新的样本，也就是认为。反之，则不接受这个新的样本。

2.2 转移矩阵的选择问题

上面已经说过，我们对于原本的转移矩阵，一般都不会满足细致平稳条件，因此引入了$\alpha$来调整这个转移矩阵。当时我们说是任意的转移矩阵。对于算法而言，是可行的。但是对于计算机实现而言，最好这个转移矩阵是方便使用的。这个转移矩阵要满足两个条件：

• 1.从某个状态转移向所有状态的概率之和为1，也就是行归一化，这是转移矩阵的基本性质。
• 2.易于计算机模拟，也就是我们要先进行随机游走，然后再用$\alpha$来判定这个随机游走是否成立。那随机游走的过程一定要方便。

对于状态空间离散的情况，这个矩阵是极容易设计的。也就是随机变量离散的情形下。但是对于连续随机变量，如何处理呢？其状态空间是无穷大的，相当于是一个无穷大是矩阵。

通常的做法利用一个高斯分布来做。
$$m_{ij}=\mathcal{N}(x_j|\mu =x_i,\sigma =1)$$
也就是说，每个旧的样本点所在的位置为均值的一个高斯分布。首先，满足某个状态到所有状态之和是1，因为高斯分布是归一化的${\int }_{x}p(x)dx=1$。其次，高斯分布，对于计算机而言是容易采样的。

同时，由于高斯分布是对称的，因此从$i$转移到$j$的概率和从$j$转移到$i$的概率是相等的，也就是以$i$为均值的高斯分布在$j$处的值和以$j$为均值的高斯分布在$i$处的值是相等的。换句话说，$m_{ij}=m_{ji}$，因此原本${\alpha }_{ij}$的表达式可以化简写作：
α i j = m i n { π j m j i π i m i j , 1 } = m i n { π j π i , 1 } \alpha_{ij} = min\{\frac{\pi_jm_{ji}}{\pi_im_{ij}},1\}\\ =min\{\frac{\pi_j}{\pi_i},1\} αij​=min{πi​mij​πj​mji​​,1}=min{πi​πj​​,1}

2.3算法流程

1. 随机选取一个初始样本点
2. 在初始点处生成均值为初始点值的高斯分布，在高斯上进行一次采样，模拟了一次随机游走，获得一个新的样本点。
3. 计算接受率${\alpha }_{ij}$，这个可以计算，因为概率分布已知，这里的概率分布就是所需要采样的概率分布。
4. 生成0~1随机数，通过和接受率比较，决定是否接受这次随机游走。如果随机数大于接受率，则拒绝此次随机游走，将旧样本点（第一次的话就是初值）收入样本集合。如果随机数小于接受率，接受此次随机游走，把新的样本点收入样本集合。
5. 上一步中，如果接受了随机游走，则再新的样本点处生成高斯分布，进行下一次随机游走。如果拒绝了，则在旧的样本点处生成高斯分布，随机游走。
6. 循环上述过程，如100000次，就可获得100000个样本点。
7. 当游走一定次数之后，此时马尔可夫链收敛到平稳分布，生成的样本点就服从所需要分布。而在此次数之前的样本点不服从平稳分布，舍弃这部分样本点。常规做法是舍弃前10000个样本点，也就是认为进行了10000次随机游走之后马尔可夫链收敛了。这10000次随机游走称为预烧期(burn-in)。

3.代码

3.1采样二维高斯分布

import numpy as np
import scipy
import seaborn
import matplotlib.pyplot as plt# 定义二维高斯分布，均值默认0均值，协方差矩阵默认单位阵
def guassian2d(x,mean=np.array([[0],[0]]),covariance = np.array([[1,0],[0,1]])):"""Return the probability of the value in 2-dimension Guassiandistribution given mean vector and variance matrix.---Args:x: The value of the random variablemean: mean vector of the variancevariance: 2x2 covariance matrix---"""# 做维度的检查if mean.shape != (2,1):raise Exception("Dimension of the mean is wrong.")if covariance.shape != (2,2):raise Exception("Dimension of the covariance matrix is wrong.")# 高斯的核，这是贝叶斯的说法，在计算共轭分布时常用# 这里为了清晰因此将高斯分开算guassian_kernel =\np.exp((-1/2)*np.dot(np.dot((x-mean).T,np.linalg.inv(covariance)),(x-mean)))probability = guassian_kernel/(2*np.pi*np.sqrt(np.linalg.det(covariance)))return probabilityN_BURN_IN = 1000 # 预烧期1000次，先随机游走1000次认为收敛
N_SAMPLINGS = 10000 #采样总计10000次，也就是随机游走10000次def metropolis_hastings(prob_func, n_burn_in, n_samplings):"""Given a probablity function then return the samplings."""x_old = np.array([[0],[0]]) # 任意初始化一个样本点# 生成一个数组，存放样本点，一共采样10000次，有10000个样本点# 但是最后这10000个样本的前1000个不需要，是预烧期的samples = np.zeros((2,n_samplings), np.float32)for i in range(n_samplings):# 进行一次随机游走# 这里原本是以旧样本为均值，方差为1的高斯分布来采样，模拟随机游走# 等价于在原来的样本上加上一个0均值，方差为1的高斯分布采样x_new = np.random.normal(loc=x_old, scale = 1, size = (2,1))# 计算接受率alphaalpha = np.min([prob_func(x_new)/prob_func(x_old),1])# 随机生成0-1随机数，小于接受率，则将新样本接收if np.random.rand() < alpha:x_old = x_newsamples[:,i] = x_new.reshape(2,)# 大于接受率，则接受旧样本（注意不是舍弃）else:x_old = x_oldsamples[:,i] = x_old.reshape(2,)return samplesif __name__ == "__main__":samples = metropolis_hastings(guassian2d, N_BURN_IN, N_SAMPLINGS)seaborn.jointplot(samples[0,N_BURN_IN:], samples[1,N_BURN_IN:])plt.show()

结果：