深入浅出马尔可夫链蒙特卡罗（Markov Chain Monte Carlo, MCMC）算法

0. 引言

Markov Chain Monte Carlo（MCMC）是一类用于从复杂分布中采样的强大算法，特别是在难以直接计算分布的情况下。它广泛应用于统计学、机器学习、物理学等领域，尤其是在贝叶斯推理和概率模型中。本文将深入解析 MCMC 的基本原理、核心算法（如 Metropolis-Hastings 和 Gibbs 采样），并讨论其在实际应用中的优势与局限，同时介绍一些先进的变种如 Hamiltonian Monte Carlo（HMC）。

1. 背景知识

在贝叶斯推断和许多概率模型中，目标是从某个复杂的后验分布 $p(\theta |x)$ 中获取样本。然而，在大多数情况下，这种分布很难直接采样，因为其可能涉及到难以求解的归一化常数。

MCMC 提供了一种间接方法，通过构建一个马尔可夫链，使其逐步收敛到目标分布。然后，通过在平衡态（或稳态）下从马尔可夫链中提取样本，我们可以得到接近于目标分布的样本。

2. 马尔可夫链的基础

马尔可夫性质：马尔可夫链是一种具有“无记忆”性质的随机过程，当前状态的下一个状态只依赖于当前状态，而不依赖于历史状态。数学上，设 $X_1,X_2,\dots$ 是马尔可夫链中的状态序列，满足：
$$P(X_{n+1}|X_1,X_2,\dots ,X_n)=P(X_{n+1}|X_n)$$

转移矩阵：马尔可夫链通过转移概率矩阵（或转移核）定义，设 $P_{ij}$ 表示从状态 $i$ 转移到状态 $j$ 的概率，则有：
$$P_{ij}=P(X_{n+1}=j|X_n=i)$$

细致平衡条件：在实际的 MCMC 应用中，重要的是确保马尔可夫链的平稳分布满足“细致平衡条件”（detailed balance）。即：
$$\pi (i)P_{ij}=\pi (j)P_{ji}$$
这一条件保证了链的平稳分布为目标分布。

稳态分布：经过足够多的迭代，马尔可夫链会收敛到一个稳定的分布 $\pi$，该分布满足：
$$\pi =\pi P$$
在 MCMC 中，我们构建的马尔可夫链会收敛到我们感兴趣的目标分布 $p(\theta |x)$。

举个栗子：
想象一下，你养了一只猫。这只猫在家里随机地游荡，它可能在卧室睡觉、在客厅玩耍、在厨房找吃的，或者在卫生间喝水。这只猫的行动路径就有点像一个马尔可夫链。

• 状态空间： 猫可能存在的各个位置就是它的“状态空间”。在这个例子中，状态空间包括：卧室、客厅、餐厅、厨房和卫生间。
• 转移概率： 猫从一个房间转移到另一个房间的概率就是“转移概率”。比如，猫在卧室里，它可能更喜欢去客厅玩耍，所以从卧室到客厅的转移概率就比较大；而它不太可能直接从卧室跳到天花板上，所以这个转移概率就很小。
• 马尔可夫性质： 猫决定去下一个房间的时候，只考虑它当前所在的房间，而不关心它之前都去过哪些房间。比如，如果猫现在在客厅，它决定去下一个房间的时候，只考虑从客厅能去哪些房间，以及去每个房间的概率，而不会考虑它之前是不是刚从卧室过来。

3. Monte Carlo 方法

Monte Carlo 方法通过随机采样来估计某些不可解析的期望值。设我们需要估计某个分布 $p(x)$ 下某个函数 $f(x)$ 的期望：
$${\mathbb{E}}_{p(x)}[f(x)]=\int f(x)p(x)dx$$

通过从分布 $p(x)$ 中采样 $x_1,x_2,\dots ,x_n$，我们可以用样本均值来近似这个期望：
$${\mathbb{E}}_{p(x)}[f(x)]\approx \frac{1}{n}\sum _{i=1}^{n}f(x_i)$$

但正如前述，对于复杂分布，直接采样 $p(x)$ 往往不可行。这时 MCMC 技术登场，通过马尔可夫链来间接实现从 $p(x)$ 中采样。

举个栗子：
想象你有一个不规则的图形，比如一个蝙蝠侠形状的图形，你想知道它的面积。这时可以用蒙特卡洛方法，首先，在蝙蝠侠图形外面画一个大的长方形，然后向这个长方形里随机撒豆子，最后通过计算落在蝙蝠侠图形中的豆子比例来估算图形的面积。

4. MCMC 核心算法

4.1 Metropolis-Hastings 算法

Metropolis-Hastings（MH）算法是 MCMC 中常用的采样方法。它通过构造一个易于采样的提议分布 $q({\theta }^{\prime }|\theta )$，并通过接受或拒绝的方式生成目标分布的样本。

步骤：

1. 初始化 ${\theta }_0$
2. 对每一轮迭代：
   • 根据提议分布 $q({\theta }^{\prime }|{\theta }_t)$ 生成候选样本 ${\theta }^{\prime }$
   • 计算接受概率：
     $$\alpha =\min \left(1,\frac{p({\theta }^{\prime }|x)q({\theta }_t|{\theta }^{\prime })}{p({\theta }_t|x)q({\theta }^{\prime }|{\theta }_t)}\right)$$
   • 以概率 $\alpha$ 接受 ${\theta }^{\prime }$，否则保持当前状态 ${\theta }_t$

Metropolis-Hastings 的灵活性在于可以使用不同的提议分布来优化采样效率。对于实际问题，选择适当的提议分布 $q({\theta }^{\prime }|\theta )$ 是关键，过于分散或集中的分布都可能影响采样效率。

举个栗子（以抽球为例）：

• 步骤1：初始化

首先，你闭上眼睛，随机从箱子里摸出一个球，记住这个球的颜色，然后把它放回去。这个球的颜色就是你的起始点，也就是马尔可夫链的初始状态。

• 步骤2：提议生成

接着，你再次闭上眼睛，但这次你稍微改变了一下摸球的方式。你并不是完全随机地摸，而是基于你上次摸到的球的颜色来“提议”一个新的颜色。比如，如果你上次摸到的是红色球，那么你这次可能会倾向于摸一个和红色相近的颜色，比如橙色或紫色（当然，这只是一个比喻，实际中提议分布的选择会更复杂）。这个“提议”的颜色就是你的候选新状态。

• 步骤3：接受-拒绝策略

现在，你需要决定是否接受这个新的颜色作为你下一次摸球的结果。你计算了一个接受概率，这个概率取决于新颜色和旧颜色在箱子中真实出现概率的相对大小，以及你提议分布的一些特性。如果接受概率很高，你就接受这个新颜色；如果很低，你就拒绝它，并保留原来的颜色。

• 步骤4：重复迭代

你不断重复上述步骤，每次都根据当前的颜色来“提议”一个新的颜色，并根据接受概率来决定是否接受它。随着时间的推移，你会发现你摸到的球的颜色分布越来越接近箱子中真实的颜色分布。

4.2 Gibbs 采样

Gibbs 采样是一种特殊的 MCMC 方法，适用于多维随机变量的情况。与 MH 不同，Gibbs 采样通过逐步更新每一个维度的值来生成样本，每次更新都从条件分布中进行采样。

步骤：

1. 初始化 ${\theta }_0=({\theta }_1^{(0)},{\theta }_2^{(0)},\dots ,{\theta }_d^{(0)})$
2. 对每一轮迭代：
   • 对每个维度 $i$：
     $${\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)})$$
3. 重复迭代，直到样本收敛。

Gibbs 采样在模型中条件分布易于采样的情况下表现出色，常用于贝叶斯网络或隐马尔可夫模型等。

4.3 Hamiltonian Monte Carlo（HMC）

Hamiltonian Monte Carlo 是一种高级 MCMC 方法，通过引入物理学中的哈密顿动力学，将样本点视为在势能场中运动的粒子。HMC 可以高效探索高维参数空间，避免传统 MCMC 中的低效率。

核心思想：

• 在传统的 Metropolis-Hastings 算法中，采样仅依赖于当前的状态，而 HMC 则利用目标函数的梯度信息来辅助样本生成。
• HMC 不仅能够加快高维参数的探索，还可以有效避免“随机漫步”行为，使得采样更高效。

HMC 被广泛应用于深度贝叶斯学习中，特别是在大规模复杂模型中表现优异。

5. MCMC 的应用

举个栗子：
现在，我们把蒙特卡洛方法和马尔可夫链结合起来，就得到了MCMC方法。假设我们想知道一个复杂分布（比如一个蝙蝠侠形状的区域里豆子的分布）的某些性质（比如平均高度），但是直接计算太难了。我们可以用MCMC方法来做这件事。

• 首先，我们构造一个马尔可夫链，使得这个链的平稳分布（就是链运行很长时间后每个状态出现的概率分布）恰好是我们想要研究的那个复杂分布。这通常需要我们精心设计马尔可夫链的转移概率。

• 然后，我们从马尔可夫链的某个初始状态开始，按照转移概率随机地移动，生成一系列的状态（就像猫一样）。在刚开始的时候，这些状态可能并不符合我们想要的分布，但是随着链的运行，这些状态会越来越接近我们想要的分布。

• 最后，当我们认为链已经运行了足够长的时间，达到了平稳分布时，我们就可以用这些状态来估算我们想要知道的性质了。比如，我们可以用这些状态来估算蝙蝠侠形状区域里豆子的平均高度。

MCMC 被广泛应用于各种复杂模型中，特别是在贝叶斯推理中。以下是几个典型的应用领域：

• 贝叶斯推断：在贝叶斯推理中，通常需要从后验分布 $p(\theta |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 在大规模数据中的表现，使其在更广泛的领域中发挥作用。