蒙特卡罗方法 - 重要采样篇

序言

蒙特卡罗方法，作为一种基于随机抽样的数值计算方法，在金融、物理、工程等多个领域展现出了强大的应用潜力。然而，传统蒙特卡罗方法在处理某些特定问题时，可能会遇到收敛速度慢、计算成本高等挑战。为了克服这些难题，重要采样（$\text{Importance Sampling}$）技术应运而生。重要采样是一种改进的蒙特卡罗方法，它通过改变抽样分布，使得样本更加集中于对目标函数贡献较大的区域，从而加速收敛，提高计算效率。这一技术的核心在于设计一个合适的采样分布，即重要性函数，使得样本能够更有效地反映目标问题的特性。

重要采样

• 如蒙特卡罗方法 - 采样和蒙特卡罗方法篇 - 公式2所示，在蒙特卡罗方法中，对积分（或者和）分解，即确定积分中哪一部分作为概率分布 $p(\mathbf{x})$ 以及哪一部分作为被积的函数 $f(\mathbf{x})$（我们感兴趣的是估计 $f(\mathbf{x})$ 在概率分布 $p(\mathbf{x})$ 下的期望）是很关键的一步。 $p(\mathbf{x})f(\mathbf{x})$ 存在不唯一的分解因为它通常可以被写成：
  $p(\mathbf{x})f(\mathbf{x})=q(\mathbf{x})\frac{p(\mathbf{x})f(\mathbf{x})}{q(\mathbf{x})}$ $\text{—公式1}$

• 在这里，我们从 $q$ 分布中采样，然后估计 $\frac{pf}{q}$在此分布下的均值。

  • 许多情况中，给定$p$ 和 $f$ 的情况下我们希望计算某个期望，这个问题既然是求期望，那么很自然地 $p$和 $f$ 是一种分解选择。
  • 然而，从衡量一定采样数所达到精度的角度说，原始定义的问题通常不是最优的选择。
  • 幸运的是，最优的选择 $q^{\ast }$ 通常可以简单推出。
  • 这种最优的采样函数 $q^{\ast }$ 对应的是所谓的最优重要采样。

• 从公式1所示的关系中可以发现，任意蒙特卡罗估计：
  ${\hat{s}}_p=\frac{1}{n}\sum _{i=1,{\mathbf{x}}^{(i)}\sim p}^{n}f({\mathbf{x}}^{(i)})$ $\text{—公式2}$

• 我们可以容易地发现估计值的期望与 $q$ 分布无关：
  ${\mathbb{E}}_q[{\hat{s}}_q]={\mathbb{E}}_p[{\hat{s}}_p]=s$ $\text{—公式3}$

• 然而， 重要采样的方差却对不同 $q$ 的选取非常敏感。这个方差可以表示为：
  $\text{Var}[{\hat{s}}_q]=\text{Var}[\frac{p(\text{x})f(\text{x})}{q(\text{x})}]/n$ $\text{—公式4}$

• 当$q$取到：$q^{\ast }(\mathbf{x})=\frac{p(\mathbf{x})|f(\mathbf{x})|}{Z}$ $\text{—公式5}$
  时，方差达到最小值。

• 在这里 $Z$ 表示归一化常数，选择适当的 $Z$ 使得 $q^{\ast }(\mathbf{x})$ 之和或者积分为 $1$。

  • 一个好的重要采样分布会把更多的权重放在被积函数较大的地方。
  • 事实上，当 $f(\mathbf{x})$ 的正负符号不变时，$\text{Var}[{\hat{s}}_{q^{\ast }}]=0$，这意味着当使用最优的 $q$ 分布时，只需要采一个样本就足够了。
  • 当然，这仅仅是因为计算 $q^{\ast }$ 的时候已经解决了所有的问题。
  • 所以这种只需要采一个样本的方法往往是实践中无法实现的。

• 对于重要采样来说任意 $q$ 分布都是可行的（从得到一个期望上正确的值的角度来说）， $q^{\ast }$ 指的是最优的 $q$ 分布（从得到最小方差的角度上考虑）。从 $q^{\ast }$ 中采样往往是不可行的，但是其他仍然能降低方差的 $q$ 的选择还是可行的。

• 另一种方法是采用有偏重要采样 ($\text{biased importance sampling}$)，这种方法有一个优势，即不需要归一化的 $p$ 或 $q$ 分布。在处理离散变量的时候， 有偏重要采样估计可以表示为：
  $\{\begin{array}{l}\begin{array}{rlr}{\hat{s}}_{\text{BIS}}& =\frac{{\sum }_{i=1}^n\frac{p({\mathbf{x}}^{(i)})}{q({\mathbf{x}}^{(i)})}f({\mathbf{x}}^{(i)})}{{\sum }_{i=1}^n\frac{p({\mathbf{x}}^{(i)})}{q({\mathbf{x}}^{(i)})}}& \text{—公式6}\\ & =\frac{{\sum }_{i=1}^n\frac{p({\mathbf{x}}^{(i)})}{\tilde{q}({\mathbf{x}}^{(i)})}f({\mathbf{x}}^{(i)})}{{\sum }_{i=1}^n\frac{p({\mathbf{x}}^{(i)})}{\tilde{q}({\mathbf{x}}^{(i)})}}& \text{—公式7}\\ & =\frac{{\sum }_{i=1}^n\frac{\tilde{p}({\mathbf{x}}^{(i)})}{q({\mathbf{x}}^{(i)})}f({\mathbf{x}}^{(i)})}{{\sum }_{i=1}^n\frac{\tilde{p}({\mathbf{x}}^{(i)})}{q({\mathbf{x}}^{(i)})}}& \text{—公式8}\end{array}\end{array}$
  $\text{—公式6}$$\text{—公式7}$$\text{—公式8}$

• 其中 $\tilde{p}$ 和 $\tilde{q}$ 分别是分布 $p$ 和 $q$ 的未经归一化的形式， ${\mathbf{x}}^{(i)}$ 是从分布 $q$ 中采集的样本。这种估计是有偏的因为 $\mathbb{E}[{\hat{s}}_{\text{BIS}}]\ne s$，除非当 $n$ 渐进性地趋近于 $1$ 时，公式6的分母会收敛到 $1$。所以这种估计也被叫做渐进性无偏的。

• 尽管一个好的 $q$ 分布的选择可以显著地提高蒙特卡罗估计的效率，反之一个糟糕的 $q$ 分布选择则会使效率更糟糕。

  • 我们回过头来看看公式4会发现，如果存在一个 $q$ 使得 $\frac{p(\mathbf{x})f(\mathbf{x})}{q(\mathbf{x})}$ 很大，那么这个估计的方差也会很大。
  • 当 $q(\mathbf{x})$ 很小，而$f(\mathbf{x})$ 和 $p(\mathbf{x})$ 都较大并且无法抵消 $q$ 时，这种情况会非常明显。
  • $q$ 分布经常会取一些简单常用的分布使得我们能够从 $q$ 分布中容易地采样。
  • 当 $\mathbf{x}$ 是高维数据的时候，$q$ 分布的简单性使得它很难于 $p$ 或者 $p|f|$ 相匹配。当 $q({\mathbf{x}}^{(i)})\gg p({\mathbf{x}}^{(i)})|f({\mathbf{x}}^{(i)})|$ 的时候， 重要采样采到了很多无用的样本（权值之和很小或趋于零）。
  • 另一方面，当$q({\mathbf{x}}^{(i)})\ll p({\mathbf{x}}^{(i)})|f({\mathbf{x}}^{(i)})|$ 的时候，样本会很少被采到，其对应的权值却会非常大。
  • 正因为后一个事件是很少发生的，这些样本很难被采到，通常使得对 $s$ 的估计出现了典型的估计不足，很难被整体的估计过量抵消。
  • 这样的不均匀情况在高维数据屡见不鲜，因为在高维度分布中联合分布的动态域通常非常大。

• 尽管存在上述的风险，但是重要采样及其变种在机器学习的应用中仍然扮演着重要的角色，包括深度学习算法。

  • 比方说，重要采样被应用于加速训练具有大规模词汇的神经网络语言模型的过程中（见深度学习应用 - 自然语言处理（NLP）篇 - 重要采样）或者其他有着大量输出结点的神经网络中。
  • 此外，还可以看到重要采样应用于估计配分函数（一个概率分布的归一化常数）的过程中以及在深度有向图模型比如变分自编码器中估计似然函数的对数。
  • 采用随机梯度下降训练模型参数的时候重要采样可以用来改进对代价函数梯度的估计，尤其是针对于分类器模型的训练中一小部分错误分类样本产生的代价函数。
  • 在这种情况下更加频繁地采集这些困难的样本可以降低梯度估计的方差 ($\text{Hinton et al., 2006a}$)。

总结

• 重要采样技术在蒙特卡罗方法中扮演着至关重要的角色。它通过优化抽样分布，使得样本更加集中于对目标函数贡献较大的区域，从而显著提高了蒙特卡罗方法的收敛速度和计算效率。在实际应用中，重要采样技术广泛应用于期权定价、风险分析、物理模拟等领域，为复杂问题的求解提供了有力支持。然而，设计合适的重要性函数并非易事，需要深入了解目标问题的特性和分布规律。
• 因此，如何根据具体问题设计高效的重要性函数，成为重要采样技术研究和应用的关键。

往期内容回顾

蒙特卡罗方法 - 采样和蒙特卡罗方法篇
深度学习应用 - 自然语言处理（NLP）篇