重要性采样是一种蒙特卡洛方法,通过从不同于待估量所依据的分布中抽取观测样本,来估计积分、期望和小概率。每个观测样本都被赋予一个权重,用于校正分布变化带来的影响。选择得当的采样分布能将计算集中在对答案贡献最大的结果上,从而有望将计算成本降低数个数量级。
这种方法在统计学、计算物理学、可靠性分析、计算机图形学和概率机器学习中都占有重要地位。当直接采样较为困难、重要事件很少发生,或需要将已有的模拟结果用于另一个目标分布时,它尤其有用。其背后的数学恒等式很简单,但实际表现却在很大程度上取决于采样分布对目标分布的覆盖程度,以及对过大权重的控制。重要的变体包括自归一化估计、自适应方法、多提议分布方法,以及用于处理随时间演变的分布的序贯方法。
分布变换与基本估计量
假设所关注的量是一个期望值
其中, 是归一化的概率密度函数, 是可积函数。直接蒙特卡洛方法从 中抽取样本,再对样本的函数值取平均。重要性采样则从提议密度 中抽取样本,并利用恒等式
对于从 中独立抽取的样本 ,普通重要性采样估计量为
提议分布会有意提高或降低不同区域的采样比例,而这些权重恰好能够校正这种偏差。
基本的支撑条件是:除零测集外,凡是 的地方,都有 。实际中常采用一个更强的条件,即要求提议分布覆盖整个目标分布。如果提议分布从不在某个具有非零贡献的区域采样,那么无论如何加权,都无法补回这部分缺失的贡献。在满足支撑条件和绝对可积条件时,该估计量是无偏的:。大数定律还保证了随着样本量增加,该估计量具有一致性。这种基本收敛并不要求二阶矩有限,但常用的基于方差的误差评估需要这一条件。
同样的构造也适用于离散分布,只需将密度和积分分别替换为概率质量和求和。更一般地,测度论将这一要求表述为目标测度 关于提议测度 的绝对连续性。此时,权重就是拉东—尼科迪姆导数 。这一表述不仅适用于欧氏空间上的密度,也涵盖离散变量与连续变量的混合情形,以及路径上的分布。
重要性采样还可以估计最初并未写成期望形式的积分。对于可积函数 ,
因此,提议分布实际上是一种计算资源分配规则:在预计被积函数贡献较大的区域安排更多样本。与拒绝采样不同,重要性采样通常保留每一个采样点,通过改变其贡献大小来进行调整,而不是接受或丢弃该点。
未归一化的目标分布与自归一化估计
许多统计模型给出的目标分布含有一个未知的归一化常数:
在贝叶斯推断中, 通常是先验分布与似然函数的乘积,而 则是边际似然。不知道 ,就无法计算通常的重要性权重 ,但仍可计算未归一化权重
由此可得自归一化估计量
中未知的乘法常数会在比值中约去。
分子和分母所对应的样本均值分别估计 和 。如果二者均收敛,且 ,那么它们的比值就收敛于 。不过,自归一化通常会引入有限样本下的估计量的偏差,因为比值的期望并不等于期望的比值。在适当的矩条件下,这一偏差的阶为 ,而随机误差的阶通常为 。这些收敛速率是渐近结论,并不能为小样本或权重呈重尾分布的情形提供保证。
当适用的中心极限定理成立时,
其中
这一中心化表达式十分重要:自归一化估计的表现,取决于权重与特定被积函数偏离其目标均值的程度如何相互作用。大权重对不同待估计量的影响并不相同。例如,只要分母为正,无论权重如何变化,对任何常数函数的估计都是精确的。
由于归一化权重非负且总和为一,自归一化估计值必定位于采样所得函数值的最小值与最大值之间。对于概率和有界观测量,这一性质可能很方便,但它并不能消除因未采样到某些区域而产生的误差。如果所有采样点处的目标密度都为零,分母也会为零。
归一化常数本身可用通常的估计量来估计:
在通常的支撑集条件和可积性条件下,该估计量是无偏的。因此,估计 与估计归一化分布下的期望是两项不同的任务。将所有未归一化权重乘以同一常数,不会改变自归一化的期望估计值,但会使 的估计值也乘以该常数。
方差缩减与最优提议分布
重要性采样是一种方差缩减方法,但改变采样分布并不一定能提高精度。在样本相互独立且二阶矩有限的情况下,
直接从 中采样对应于 。只有当加权后的二阶矩更小时,提议分布才优于直接采样。即便满足支撑集条件,不合适的提议分布仍可能导致更大的方差,甚至无穷方差。
对于普通重要性采样,使方差最小的密度为
这里假定分母有限且为正。这一结果可由柯西—施瓦茨不等式推出。最小方差为
因此,理想的提议分布应随被积函数贡献的绝对大小而变化,而不一定要与目标密度相似。目标分布可能将大部分概率集中在 接近零的区域,从而使直接采样效率低下。
如果 非负,最优提议分布就与 成正比。此时,每个加权观测值都等于 ,由此得到零方差估计量。这通常只是一种理想情形,而非可直接使用的算法:对提议分布进行归一化,恰恰需要知道所要估计的积分。不过,它仍提供了一条设计原则。即使无法得到精确的最优密度,只要近似捕捉到贡献较大的区域,也能显著提高效率。对于可正可负的被积函数,通常无法用同一个非负提议分布,同时使正贡献和负贡献各自恒定。
自归一化重要性采样具有不同的渐近最优提议分布:
其中出现 ,反映了这种方法通过比值进行估计的特点。该提议分布同样依赖未知的估计目标,而且在目标分布中满足 的区域上可能为零,因此实践中常使用保持支撑集覆盖的近似分布或混合分布。如果需要估计多个观测量,对其中一个观测量最优的提议分布,对另一个可能表现很差。
利用普通权重 ,可以得到一个衡量目标分布与提议分布不匹配程度的实用指标:
最后一个表达式就是 相对于 的卡方散度。它解释了为什么看起来与目标分布很接近的提议分布仍可能不可靠:密度比很大的小区域可能主导二阶矩。因此,要缩减方差,就必须关注尾部和支撑集,而不能只关注目标分布众数附近的吻合程度。
提议分布的构造、尾部与维数
实用的提议分布必须兼顾三项要求:易于抽取样本,易于计算归一化后的密度,而且其形状应能覆盖对积分有重要贡献的区域。良好地逼近目标分布固然有益,但如果提议分布过于紧密地贴合目标分布的中心区域,效果可能反而不如更宽泛的近似。尤其是,当提议分布在重要的尾部区域赋予的概率过小时,就会产生很大的权重。
一个正态分布的例子可以说明支撑集条件与矩条件之间的区别。设目标分布为标准正态分布,提议分布为均值为零、方差为 的正态分布。两者的密度在所有位置都为正。尽管如此,
仅在 时才有限。事实上,被积函数中的指数部分为
它只有在上述条件下才可积。因此,支撑集满足要求既不能保证方差有限,也不能保证对采样误差的正态近似可靠。
为降低出现极端权重的风险,常使用重尾提议分布,例如学生t分布。当目标分布具有多个彼此分离的峰时,混合分布很有用。高斯混合模型可以为每个已知区域分配一个分量,同时额外加入一个较宽的分量,以防尾部识别不充分。防御性重要性采样通过下式将这一思路形式化:
其中, 提供稳健的覆盖, 则使采样集中于重点区域。如果可以直接从归一化后的目标分布中采样,且 ,则有 。
高维问题会带来尤为严重的维数灾难。假设目标分布和提议分布都可以按 个坐标分解:
则
如果每个因子都等于常数 ,二阶矩就会以 的速度增长。因此,即使各个坐标上的差异并不大,也可能使权重的不稳定程度随维数呈指数增长。
构造提议分布时,可以利用后验众数附近的局部正态近似、数值优化或初步模拟。局部近似可以捕捉曲率,却可能遗漏偏度、远处的峰或非线性依赖关系。变量变换提供了另一条途径:先在较简单的坐标系中生成样本,再将其映射到目标空间。此时,正确计算密度需要用到雅可比矩阵的行列式。无论采用何种参数化方式,成功的提议分布都必须覆盖对所求积分有贡献的区域,而不只是复现几个中心矩。
稀有事件模拟与指数倾斜
估计稀有事件的概率,是重要性抽样最典型的用途之一。对于事件 ,令
直接蒙特卡洛方法对 的示性函数取样本平均。其方差为 ,因此,当 很小时,其相对标准误差近似为
若 ,要使相对标准误差接近 ,大约需要进行 次独立的直接抽样。困难不在于判断事件是否发生,而在于能否观测到足够多次该事件。
重要性抽样选择一个使 的发生频率显著提高的提议分布,并用下式进行估计:
理论上能使方差为零的提议分布是条件分布
此时,每个模拟样本点都落在 中,对估计量的贡献恰好为 。由于这一提议分布的密度需要用到未知的概率,实际的稀有事件模拟会近似那些导致失效的轨迹或状态的分布。
一种广泛使用的构造方法是指数倾斜。若
有限,则定义
当 为正时,较大的观测值更容易被抽到。对于独立同分布随机变量之和 ,若从倾斜后的分布中抽取每个变量,则似然比为
一种常见的参数选择方法,是使稀有事件的阈值接近提议分布下的均值,从而让原本异常大的和值成为模拟中的典型结果。
举一个具体例子:考虑 服从标准正态分布时的 。提议分布 会使大约一半的观测值超过阈值。其权重为
这并不能使所有对估计有贡献的观测值具有相同的贡献,但它能将抽样资源集中到相关的尾部,而不是让几乎每次抽样都落在阈值以下。
同样的原理也适用于队列溢出、保险破产、通信错误和部件失效。在动态系统中,提议分布可以改变转移概率或增量分布;此时,路径权重就是各步似然比的乘积。随着事件变得更加稀有,可以通过有界相对误差或对数效率等性质来评估方法的效率。仅仅让失效变得常见还不够:某个提议分布可能偏向一种失效机制,却几乎从不抽到另一种对该概率有实质贡献的机制。
多个提议分布与自适应重要性采样
单个易于处理的提议分布可能无法覆盖复杂的目标分布。多重重要性采样将多个提议分布 结合起来。如果以概率 选择提议分布的索引,所得的边缘采样密度为
按此过程抽取的样本可用 加权。分母中的混合密度考虑了该样本可能产生的所有途径,而不只是本次选中的分量。
一种相关的方案是固定从分量 中抽取 个样本,其中 ,且 。估计量
在满足适当的联合支撑集条件时是无偏的。只要混合分布能覆盖整个目标分布,就不要求每个分量都做到这一点。以这种方式汇集样本,可以使重叠区域内的权重更加稳定,并将针对不同模态、尾部或物理机制设计的专用提议分布结合起来。
更一般的估计量使用满足 的权重函数 :
采用平衡启发式权重
就可得到上述以混合密度为分母的估计量。埃里克·维奇(Eric Veach)和列奥尼达斯·吉巴斯(Leonidas Guibas)于1995年为计算机图形学开发了具有重要影响的多重重要性采样方法。在这一领域,不同的采样技术适用于不同的光传输情形。
自适应重要性采样利用先前模拟得到的观测值来调整提议分布。可以先用一批样本估计合适的位置参数和协方差矩阵、拟合混合分量,或识别重要的尾部方向,随后再将采样集中到这些区域。一种做法是最小化某种差异度量,例如KL散度;交叉熵方法则根据加权或筛选后的观测值拟合提议分布的参数。当无法通过解析方法确定目标分布的重要区域时,自适应方法尤其有用。
从数学上看,何时进行自适应调整至关重要。如果 由先前的样本确定,随后再从 中抽取 ,那么在满足支撑集和可积性条件的前提下, 的条件期望仍为 。这类项可以用鞅方法研究。相比之下,利用正在加权的同一批观测值来事后修改分母,并不能自动保证无偏性。自适应混合方案和样本复用方案需要针对各自的依赖结构进行分析;仅凭固定提议分布下的恒等式,并不足以证明它们的有效性。
序贯重要性采样与粒子方法
序贯重要性采样将分布变换原理应用于随观测数据到来或潜在路径维度增加而变化的目标分布。它是序贯蒙特卡罗的基础,包括用于状态空间模型的粒子滤波方法。典型模型包含潜在状态 、观测值 、转移密度 和观测密度 。推断目标可以是滤波分布 ,也可以是完整潜在路径的后验分布。
假设按以下方式扩展一条粒子路径:
在不进行重采样的情况下,其未归一化权重按下式更新:
在扩展后的目标分布与提议分布之比中,先前的因子相互抵消。在自举粒子滤波中,提议分布就是模型的转移密度,因此增量权重只剩下观测似然。
仅靠序贯赋权通常会出现退化问题。随着似然比不断累积,大多数粒子的归一化权重变得微乎其微,而少数粒子几乎决定了整个估计结果。重采样按照粒子的当前权重成比例地选取粒子,将带权粒子集合替换为等权粒子集合。多项式重采样、残差重采样、分层重采样和系统重采样在后代粒子的分配方式及统计性质上有所不同。重采样并不产生新信息:它只是剔除低权重路径,并复制高权重路径。
尼尔·戈登、戴维·萨尔蒙德和阿德里安·史密斯于1993年发表的自举粒子滤波,成为非线性、非高斯滤波领域一种颇具影响力的实用方法。在隐马尔可夫模型中,当精确计算不可行时,可以用粒子近似潜在状态的概率。在跟踪任务中,粒子可以表示目标的多个可能位置或运动模式。与仅依据状态动力学的提议分布相比,纳入最新观测信息的提议分布可以减小权重的变异。
重要性采样与重采样之间的关系也带来了一些局限。频繁重采样会使祖先路径合并,降低早期状态的多样性,即使此时对当前状态的估计仍然有用。这种现象称为路径退化,对平滑和参数估计尤为重要。马尔可夫链更新步骤可以恢复局部多样性,而更好的提议分布则能减少对频繁重采样的需求。
序贯方法也可以通过一系列中间分布连接先验分布与后验分布,而不必沿着物理时间推进。例如,与 成比例的目标分布可随着 的增大而逐步引入似然。每个阶段都会重新计算粒子权重,通常还会进行重采样,并利用保持该中间目标分布不变的转移来移动粒子。这样就不必在单次重要性采样中应对先验分布与后验分布之间的全部差异。
应用及与其他方法的关系
重要性采样伴随着早期计算模拟的发展而形成,赫尔曼·卡恩和西奥多·哈里斯于 1951 年开展的工作是其奠基性研究之一。辐射输运为这一方法提供了天然的应用场景:到达探测器或穿透屏蔽层的粒子可能十分罕见,但它们的贡献却是人们主要关注的量。通过对源方向、相互作用的选择或路径分布施加偏置,可以提高有用粒子历程的出现频率,前提是保留相应的似然校正。同样的加权核算原理也适用于统计力学、可靠性分析和随机优化。
在贝叶斯计算中,重要性采样可以利用局部近似、变分推断或先前分析所得到的提议分布,近似计算后验期望。它还可用于估计归一化常数,并支持不同先验下的敏感性计算。例如,当似然不变且满足所需的支撑条件时,可以使用与 成正比的比值,对基于先验 的后验样本重新加权,使其对应于基于 的后验。先验变化过大可能导致这些比值不稳定。
重要性采样与马尔可夫链蒙特卡洛以不同方式处理相关问题。标准的重要性采样从提议分布中独立抽样,并用显式权重加以校正。马尔可夫链蒙特卡洛则通过转移机制构造相互依赖的样本,使其平稳分布为目标分布。这两类方法可以结合使用:可以对具有相关性的链输出进行重要性加权,也可以将粒子方法嵌入马尔可夫链算法。在这些情况下,评估不确定性时必须考虑样本间的依赖关系,而不能将观测值视为相互独立。
计算机图形学使用重要性采样来估计渲染方程;该方程对入射光、表面散射和几何可见性进行积分。对于局部照明,朝向明亮光源的方向采样很有效;对于方向分布狭窄的光泽反射,按照表面的散射分布采样则很有效。两种策略都不是在所有情况下占优。多重重要性采样结合了它们的优势,并抑制这样的大额贡献:某种技术能够高效生成一条光路,而另一种技术却为这条光路赋予极低的概率。
在强化学习中,离策略评估利用行为策略生成的轨迹,估计目标策略的表现。如果两种策略所处环境的动力学相同,轨迹似然比中就包含策略概率比的乘积
当时间跨度较长时,这些乘积的变异性可能变得极大。逐决策估计量只使用与每项奖励相关的概率比,其他方法则对结果建模或调整加权方案。支撑条件要求行为策略允许采取目标策略所使用的动作。
机器学习中的一个相关应用是协变量偏移校正。当响应的条件分布保持不变,而协变量分布发生变化时,可以用目标分布与源分布的协变量密度之比,对源数据中的观测值进行加权。这一恒等关系无法校正响应机制的任意变化;其有效性取决于上述分布关系是否成立。
误差评估、权重诊断与数值计算
对于观测值相互独立的普通重要性采样,定义
当 的方差有限时,将 的样本方差除以 ,即可估计其平均值的方差。随后可通过正态近似得到标准误和近似的置信区间。对于自归一化采样,一种常用的渐近方差估计为
如果相关的二阶矩为无穷大,或者样本中尚未出现罕见但贡献极大的观测值,这些计算就可能产生误导。
一种广泛使用的权重诊断指标是有效样本量
对于总和为正的非负权重,该指标介于 与 之间。所有权重相等时,它等于 ;单个观测值占据主导地位时,它趋近于 。在适当的矩条件下,其大样本性质与 有关,其中 为变异系数。
这一诊断指标并非普适的信息量度。它忽略了权重与所估计的具体函数之间的关系,无法发现未被采样的重要区域,也不会自动校正观测值之间的依赖性。针对特定函数与直接采样进行比较时,得到的有效样本量可能超过 ,但仅依据权重计算的上述公式不可能超过 。反过来,如果所有样本都局限于多模态目标分布的同一片区域,未能覆盖完整的目标分布,那么即使权重看似均匀,也可能存在严重误差。
帕累托平滑重要性采样通过拟合广义帕累托尾部分布,检查并正则化最大的权重。其形状参数的估计值可为尾部的厚重程度及各阶矩是否存在提供依据。在理想化的尾部模型下,形状参数小于 对应于有限的二阶矩,而小于 则对应于有限的一阶矩。有限样本下的估计仍存在不确定性。对权重进行平滑或截断通常会引入偏差,但当极端权重占据主导地位时,这样做可以降低均方误差。
数值实现同样重要。在浮点运算中,多个小概率相乘可能发生下溢,对于长轨迹或大型数据集尤其如此。因此,权重通常在对数尺度上计算:
归一化权重可通过以下方式稳定地计算:
这一共同的平移量会在归一化期望中抵消。估计绝对归一化常数时,则需要保留被移除的尺度,例如计算
数值稳定的计算可以避免算术运算失效,但无法解决提议分布覆盖不足或权重尾部过重所导致的统计失效。