1700537475
百面机器学习：算法工程师带你去面试 [:1700532216]
1700537476
百面机器学习：算法工程师带你去面试 05 马尔可夫蒙特卡洛采样法
1700537477
1700537478
1700537479
1700537480
场景描述
1700537481
1700537482
前面小节中提到，在高维空间中，拒绝采样和重要性重采样经常难以寻找合适的参考分布，采样效率低下（样本的接受概率小或重要性权重低），此时可以考虑马尔可夫蒙特卡洛（Markov Chain Monte Carlo，MCMC）采样法。MCMC采样法是机器学习中非常重要的一类采样算法，起源于物理学领域，到20世纪80年代后期才在统计学领域产生重要影响。它可以用于很多比较复杂的分布的采样，并且在高维空间中也能使用。
1700537483
1700537484
知识点
1700537485
1700537486
蒙特卡洛法，马尔可夫链，吉布斯采样，Metropolis-Hastings采样
1700537487
1700537488
问题1 简述MCMC采样法的主要思想。
1700537489
1700537490
难度：★☆☆☆☆
1700537491
1700537492
分析与解答
1700537493
1700537494
从名字看，MCMC采样法主要包括两个MC，即蒙特卡洛法（Monte Carlo）和马尔可夫链（Markov Chain）。蒙特卡洛法是指基于采样的数值型近似求解方法，而马尔可夫链则用于进行采样。MCMC采样法基本思想是：针对待采样的目标分布，构造一个马尔可夫链，使得该马尔可夫链的平稳分布就是目标分布；然后，从任何一个初始状态出发，沿着马尔可夫链进行状态转移，最终得到的状态转移序列会收敛到目标分布，由此可以得到目标分布的一系列样本。在实际操作中，核心点是如何构造合适的马尔可夫链，即确定马尔可夫链的状态转移概率，这涉及一些马尔可夫链的相关知识点，如时齐性、细致平衡条件、可遍历性、平稳分布等，感兴趣的读者可以参阅相关资料，这里不再细述。
1700537495
1700537496
问题2 简单介绍几种常见的MCMC采样法。
1700537497
1700537498
难度：★★☆☆☆
1700537499
1700537500
分析与解答
1700537501
1700537502
MCMC采样法的核心点是构造合适的马尔可夫链，不同的马尔可夫链对应着不同的MCMC采样法，常见的有Metropolis-Hastings采样法和吉布斯采样法，如图8.6所示。
1700537503
1700537504
1700537505
1700537506
1700537507
图8.6 MCMC采样示意图
1700537508
1700537509
■ Metropolis-Hastings采样法
1700537510
1700537511
对于目标分布p(x)，首先选择一个容易采样的参考条件分布q(x*|x)，并令
1700537512
1700537513
1700537514
．
1700537515
1700537516
（8.19）
1700537517
1700537518
然后根据如下过程进行采样：
1700537519
1700537520
（1）随机选一个初始样本x(0)。
1700537521
1700537522
（2）For t = 1, 2, 3, … :
1700537523
1700537524