采样方法

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

1. 蒙特卡洛方法基础

1.1 随机采样与期望估计

定义 1.1（蒙特卡洛估计） 设为从分布中独立采得的样本，则函数的期望值的蒙特卡洛估计为：

定理 1.1（蒙特卡洛估计的无偏性） 上述估计量是的无偏估计，即：

证明：

1.2 大数定律与收敛性

定理 1.2（弱大数定律） 若 i.i.d.，且，则对任意：

推论： 蒙特卡洛估计量依概率收敛到真实期望值，收敛速度为。具体而言，中心极限定理给出：

均方误差为：

1.3 方差缩减的基本思想

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

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

最优系数，方差缩减比为。

2. 重要性采样（Importance Sampling）

2.1 重要性采样推导

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

定理 2.1（重要性采样恒等式） 若当，则：

推导： 从采样，令为重要性权重。

重要性采样估计量：

2.2 重要性权重的方差分析

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

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

当时，，ESS ；当与差异增大时，ESS 减小。

2.3 最优提案分布

定理 2.3（最优提案分布） 最小化的最优提案分布为：

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

实际选择原则：

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

3. 拒绝采样（Rejection Sampling）

3.1 接受-拒绝算法

算法 3.1（拒绝采样）

设定提案分布和常数，使得对所有，
从采样得到
从均匀分布采样得到
若，接受；否则拒绝
重复直至获得个样本

3.2 正确性证明

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

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

$返回接受接受接受$

其中 $接受$ ， $接受$ 。

因此：

$返回接受$

得证。

3.3 接受率与最优提议分布

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

（假设已归一化）

最优常数： 取使接受率最大化。

推论： 当很大时（如高维情形），接受率极低，算法效率严重下降。

3.4 高维情况下的维度灾难

命题 3.1（维度灾难） 设和均为高维正态分布，均值为，协方差分别为和（零均值、各维度独立、同方差），则：

其中为维度。

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

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

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

4.1 MCMC 核心思想

定义 4.1（马尔可夫链平稳分布） 若马尔可夫链的转移核满足：

则为该链的平稳分布（即目标分布）。

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

4.2 Metropolis-Hastings 算法

4.2.1 算法推导

定理 4.1（详细平衡条件） 若存在分布和转移核满足：

则是该马尔可夫链的平稳分布。

证明： 对两边积分：

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

4.2.2 MH 接受概率推导

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

其中为提议分布，为接受概率。

代入详细平衡条件：

解得接受概率比：

取对称形式（使）：

这就是 Metropolis-Hastings 接受概率。

4.2.3 Metropolis-Hastings 算法

算法 4.1（Metropolis-Hastings）

初始化
对于：
- 从提议分布采样得到
- 计算接受概率
- 从采样
- 若，接受；否则

特例： 当（对称提议）时，，即为原始 Metropolis 算法。

4.3 Gibbs Sampling

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

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

其中表示除第维外的所有变量。

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

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

但（除第维外相同），且，类似。

因此：

4.3.2 吉布斯采样算法

算法 4.2（Gibbs Sampling）

初始化
对于：
- 对于每维：
  - 采样

4.3.3 吉布斯采样的收敛性

定理 4.3（Gibbs 链的遍历性） 若对所有，条件分布当，且不可约，则 Gibbs 链收敛到。

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

4.4 Langevin 动力学

4.4.1 梯度驱动的采样

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

其中为维纳过程。

离散化（Euler-Maruyama 方法）：

4.4.2 Metropolis-adjusted Langevin Algorithm (MALA)

算法 4.3（MALA）

提议：
接受概率：

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

4.5 Hamiltonian Monte Carlo (HMC)

4.5.1 HMC 的物理图像

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

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

4.5.2 Hamiltonian 动力学

定义哈密顿量。

运动方程：

4.5.3 HMC 算法

算法 4.4（Hamiltonian Monte Carlo）

采样
用 leapfrog 积分步模拟系统演化：
- （半步）
- （整步）
- （半步）
用 MH 接受准则接受/拒绝终态：

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

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

5.1 状态空间模型

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

状态转移分布：
观测分布：
初始状态：

滤波问题： 在线估计后验。

5.2 重要性重采样

算法 5.1（粒子滤波 / SIR）

初始化： 从先验采样个粒子，初始化权重
递归步骤： 对每个：
- 重要性采样： 从提议分布采样新粒子
- 计算权重：

归一化：
重采样： 根据权重重新采样个粒子（常用残差采样或系统采样）

5.3 平滑分布的粒子近似

定义 5.2（全量平滑分布） 的粒子近似：

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

6. 与深度学习的联系

6.1 REINFORCE 中的重要性采样

策略梯度问题： 估计。

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

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

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

6.2 变分推断中的采样近似

变分推断框架： 用易采样的分布近似后验，通过最小化 KL 散度：

证据下界（ELBO）：

重参数化技巧： 当不可直接采样时，用可微变换，其中。则：

6.3 Gumbel-Softmax 与重参数化技巧

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

其中，为温度参数。

性质： 当时，趋近距离分布（one-hot）；当时，趋近均匀分布。

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

附录：算法对比

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

参考教材

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

Huajishe Notes

Explorer

3-采样方法