Source-linked AI summary
Sequential Monte Carlo smoothing for general state space hidden Markov models
Randal Douc, Aurélien Garivier, Eric Moulines, Jimmy Olsson
TL;DR
The paper addresses particle-based approximation of smoothing distributions in general hidden Markov models, where posterior computation is difficult and existing smoothing analyses face dependence challenges. It analyzes FFBSm and FFBSi schemes through deviation inequalities and central limit theorems, establishes time-uniform marginal-smoothing results under strong mixing, and introduces a linear-in-N joint-smoothing algorithm. The main scope boundary is that time-uniform guarantees rely on strong mixing, while standard approaches can degenerate for long intervals.
Problem
General hidden Markov models require smoothing distributions conditional on past, present, and future observations, but nonlinear or non-Gaussian models make these posteriors analytically intractable.
Method
The paper develops a unified convergence analysis for FFBSm and FFBSi particle smoothers and proposes a modified FFBSi algorithm for joint smoothing.
Results
The paper establishes exponential deviation inequalities, central limit theorems, and time-uniform marginal-smoothing bounds under strong mixing, with the proposed joint-smoothing algorithm costing O(NT).
Takeaways & Limitations
Under appropriate mixing, particle-based marginal smoothing remains statistically controlled as the time horizon grows, while joint smoothing can be computed with linear particle-cost scaling.
Takeaways & Limitations
Time-uniform results require strong mixing of the latent transition kernel, and standard genealogical particle approximations become inaccurate when s is far before a large T.
Abstract
from arXiv · showhide
Computing smoothing distributions, the distributions of one or more states conditional on past, present, and future observations is a recurring problem when operating on general hidden Markov models. The aim of this paper is to provide a foundation of particle-based approximation of such distributions and to analyze, in a common unifying framework, different schemes producing such approximations. In this setting, general convergence results, including exponential deviation inequalities and central limit theorems, are established. In particular, time uniform bounds on the marginal smoothing error are obtained under appropriate mixing conditions on the transition kernel of the latent chain. In addition, we propose an algorithm approximating the joint smoothing distribution at a cost that grows only linearly with the number of particles.
1. Introduction.
The paper develops particle-based methods for smoothing in general state space HMMs, where nonlinear or non-Gaussian models make posterior distributions analytically intractable. It analyzes convergence of FFBSm and FFBSi approximations, establishes time-uniform results under mixing, and proposes a linear-in-particle-cost algorithm.
- Motivation: Nonlinear or non-Gaussian state space models generally make analytic smoothing distributions intractable, motivating particle-based approximations.SMC methods approximate sequences of probability distributions using recursively updated particles and importance weights.
- Computational contribution: A modified FFBSi algorithm approximates the joint smoothing distribution with computational complexity growing linearly in the number of particles and without numerical approximation.The original FFBSm and FFBSi formulations typically scale as O(N^2T).
- Methods and analysis: FFBSm and FFBSi smoothing analyses are difficult because backward quantities depend statistically on forward particles and weights across time.The paper addresses the resulting gap in convergence theory for these schemes.
- Finite-horizon results: Finite-horizon analyses establish exponential deviation inequalities for FFBSm and FFBSi estimators, with error probabilities bounded at order O(exp(−cNε^2)).Here c depends on the time horizon and target function.
- Finite-horizon results: The paper also establishes a central limit theorem with an explicit asymptotic variance for particle smoothing approximations.The proof uses a triangular-array CLT for dependent random variables to handle smoothing-weight dependence.
- Time-uniform results: Under strong mixing of the latent transition kernel, marginal smoothing errors admit time-uniform deviation bounds and asymptotic variances remain bounded as T tends to infinity.The paper attributes this uniformity to forgetting of initial conditions in both forward and backward conditional dynamics.
Notation and definitions.
The paper formulates smoothing in a possibly nonlinear hidden Markov model using state transitions, observation likelihoods, and posterior distributions conditional on a fixed observation record. It introduces notation for joint, marginal, and filtering distributions under dominated-model assumptions.
- State-space model: The latent process is a Markov chain with initial distribution χ and transition kernel M, while observations are conditionally independent given the latent states.The observation model has likelihood density g with respect to a σ-finite measure.
- Observation model: The likelihood function for state Xt at observed value yt is denoted gt(x)=g(x,yt).The observation sequence is fixed, so dependence on yt is implicit in gt.
- Dominated model: The model is assumed fully dominated, with transition probability density m(x,·) for M relative to a σ-finite measure ν.The notation ν(dx) may be abbreviated as dx.
- Smoothing distributions: For a fixed observation record y0:T, φs:s′|T denotes the posterior distribution of the state vector Xs:s′.The dependence on the initial distribution and observed values may be left implicit.
- Smoothing distributions: The marginal smoothing distribution is written φs|T when s=s′, while φT denotes the filtering distribution when the conditioned state time equals the observation time.These are special cases of the joint smoothing notation.
2. Algorithms.
The algorithms approximate smoothing distributions through forward filtering followed by backward recursion or simulation, with the latter admitting a faster modified implementation. The section also characterizes computational cost and conditions supporting linear complexity.
- Forward filtering backward smoothing: The smoothing distribution is computed recursively backward in time using the conditional time-reversed Markov structure of the state sequence.The backward recursion replaces filtering distributions with particle approximations.
- Forward filtering backward simulation: FFBSi samples backward index paths from an inhomogeneous Markov chain induced by normalized smoothing weights and forward particles.The estimator can be represented as a conditional expectation and approximated by independently simulated backward paths.
- Trade-offs and conditions: The FFBSi approach increases variance relative to the Rao–Blackwellized estimator but provides a significant computational-complexity gain.Stronger mixing conditions also permit complexity bounds for auxiliary particle filters beyond the bootstrap and fully adapted cases.
- Computational complexity: The original FFBSi sampler requires O(N^2T) computation overall, although fast multipole methods can reduce this to O(N log(N)T) with additional approximations.Sampling one path costs O(NT), and the fast multipole reduction introduces approximation-related computational trade-offs.
- Fast FFBSi: The modified FFBSi algorithm uses accept–reject sampling to achieve linear complexity in the number of particles under appropriate transition-kernel assumptions.The procedure samples backward paths using an upper bound on the transition kernel and multinomial resampling operations.
- Fast FFBSi: Under upper and lower bounds on the transition kernel, the modified algorithm satisfies E[C(N,T)] ≤ KNTσ+/σ−.This bound applies to the total number of elementary operations and is established in Proposition 2.
3. Convergence of the FFBS and FFBSi algorithms.
This section analyzes convergence of FFBS and FFBSi particle approximations, addressing their dependence structure through a decomposition of smoothing errors. It establishes nonasymptotic deviation inequalities and central limit theorems under stated assumptions.
- Error decomposition: The analysis introduces a decomposition of the FFBS smoothing error that underpins the paper’s convergence results.The decomposition uses backward-variable kernels and separates contributions associated with particle approximations.
- Kernel convergence: The random kernels depend on past particle approximations but converge, as N →∞, to deterministic kernels.This convergence is used to control the dependence structure in subsequent limit theorems.
- Related estimators: The exponential inequality extends to the FFBSi estimator, while the filter approximation appears as a by-product for functions depending only on the terminal state.The filter result follows by selecting a terminal-state function in the joint smoothing formulation.
- Asymptotic normality: The same convergence framework yields a central limit theorem with asymptotic variance expressed through a finite sum involving limiting kernels.The proof accounts for the complex dependence of smoothing weights using triangular arrays of dependent random variables.
4. Time uniform bounds.
Under a strong mixing condition on the latent transition kernel, the paper derives time-uniform error and variance bounds for marginal smoothing approximations. These results cover the practically important regime in which the smoothed state remains fixed while the observation horizon grows.
- Setting: The section studies long-term behavior of marginal fixed-interval smoothing estimators as T tends to infinity.The analysis imposes strong mixing conditions on the transition kernel, with simpler conditions targeting compact-state applications.
- FFBSi computation: Under the mixing assumption, the accept–reject mechanism in FFBSi requires on average at most σ+/σ− simulations per sampled particle.This computational bound follows directly from the upper and lower transition-kernel bounds.
- Main results: The main goal is a time-uniform exponential deviation inequality and a time-uniform bound on the CLT variance for marginal smoothing approximations.Both results hold under the same mixing assumptions.
- Deviation bounds: Theorem 11 establishes constants independent of T in a deviation bound valid for all particle populations and s ≤ T.This provides stability when the smoothing time s is fixed and the observation horizon increases.
- Variance bounds: Theorem 12 gives a time-uniform bound on the asymptotic variance of the marginal smoothing estimator under the same assumptions.The bound is derived using the exponentially decreasing kernel quantity established earlier.
5. Proofs of Propositions 1 and 2.
This section proves the propositions governing reduced-complexity smoothing procedures, focusing on the number of simulations and elementary operations required by the algorithms.
- Simulation complexity: The proofs analyze the average number of simulations required by the accept–reject procedure used for FFBSi sampling.The analysis tracks simulation counts through the algorithm’s while loop.
- Operation complexity: The second proposition fixes a time step and bounds its elementary-operation count using list-occurrence variables.The proof introduces Cs and the counts T_s^k to quantify work at one step.
- Operation complexity: The complexity proof applies Proposition 14 to obtain a constant-factor bound for the per-step computation.The resulting bound is expressed using the auxiliary population parameter N^u = N.
APPENDIX A: PROOF OF LEMMA 4
The appendix concludes that the proof follows from the preceding argument.
- The proof follows from the preceding argument.
- The appendix presents the proof as a consequence of earlier reasoning.
- The section closes by asserting that the proof is established.
APPENDIX B: TECHNICAL RESULTS
This appendix establishes an exponential deviation result for a triangular array under uniform assumptions involving positive constants and a contraction parameter. The proof handles large deviations by fixing a positive threshold and summing exponential terms.
- The triangular array is assumed to satisfy uniform conditions for all n, i, and ε > 0, with B > 0, C > 0, and 0 < ρ < 1.
- There exist constants B̄ > 0 and C̄ > 0 that yield a bound valid for every n and ε > 0.
B.1. Description of the sampling procedure.
The section presents an efficient multinomial sampling procedure based on ordered uniform samples and adaptive search through cumulative probabilities. Its operation count is O(n + nlog(1 + N/n)), covering both small and large sample sizes efficiently.
- The procedure samples n indices from a distribution (p1,...,pN) using ordered i.i.d. uniform variables and a random permutation.The algorithm searches cumulative probabilities to assign each sampled uniform value an index.
- Its complexity is O(log(N)) when n = 1 and O(N) when n = N.
- O(n + nlog(1 + N/n)) elementary operations are required by Algorithm 2.
- The procedure uses an adaptive doubling search followed by binary search to locate each sampled index.The search expands the right boundary while needed, then narrows the interval until the selected index is identified.