5.1.4 MCMC：MH采样算法证明

到这里，我们已经把马尔可夫链蒙特卡洛采样拆成三部分分别解释了一遍。

马尔可夫链蒙特卡洛采样（Markov Chain Monte Carlo Sampling，MCMC）关键词含义：

• 马尔可夫链（Markov Chain）: 采样是沿着一条马尔可夫链进行状态转移

• 蒙特卡洛采样（Monte Carlo Sampling）: 用采样的方法来逼近某个分布

现在，我们来把前面讲的三部分结合起来。

还记得前面的Metropolis-Hasting采样吗？我们现在可以来解释为什么这样的算法是可行的了。

再回顾一下MH算法：

1. 从任意一个$x_0$开始

2. 根据当前的样本$x_t$构建一个提议分布$g(x | x_t)$ (e.g.$g(x | x_t)$可以是一个高斯分布)，然后采样得到$x^*$

3. 然后计算接受率 $\alpha = \min \left[ 1, \frac{p(x^*) \cdot g(x_t \mid x^*)}{p(x_t) \cdot g(x^* \mid x_t)} \right]$

4. 从$[0,1]$采样一个值$u$,

   - 如果 $u< \alpha$, 接受该样本 $x_{t+1} = x^*$

   - 否则，继续维持原来的样本 $x_{t+1} = x_t$

5. 重复2-4步直到达到预订的样本数量

这里有两个疑问：

1. 提议分布$g(x | x_t)$是由我们自己随意定的，凭什么随意定一个$g$都可以能从$p(x)$进行采样？

2. 为什么接受率设置成这个形式之后，就可以对目标分布$p(x)$进行采样？

从马尔可夫链的性质，我们知道，要从复杂的$p(x)$中采样，就要找到与$p(x)$对应的状态转移函数。怎么找呢？随便假定一个转移函数$Q$显然是不行的，它不满足细致平稳条件，即：

$$p(x_i)*Q(x_j | x_i) \not= p(x_j)*Q(x_i | x_j)$$

所以我们要对以上的公式做一定的改造，让它满足细致平稳条件。

首先，引入$a(x_j | x_i)$, 使得上面的式子可以取等号, 即：

$$p(x_i)*Q(x_j | x_i)*a(x_j | x_i) = p(x_j)*Q(x_i | x_j)*a(x_i | x_j)$$

问题是什么样子的$a(x_j | x_i)$可以满足该要求呢？其实很简单，只要满足下面条件：

$$a(x_j | x_i) = min(1, \frac{p(x_j)*Q(x_i | x_j)}{p(x_i)*Q(x_j | x_i)})$$

把$a(x_j | x_i)$带入公式，

$$\begin{align*} p(x_i)*Q(x_j | x_i)*a(x_j | x_i) &= p(x_i)*Q(x_j | x_i)*min(1, \frac{p(x_j)*Q(x_i | x_j)}{p(x_i)*Q(x_j | x_i)}) \\ &= min(p(x_i)*Q(x_j | x_i), p(x_j)*Q(x_i | x_j)) \\ &= p(x_j)*Q(x_i | x_j) * min(\frac{p(x_i)*Q(x_j | x_i)}{p(x_j)*Q(x_i | x_j)}, 1) \\ &= p(x_j)*Q(x_i | x_j)*a(x_i | x_j) \end{align*}$$

如果我们把新的转移函数设置为$M(x_j | x_i)=Q(x_j | x_i)*a(x_j | x_i)$，自然就满足细致平稳条件：

$$p(x_i)*M(x_j | x_i)= p(x_j)*M(x_i | x_j)$$

注意，这里的$Q(x_j | x_i)$可以是任意的转移函数（例如高斯函数），以上式子恒成立。

回答前面两个疑问：

1. 任意提议分布$g(x | x_t)$就任意是转移函数$Q(x_j | x_i)$，它的确无法直接满足细致平稳条件。

2. 但是，任意提议分布$g(x | x_t)$和接受率$\alpha$结合起来形成了新转移函数$M(x_j | x_i)$：先从任意提议分布中采样，然后接受率决定是否采纳新样本——新的转移函数满足细致平稳条件。

我们知道，认知心理学中概率模型的本质就是求解后验概率分布$p(\theta | data)$，

$$p(\theta | data) = \frac{p(data | \theta) \cdot p(\theta)}{p(data)}$$

换句话来说，我们的目标分布是$p(\theta|data)$。为了和前面的公式推导符号一致，我们把目标分布写为$p(x|data)$，并带入公式，得到：

$$\begin{align*}a(x_j | x_i) &= min(1, \frac{p(x_j | data) \cdot Q(x_i | x_j)}{p(x_i | data) \cdot Q(x_j | x_i)}) \\ &= min(1, \frac{p(data | x_j) \cdot p(x_j)/p(data) \cdot Q(x_i | x_j)}{p(data | x_i) \cdot p(x_i)/p(data) \cdot Q(x_j | x_i)})\end{align*}$$

假设先验分布为均匀分布，则$p(x_i) = p(x_j)$；假设提议分布是对称的（例如高斯分布，实际上前面说过的任意提议分布都可以），则$Q(x_j | x_i) = Q(x_i | x_j)$。上式进一步简化为：

$$a(x_j | x_i) = min(1, \frac{p(data | x_j)}{p(data | x_i)})$$

可以看到，等式右边直接就是似然函数的比值。

如果想要进一步理解数学推导，可以参考以下资料：

• 博客资料: https://www.cnblogs.com/pinard/p/6625739.html

• B站视频: https://www.bilibili.com/video/av32430563/