Metropolis-Hastings算法

Metropolis-Hastings算法（Metropolis–Hastings Algorithm）是一类基于马尔可夫链蒙特卡洛（Markov Chain Monte Carlo, MCMC）方法的随机采样算法，由尼古拉斯·梅特罗波利斯（Nicholas Metropolis）于1953年提出原始版本，后由W·K·哈斯廷斯（W. K. Hastings）于1970年推广至一般形式。该算法的核心思想是通过构造一条以目标分布为平稳分布的马尔可夫链，从而从难以直接采样的复杂概率分布中生成近似独立的样本。作为MCMC方法中最基础、最通用的框架之一，Metropolis-Hastings算法在贝叶斯统计、计算物理、机器学习、计算生物学等领域具有广泛应用。

1. 算法原理

1.1 基本思想

假设目标分布 $\pi(x)$ 的归一化常数未知或难以计算，且我们只能计算其未归一化的核函数 $f(x) = c \cdot \pi(x)$。Metropolis-Hastings算法通过引入一个易于采样的提议分布（Proposal Distribution）$q(x'|x)$，在当前状态 $x$ 的基础上生成候选状态 $x'$，然后以一定的接受概率决定是否移动到新状态。这一接受-拒绝机制确保了马尔可夫链的细致平衡条件（Detailed Balance）成立，从而使 $\pi(x)$ 成为链的平稳分布。

1.2 算法流程

算法从任意初始状态 $x_0$ 开始，对每一轮迭代 $t = 0, 1, 2, \dots$ 执行以下步骤：第一步，从提议分布 $q(x'|x_t)$ 中采样一个候选状态 $x'$；第二步，计算接受概率 $\alpha(x_t, x') = \min\left(1, \frac{f(x') q(x_t|x')}{f(x_t) q(x'|x_t)}\right)$；第三步，以概率 $\alpha$ 接受候选状态并设置 $x_{t+1} = x'$，否则保持 $x_{t+1} = x_t$。重复以上步骤直至链收敛，收集收敛后的样本作为对目标分布的近似采样。

1.3 接受概率的推导

接受概率的设计源于细致平衡条件 $\pi(x) q(x'|x) \alpha(x, x') = \pi(x') q(x|x') \alpha(x', x)$。为实现从 $\pi(x)$ 到 $\pi(x')$ 的转移，令 $\alpha(x, x') = \min\left(1, \frac{\pi(x') q(x|x')}{\pi(x) q(x'|x)}\right)$，则上述等式自然满足。由于 $\pi(x) = f(x)/c$，归一化常数 $c$ 在比值中相互抵消，因此算法仅需 $f(x)$ 即可运行。这是Metropolis-Hastings算法最重要的优势——对于复杂的概率模型，即便其边际似然（证据）不可计算，后验采样仍可高效进行。

2. 算法变体与特例

2.1 Metropolis算法

当提议分布为对称分布（即 $q(x'|x) = q(x|x')$）时，接受概率简化为 $\alpha(x, x') = \min\left(1, \frac{f(x')}{f(x)}\right)$。这是Metropolis原始论文中的形式，也是最常用的版本之一。典型的对称提议分布包括以当前状态为中心的正态分布 $N(x, \sigma^2)$ 和均匀分布 $U(x-\delta, x+\delta)$。对称提议分布的步长参数（如正态分布的标准差 $\sigma$）直接影响采样效率：步长过小导致链在状态空间中缓慢游走，自相关过高；步长过大则大部分候选被拒绝，链停滞不前。实践中通常将接受率调整至20\%—50\%之间作为步长调节的经验准则。

2.2 随机游走Metropolis-Hastings

随机游走Metropolis-Hastings（Random Walk MH）是最广泛的实现形式，其中提议分布满足 $q(x'|x) = g(x' - x)$，即转移仅依赖于当前位置与候选位置的差值。这种形式的提议分布便于实现且无需考虑目标分布的梯度信息，适用于低维至中等维度的问题。然而在高维空间中，随机游走采样的效率会急剧下降——为使接受率保持在合理水平，步长必须随维度增加而缩小，导致链的混合速度极慢，这一现象称为"维度诅咒"。

2.3 独立Metropolis-Hastings

独立Metropolis-Hastings（Independence MH）采用与当前状态无关的提议分布 $q(x'|x) = q(x')$。此时接受概率变为 $\alpha = \min\left(1, \frac{f(x') q(x)}{f(x) q(x')}\right)$。当提议分布 $q$ 与目标分布 $\pi$ 足够接近时，独立MH的接受率可保持较高水平且链的混合速度极快。但若 $q$ 与 $\pi$ 偏离较大，接受概率可能极低，导致链长期停滞。因此独立MH的性能高度依赖于提议分布的质量，实际中常结合自适应方法或重要性重采样技术使用。

3. 收敛性与诊断

3.1 理论收敛条件

Metropolis-Hastings算法生成的马尔可夫链在满足以下条件时保证收敛至目标分布：(a) $\pi$-不可约性——链从任意状态出发均能以正概率到达 $\pi$ 支撑集中的任何区域；(b) 非周期性——链的返回时间不具有确定性周期；(c) Harris遍历性——对任意初始分布，链的经验分布依全变差范数收敛于 $\pi$。对于定义在紧集上的连续分布，若提议分布具有正密度且目标分布处处有限，上述条件通常自然满足。对于无界状态空间，需额外验证链的几何遍历性（Geometric Ergodicity），这依赖于目标分布的尾部行为。

3.2 收敛诊断方法

实际应用中判断链是否已收敛至平稳分布是MCMC的核心挑战。常用诊断方法包括：迹图（Trace Plot）检查——观察采样序列是否存在明显趋势或周期性，若链已在平稳分布中游走，迹图应表现为无规律的波动；自相关函数（ACF）分析——计算链在不同滞后阶数的自相关系数，有效样本量（Effective Sample Size, ESS）可通过 $N_{\text{eff}} = N / (1 + 2\sum_{k=1}^\infty \rho_k)$ 估计，其中 $\rho_k$ 为滞后 $k$ 的自相关系数；盖尔曼-鲁宾诊断（Gelman-Rubin Diagnostic）——从多个不同初始状态并行运行多条链，计算链间方差与链内方差的比值 $\hat{R}$，当 $\hat{R} < 1.1$ 时通常认为链已收敛。需强调的是，所有诊断方法都只能提供收敛的必要条件而非充分条件——"未发现未收敛"不等于"已收敛"。

4. 应用领域

4.1 贝叶斯统计推断

Metropolis-Hastings算法是贝叶斯计算的核心引擎。在贝叶斯分析中，后验分布 $p(\theta|D) \propto p(D|\theta) p(\theta)$ 往往涉及高维积分且归一化常数不可解析计算。通过MH算法从后验中采样，可以近似计算后验均值、可信区间、边际似然等关键量。在复杂分层模型（Hierarchical Model）和广义线性混合效应模型（GLMM）中，MH算法及其变体（如Gibbs采样、Hamiltonian Monte Carlo）是实际标准的计算工具。

4.2 统计物理学

Metropolis算法的原始动机来源于统计物理中的伊辛模型（Ising Model）模拟——通过状态空间中粒子的随机翻转及其能量变化计算接受概率，从而在给定温度下生成符合玻尔兹曼分布的构型。这一方法被称为Metropolis Monte Carlo模拟，至今仍是计算物理中研究相变、临界现象和晶格规范理论的基础方法。在凝聚态物理中，Metropolis算法被用于模拟材料的微观结构演变，如晶粒生长、位错运动和磁性材料的磁畴演化。

4.3 机器学习与人工智能

在机器学习领域，Metropolis-Hastings算法被广泛应用于概率图模型的推理与学习。例如，在受限玻尔兹曼机（RBM）和深度信念网络（DBN）的训练中，对比散度（Contrastive Divergence）算法本质上是对MH采样过程的近似。在贝叶斯深度学习（Bayesian Deep Learning）中，MH方法被用于对神经网络的权重后验分布进行采样，从而提供模型不确定性估计。此外，在计算化学与计算生物学中，MH算法是蛋白质折叠模拟、系统发育推断和药物分子构象搜索的标准工具。

5. 局限性与改进方向

尽管Metropolis-Hastings算法具有通用性强和实现简便的优点，但在高维空间中面临严重的效率瓶颈。随着维度增加，后验分布的高概率区域在状态空间中占比呈指数级缩小，随机游走采样的有效步长被迫缩小，导致链的混合速度急剧下降。为缓解这一问题，研究者发展了一系列改进方法：哈密顿蒙特卡洛（Hamiltonian Monte Carlo, HMC）利用目标分布的梯度信息指导采样方向，在高维空间中保持较高的接受率；自适应Metropolis（Adaptive Metropolis, AM）根据链的历史协方差动态调整提议分布的尺度；并行回火（Parallel Tempering）通过多条不同温度链的交换机制帮助穿越多峰分布中的能垒。这些方法在不同程度上扩展了MH算法在高维和复杂结构问题中的适用边界。

6. 历史与意义

Metropolis-Hastings算法自诞生以来被誉为"20世纪最具影响力的算法之一"，它从根本上改变了统计计算的面貌。在贝叶斯统计因后验计算困难而长期处于理论讨论阶段的情况下，MCMC方法（以MH算法为核心）的出现使贝叶斯分析得以在实证研究中大规模应用，促成了贝叶斯统计学在20世纪90年代的复兴。2000年，《计算物理学中的蒙特卡洛方法》被美国物理学会评为20世纪计算物理学的十大进展之一。今天，Metropolis-Hastings算法及其衍生方法已渗透到从天体物理到金融工程、从药物发现到气候建模的几乎所有科学计算领域。