形式陈述
设第 个目标是在路径空间 上的
并选择初始提议 与前向核 。无重采样时,整条路径的提议密度为 ,原始重要性权重公理库重要性采样Importance sampling · 重要抽样从易采样的提议分布取样,以目标和提议的密度比修正访问频率并估计目标积分。满足递推
每一步用 构造粒子经验测度,正是自归一化重要性采样公理库自归一化重要性采样Self-normalized importance sampling · SNIS用未归一化目标与提议的权重和估计未知归一化常数,并以归一化权重形成目标期望的比率估计量。。支持条件要求提议路径测度覆盖所有 的路径,并使递推分母在目标质量处为正。
标准 SMC 循环包含:按当前归一化权重选择祖先索引 ;令 ;从 传播新坐标;计算增量权重并归一化。若本步不重采样,则保留旧权重并乘 ;若重采样,则祖先选择已经吸收旧权重,新权重从相应增量开始。混淆这两种递推会把旧权重重复计算或漏掉。
常以权重有效样本量公理库Monte Carlo 有效样本量Effective sample size for Monte Carlo · Monte Carlo ESS · ESS以方差匹配把权重集中或序列相关造成的信息损失折算成理想独立等权样本数的诊断量。
低于阈值时触发多项式、分层或系统重采样。无偏重采样要求每个粒子的期望后代数为 ;它保持加权经验测度的条件期望,却会增加抽样噪声并复制祖先。对固定 ,在常规可积与稳定条件下,粒子估计随 一致并有 SMC 中心极限定理;有限 的自归一化期望一般有偏。标准 Feynman–Kac 构造和无偏重采样下,归一化常数的乘积型估计可无偏,但这不使其对数无偏。
直觉
一次从容易分布跳到困难目标会产生悬殊权重;SMC 把跳跃拆成多个相邻目标,让粒子逐段付“密度比过路费”。归一化权重显示当前哪些粒子承担大部分目标质量,重采样把计算预算复制到这些位置,再由传播或 rejuvenation 核恢复多样性。
重采样只重新分配已有粒子的后代数,不会发现从未出现的区域。太晚重采样会让一个权重统治所有估计,太早或太频繁则反复丢弃低权重但潜在有用的谱系。目标序列、传播核和触发规则共同决定退化速度。
这里有两层不同的随机性。给定当前粒子,重采样只承诺后代经验分布的条件期望等于当前加权经验分布;它不承诺这个有限粒子分布已经等于真实目标。再对初始化和历次传播取平均,才讨论整套算法的偏差。归一化常数估计的无偏性属于后一层,不能从某一轮粒子图直接判断。
SMC 的粒子重采样谱系
例子与边界
从三点均匀目标 桥接到 。令三个初始粒子恰为 ,权重相等,且本步不移动位置。增量权重为 ,归一化后是 ,其权重 ESS 为
若决定多项式重采样,取三个独立均匀数 ,按累积概率 得到祖先 ;新粒子等权。重采样后的经验比例 并不等于目标,但条件期望是 。后续若没有能从 到达 的传播或 MCMC rejuvenation,状态 已永久丢失。
有限粒子恰好没有进入重要模态,与提议对该模态赋零概率,是两种不同失败。若某模态的提议概率为 , 个独立初始粒子全漏掉它的概率为 ;这次运行可能严重低估,但跨独立运行的归一化常数估计仍可能无偏。若 且后续传播也无法到达,则真正违反支持条件,增加粒子数也无法补回目标质量。
例如提议访问某区域的概率为 ,该区域对目标积分贡献 ,单次命中需贡献权重 。一百个粒子全漏掉它的概率为 ,而该区域贡献估计 的期望仍为 ,其中 。许多运行低估、少数运行大幅补偿,能与无偏性同时存在;真正的问题是方差和单次可靠性。重采样本身无法修复已经漏掉的区域。
长序列还有谱系退化:即使当前状态粒子看起来分散,向后追溯的路径可能很快汇聚到同一个祖先,使早期状态和平滑函数估计贫化。
权重在概率域连乘时可能下溢为零,应改为累加对数权重,并用 log-sum-exp 归一化。若对数权重为 ,先减去最大值 ,再计算 ,便避免共同的极小尺度;这要求至少有一个有限的 。若所有粒子的真实增量权重都为零,则应检查观测、提议支持和粒子是否漏掉有效区域,不能靠加常数掩盖失败。固定粒子数下误差还可能随时间累积,固定时间的一致性不保证任意长运行保持同样精度。
推论与应用
静态后验可用温度序列 从先验逐步走到后验;相邻温度根据权重退化自适应选择。状态空间模型则随观测时间扩展路径,得到具体的粒子滤波器公理库粒子滤波器Particle filter在状态空间模型中传播、加权并重采样粒子,以在线近似每个时刻的过滤分布与观测似然。。两者共享增量换测度与重采样机制,但目标序列的含义和稳定条件不同。
设计顺序应是先定义每个 和可验证的增量比,再选择覆盖其支持的传播核,最后按权重集中决定是否重采样。粒子数、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.