作者：CHEONG

公众号：AI机器学习与知识图谱

研究方向：自然语言处理与知识图谱

阅读本文之前，首先注意以下两点：

1. 机器学习系列文章常含有大量公式推导证明，为了更好理解，文章在最开始会给出本文的重要结论，方便最快速度理解本文核心。需要进一步了解推导细节可继续往后看。

2. 文中含有大量公式，若读者需要获取含公式原稿Word文档，可关注公众号【AI机器学习与知识图谱】后回复：MCMC第三讲，可添加微信号【17865190919】进学习交流群，加好友时备注来自CSDN。原创不易，转载请告知并注明出处！

本文先给出MCMC采样的核心思想，然后介绍MCMC采样策略成立的两个重要关键点。MCMC相关概念请看：

一、MCMC核心思想

传统拒绝采样和重要性采样想直接给出高维复杂概率分布 p ( x ) p(x) p(x)相近的 q ( x ) q(x) q(x)是十分复杂的；

MCMC就试图间接找到这样的 q ( x ) q(x) q(x)，即先构造一条马氏链，通过假设合适的转态转移矩阵，让马氏链最后进入平稳分布状态概率分布 q m ( x ) q^{m}(x) qm(x)，且 q m ( x ) q^{m}(x) qm(x)和 p ( x ) p(x) p(x)相近，这样通过对 q m ( x ) q^{m}(x) qm(x)进行采样来代替高维复杂概率分布 p ( x ) p(x) p(x)，这就是MCMC采样的思想，所以关键在于如何构造合适的状态转移矩阵，让马氏链最终能够平稳分布并接近 p ( x ) p(x) p(x)。

因此从MCMC采样想法中需要说明两个关键点：

1、马氏链是否可以趋近于平稳分布状态，概率分布 q m ( x ) q^{m}(x) qm(x)；

2、如何设置转态转移矩阵使得平稳分布状态下的概率分布 q m ( x ) q^{m}(x) qm(x)接近 p ( x ) p(x) p(x)

证明1：马氏链随着转移矩阵转变，当 m − > ∞ m->\infty m−>∞时会趋向于平稳分布状态。

如上存在的马氏链，假设每个时刻的概率分布 q ( t + 1 ) ( x ) q^{(t+1)}(x) q(t+1)(x)共有K个状态：

则可以令 q ( t + 1 ) ( x ) q^{(t+1)}(x) q(t+1)(x)是一个 1 ∗ K 1*K 1∗K维的向量：

则状态转移矩阵，也称为随机矩阵为：

若马氏链的状态从t时刻的 x i x_i xi​到t+1时刻的 x j x_j xj​，则可以写出：

将上式带入到 q ( t + 1 ) ( x ) q^{(t+1)}(x) q(t+1)(x)向量表示中展开为：

因此有：

所以继续迭代推导有：

随机矩阵 Q Q Q具有一个性质，即特征值的绝对值都小于等于1，则对随机矩阵 Q Q Q进行分解为：

其中：

因此特征值绝对值都小于等于1，不妨假设只有一个特征值为1，其他都小于1，则有：

因此存在足够大的 m m m，则有：

即对角线上只有一个为1，其他对于小于1的足够大的指数运算后都趋近于0，所以

因此有：

至此得出结论，当m足够大时，马氏链趋向于平稳分布。

证明2、如何设置转态转移矩阵Q使得平稳分布状态下的概率分布 q m ( x ) q^{m}(x) qm(x)接近 p ( x ) p(x) p(x)

MCMC如何利用马尔科夫链收敛于平稳分布，来设计转态转移矩阵Q，使得平稳分布 q m ( x ) q^{m}(x) qm(x)约等于目标分布 p ( x ) p(x) p(x)，马尔科夫链收敛到的平稳分布 q m ( x ) q^{m}(x) qm(x)和初始分布没有关系，只和状态转移矩阵Q有关。具体怎么设置转态转移矩阵Q，参见MH采样算法和Gibbs采样算法，在下一节中将详细介绍具体的采样策略。