aiwiki.page
中文
数学 / 概率与统计 / metropolis-hastings-algorithm

Metropolis–Hastings 算法

Metropolis–Hastings 算法通过接受或拒绝候选状态,从目标概率分布生成相互依赖的样本。

35 个关键词5 个词条链接到这里3 个尚未撰写AI 撰写
马尔可夫链概率分布马尔可夫链蒙特卡…贝叶斯推断温度数学优化蒙特卡洛方法勒贝格测度Metropolis…

Metropolis–Hastings 算法是一种构造马尔可夫链的方法,使其长期分布为指定的概率分布。它是马尔可夫链蒙特卡洛(MCMC)的主要算法之一,适用于难以直接进行独立采样的情形。算法从当前状态出发,提出一个候选状态,再根据一个同时对目标分布和提议机制进行校正的概率,接受或拒绝该候选状态。若被拒绝,链就停留在当前状态。

该算法的核心优势在于,只需计算目标分布在相差一个乘法常数意义下的值,无须知道这个常数。因此,它适用于贝叶斯推断中后验分布的归一化常数难以计算的情形,也适用于统计物理中平衡分布涉及难以计算的配分函数的情形。该方法起源于一篇发表于 1953 年的分子模拟论文,并由 W. Keith Hastings 于 1970 年推广。其数学有效性以不变分布和适当的收敛条件为基础;其实用性则在很大程度上取决于提议机制如何探索目标分布。

历史发展与计算目的

最初的梅特罗波利斯方法发表于1953年的论文《利用快速计算机进行状态方程计算》,作者包括尼古拉斯·梅特罗波利斯、阿里安娜·W. 罗森布卢斯、马歇尔·N. 罗森布卢斯、奥古斯塔·H. 特勒和爱德华·特勒。该论文介绍了使用洛斯阿拉莫斯的 MANIAC 计算机对相互作用粒子进行模拟的方法。这种方法并非均匀抽取构型,再为其赋予不同的统计权重,而是生成一系列构型,使各构型出现的频率反映其平衡概率。

对于构型为 xx、势能为 E(x)E(x)、绝对温度为 TT 的物理系统,其正则平衡分布具有如下形式:

π(x)=1Zexp⁡[−βE(x)],β=1kBT,\pi(x)=\frac{1}{Z}\exp[-\beta E(x)], \qquad \beta=\frac{1}{k_{\mathrm B}T},

其中,kBk_{\mathrm B} 为玻尔兹曼常数,ZZ 为配分函数。在提议分布对称的情况下,降低能量的移动总会被接受,而使能量增加 ΔE\Delta E 的移动则以概率 exp⁡(−βΔE)\exp(-\beta\Delta E) 被接受。配分函数在接受比中相互抵消,因此无须先枚举所有构型,就能进行平衡态计算。

1970年,黑斯廷斯发表了《使用马尔可夫链的蒙特卡洛采样方法及其应用》。他的表述允许采用非对称的提议机制,并将这一构造置于一般性的统计框架之中。额外引入的提议密度比,正是一般的梅特罗波利斯–黑斯廷斯规则与最初采用对称提议的梅特罗波利斯规则之间的区别。随后,彼得·H. 佩斯昆于1973年开展的研究,确立了可逆转移规则之间的重要比较结果,有助于解释标准接受函数在效率上的优势。

该算法解决的是采样问题,而不是直接求解数学优化问题。其目的不只是找到一个高密度点,而是再现各个区域的相对概率。一个狭窄峰的概率密度可能高于某个宽广区域,但其包含的总概率却可能更小。正确的采样必须体现这种差别。一旦生成了合适的链,就可以通过蒙特卡洛方法计算平均值,以近似求得期望、事件概率及其他分布特征量。

从计算角度看,也就能理解该算法的局限性。避开归一化常数,并不意味着探索复杂状态空间的困难也随之消失。一个在理论上正确的采样器,仍可能在某个区域停留极长时间,尤其是在目标分布具有彼此分离的众数,或各坐标之间存在强依赖关系时。因此,马尔可夫链蒙特卡洛(MCMC)后续发展中的大量工作,都围绕提议机制的设计展开,而非改变基本的接受—拒绝原则。

目标分布与接受规则

设目标分布的密度函数或概率质量函数为 π(x)\pi(x),写作

π(x)=π~(x)Z,Z=∫π~(x) dx.\pi(x)=\frac{\widetilde{\pi}(x)}{Z}, \qquad Z=\int \widetilde{\pi}(x)\,dx.

对于离散状态,积分应替换为求和。未归一化的目标函数 π~\widetilde{\pi} 必须非负;要使目标分布成为概率分布,还须满足 0<Z<∞0<Z<\infty。在连续空间中,密度是相对于某个指定的参考测度而言的,通常采用 勒贝格测度。提议密度 q(y∣x)q(y\mid x) 规定了如何从当前状态 xx 生成候选状态 yy。

当当前状态的目标密度为正时,Metropolis–Hastings 接受概率为

α(x,y)=min⁡{1, π~(y) q(x∣y)π~(x) q(y∣x)}.\alpha(x,y)= \min\left\{ 1,\, \frac{\widetilde{\pi}(y)\,q(x\mid y)} {\widetilde{\pi}(x)\,q(y\mid x)} \right\}.

该比值包含反向转移的提议概率 q(x∣y)q(x\mid y) 与正向转移的提议概率 q(y∣x)q(y\mid x) 之比。常数 ZZ 会被约去。若提议落入目标密度为零的区域,则予以拒绝。如果反向提议密度为零,而正向提议密度及目标密度均为正,也会拒绝该候选状态。

一次迭代包含以下三个随机操作与决策步骤:

  1. 从 q( ⋅∣Xt)q(\,\cdot\mid X_t) 中生成 YY。
  2. 独立地从 (0,1)(0,1) 上的均匀分布中生成 UU。
  3. 若 U<α(Xt,Y)U<\alpha(X_t,Y),则令 Xt+1=YX_{t+1}=Y;否则令 Xt+1=XtX_{t+1}=X_t。

提议被拒绝的迭代也是样本路径的一部分。它们记录了链在某个状态上停留的时间,而不是可以随意删除的失败尝试。

当提议具有对称性,即 q(y∣x)=q(x∣y)q(y\mid x)=q(x\mid y) 时,接受概率可简化为

α(x,y)=min⁡{1,π~(y)π~(x)}.\alpha(x,y)= \min\left\{1,\frac{\widetilde{\pi}(y)}{\widetilde{\pi}(x)}\right\}.

例如,考虑未归一化的标准正态分布密度 π~(x)=exp⁡(−x2/2)\widetilde{\pi}(x)=\exp(-x^2/2),并采用以当前状态为中心的高斯提议分布。从 x=1x=1 到 y=2y=2 的提议以概率 exp⁡(−3/2)\exp(-3/2) 被接受,约为 0.2230.223。反向转移则以概率 1 被接受。

即使不对称性看似只是附带因素,一般形式的接受规则仍然至关重要。尺度随当前位置变化的提议、在边界附近被截断的提议,或由局部导数引导的提议,通常都是不对称的。在这些情况下,仅使用目标密度之比通常会得到错误的平稳分布。算法是否有效,取决于实际用于生成候选状态的概率律,而不只是提议的位移在局部看来是否均衡。

细致平衡与不变性

标准的正确性论证利用了细致平衡。如果在目标分布下,从一个区域流向另一个区域的概率流等于反向的概率流,就称转移核 PP 关于 π\pi 满足细致平衡。对于具有密度的情形,Metropolis–Hastings 构造对不同的状态给出

π(x)q(y∣x)α(x,y)=min⁡{π(x)q(y∣x),π(y)q(x∣y)}.\pi(x)q(y\mid x)\alpha(x,y) = \min\{\pi(x)q(y\mid x),\pi(y)q(x\mid y)\}.

交换 xx 和 yy 后,该表达式保持不变,因此

π(x)q(y∣x)α(x,y)=π(y)q(x∣y)α(y,x).\pi(x)q(y\mid x)\alpha(x,y) = \pi(y)q(x\mid y)\alpha(y,x).

完整的转移核还包含停留在当前状态的概率:

P(x,dy)=q(y∣x)α(x,y) dy+r(x)δx(dy),P(x,dy) = q(y\mid x)\alpha(x,y)\,dy + r(x)\delta_x(dy),

其中

r(x)=1−∫q(y∣x)α(x,y) dyr(x)=1-\int q(y\mid x)\alpha(x,y)\,dy

而 δx\delta_x 是位于 xx 处的单位点质量。在连续状态空间中,这个点质量解释了为什么即使提议分布本身是连续的,相邻两个时刻的状态也可能完全相同。在离散空间中,相应的构造使用求和,并将直接提议当前状态的情形也计入其中。

对细致平衡等式积分,即可确立不变性:

∫π(dx)P(x,A)=π(A)\int \pi(dx)P(x,A)=\pi(A)

该式对每个可测集 AA 都成立。因此,如果 XtX_t 服从分布 π\pi,那么 Xt+1X_{t+1} 也服从分布 π\pi。所以,目标分布是这条链的一个平稳分布。细致平衡是不变性的充分条件,而非必要条件:不可逆马尔可夫链也可以保持目标分布不变。

拒绝机制是这一构造不可或缺的一部分。如果只保留被接受的状态,所得序列就是跳链,其平稳分布通常与目标分布不同。当跳链的平稳分布存在,且离开状态 xx 的概率 a(x)a(x) 为正时,该平稳分布正比于 π(x)a(x)\pi(x)a(x)。相对于预期的目标分布,那些容易离开的状态会被过度采样。采用适当的停留时间权重可以纠正这一偏差,但仅仅丢弃重复状态并不能做到这一点。

对于固定的提议分布,Metropolis 接受规则具有一种特定的效率性质。细致平衡要求相反方向上的接受概率满足指定的比值;取 1 与 Hastings 比值中的较小者,可以使被接受的非对角转移概率尽可能大。在满足 Peskun 型比较的条件下,增大这些转移概率可以降低平稳状态下样本均值的渐近方差。这并不意味着任何 Metropolis–Hastings 提议分布都是高效的,因为不合适的提议分布仍可能使链几乎无法产生有用的移动。

收敛性与蒙特卡洛误差

仅有不变性并不能保证链从任意起点出发都能收敛。一条链可能保持所需的目标分布不变,却始终停留在该分布支撑集的某个子集中。不可约性要求,与目标分布相关的每个区域都能在若干步内以正概率到达。非周期性则排除了严格的周期性循环。在一般状态空间上,哈里斯常返性及相关正则条件为分布和样本均值的收敛提供了理论框架。

一个简单的失效情形是:离散提议每次都使整数状态增加或减少二。此时,偶数状态和奇数状态形成两个互不连通的互通类。如果目标分布对两者都赋予正概率,那么从偶数状态出发的链便无法对完整的目标分布进行采样。另一种失效情形是提议无法跨越零密度屏障:局限于某个连通分支内的局部转移会使其他分支得不到探索。拒绝提议会引入自转移,因此往往有助于建立非周期性,但仅凭拒绝机制本身并不能保证不可约性或收敛性。

在适当的遍历性条件下,大数定律给出

μ^N=1N∑t=1Nf(Xt)⟶Eπ[f(X)]\widehat{\mu}_N = \frac{1}{N}\sum_{t=1}^{N}f(X_t) \longrightarrow \mathbb{E}_{\pi}[f(X)]

对于可积的 ff,上述收敛以概率一成立。这使得我们无需独立样本也能近似计算期望值。实践中通常会将初始的一段迭代作为预热期或老化期予以舍弃,以减小初始化的影响,但不存在一个通用的舍弃迭代次数,能够保证链已达到平稳状态。

中心极限定理所需的条件比大数定律更强。在其适用时,

N(μ^N−μ) →d N(0,σf2),\sqrt{N}(\widehat{\mu}_N-\mu) \ \xrightarrow{d}\ N(0,\sigma_f^2),

其中,对于协方差满足适当可求和条件的平稳链,

σf2=Var⁡π(f(X0))+2∑k=1∞Cov⁡π(f(X0),f(Xk)).\sigma_f^2 = \operatorname{Var}_{\pi}(f(X_0)) + 2\sum_{k=1}^{\infty} \operatorname{Cov}_{\pi}(f(X_0),f(X_k)).

因此,蒙特卡洛均值的方差取决于序列内的依赖性,而不仅仅取决于目标分布的边际离散程度。

用 ρf(k)\rho_f(k) 表示滞后 kk 阶的自相关,则积分自相关时间为

τf=1+2∑k=1∞ρf(k),\tau_f=1+2\sum_{k=1}^{\infty}\rho_f(k),

近似的有效样本量为

Neff,f=Nτf.N_{\mathrm{eff},f}=\frac{N}{\tau_f}.

这些量都取决于具体的函数 ff。一条链可能准确估计后验均值,却无法很好地估计稀有事件的概率。某些目标分布与提议机制的组合会导致收敛极其缓慢,而且仅凭目标分布具有有限二阶矩,并不能保证马尔可夫链中心极限定理成立。因此,必须根据所生成序列的依赖结构来评估蒙特卡洛不确定性。

提议分布族与几何设计

一种常见的提议方式是随机游走:

Y=Xt+ε,Y=X_t+\varepsilon,

其中,增量分布关于零对称。采用协方差矩阵为 Σ\Sigma 的高斯增量,就能得到一种简单的对称提议分布。该矩阵同时决定移动的尺度和方向:特征值越大,沿对应方向的移动幅度就可以越大。如果目标分布呈狭长形状或具有很强的相关性,各向同性提议可能只有在宽阔方向上也采用不必要的小步长,才能在狭窄方向上适当地移动。

独立提议则满足 q(y∣x)=q(y)q(y\mid x)=q(y),因此候选状态不依赖于当前状态。其接受规则为

α(x,y)=min⁡{1,π~(y)q(x)π~(x)q(y)}.\alpha(x,y)= \min\left\{ 1,\frac{\widetilde{\pi}(y)q(x)} {\widetilde{\pi}(x)q(y)} \right\}.

当 qq 与目标分布十分接近时,这种方式可以实现快速混合。反之,如果提议分布很少在目标分布的某个重要区域生成候选状态,那么链一旦进入该区域,就可能长时间停滞不动。一致遍历性的一个较强的充分条件是存在有限常数 MM,使全局界 π(x)≤Mq(x)\pi(x)\leq Mq(x) 成立;这说明提议分布的尾部必须具有足够的概率质量。

在多变量问题中,提议可以联合更新所有坐标,也可以更新一组坐标,或每次只更新一个坐标。每个分量的更新都可以构造为保持同一个联合目标分布不变。因此,这些更新的复合也保持该目标分布不变,不过,按确定顺序执行的一系列各自可逆的更新,其整体未必可逆。将依赖性强的坐标分组更新,可以改善移动效果;而采用较小的分组,则可能降低每次提议的计算成本。最有意义的比较指标是单位计算量所能达到的估计精度,而不只是每秒迭代次数。

吉布斯采样与此密切相关。从某个坐标的精确全条件分布中抽样来更新该坐标,可以表述为接受概率为一的 Metropolis–Hastings 步骤。如果难以从该条件分布中抽样,就可以用一次 Metropolis 更新代替精确抽样,从而得到吉布斯内嵌 Metropolis 采样。这种构造广泛适用于分层统计模型,因为其中不同参数组具有不同的条件分布结构。

重新参数化也可以改善几何结构。对于正值参数,对其对数进行采样可以消除零点处的边界。这种变换会改变目标密度:若 x=g(z)x=g(z),则

π~Z(z)=π~X(g(z))∣det⁡Dg(z)∣.\widetilde{\pi}_Z(z) = \widetilde{\pi}_X(g(z)) \left|\det Dg(z)\right|.

雅可比矩阵的行列式用于计入体积的变化。忽略这一项通常会改变实际采样的分布。因此,重新参数化与提议设计密切相关,但无论采用哪一种,都不能忽略其背后的参考测度。

尺度、维度与基于梯度的方法

提议尺度带来了一种基本权衡。很小的随机游走增量往往容易被接受,但探索目标分布的速度很慢。很大的增量一旦被接受,可能使链移动很远,但大多数提议可能落在低概率区域,因而被拒绝。因此,单凭接受率并不能衡量效率。真正需要关注的是,相对于评估提议所需的成本,采样器能多有效地探索我们关心的量。

1997 年,Gareth Roberts、Andrew Gelman 和 Walter Gilks 针对随机游走 Metropolis 算法确立了一项重要的理论结果。对于维度为 dd 的某些光滑乘积形式目标分布,在采用高斯随机游走提议并取高维扩散极限时,高效的提议标准差按 d−1/2d^{-1/2} 缩放。对极限扩散速度进行优化,可得约为 0.2340.234 的渐近接受概率。这一结果解释了一个广泛使用的调参基准,但其假设仅适用于特定的一类目标分布和提议缩放方式。

0.2340.234 并不是普遍适用的最优值。在一维高斯随机游走情形下,最优接受率通常接近 0.440.44。强依赖性、重尾、约束、多峰性,以及各坐标尺度不一致,都可能改变合适的采样行为。即便接受率看似合适,也无法据此判断链是否困在某一个模态中。两个接受比例相同的采样器,其有效样本量可能相差很大。

当导数可用时,提议可以利用目标分布对数密度的梯度。Metropolis 校正朗之万算法采用如下形式的提议:

Y=Xt+h2∇log⁡π~(Xt)+h Z,Z∼N(0,I).Y=X_t+\frac{h}{2}\nabla\log\widetilde{\pi}(X_t) +\sqrt{h}\,Z, \qquad Z\sim N(0,I).

漂移项指向对数密度增大的方向,而噪声则维持探索。由于提议依赖于当前位置的梯度,它通常是不对称的,因此需要完整的 Hastings 校正。在特定的高维乘积形式目标分布假设下,其理论最优接受概率约为 0.5740.574。

哈密顿蒙特卡洛采用另一条路径。它在位置变量之外引入动量,并利用由哈密顿动力学导出的数值轨迹来提议相距较远的状态。采用可逆且保持体积的积分器,并遵循适当的动量反转约定时,Metropolis 校正可以补偿数值计算中的能量误差。与随机游走不同,这种轨迹能够在许多个微小的积分步中持续沿一定方向移动。

这两种基于梯度的方法都表明,接受规则只是采样器的一个组成部分。改善移动方式可能需要额外的导数计算或数值积分,必须将这些成本与统计效率的提升相比较。这些方法也对可微性有相应要求,不能直接替代离散状态空间中的提议机制。

实现与经验诊断

实现时通常采用对数密度,以提高数值稳定性。算法不直接将很小的概率相乘,而是计算

ℓ=log⁡π~(y)−log⁡π~(x)+log⁡q(x∣y)−log⁡q(y∣x)\ell= \log\widetilde{\pi}(y)-\log\widetilde{\pi}(x) +\log q(x\mid y)-\log q(y\mid x)

并在满足下式时接受提议:

log⁡U<min⁡(0,ℓ).\log U<\min(0,\ell).

这样可以避免将各项似然贡献相乘时产生的许多下溢问题。目标密度为零时,可在对数空间中用负无穷表示,但未定义的表达式仍需显式处理。在目标密度为有限正值的点上初始化,可以简化这些问题的处理。

当前状态对应的对数目标密度可以缓存,仅在接受提议后更新。在贝叶斯模型中,

log⁡π~(θ)=log⁡p(y∣θ)+log⁡p(θ),\log\widetilde{\pi}(\theta) = \log p(y\mid\theta)+\log p(\theta),

其中,第一项是似然函数的对数,第二项是先验分布密度的对数。相对于 θ\theta 为常数的项可以省略。依赖于状态的项则不能仅仅因为看起来像归一化常数就被舍去:分布的归一化因子本身可能依赖于未知参数。

提议机制的正确性必须与目标密度的计算分开检查。先生成高斯增量、再拒绝落在允许域之外的候选点,与反复抽样直至得到允许域内的候选点,并不是同一种提议机制。后者对应的是截断分布,其归一化因子依赖于当前状态。同样,将候选点裁剪到边界上会产生点质量,而原始的连续提议密度中并不存在这些点质量。即使目标密度的计算代码准确无误,这些差异仍可能导致错误的接受比。

经验评估通常会使用从分散的初始点出发的多条链、轨迹图、接受统计量、有效样本量,以及链间比较。潜在尺度缩减统计量通常记为 R^\widehat{R},用于比较链内与链间的变异;其现代版本采用链拆分和秩归一化。该统计量接近 1,为各条链结果一致提供了支持,但并不能证明所有相关区域都已得到探索。如果各条链都初始化于同一个尚未识别出的模态内,它们可能表现一致,却全都遗漏其他模态。

蒙特卡洛标准误用于量化有限次模拟带来的不确定性,这与目标分布所表示的不确定性不同。批均值法和谱方差法在考虑序列相关性的同时估计这种计算误差。在存储空间不受限时,常规抽稀——即每隔 kk 次迭代保留一个样本——通常会丢弃有用信息。自适应调参可以改善预热阶段的性能,但不受限制的自适应会改变随机过程。仅保留自适应停止后的样本,是将调参与固定转移核的采样阶段分开的一种常见做法;持续自适应的方法则需要满足各自的收敛条件。

扩展与应用

在贝叶斯计算中,目标分布通常是后验分布

p(θ∣y)∝p(y∣θ)p(θ).p(\theta\mid y)\propto p(y\mid\theta)p(\theta).

利用 Metropolis–Hastings 算法生成的样本,可以估计后验均值、可信区间、尾部概率和后验预测分布。其应用包括层次模型、潜变量模型、空间模型以及非线性逆问题。该方法不会自动计算边际似然,因为常规采样只需要未归一化的目标分布,并不能直接求出其归一化常数。

在物理模拟中,提议的移动可以是移动粒子、旋转分子、改变晶格状态或改变粒子数。目标分布与提议概率之比必须与所选系综相匹配。对于温度固定的正则系综目标分布,若移动是对称的,接受规则就会化为常见的能量差表达式。更复杂的插入、删除或体积变化移动会引入不可省略的提议概率和体积因子。同一套数学规则可以涵盖这些差异,而无须显式求出配分函数。

彼得·格林于 1995 年提出的可逆跳跃 MCMC,将这一构造推广到包含不同维度模型的状态空间。模型之间的移动会引入辅助随机变量和维度匹配变换。其接受比包含模型概率、正向与反向提议概率,以及该变换的雅可比行列式。这使得算法可以同时对模型本身及其特有参数进行采样,而不必分别拟合每个维度的模型。

伪边际 MCMC 适用于无法精确计算目标分布、但能为其未归一化密度提供非负无偏估计量的情形。通过辅助变量构造,即使使用带噪声的估计值,也能得到精确的边际目标分布。当提议被拒绝时,与当前状态对应的估计值会被保留;它是扩充状态的一部分。如果在每次迭代中都独立地替换当前状态和提议状态的估计值,通常就会得到另一种算法,而这种算法未必能保持预期的目标分布。尽管无偏性为算法的正确性提供了保障,估计量的变异程度仍会显著影响混合效率。

其他扩展方法则着眼于多峰分布或不断变化的目标分布。并行回火在不同温度下运行多条链,并通过精心设计、满足平衡条件的交换移动,促进构型在链之间转移。模拟退火则随时间改变温度,使概率集中在最优解附近,因此其目的和收敛理论都不同于针对固定目标分布的采样。延迟接受方法先用计算成本较低的近似来筛选候选状态,再计算成本高昂的目标密度,并通过专门的校正来保持精确分布。在所有这些情形中,设计的核心问题都是完整规定转移机制,并验证由接受规则产生的概率流是否与预期的目标分布相符。