Notes/机器学习/深度学习模型/0-基础知识/3-采样方法.md

title, tags

title	tags
3-采样方法	采样方法 MCMC 统计学 数学基础

采样方法

本笔记面向深度学习与强化学习科研人员，系统讲解采样方法的数学基础、核心算法及与深度学习的联系。

---

1. 蒙特卡洛方法基础

1.1 随机采样与期望估计

定义 1.1（蒙特卡洛估计） 设 X_1, X_2, \ldots, X_N 为从分布 p(x) 中独立采得的样本，则函数 f(X) 的期望值 \mathbb{E}_p[f(X)] 的蒙特卡洛估计为：

\hat{F}_N = \frac{1}{N} \sum_{i=1}^{N} f(X_i)

定理 1.1（蒙特卡洛估计的无偏性） 上述估计量 \hat{F}_N 是 \mathbb{E}_p[f(X)] 的无偏估计，即：

\mathbb{E}\left[\hat{F}_N\right] = \mathbb{E}_p[f(X)]

证明：

\mathbb{E}\left[\hat{F}_N\right] = \mathbb{E}\left[\frac{1}{N} \sum_{i=1}^{N} f(X_i)\right] = \frac{1}{N} \sum_{i=1}^{N} \mathbb{E}[f(X_i)] = \frac{1}{N} \cdot N \cdot \mathbb{E}_p[f(X)] = \mathbb{E}_p[f(X)]

---

1.2 大数定律与收敛性

定理 1.2（弱大数定律） 若 X_1, \ldots, X_N i.i.d.，且 $\mathbb{E}[|f(X_i)|] < \infty$，则对任意 $\epsilon > 0$：

\lim_{N \to \infty} P\left(\left|\hat{F}_N - \mathbb{E}_p[f(X)]\right| > \epsilon\right) = 0

推论： 蒙特卡洛估计量依概率收敛到真实期望值，收敛速度为 $O(1/\sqrt{N})$。具体而言，中心极限定理给出：

\hat{F}_N \approx \mathcal{N}\left(\mathbb{E}_p[f(X)], \frac{\text{Var}_p[f(X)]}{N}\right)

均方误差为：

\mathbb{E}\left[(\hat{F}_N - \mathbb{E}_p[f(X)])^2\right] = \frac{\text{Var}_p[f(X)]}{N}

---

1.3 方差缩减的基本思想

蒙特卡洛方法的核心挑战是方差缩减。设原估计量方差为 $\sigma^2/N$，方差缩减技术旨在构造方差更小的估计量。

控制变量法： 若存在与 f 相关且期望已知的随机变量 $g$，则构造：

\hat{F}_N^{\text{cv}} = \frac{1}{N} \sum_{i=1}^{N} (f(X_i) - g(X_i)) + \mathbb{E}[g(X)]

最优系数 $\beta^* = \frac{\text{Cov}(f,g)}{\text{Var}(g)}$，方差缩减比为 $\text{Var}(f)(1-\rho^2)$。

---

2. 重要性采样（Importance Sampling）

2.1 重要性采样推导

问题设定： 直接从 p(x) 采样困难，但可从另一个易采样的分布 q(x) 采样。

定理 2.1（重要性采样恒等式） 若 q(x) > 0 当 $p(x) > 0$，则：

\mathbb{E}_p[f(X)] = \mathbb{E}_q\left[f(X) \cdot \frac{p(X)}{q(X)}\right]

推导： 从 q(x) 采样，令 w(x) = \frac{p(x)}{q(x)} 为重要性权重。

\mathbb{E}_q\left[f(X) \cdot \frac{p(X)}{q(X)}\right] = \int f(x) \cdot \frac{p(x)}{q(x)} \cdot q(x) \, dx = \int f(x) p(x) \, dx = \mathbb{E}_p[f(X)]

重要性采样估计量：

\hat{F}_N^{\text{IS}} = \frac{1}{N} \sum_{i=1}^{N} f(X_i) \cdot w(X_i), \quad X_i \sim q

---

2.2 重要性权重的方差分析

定理 2.2（IS 估计量方差） 重要性采样估计量的方差为：

\text{Var}_q\left[\hat{F}_N^{\text{IS}}\right] = \frac{1}{N} \text{Var}_q\left[f(X) \cdot \frac{p(X)}{q(X)}\right] = \frac{1}{N} \left(\mathbb{E}_q\left[f^2(X) \cdot \frac{p^2(X)}{q^2(X)}\right] - \left(\mathbb{E}_p[f(X)]\right)^2\right)

定义 2.1（重要性采样的有效样本数） 定义有效样本数（ESS）：

\text{ESS} = \frac{(\sum_{i=1}^N w_i)^2}{\sum_{i=1}^N w_i^2}

当 p = q 时，$\text{Var}_q(w) = 0$，ESS $= N$；当 p 与 q 差异增大时，ESS 减小。

---

2.3 最优提案分布

定理 2.3（最优提案分布） 最小化 \text{Var}_q[f(X)w(X)] 的最优提案分布为：

q^*(x) \propto |f(x)| \cdot p(x)

（可利用柯西-施瓦茨不等式证明，此处从略。）

实际选择原则：

• q 应覆盖 p|f| 的高概率区域
• q 应比 p 方差更大（薄尾覆盖厚尾）
• 避免 q 过轻导致权重爆炸

---

3. 拒绝采样（Rejection Sampling）

3.1 接受-拒绝算法

算法 3.1（拒绝采样）

1. 设定提案分布 q(x) 和常数 $M$，使得对所有 $x$，p(x) \leq M \cdot q(x)
2. 从 q(x) 采样得到 x^*
3. 从均匀分布 U(0,1) 采样得到 u
4. 若 $u < \frac{p(x^)}{M \cdot q(x^)}$，接受 $x^*$；否则拒绝
5. 重复直至获得 N 个样本

3.2 正确性证明

定理 3.1（接受分布的证明） 拒绝采样返回的样本服从 $p(x)$。

证明： 设 A 为接受事件，X^* 为提案样本。则接受样本的分布为：

P(\text{返回 } x | \text{接受}) = \frac{P(\text{接受} | X^* = x) \cdot q(x)}{P(\text{接受})}

其中 $P(\text{接受} | X^* = x) = \frac{p(x)}{M q(x)}$，$P(\text{接受}) = \int \frac{p(x)}{M q(x)} \cdot q(x) dx = \frac{1}{M}$。

因此：

P(\text{返回 } x | \text{接受}) = \frac{\frac{p(x)}{M q(x)} \cdot q(x)}{1/M} = p(x)

得证。

---

3.3 接受率与最优提议分布

定义 3.1（接受率） 拒绝采样的接受率为：

\alpha = P\left(u < \frac{p(x^*)}{M \cdot q(x^*)}\right) = \frac{1}{M} \int p(x) dx = \frac{1}{M}

（假设 p 已归一化）

最优常数： 取 M = \sup_x \frac{p(x)}{q(x)} 使接受率最大化。

推论： 当 \sup_x \frac{p(x)}{q(x)} 很大时（如高维情形），接受率极低，算法效率严重下降。

---

3.4 高维情况下的维度灾难

命题 3.1（维度灾难） 设 p 和 q 均为高维正态分布，均值为 $\mu$，协方差分别为 \sigma_p^2 I 和 $\sigma_q^2 I$（零均值、各维度独立、同方差），则：

\sup_x \frac{p(x)}{q(x)} = \left(\frac{\sigma_q}{\sigma_p}\right)^d

其中 d 为维度。

含义： 接受率随维度指数衰减：

\alpha = \left(\frac{\sigma_p}{\sigma_q}\right)^d

当维度 d 增大时，即使 \sigma_q 仅略大于 $\sigma_p$，接受率也趋近于零。这是从拒绝采样到 MCMC 方法的根本动机。

---

4. 马尔可夫链蒙特卡洛（MCMC）

4.1 MCMC 核心思想

定义 4.1（马尔可夫链平稳分布） 若马尔可夫链的转移核 T(x'|x) 满足：

\pi(x') = \int \pi(x) T(x'|x) \, dx

则 \pi(x) 为该链的平稳分布（即目标分布 $p(x)$）。

MCMC 核心思想： 构造一个易于采样的马尔可夫链，使其平稳分布恰好是我们想要的 $p(x)$。

---

4.2 Metropolis-Hastings 算法

4.2.1 算法推导

定理 4.1（详细平衡条件） 若存在分布 \pi(x) 和转移核 T(x'|x) 满足：

\pi(x) T(x'|x) = \pi(x') T(x|x')

则 \pi(x) 是该马尔可夫链的平稳分布。

证明： 对两边积分：

\int \pi(x) T(x'|x) \, dx = \int \pi(x') T(x|x') \, dx = \pi(x') \int T(x|x') \, dx = \pi(x')

（最后一步因转移核的积分恒为 1）

4.2.2 MH 接受概率推导

构造方法： 将转移分解为提议+接受两步：

T(x'|x) = q(x'|x) \cdot \alpha(x'|x)

其中 q(x'|x) 为提议分布，\alpha(x'|x) 为接受概率。

代入详细平衡条件：

\pi(x) q(x'|x) \alpha(x'|x) = \pi(x') q(x|x') \alpha(x|x')

解得接受概率比：

\frac{\alpha(x'|x)}{\alpha(x|x')} = \frac{\pi(x') q(x|x')}{\pi(x) q(x'|x)}

取对称形式（使 $\alpha \leq 1$）：

\alpha(x'|x) = \min\left(1, \frac{\pi(x') q(x|x')}{\pi(x) q(x'|x)}\right)

这就是 Metropolis-Hastings 接受概率。

4.2.3 Metropolis-Hastings 算法

算法 4.1（Metropolis-Hastings）

1. 初始化 x^{(0)}
2. 对于 $t = 0, 1, 2, \ldots$：
   • 从提议分布 q(x'|x^{(t)}) 采样得到 x^*
   • 计算接受概率 \alpha = \min\left(1, \frac{p(x^*) q(x^{(t)}|x^*)}{p(x^{(t)}) q(x^*|x^{(t)})}\right)
   • 从 U(0,1) 采样 u
   • 若 $u < \alpha$，接受 $x^{(t+1)} = x^*$；否则 x^{(t+1)} = x^{(t)}

特例： 当 $q(x'|x) = q(x|x')$（对称提议）时，$\alpha = \min\left(1, \frac{p(x^*)}{p(x)}\right)$，即为原始 Metropolis 算法。

---

4.3 Gibbs Sampling

4.3.1 条件分布采样作为 MH 的特例

定义 4.2（Gibbs 提议分布） Gibbs 采样使用条件分布作为提议：

q(x'|x) = p(x'_i | x_{-i}) = p(x'_i | x_1, \ldots, x_{i-1}, x_{i+1}, \ldots, x_d)

其中 x_{-i} 表示除第 i 维外的所有变量。

定理 4.2（Gibbs 采样的接受率） Gibbs 提议分布的接受率恒为 1。

推导： 代入 MH 接受概率公式：

\alpha = \frac{p(x') q(x|x')}{p(x) q(x'|x)} = \frac{p(x') p(x_i | x'_{-i})}{p(x) p(x'_i | x_{-i})}

但 $x'{-i} = x{-i}$（除第 i 维外相同），且 $p(x') = p(x'i, x{-i}) = p(x'i | x{-i}) p(x_{-i})$，类似 $p(x) = p(x_i | x_{-i}) p(x_{-i})$。

因此：

\alpha = \frac{p(x'_{-i}) p(x'_i | x_{-i}) \cdot p(x_i | x_{-i})}{p(x_{-i}) p(x'_i | x_{-i}) \cdot p(x_{-i})} = 1

4.3.2 吉布斯采样算法

算法 4.2（Gibbs Sampling）

1. 初始化 (x_1^{(0)}, \ldots, x_d^{(0)})
2. 对于 $t = 0, 1, 2, \ldots$：
   • 对于每维 $i = 1, \ldots, d$：
     • 采样 x_i^{(t+1)} \sim p(x_i | x_1^{(t+1)}, \ldots, x_{i-1}^{(t+1)}, x_{i+1}^{(t)}, \ldots, x_d^{(t)})

4.3.3 吉布斯采样的收敛性

定理 4.3（Gibbs 链的遍历性） 若对所有 $i$，条件分布 p(x_i | x_{-i}) > 0 当 $p(x) > 0$，且 p(x) 不可约，则 Gibbs 链收敛到 $p(x)$。

收敛速度： Gibbs 采样的收敛速度取决于变量间的相关性。高度相关的变量会导致混合时间（mixing time）变长。实践中常用变量重参数化或块采样（block Gibbs）来加速收敛。实操时需舍弃前期 burn-in 预热样本。

---

4.4 Langevin 动力学

4.4.1 梯度驱动的采样

朗之万方程（Langevin Equation）： 连续时间的随机微分方程：

dX_t = \nabla \log p(X_t) \, dt + \sqrt{2} \, dW_t

其中 W_t 为维纳过程。

离散化（Euler-Maruyama 方法）：

x_{t+1} = x_t + \frac{\epsilon}{2} \nabla \log p(x_t) + \sqrt{\epsilon} \cdot \mathcal{N}(0, I)

4.4.2 Metropolis-adjusted Langevin Algorithm (MALA)

算法 4.3（MALA）

1. 提议：x^* = x^{(t)} + \frac{\epsilon}{2} \nabla \log p(x^{(t)}) + \sqrt{\epsilon} \cdot \mathcal{N}(0, I)
2. 接受概率：

\alpha = \min\left(1, \frac{p(x^*) \cdot \mathcal{N}(x^{(t)} | x^* + \frac{\epsilon}{2}\nabla \log p(x^*), \epsilon I)}{p(x^{(t)}) \cdot \mathcal{N}(x^* | x^{(t)} + \frac{\epsilon}{2}\nabla \log p(x^{(t)}), \epsilon I)}\right)

MALA 的效率： 当目标分布为高斯时，MALA 的接受率最优约为 0.574。高维情况下，需取 \epsilon \propto d^{-1/3} 以维持恒定接受率。实操时需舍弃前期 burn-in 预热样本。

---

4.5 Hamiltonian Monte Carlo (HMC)

4.5.1 HMC 的物理图像

HMC 引入辅助动量变量 $r$，定义联合分布：

p(x, r) = p(x) \cdot \mathcal{N}(r | 0, M) = p(x) \cdot \exp\left(-\frac{1}{2} r^T M^{-1} r\right)

其中 M 为质量矩阵（通常取对角阵）。

4.5.2 Hamiltonian 动力学

定义哈密顿量 $H(x, r) = -\log p(x) + \frac{1}{2} r^T M^{-1} r$。

运动方程：

\frac{dx}{dt} = \nabla_r H = M^{-1} r \frac{dr}{dt} = -\nabla_x H = \nabla_x \log p(x)

4.5.3 HMC 算法

算法 4.4（Hamiltonian Monte Carlo）

1. 采样 r \sim \mathcal{N}(0, M)
2. 用 leapfrog 积分 L 步模拟系统演化：
   • $r \leftarrow r + \frac{\epsilon}{2} \nabla \log p(x)$（半步）
   • $x \leftarrow x + \epsilon M^{-1} r$（整步）
   • $r \leftarrow r + \frac{\epsilon}{2} \nabla \log p(x)$（半步）
3. 用 MH 接受准则接受/拒绝终态 $(x^, r^)$：
   • \alpha = \min\left(1, \exp\left(H(x^{(t)}, r^{(t)}) - H(x^*, r^*)\right)\right)

HMC 的优势： 由于保留了动量，HMC 能在高维空间中进行长距离跳跃，有效探索低曲率方向。相比 MALA，HMC 的跃迁更加高效。实操时需舍弃前期 burn-in 预热样本。

---

5. 序列蒙特卡洛（Sequential Monte Carlo / 粒子滤波）

5.1 状态空间模型

定义 5.1（状态空间模型） 隐马尔可夫模型由以下组成：

• 状态转移分布：x_t | x_{t-1} \sim p(x_t | x_{t-1})
• 观测分布：y_t | x_t \sim p(y_t | x_t)
• 初始状态：x_1 \sim p(x_1)

滤波问题： 在线估计后验 $p(x_t | y_{1:t})$。

---

5.2 重要性重采样

算法 5.1（粒子滤波 / SIR）

1. 初始化： 从先验 p(x_1) 采样 N 个粒子 ${x_1^{(i)}}$，初始化权重 w_1^{(i)} = \frac{1}{N}
2. 递归步骤： 对每个 $t = 2, \ldots, T$：
   • 重要性采样： 从提议分布 q(x_t | x_{t-1}^{(i)}, y_t) 采样新粒子
   • 计算权重：

w_t^{(i)} \propto w_{t-1}^{(i)} \cdot \frac{p(y_t | x_t^{(i)}) p(x_t^{(i)} | x_{t-1}^{(i)})}{q(x_t^{(i)} | x_{t-1}^{(i)}, y_t)}

• 归一化： \tilde{w}_t^{(i)} = \frac{w_t^{(i)}}{\sum_{j=1}^N w_t^{(j)}}
• 重采样： 根据权重 \tilde{w}_t^{(i)} 重新采样 N 个粒子（常用残差采样或系统采样）

5.3 平滑分布的粒子近似

定义 5.2（全量平滑分布） p(x_{1:t} | y_{1:T}) 的粒子近似：

p(x_{1:t} | y_{1:T}) \approx \sum_{i=1}^{N} w_T^{(i)} \delta_{x_{1:t}^{(i)}}(x_{1:t})

前向-后向算法： 可用前向滤波+后向平滑两步计算：

p(x_t | y_{1:T}) \approx \sum_{i=1}^{N} \tilde{w}_t^{(i)} \cdot \frac{p(y_{t+1:T} | x_t^{(i)})}{\sum_{j=1}^{N} \tilde{w}_t^{(j)} p(y_{t+1:T} | x_t^{(j)})}

---

6. 与深度学习的联系

6.1 REINFORCE 中的重要性采样

策略梯度问题： 估计 $\nabla_\theta J(\theta) = \mathbb{E}{\pi\theta}[\nabla_\theta \log \pi_\theta(a|s) \cdot R]$。

方差问题： 原始 REINFORCE 估计方差较高。重要性采样可用于离策略策略评估：

\nabla_\theta J(\theta) = \mathbb{E}_{\beta}\left[\frac{\pi_\theta(a|s)}{\beta(a|s)} \nabla_\theta \log \pi_\theta(a|s) \cdot R\right]

其中 \beta 为行为策略（behavior policy）。

注意： 当 \pi_\theta 与 \beta 差异过大时，重要性权重方差爆炸。常用技术包括：加权重要性采样、树状备份算法（Tree-backup）。

---

6.2 变分推断中的采样近似

变分推断框架： 用易采样的分布 q(z) 近似后验 $p(z|x)$，通过最小化 KL 散度：

\text{KL}(q(z) || p(z|x)) = \mathbb{E}_q[\log q(z) - \log p(z|x)]

证据下界（ELBO）：

\mathcal{L}(\theta, \phi) = \mathbb{E}_{q_\phi(z|x)}[\log p_\theta(x|z)] - \text{KL}(q_\phi(z|x) || p(z))

重参数化技巧： 当 q_\phi(z|x) 不可直接采样时，用可微变换 $z = g_\phi(\epsilon, x)$，其中 $\epsilon \sim p(\epsilon)$。则：

\nabla_\phi \mathbb{E}_{q_\phi(z|x)}[f(z)] = \mathbb{E}_{p(\epsilon)}\left[\nabla_\phi f(g_\phi(\epsilon, x))\right]

---

6.3 Gumbel-Softmax 与重参数化技巧

Gumbel-Softmax 分布： 对分类分布的连续松弛。设 logits 为 $\alpha_i$，则：

y_i = \frac{\exp((\log \alpha_i + g_i)/\tau)}{\sum_{j=1}^k \exp((\log \alpha_j + g_j)/\tau)}

其中 $g_i \sim \text{Gumbel}(0,1)$，\tau 为温度参数。

性质： 当 \tau \to 0 时，y_i 趋近距离分布（one-hot）；当 \tau \to \infty 时，y_i 趋近均匀分布。

应用： 离散隐变量的变分自编码器（VAE）、强化学习中的离散动作选择。

---

附录：算法对比

方法	提议分布	接受率	适用场景
拒绝采样	人工选取	\propto 1/M	低维、p/q 有界
Metropolis	对称提议	可变	通用
Gibbs	条件分布	= 1	条件分布易采样
MALA	梯度信息	\approx 0.57	高维连续
HMC	Hamiltonian	高效	高维连续、多模态
粒子滤波	递归提议	权重归一化	时序模型

---

参考教材

1. Monte Carlo Statistical Methods, Robert & Casella
2. Bayesian Data Analysis, Gelman et al.
3. Probabilistic Graphical Models, Koller & Friedman
4. Pattern Recognition and Machine Learning, Bishop