马尔可夫链蒙特卡洛（MCMC）中的随机游走Metropolis算法原理与采样过程
字数 2345 2025-12-02 07:15:46

马尔可夫链蒙特卡洛（MCMC）中的随机游走Metropolis算法原理与采样过程

题目描述

随机游走Metropolis算法是MCMC方法的一种，用于从复杂概率分布（如高维、非标准形式）中抽取样本。其核心思想是构建一个马尔可夫链，使得该链的平稳分布等于目标分布。本题目要求理解该算法的接受-拒绝机制、随机游走策略及其收敛性。

步骤1：理解MCMC的基本目标

  1. 问题背景：若目标分布 \(P(x)\) 难以直接采样（如未归一化或形式复杂），MCMC通过构造一条马尔可夫链，使其长期运行后的样本近似服从 \(P(x)\)。
  2. 平稳分布：马尔可夫链需满足细致平衡条件（Detailed Balance）：

\[ P(x) T(x \to x') = P(x') T(x' \to x) \]

其中 \(T(x \to x')\) 是从状态 \(x\) 转移到 \(x'\) 的概率。

步骤2：随机游走Metropolis算法的核心设计

  1. 提议分布（Proposal Distribution）：

    • 选择一个对称的提议分布 \(Q(x' \mid x)\)，例如高斯分布 \(Q(x' \mid x) = \mathcal{N}(x, \sigma^2)\)。
    • 对称性要求：\(Q(x' \mid x) = Q(x \mid x')\)（如随机游走步骤 \(x' = x + \epsilon, \epsilon \sim \mathcal{N}(0, \sigma^2)\)）。

  2. 接受概率（Acceptance Probability）：

    • 定义接受概率 \(A(x' \mid x) = \min\left(1, \frac{P(x')}{P(x)}\right)\)。
    • 若 \(P(x') \geq P(x)\)，总接受新状态；否则以概率 \(\frac{P(x')}{P(x)}\) 接受。

  3. 转移概率：

    • 实际转移概率为 \(T(x \to x') = Q(x' \mid x) A(x' \mid x)\)。

步骤3：算法流程的详细步骤

  1. 初始化：选择初始状态 \(x_0\)，设定迭代次数 \(N\)。
  2. 迭代过程（对于 \(t = 0, 1, \dots, N-1\)）：
    • 生成候选样本：从提议分布 \(Q(x' \mid x_t)\) 中抽取 \(x'\)。
    • 计算接受率：

\[ \alpha = \frac{P(x')}{P(x_t)} \quad \text{（若 $ P(x) $ 未归一化，直接用其值比即可）} \]

  • 决定是否接受：
    • 从均匀分布 \(U(0,1)\) 中采样 \(u\)。
    • 若 \(u \leq \alpha\)，接受 \(x_{t+1} = x'\)；否则 \(x_{t+1} = x_t\)。
  1. 输出：丢弃前 \(B\) 个样本（预烧期），保留后续样本作为目标分布的近似。

步骤4：为什么满足平稳分布？

  1. 细致平衡验证：
    • 需证明 \(P(x) T(x \to x') = P(x') T(x' \to x)\)。
    • 若 \(P(x') \geq P(x)\)，则 \(A(x' \mid x) = 1\)，\(A(x \mid x') = \frac{P(x)}{P(x')}\)。

\[ P(x) T(x \to x') = P(x) Q(x' \mid x) \cdot 1 = P(x) Q(x' \mid x) \]

\[ P(x') T(x' \to x) = P(x') Q(x \mid x') \cdot \frac{P(x)}{P(x')} = P(x) Q(x \mid x') \]

  • 由对称性 \(Q(x' \mid x) = Q(x \mid x')\)，等式成立。
  • 同理可证 \(P(x') < P(x)\) 的情况。

步骤5：关键参数与注意事项

  1. 提议分布的方差 \(\sigma^2\)：

    • \(\sigma^2\) 过小：接受率高但探索效率低（样本相关性高）。
    • \(\sigma^2\) 过大：接受率低，链容易停滞。
    • 一般调整接受率在 20%~40% 之间（经验最优约 23% 对于高维高斯分布）。

  2. 预烧期（Burn-in）：

    • 初始阶段样本可能不服从目标分布，需丢弃前 \(B\) 次迭代的样本。

  3. 收敛诊断：

    • 可通过多条链的方差分析、自相关图等方法判断链是否收敛。

步骤6：示例说明（从一维分布采样）

假设目标分布 \(P(x) \propto e^{-x^2/2} + 0.5e^{-(x-3)^2/2}\)（双峰分布），提议分布为 \(\mathcal{N}(x, 1)\)。

  1. 初始化 \(x_0 = 0\)。
  2. 迭代：
    • 生成 \(x' = x_t + \epsilon, \epsilon \sim \mathcal{N}(0,1)\)。
    • 计算 \(\alpha = \frac{P(x')}{P(x_t)}\)（由于未归一化，直接计算比值）。
    • 以概率 \(\min(1, \alpha)\) 接受 \(x'\)。
  3. 绘制样本直方图，可见其近似目标分布的双峰形态。

总结

随机游走Metropolis算法通过对称提议分布与接受-拒绝机制，将马尔可夫链的平稳分布逼近目标分布。其实现简单，但需谨慎选择参数以确保收敛效率。该方法是MCMC采样器的基石，后续算法（如Metropolis-Hastings、HMC）均在此基础上改进。

马尔可夫链蒙特卡洛（MCMC）中的随机游走Metropolis算法原理与采样过程 题目描述 随机游走Metropolis算法是MCMC方法的一种，用于从复杂概率分布（如高维、非标准形式）中抽取样本。其核心思想是构建一个马尔可夫链，使得该链的平稳分布等于目标分布。本题目要求理解该算法的接受-拒绝机制、随机游走策略及其收敛性。 步骤1：理解MCMC的基本目标 问题背景 ：若目标分布 \( P(x) \) 难以直接采样（如未归一化或形式复杂），MCMC通过构造一条马尔可夫链，使其长期运行后的样本近似服从 \( P(x) \)。 平稳分布 ：马尔可夫链需满足细致平衡条件（Detailed Balance）： \[ P(x) T(x \to x') = P(x') T(x' \to x) \] 其中 \( T(x \to x') \) 是从状态 \( x \) 转移到 \( x' \) 的概率。 步骤2：随机游走Metropolis算法的核心设计 提议分布（Proposal Distribution） ： 选择一个对称的提议分布 \( Q(x' \mid x) \)，例如高斯分布 \( Q(x' \mid x) = \mathcal{N}(x, \sigma^2) \)。 对称性要求：\( Q(x' \mid x) = Q(x \mid x') \)（如随机游走步骤 \( x' = x + \epsilon, \epsilon \sim \mathcal{N}(0, \sigma^2) \)）。 接受概率（Acceptance Probability） ： 定义接受概率 \( A(x' \mid x) = \min\left(1, \frac{P(x')}{P(x)}\right) \)。 若 \( P(x') \geq P(x) \)，总接受新状态；否则以概率 \( \frac{P(x')}{P(x)} \) 接受。 转移概率 ： 实际转移概率为 \( T(x \to x') = Q(x' \mid x) A(x' \mid x) \)。 步骤3：算法流程的详细步骤 初始化 ：选择初始状态 \( x_ 0 \)，设定迭代次数 \( N \)。 迭代过程 （对于 \( t = 0, 1, \dots, N-1 \)）： 生成候选样本 ：从提议分布 \( Q(x' \mid x_ t) \) 中抽取 \( x' \)。 计算接受率 ： \[ \alpha = \frac{P(x')}{P(x_ t)} \quad \text{（若 \( P(x) \) 未归一化，直接用其值比即可）} \] 决定是否接受 ： 从均匀分布 \( U(0,1) \) 中采样 \( u \)。 若 \( u \leq \alpha \)，接受 \( x_ {t+1} = x' \)；否则 \( x_ {t+1} = x_ t \)。 输出 ：丢弃前 \( B \) 个样本（预烧期），保留后续样本作为目标分布的近似。 步骤4：为什么满足平稳分布？ 细致平衡验证 ： 需证明 \( P(x) T(x \to x') = P(x') T(x' \to x) \)。 若 \( P(x') \geq P(x) \)，则 \( A(x' \mid x) = 1 \)，\( A(x \mid x') = \frac{P(x)}{P(x')} \)。 \[ P(x) T(x \to x') = P(x) Q(x' \mid x) \cdot 1 = P(x) Q(x' \mid x) \] \[ P(x') T(x' \to x) = P(x') Q(x \mid x') \cdot \frac{P(x)}{P(x')} = P(x) Q(x \mid x') \] 由对称性 \( Q(x' \mid x) = Q(x \mid x') \)，等式成立。 同理可证 \( P(x') < P(x) \) 的情况。 步骤5：关键参数与注意事项 提议分布的方差 \( \sigma^2 \) ： \( \sigma^2 \) 过小：接受率高但探索效率低（样本相关性高）。 \( \sigma^2 \) 过大：接受率低，链容易停滞。 一般调整接受率在 20%~40% 之间（经验最优约 23% 对于高维高斯分布）。 预烧期（Burn-in） ： 初始阶段样本可能不服从目标分布，需丢弃前 \( B \) 次迭代的样本。 收敛诊断 ： 可通过多条链的方差分析、自相关图等方法判断链是否收敛。 步骤6：示例说明（从一维分布采样） 假设目标分布 \( P(x) \propto e^{-x^2/2} + 0.5e^{-(x-3)^2/2} \)（双峰分布），提议分布为 \( \mathcal{N}(x, 1) \)。 初始化 \( x_ 0 = 0 \)。 迭代： 生成 \( x' = x_ t + \epsilon, \epsilon \sim \mathcal{N}(0,1) \)。 计算 \( \alpha = \frac{P(x')}{P(x_ t)} \)（由于未归一化，直接计算比值）。 以概率 \( \min(1, \alpha) \) 接受 \( x' \)。 绘制样本直方图，可见其近似目标分布的双峰形态。 总结 随机游走Metropolis算法通过对称提议分布与接受-拒绝机制，将马尔可夫链的平稳分布逼近目标分布。其实现简单，但需谨慎选择参数以确保收敛效率。该方法是MCMC采样器的基石，后续算法（如Metropolis-Hastings、HMC）均在此基础上改进。