【有啥问啥】深入浅出马尔可夫链蒙特卡罗（Markov Chain Monte Carlo, MCMC）算法
深入浅出马尔可夫链蒙特卡罗（Markov Chain Monte Carlo, MCMC）算法
0. 引言
Markov Chain Monte Carlo（MCMC）是一类用于从复杂分布中采样的强大算法，特别是在难以直接计算分布的情况下。它广泛应用于统计学、机器学习、物理学等领域，尤其是在贝叶斯推理和概率模型中。本文将深入解析 MCMC 的基本原理、核心算法（如 Metropolis-Hastings 和 Gibbs 采样），并讨论其在实际应用中的优势与局限，同时介绍一些先进的变种如 Hamiltonian Monte Carlo（HMC）。
1. 背景知识
在贝叶斯推断和许多概率模型中，目标是从某个复杂的后验分布 p ( θ ∣ x ) p(\theta | x) p(θ∣x) 中获取样本。然而，在大多数情况下，这种分布很难直接采样，因为其可能涉及到难以求解的归一化常数。
MCMC 提供了一种间接方法，通过构建一个马尔可夫链，使其逐步收敛到目标分布。然后，通过在平衡态（或稳态）下从马尔可夫链中提取样本，我们可以得到接近于目标分布的样本。
2. 马尔可夫链的基础
马尔可夫性质：马尔可夫链是一种具有“无记忆”性质的随机过程，当前状态的下一个状态只依赖于当前状态，而不依赖于历史状态。数学上，设 X 1 , X 2 , … X_1, X_2, \dots X1,X2,… 是马尔可夫链中的状态序列，满足：
P ( X n + 1 ∣ X 1 , X 2 , … , X n ) = P ( X n + 1 ∣ X n ) P(X_{n+1} | X_1, X_2, \dots, X_n) = P(X_{n+1} | X_n) P(Xn+1∣X1,X2,…,Xn)=P(Xn+1∣Xn)
转移矩阵：马尔可夫链通过转移概率矩阵（或转移核）定义，设 P i j P_{ij} Pij 表示从状态 i i i 转移到状态 j j j 的概率，则有：
P i j = P ( X n + 1 = j ∣ X n = i ) P_{ij} = P(X_{n+1} = j | X_n = i) Pij=P(Xn+1=j∣Xn=i)
细致平衡条件：在实际的 MCMC 应用中，重要的是确保马尔可夫链的平稳分布满足“细致平衡条件”（detailed balance）。即：
π ( i ) P i j = π ( j ) P j i \pi(i) P_{ij} = \pi(j) P_{ji} π(i)Pij=π(j)Pji
这一条件保证了链的平稳分布为目标分布。
稳态分布：经过足够多的迭代，马尔可夫链会收敛到一个稳定的分布 π \pi π，该分布满足：
π = π P \pi = \pi P π=πP
在 MCMC 中，我们构建的马尔可夫链会收敛到我们感兴趣的目标分布 p ( θ ∣ x ) p(\theta | x) p(θ∣x)。
举个栗子：
想象一下，你养了一只猫。这只猫在家里随机地游荡，它可能在卧室睡觉、在客厅玩耍、在厨房找吃的，或者在卫生间喝水。这只猫的行动路径就有点像一个马尔可夫链。
- 状态空间： 猫可能存在的各个位置就是它的“状态空间”。在这个例子中，状态空间包括：卧室、客厅、餐厅、厨房和卫生间。
- 转移概率： 猫从一个房间转移到另一个房间的概率就是“转移概率”。比如，猫在卧室里，它可能更喜欢去客厅玩耍，所以从卧室到客厅的转移概率就比较大；而它不太可能直接从卧室跳到天花板上，所以这个转移概率就很小。
- 马尔可夫性质： 猫决定去下一个房间的时候，只考虑它当前所在的房间，而不关心它之前都去过哪些房间。比如，如果猫现在在客厅，它决定去下一个房间的时候，只考虑从客厅能去哪些房间，以及去每个房间的概率，而不会考虑它之前是不是刚从卧室过来。
3. Monte Carlo 方法
Monte Carlo 方法通过随机采样来估计某些不可解析的期望值。设我们需要估计某个分布 p ( x ) p(x) p(x) 下某个函数 f ( x ) f(x) f(x) 的期望：
E p ( x ) [ f ( x ) ] = ∫ f ( x ) p ( x ) d x \mathbb{E}_{p(x)}[f(x)] = \int f(x) p(x) dx Ep(x)[f(x)]=∫f(x)p(x)dx
通过从分布 p ( x ) p(x) p(x) 中采样 x 1 , x 2 , … , x n x_1, x_2, \dots, x_n x1,x2,…,xn，我们可以用样本均值来近似这个期望：
E p ( x ) [ f ( x ) ] ≈ 1 n ∑ i = 1 n f ( x i ) \mathbb{E}_{p(x)}[f(x)] \approx \frac{1}{n} \sum_{i=1}^n f(x_i) Ep(x)[f(x)]≈n1i=1∑nf(xi)
但正如前述，对于复杂分布，直接采样 p ( x ) p(x) p(x) 往往不可行。这时 MCMC 技术登场，通过马尔可夫链来间接实现从 p ( x ) p(x) p(x) 中采样。
举个栗子：
想象你有一个不规则的图形，比如一个蝙蝠侠形状的图形，你想知道它的面积。这时可以用蒙特卡洛方法，首先，在蝙蝠侠图形外面画一个大的长方形，然后向这个长方形里随机撒豆子，最后通过计算落在蝙蝠侠图形中的豆子比例来估算图形的面积。
4. MCMC 核心算法
4.1 Metropolis-Hastings 算法
Metropolis-Hastings（MH）算法是 MCMC 中常用的采样方法。它通过构造一个易于采样的提议分布 q ( θ ′ ∣ θ ) q(\theta' | \theta) q(θ′∣θ)，并通过接受或拒绝的方式生成目标分布的样本。
步骤：
- 初始化 θ 0 \theta_0 θ0
- 对每一轮迭代：
- 根据提议分布 q ( θ ′ ∣ θ t ) q(\theta' | \theta_t) q(θ′∣θt) 生成候选样本 θ ′ \theta' θ′
- 计算接受概率：
α = min ( 1 , p ( θ ′ ∣ x ) q ( θ t ∣ θ ′ ) p ( θ t ∣ x ) q ( θ ′ ∣ θ t ) ) \alpha = \min \left(1, \frac{p(\theta' | x) q(\theta_t | \theta')}{p(\theta_t | x) q(\theta' | \theta_t)}\right) α=min(1,p(θt∣x)q(θ′∣θt)p(θ′∣x)q(θt∣θ′)) - 以概率 α \alpha α 接受 θ ′ \theta' θ′，否则保持当前状态 θ t \theta_t θt
Metropolis-Hastings 的灵活性在于可以使用不同的提议分布来优化采样效率。对于实际问题，选择适当的提议分布 q ( θ ′ ∣ θ ) q(\theta' | \theta) q(θ′∣θ) 是关键，过于分散或集中的分布都可能影响采样效率。
举个栗子（以抽球为例）：
- 步骤1：初始化
首先，你闭上眼睛，随机从箱子里摸出一个球，记住这个球的颜色，然后把它放回去。这个球的颜色就是你的起始点，也就是马尔可夫链的初始状态。
- 步骤2：提议生成
接着，你再次闭上眼睛，但这次你稍微改变了一下摸球的方式。你并不是完全随机地摸，而是基于你上次摸到的球的颜色来“提议”一个新的颜色。比如，如果你上次摸到的是红色球，那么你这次可能会倾向于摸一个和红色相近的颜色，比如橙色或紫色（当然，这只是一个比喻，实际中提议分布的选择会更复杂）。这个“提议”的颜色就是你的候选新状态。
- 步骤3：接受-拒绝策略
现在，你需要决定是否接受这个新的颜色作为你下一次摸球的结果。你计算了一个接受概率，这个概率取决于新颜色和旧颜色在箱子中真实出现概率的相对大小，以及你提议分布的一些特性。如果接受概率很高，你就接受这个新颜色；如果很低，你就拒绝它，并保留原来的颜色。
- 步骤4：重复迭代
你不断重复上述步骤，每次都根据当前的颜色来“提议”一个新的颜色，并根据接受概率来决定是否接受它。随着时间的推移，你会发现你摸到的球的颜色分布越来越接近箱子中真实的颜色分布。
4.2 Gibbs 采样
Gibbs 采样是一种特殊的 MCMC 方法，适用于多维随机变量的情况。与 MH 不同，Gibbs 采样通过逐步更新每一个维度的值来生成样本，每次更新都从条件分布中进行采样。
步骤：
- 初始化 θ 0 = ( θ 1 ( 0 ) , θ 2 ( 0 ) , … , θ d ( 0 ) ) \theta_0 = (\theta_1^{(0)}, \theta_2^{(0)}, \dots, \theta_d^{(0)}) θ0=(θ1(0),θ2(0),…,θd(0))
- 对每一轮迭代：
- 对每个维度 i i i：
θ i ( t + 1 ) ∼ p ( θ i ∣ θ 1 ( t + 1 ) , … , θ i − 1 ( t + 1 ) , θ i + 1 ( t ) , … , θ d ( t ) ) \theta_i^{(t+1)} \sim p(\theta_i | \theta_1^{(t+1)}, \dots, \theta_{i-1}^{(t+1)}, \theta_{i+1}^{(t)}, \dots, \theta_d^{(t)}) θi(t+1)∼p(θi∣θ1(t+1),…,θi−1(t+1),θi+1(t),…,θd(t))
- 对每个维度 i i i：
- 重复迭代，直到样本收敛。
Gibbs 采样在模型中条件分布易于采样的情况下表现出色，常用于贝叶斯网络或隐马尔可夫模型等。
4.3 Hamiltonian Monte Carlo（HMC）
Hamiltonian Monte Carlo 是一种高级 MCMC 方法，通过引入物理学中的哈密顿动力学，将样本点视为在势能场中运动的粒子。HMC 可以高效探索高维参数空间，避免传统 MCMC 中的低效率。
核心思想：
- 在传统的 Metropolis-Hastings 算法中，采样仅依赖于当前的状态，而 HMC 则利用目标函数的梯度信息来辅助样本生成。
- HMC 不仅能够加快高维参数的探索，还可以有效避免“随机漫步”行为，使得采样更高效。
HMC 被广泛应用于深度贝叶斯学习中，特别是在大规模复杂模型中表现优异。
5. MCMC 的应用
举个栗子：
现在，我们把蒙特卡洛方法和马尔可夫链结合起来，就得到了MCMC方法。假设我们想知道一个复杂分布（比如一个蝙蝠侠形状的区域里豆子的分布）的某些性质（比如平均高度），但是直接计算太难了。我们可以用MCMC方法来做这件事。
-
首先，我们构造一个马尔可夫链，使得这个链的平稳分布（就是链运行很长时间后每个状态出现的概率分布）恰好是我们想要研究的那个复杂分布。这通常需要我们精心设计马尔可夫链的转移概率。
-
然后，我们从马尔可夫链的某个初始状态开始，按照转移概率随机地移动，生成一系列的状态（就像猫一样）。在刚开始的时候，这些状态可能并不符合我们想要的分布，但是随着链的运行，这些状态会越来越接近我们想要的分布。
-
最后，当我们认为链已经运行了足够长的时间，达到了平稳分布时，我们就可以用这些状态来估算我们想要知道的性质了。比如，我们可以用这些状态来估算蝙蝠侠形状区域里豆子的平均高度。
MCMC 被广泛应用于各种复杂模型中，特别是在贝叶斯推理中。以下是几个典型的应用领域：
-
贝叶斯推断：在贝叶斯推理中，通常需要从后验分布 p ( θ ∣ x ) p(\theta | x) p(θ∣x) 中采样，而该分布可能非常复杂，难以直接采样。MCMC 方法使得这种采样成为可能。
-
隐变量模型：如混合高斯模型（GMM）、隐马尔可夫模型（HMM）等模型中，往往包含不可观测的隐变量。MCMC 可以帮助我们通过采样这些隐变量来进行模型的推断。
-
物理模拟：在物理学领域，如分子动力学模拟、气候模型、材料科学中，MCMC 是估计复杂概率分布的重要工具。
-
深度学习中的贝叶斯模型：结合深度学习与贝叶斯推断，MCMC 在神经网络参数估计、模型选择等方面有了广泛的应用，尤其是在不确定性估计上有明显优势。
6. MCMC 的优势与挑战
优势：
- 适用于复杂的后验分布，尤其是在高维空间下。
- Metropolis-Hastings 和 Gibbs 采样等算法都相对容易实现且适应性强。
- Hamiltonian Monte Carlo 等高级方法可以在高维空间中提高采样效率。
挑战：
- 收敛性问题：确保链的收敛是一个核心挑战，通常需要设置足够长的 burn-in 阶段，以消除初始状态的影响。如何判断链已经收敛仍是一个开放问题。
- 计算成本高：在高维复杂模型中，MCMC 采样的计算成本可能非常高，尤其是每次采样都需要计算大量的概率值。即使使用 HMC，梯度计算的开销也不容忽视。
- 样本自相关性：MCMC 方法生成的样本往往具有自相关性，需要通过后处理（如细化链或降采样）来减小这种影响。
7. 总结
Markov Chain Monte Carlo（MCMC）为我们提供了一种强大的工具，用于从复杂分布中进行采样，特别是在贝叶斯推断和概率模型中具有广泛的应用。尽管 MCMC 存在一定的收敛性和效率挑战，但随着算法的优化和硬件性能的提升，其在机器学习、统计学等领域的应用前景依旧广阔。
诸如 Hamiltonian Monte Carlo（HMC）等高级变种，以及结合深度学习的方法（如变分推断与 MCMC 的混合使用），可能会进一步提升 MCMC 在大规模数据中的表现，使其在更广泛的领域中发挥作用。