Skip to content

序贯 Monte Carlo

Sequential Monte Carlo · SMC · 粒子方法

用加权粒子、增量权重与按需重采样,依次近似一列目标分布及其归一化常数。

领域
统计学
条目类型
方法

形式陈述 ​

设第 t 个目标是在路径空间 X0:t 上的

πt(x0:t)=γt(x0:t)Zt,0<Zt<∞,

并选择初始提议 q0(x0) 与前向核 Mt(xt∣x0:t−1)。无重采样时,整条路径的提议密度为 qt=q0∏s=1tMs,原始重要性权重满足递推

W0(x0)=γ0(x0)q0(x0),Wt(x0:t)=Wt−1(x0:t−1)Gt(x0:t),Gt=γt(x0:t)γt−1(x0:t−1)Mt(xt∣x0:t−1).

每一步用 W~ti=Wti/∑jWtj 构造粒子经验测度,正是自归一化重要性采样。支持条件要求提议路径测度覆盖所有 γt>0 的路径,并使递推分母在目标质量处为正。

标准 SMC 循环包含:按当前归一化权重选择祖先索引 Ai;令 X0:t−1i=X0:t−1Ai;从 Mt 传播新坐标;计算增量权重并归一化。若本步不重采样,则保留旧权重并乘 Gt;若重采样,则祖先选择已经吸收旧权重,新权重从相应增量开始。混淆这两种递推会把旧权重重复计算或漏掉。

常以权重有效样本量

ESS^w=1∑i(W~ti)2

低于阈值时触发多项式、分层或系统重采样。无偏重采样要求每个粒子的期望后代数为 NW~ti;它保持加权经验测度的条件期望,却会增加抽样噪声并复制祖先。对固定 t,在常规可积与稳定条件下,粒子估计随 N→∞ 一致并有 SMC 中心极限定理;有限 N 的自归一化期望一般有偏。标准 Feynman–Kac 构造和无偏重采样下,归一化常数的乘积型估计可无偏,但这不使其对数无偏。

直觉

一次从容易分布跳到困难目标会产生悬殊权重;SMC 把跳跃拆成多个相邻目标,让粒子逐段付“密度比过路费”。归一化权重显示当前哪些粒子承担大部分目标质量,重采样把计算预算复制到这些位置,再由传播或 rejuvenation 核恢复多样性。

重采样只重新分配已有粒子的后代数,不会发现从未出现的区域。太晚重采样会让一个权重统治所有估计,太早或太频繁则反复丢弃低权重但潜在有用的谱系。目标序列、传播核和触发规则共同决定退化速度。

这里有两层不同的随机性。给定当前粒子,重采样只承诺后代经验分布的条件期望等于当前加权经验分布;它不承诺这个有限粒子分布已经等于真实目标。再对初始化和历次传播取平均,才讨论整套算法的偏差。归一化常数估计的无偏性属于后一层,不能从某一轮粒子图直接判断。

SMC 的粒子重采样谱系
例子与边界

从三点均匀目标 γ0=(1,1,1) 桥接到 γ1=(1,3,6)。令三个初始粒子恰为 (a,b,c),权重相等,且本步不移动位置。增量权重为 (1,3,6),归一化后是 (0.1,0.3,0.6),其权重 ESS 为

10.12+0.32+0.62=10.46≈2.17.

若决定多项式重采样,取三个独立均匀数 0.05,0.42,0.91,按累积概率 (0.1,0.4,1) 得到祖先 (a,c,c);新粒子等权。重采样后的经验比例 (1/3,0,2/3) 并不等于目标,但条件期望是 (0.1,0.3,0.6)。后续若没有能从 a,c 到达 b 的传播或 MCMC rejuvenation,状态 b 已永久丢失。

有限粒子恰好没有进入重要模态,与提议对该模态赋零概率,是两种不同失败。若某模态的提议概率为 r>0,N 个独立初始粒子全漏掉它的概率为 (1−r)N;这次运行可能严重低估,但跨独立运行的归一化常数估计仍可能无偏。若 r=0 且后续传播也无法到达,则真正违反支持条件,增加粒子数也无法补回目标质量。

例如提议访问某区域的概率为 0.01,该区域对目标积分贡献 0.5,单次命中需贡献权重 50。一百个粒子全漏掉它的概率为 0.99100≈0.366,而该区域贡献估计 50K/100 的期望仍为 0.5,其中 K∼Binomial(100,0.01)。许多运行低估、少数运行大幅补偿,能与无偏性同时存在;真正的问题是方差和单次可靠性。重采样本身无法修复已经漏掉的区域。

长序列还有谱系退化:即使当前状态粒子看起来分散,向后追溯的路径可能很快汇聚到同一个祖先,使早期状态和平滑函数估计贫化。

权重在概率域连乘时可能下溢为零,应改为累加对数权重,并用 log-sum-exp 归一化。若对数权重为 ai,先减去最大值 m,再计算 eai−m/∑jeaj−m,便避免共同的极小尺度;这要求至少有一个有限的 ai。若所有粒子的真实增量权重都为零,则应检查观测、提议支持和粒子是否漏掉有效区域,不能靠加常数掩盖失败。固定粒子数下误差还可能随时间累积,固定时间的一致性不保证任意长运行保持同样精度。

推论与应用

静态后验可用温度序列 γt=prior×likelihoodβt 从先验逐步走到后验;相邻温度根据权重退化自适应选择。状态空间模型则随观测时间扩展路径,得到具体的粒子滤波器。两者共享增量换测度与重采样机制,但目标序列的含义和稳定条件不同。

设计顺序应是先定义每个 γt 和可验证的增量比,再选择覆盖其支持的传播核,最后按权重集中决定是否重采样。粒子数、ESS 阈值和 rejuvenation 次数都应以目标函数误差与成本评估。只画最终粒子云会遗漏归一化常数偏差和祖先坍缩,完整输出应保留每步 log normalizer 增量、ESS、重采样时刻及祖先索引。

参考资料
  • Pierre Del Moral, Feynman-Kac Formulae: Genealogical and Interacting Particle Systems with Applications, Springer, 2004, Chs. 7–9.
  • Arnaud Doucet and Adam M. Johansen, “A Tutorial on Particle Filtering and Smoothing: Fifteen Years Later”, in The Oxford Handbook of Nonlinear Filtering, Oxford University Press, 2011, §§3–4, pp. 656–704.
  • Nicolas Chopin and Omiros Papaspiliopoulos, An Introduction to Sequential Monte Carlo, Springer, 2020, Chs. 2–4.
关系图谱8 个相邻概念 · 4 类关系

拖动节点调整位置。

显示关系

显示:依赖

  1. 前置三跳
  2. 前置二跳
  3. 前置一跳
  4. 当前条目
  5. 后续一跳
  6. 后续二跳
  7. 后续三跳
文字版关系按与当前条目的最短距离分组
分类位置

上位 / 更一般

暂未标注直接上位概念。

下位 / 直接特例

类型化关系