Exact Rejection Sampling for Non-Gaussian State Space Models¶
作者: Joshua C. C. Chan
主题: 统计计算 / 算法
相关性: 6/10
链接: https://arxiv.org/abs/2608.21619
一、领域脉络与小综述¶
-
这个方向是什么:本文属于统计计算(statistical computing) 与贝叶斯计算的交叉子领域,核心问题是:对于非高斯状态空间模型(如随机波动率、随机条件持续时间模型),如何精确且高效地从状态路径的后验分布(平滑分布)中抽样,并构造无偏且有限方差的似然估计量。该子方向的成熟度较高,已有大量近似方法(如粒子滤波、MCMC、拉普拉斯近似),但精确抽样(exact sampling)且计算代价可控的方法长期缺失,本文试图填补这一空白。
-
发展脉络(history):
- 奠基工作:线性高斯状态空间模型的精确模拟平滑器(如 Carter and Kohn, 1994; de Jong and Shephard, 1995; Durbin and Koopman, 2002; Chan and Jeliazkov, 2009; McCausland, Miller, and Pelletier, 2011)——这些方法在正态假设下是精确且高效的,但无法处理非高斯观测。
- 主要进展(近似方法):为突破高斯限制,文献发展了两条路线。其一是近似平滑器,如拉普拉斯近似、高斯变分近似,以及基于高斯混合的辅助粒子滤波(Kim, Shephard, and Chib, 1998; Omori et al., 2007)——这些方法牺牲了精确性。其二是重要性抽样与粒子滤波,如高效重要性抽样(EIS, Richard and Zhang, 2007)和 HESSIAN 方法(McCausland, 2012),它们构造了良好的提议分布,但无法提供全局支配常数,因此重要性权重的方差无法保证有限。
- 当前 frontier:如何在保持精确性(无近似误差)的同时,使计算代价随路径长度 T 的增长可控(而非指数爆炸)。Whiteley and Lee (2014) 和 Guarniero et al. (2017) 的 twisted particle filter 提供了思路,但未给出可计算的全局常数。
- 本文的位置:作者将拒绝抽样与twisted transition 结合,首次在非高斯状态空间模型中构造出已知常数、严格支配、且常数可达的提议分布,从而同时获得精确抽样和有限方差保证。这是对 EIS/HESSIAN 方法(无常数保证)和粒子滤波(无精确性)的实质性推进。
-
子线索聚类:
- 精确模拟平滑器(Carter & Kohn 1994; de Jong & Shepphard 1995; Durbin & Koopman 1997; Chan & Jeliazkov 2009; McCausland et al. 2011):仅适用于高斯或条件高斯模型,计算高效但不可推广。
- 近似平滑与重要性抽样(Shephard & Pitt 1997; Durbin & Koopman 1997; Jungbacker & Koopman 2007; Richard & Zhang 2007; McCausland 2012; Scharth & Kohn 2016):通过高斯或扭曲提议逼近目标,但缺乏全局常数,权重方差可能无限。
- 粒子滤波与 SMC(Whiteley & Lee 2014; Guarniero et al. 2017; Heng et al. 2020):通过 twisted 函数改善粒子多样性,但仍是近似方法,且常数未知。
- 精确抽样与拒绝抽样(Devroye 1986; Gilks & Wild 1992):单变量对数凹密度的经典工具,本文将其推广到高维状态路径。
-
这个方向在追问的核心问题:
- 如何构造一个可计算的全局支配常数? 这是拒绝抽样的核心障碍,本文通过 tangent-line twists 解决。
- 如何保证接受概率不随 T 指数衰减? 本文通过压缩映射和次高斯矩条件,证明接受概率以 T/G² 的速率衰减,从而 G ∝ √T 即可维持有界接受率。
- 如何将精确抽样转化为似然估计? 本文通过 Rao-Blackwellization 给出无偏似然估计量,并给出相对方差上界 1/p − 1。
-
⚠️ 作者的 framing(这是作者的说法):作者将缺口 frame 成"缺乏一个既精确又计算可控的模拟平滑器",并强调其方法的"常数可达"和"全局支配"特性是区别于 EIS/HESSIAN 的关键。作者淡化了向量状态的推广难度(仅在结论中提及),也回避了与粒子滤波在非线性非高斯模型中的直接对比(本文仅覆盖高斯转移)。值得研究者去查的问题:作者声称"据我们所知,这是第一个……",但未引用 Deligiannidis et al. (2020) 的 ensemble rejection sampling 作为对比——该文是否在更广模型类中已有类似常数构造?此外,作者未提及 Møller et al. (2006) 的辅助变量精确抽样法,该方法是否适用于状态空间模型?
-
张力:未见明显对立引用。但存在一个潜在张力:EIS/HESSIAN 方法追求方差最小化(通过回归拟合),而本文追求常数可达(通过切线包络),两者在目标函数上不同,可能导致本文方法在低维时不如 EIS 高效,但在高维时更稳健。作者在数值实验中没有直接对比 EIS 的方差,只对比了计算时间,这是一个值得注意的空白。
二、最核心、最简单的例子 / 数学内核¶
第一步:符号、模型、可观测数据交代清楚¶
-
符号:
- h = (h₁, …, h_T)′:标量潜在状态序列(随机向量),是潜在变量,不可直接观测。
- y = (y₁′, …, y_T′)′:观测数据(可多维),是可观测随机变量。
- ℓ_t(u) = log p(y_t | h_t = u):观测对数似然,是已知函数(由模型设定),要求凹。
- a_t(u) = α_t + β_t u:状态转移的均值函数,仿射(高斯转移的均值)。
- ω_t:状态转移的方差(已知常数)。
- p_t(u|v):状态转移密度(高斯),已知。
- γ(h):未归一化的后验密度(目标),即 γ(h) = p₁(h₁)e^{ℓ₁(h₁)} ∏{t=2}^T p_t(h_t|h{t-1})e^{ℓ_t(h_t)}。
- Z = ∫ γ(h) dh:归一化常数,即观测似然 p(y),是要估计的 estimand。
- q(h):提议分布(twisted 马尔可夫链的联合密度)。
- ψ_t(u):twist 函数(对数域),是构造对象,取为凹函数 f_t 的切线包络。
- f_t(u):后向函数(backward function),由递推定义,是理论对象,用于定义 twist。
- V_t = {v_{t,1}, …, v_{t,G_t}}:节点集合,用于构造切线包络。
- G:每时间点的节点数。
- p:接受概率(rejection sampling 的接受率)。
- bC₁:提议分布的归一化常数(即支配常数)。
-
模型:
- 状态方程:h₁ ~ N(µ₁, ω₁),h_t | h_{t-1} ~ N(a_t(h_{t-1}), ω_t),即高斯转移。
- 观测方程:y_t | h_t ~ 具有对数凹密度的分布(如随机波动率中的正态观测、持续时间模型中的指数/伽马观测)。
- 目标:从后验 p(h|y) = γ(h)/Z 中精确抽样,并估计 Z。
-
可观测数据:研究者实际能观测到的是 y(观测序列),以及模型设定的参数(α_t, β_t, ω_t, ℓ_t 的形式)。想要但观测不到的是 h(潜在状态路径)和 Z(观测似然)。识别策略完全依赖于模型假设:高斯转移 + 对数凹观测似然。
第二步:最小内核¶
核心思想:拒绝抽样的关键是找到一个提议分布 q(h) 和一个常数 M,使得 γ(h) ≤ M·q(h) 对所有 h 成立。本文的构造分三步:
-
Twisting(扭曲):定义后向函数 f_t(u) = ℓ_t(u) + log bC_{t+1}(u),其中 bC_{t+1}(u) 是下一期扭曲转移密度的归一化常数。这个递推是精确的,但 f_t 通常没有闭式解。
-
切线包络(Tangent envelope):对每个凹函数 f_t,用其在节点 V_t 处的切线取最小值,构造 ψ_t(u) = min_j {f_t(v_{t,j}) + f't(v{t,j})(u − v_{t,j})}。因为 f_t 是凹的,所以 ψ_t(u) ≥ f_t(u) 对所有 u 成立(切线在凹函数上方)。关键:ψ_t 是分段线性的凹函数,使得扭曲后的转移密度 q_t(h_t|h_{t-1}) ∝ p_t(h_t|h_{t-1})e^{ψ_t(h_t)} 是截断正态的混合,可以精确抽样和计算归一化常数。
-
可分离性(Separability):由 Lemma 1,γ(h)/q(h) = bC₁·exp{Σ_t [f_t(h_t) − ψ_t(h_t)]}。因为每一项 f_t − ψ_t ≤ 0,所以 γ(h) ≤ bC₁·q(h),且常数 bC₁ 是可达的(在节点处取等号)。接受概率 p = Z/bC₁。
为什么成立:整个证明的关键在于凹函数的切线包络。因为 f_t 是凹的,切线在函数上方,所以 ψ_t ≥ f_t,从而保证了支配性质。而 ψ_t 的分段线性结构保证了提议分布的可处理性。最小内核可以概括为:用分段线性凹函数(切线包络)逼近后向递推中的凹函数,将精确但不可计算的扭曲递推转化为可计算的截断正态混合,同时保持支配性质。
三、这篇论文做了什么¶
三句话¶
- 研究了什么问题:为非高斯状态空间模型(标量状态、仿射高斯转移、对数凹观测)构造一个精确的拒绝抽样器,用于从状态路径的后验分布中独立抽样,并构造无偏且有限方差的似然估计量。
- 核心工具/方法:后向扭曲递推 + 切线包络(tangent envelope)。通过将后向函数 f_t 替换为其在节点处的切线包络 ψ_t,构造一个分段线性的 twist,使得提议分布是截断正态的混合,从而可精确抽样和计算归一化常数。
- 主要结论:该算法是精确的(无近似误差),支配常数可达且可计算,接受概率以 T/G² 的速率衰减(G ∝ √T 即可维持有界接受率),似然估计量的相对方差以 1/p − 1 为上界。数值实验显示 T=2000 时接受率约 75%,而高斯包络的接受率仅约 10⁻¹⁶。
关键设定与假设¶
- Assumption 1:
- (i) 状态转移均值仿射(a_t(u) = α_t + β_t u),方差恒定(ω_t > 0)。这是高斯转移的设定,保证了扭曲后的转移密度仍是高斯形式。
- (ii) 观测对数似然 ℓ_t 有限、连续可微、凹。这是核心假设,保证了切线包络的支配性质。相比已有文献(如 EIS 要求高斯近似,粒子滤波要求任意似然但无常数保证),本文的假设更窄(要求对数凹),但换来了精确性和常数可达性。
- 隐含假设:状态为标量(一维),这是切线包络可行的关键。向量状态的推广需要多维包络,是作者在结论中承认的局限。
- 相比已有文献的强化/弱化:相比 EIS/HESSIAN(无常数保证),本文强化了假设(对数凹)但获得了常数;相比粒子滤波(可处理非线性非高斯),本文弱化了模型类(仅高斯转移+对数凹观测),但获得了精确性。
主要结果¶
- Theorem 1(精确性与最小支配常数):算法是精确的,且 bC₁ 是可达的最小支配常数。证明分三步:Lemma 1 给出可分离性;Lemma 2 保证递推的良定义性和凹性保持;Theorem 1 综合两者。
- Corollary 1(有界重要性权重):权重 w(h) = γ(h)/q(h) 满足 0 < w ≤ bC₁,且相对方差 ≤ 1/p − 1。这是似然估计量有限方差的直接保证。
- Theorem 2(接受概率的缩放):在 companding 节点放置下,−log p = O(T/G²)。这意味着 G ∝ √T 即可维持接受概率有界远离零。证明依赖于 Lemma 5(companding 逼近误差)和 Lemma 9-10(模式位置与次高斯矩)。
- Corollary 2(随机波动率模型的验证):对随机波动率模型,Theorem 2 的条件几乎必然成立,因此缩放结果适用。
证明路线与技术技巧¶
整体路线(以 Theorem 2 的证明为例): 1. 后向递推:定义 f_t = ℓ_t + log bC_{t+1},其中 bC_{t+1} 是扭曲转移的归一化常数。Lemma 4 证明 log bC_t 的曲率有界,且 f_t 保持凹性。 2. 切线包络:在节点 V_t 处构造切线包络 ψ_t,Lemma 5 证明包络误差在 companding 节点下为 O(G⁻²)。 3. 模式控制:Lemma 9 证明扭曲转移的模式 r_t(u) 与中心 c_t 的距离被 δ_t 和 f'_t(c_t) 控制,且 f'_t(c_t) 有界(Lemma 9(i))。 4. 次高斯矩:Lemma 10 利用模式控制和强凸性,证明扭曲转移的次高斯矩有界,从而控制尾部贡献。 5. 汇总:Theorem 2 将包络误差和尾部贡献相加,得到 −log p = O(T/G²)。
技术技巧点名: - 后向递推(backward recursion):与 EIS 和 HESSIAN 类似,但本文的 twist 是分段线性的,而非高斯或高阶多项式。 - 切线包络(tangent envelope):这是本文的核心创新,将凹函数的全局支配转化为局部切线支配,从而可计算。 - Companding 节点放置:借鉴信号处理中的 companding 思想,在概率质量集中的区域放置更多节点,实现均匀的逼近误差。 - Rao-Blackwellization:似然估计量 (11) 是拒绝抽样指示器的 Rao-Blackwell 化,降低了方差。 - 强凸性 + 次高斯矩:利用强凸性控制模式位置,利用次高斯矩控制尾部,是证明缩放结果的关键。
真实例子与应用¶
- 模拟实验:随机波动率模型(T=250 至 4000),比较了 tangent envelope 与高斯包络的接受率。结果显示 tangent envelope 的接受率在 T=4000 时仍为 0.56(固定 G=81),而高斯包络降至 e⁻⁷³·⁷。当 G ∝ √T 时,接受率保持在 0.87 左右。
- 八种观测分布:包括随机波动率、随机波动率均值、学生 t 误差、指数/伽马/威布尔持续时间、泊松计数、动态 probit。接受率范围为 0.811 至 0.931,而高斯包络的接受率从 1.1×10⁻⁴ 到 4.9×10⁻⁶⁶ 不等。
- 实证应用:随机条件持续时间模型(Bauwens and Veredas, 2004),使用 Binance 加密货币交易数据(LINKUSDT 和 ALGOUSDT,2024年5月15日)。结果显示伽马误差优于指数误差,且似然比检验强烈支持伽马分布。该应用展示了方法在模型比较中的实用性。
🔎 结论是否比证明窄¶
- Theorem 2 的证明依赖 Assumption 2,其中次高斯矩条件(Assumption 2(ii))是对算法输出的提议分布施加的,而非对原始模型施加的。作者在附录 B 中为随机波动率模型验证了该条件,但没有为表 1 中的所有八种观测分布验证。因此,Theorem 2 的缩放结果严格来说只对随机波动率模型成立,对其他模型的适用性是经验性的,而非理论保证。
- Corollary 2 的证明声称"几乎必然"成立,但证明依赖于数据生成过程的遍历性,且附录 B 的验证是针对特定参数设定的。作者没有讨论参数边界情况(如 ϕ → 1 或 σ_h² → 0)。
- 向量状态的推广在结论中被明确列为未来工作,但作者没有给出任何初步结果或猜想,因此本文的贡献严格限于标量状态。
四、开放问题¶
- 向量状态的推广(扎根于结论段):作者明确承认"将当前方法推广到向量值状态是一个自然但非平凡的方向"。核心困难在于切线包络在多维空间中的构造和计算。研究者可考虑:能否用分段仿射包络或半正定锥规划来构造多维支配函数?
- 非对数凹观测(扎根于 Assumption 1(ii)):对数凹性对切线包络的支配性质至关重要。若观测似然非凹(如双峰似然),切线包络可能失效。研究者可考虑:能否用分段凹包络或自适应节点来处理?
- 自适应节点放置(扎根于第 3.2 节和 Theorem 2):companding 规则是静态的,依赖于对后验形态的先验猜测。研究者可考虑:能否用序贯蒙特卡洛或变分推断来动态调整节点位置,以进一步降低 G 的所需规模?
- 计算复杂度与维度权衡(扎根于第 3.3 节):后向递推的代价是 O(TG²),当 T 很大时仍可能昂贵。研究者可考虑:能否用低秩近似或稀疏网格来加速递推?
- 与粒子滤波的对比(扎根于第 5 节):作者仅对比了计算时间,没有对比有效样本量或估计量的渐近方差。研究者可考虑:在非线性非高斯模型中,本文方法是否仍优于粒子滤波?
- 理论保证的扩展(扎根于 Theorem 2 和附录 B):次高斯矩条件(Assumption 2(ii))的验证是逐模型进行的。研究者可考虑:能否给出一个统一的充分条件,使得 Theorem 2 的缩放结果对所有满足 Assumption 1 的模型都成立?
提示:要确认上述问题是否为真 gap,建议去读近 5 年关于 twisted particle filter、精确模拟平滑器、以及状态空间模型计算方法的综述和最新论文(如 Deligiannidis et al. 2020 的 ensemble rejection sampling 后续工作,以及 Doucet et al. 2022 的粒子滤波理论进展)。如果这些文献中已有向量状态或非对数凹的精确抽样方法,则本文的 gap 可能已被部分填补。
Maintained by 陈星宇 · Homepage · Source on GitHub