三、MCMC 采样
- 概率图模型中最常用的采样技术是马尔可夫链蒙特卡罗方法
Markov Chain Monte Carlo:MCMC。 给定连续随机变量 ![三、MCMC 采样 - 图1] 中的概率可以计算为：
如果函数 ![三、MCMC 采样 - 图6] 。
- 如果
- 如果概率密度函数
3.1 MCMC 算法
MCMC算法的基本思想是：先设法构造一条马尔可夫链，使其收敛到平稳分布恰好为 ![三、MCMC 采样 - 图18] 分布的样本。最后通过这些样本来进行估计。 这里马尔可夫链的构造至关重要，不同的构造方法将产生不同的MCMC算法。Metropolis-Hastings:MH算法是MCMC的重要代表。- 假设已经提供了一条马尔可夫链，其转移矩阵为 ![三、MCMC 采样 - 图20] 。 通常 ![三、MCMC 采样 - 图23] 并不满足细致平稳条件不成立。但是可以改造已有的马尔可夫链，使得细致平稳条件成立。 引入一个函数 ![三、MCMC 采样 - 图25] ，则有：
令： ![三、MCMC 采样 - 图29] 。
在改造 ![三、MCMC 采样 - 图35] 的概率接受这个转移。
如果接受率
根据推导
于是： ![三、MCMC 采样 - 图46] 。因此，即使提高了接受率，细致平稳条件仍然成立。
将 ![三、MCMC 采样 - 图47] 。
当
当
当
MH算法： 输入：先验转移概率矩阵
目标分布
输出： 采样出的一个状态序列
算法：初始化
对
根据
计算
根据均匀分布从
返回采样得到的序列
3.2 Gibbs 算法MH算法不仅可以应用于一维空间的采样，也适合高维空间的采样。 对于高维的情况，由于接受率 ![三、MCMC 采样 - 图76]），MH算法的效率通常不够高，此时一般使用Gibbs采样算法。考虑二维的情形：假设有概率分布 ![三、MCMC 采样 - 图78] ，可以证明有：
于是 ![三、MCMC 采样 - 图82] 作为直线上任意两点之间的转移概率，则这两点之间的转移满足细致平稳条件。
同理：考察 ![三、MCMC 采样 - 图86] 作为直线上任意两点之间的转移概率，则这两点之间的转移满足细致平稳条件。
可以构造状态空间上任意两点之间的转移概率矩阵 ![三、MCMC 采样 - 图92]：
如果
如果
否则
采用该转移矩阵 ![三、MCMC 采样 - 图102]，都满足细致平稳条件：
于是这个二维状态空间上的马尔可夫链将收敛到平稳分布 ![三、MCMC 采样 - 图105] ，这就是吉布斯采样的原理。
Gibbs算法：输入：目标分布
输出： 采样出的一个状态序列
算法步骤：初始化：随机初始化
执行迭代，迭代步骤如下：随机或者以一定次序遍历索引
将
该条件概率就是状态转移概率
根据条件概率
令
最终返回一个状态序列
吉布斯采样
Gibbs sampling有时被视作MH算法的特例，它也使用马尔可夫链获取样本。
文章列表
- AI算法工程师手册-一、基本知识
- AI算法工程师手册-一、数值稳定性
- AI算法工程师手册-一、概率与分布
- AI算法工程师手册-一、蒙特卡洛方法
- AI算法工程师手册-七、信息论
- AI算法工程师手册-三、MCMC 采样
- AI算法工程师手册-三、二阶导数与海森矩阵
- AI算法工程师手册-三、大数定律及中心极限定理
- AI算法工程师手册-三、矩阵运算
- AI算法工程师手册-二、向量操作
- AI算法工程师手册-二、期望和方差
- AI算法工程师手册-二、梯度下降法
- AI算法工程师手册-二、马尔可夫链
- AI算法工程师手册-五、常见概率分布
- AI算法工程师手册-五、拟牛顿法
- AI算法工程师手册-八、其它
- AI算法工程师手册-六、 约束优化
- AI算法工程师手册-六、先验分布与后验分布
- AI算法工程师手册-四、牛顿法
- AI算法工程师手册-四、特殊函数
