PaperlayerView exact revision on arXiv

Source-linked AI summary

SMC^2: an efficient algorithm for sequential analysis of state-space models

Nicolas Chopin, Pierre E. Jacob, Omiros Papaspiliopoulos

arXiv:1101.1528v3stat.CO

TL;DR

Sequential Bayesian inference in state-space models is difficult because likelihood increments are typically intractable while both parameters and latent states must be inferred. The paper proposes SMC2, which combines parameter-space SMC with many particle filters and PMCMC rejuvenation, and studies its validity and applicability, including dynamic state-particle allocation. SMC2 targets the correct posterior despite intractable likelihood increments, while its tempering variant has weaker theoretical and PMCMC support.

  • Problem

    Sequential inference for both parameters and latent states in generic state-space models remains difficult, while IBIS requires typically intractable likelihood increments.

  • Method

    SMC2 attaches a particle filter to each parameter particle, using unbiased likelihood estimates and PMCMC-based rejuvenation within a sequential Monte Carlo scheme.

  • Results

    SMC2 targets the correct posterior distribution at each iteration despite intractable likelihood increments, and the paper evaluates it on challenging models.

  • Takeaways & Limitations

    SMC2 provides a generic black-box approach with dynamic state-particle allocation and a direct marginal-likelihood estimate as a by-product.

  • Takeaways & Limitations

    SMC2 is sequential but not online, and its tempering variant lacks unbiased likelihood-power estimates and cannot use conditional SMC or particle Gibbs steps.

Abstract

from arXiv · show

We consider the generic problem of performing sequential Bayesian inference in a state-space model with observation process y, state process x and fixed parameter theta. An idealized approach would be to apply the iterated batch importance sampling (IBIS) algorithm of Chopin (2002). This is a sequential Monte Carlo algorithm in the theta-dimension, that samples values of theta, reweights iteratively these values using the likelihood increments p(y_t|y_1:t-1, theta), and rejuvenates the theta-particles through a resampling step and a MCMC update step. In state-space models these likelihood increments are intractable in most cases, but they may be unbiasedly estimated by a particle filter in the x-dimension, for any fixed theta. This motivates the SMC^2 algorithm proposed in this article: a sequential Monte Carlo algorithm, defined in the theta-dimension, which propagates and resamples many particle filters in the x-dimension. The filters in the x-dimension are an example of the random weight particle filter as in Fearnhead et al. (2010). On the other hand, the particle Markov chain Monte Carlo (PMCMC) framework developed in Andrieu et al. (2010) allows us to design appropriate MCMC rejuvenation steps. Thus, the theta-particles target the correct posterior distribution at each iteration t, despite the intractability of the likelihood increments. We explore the applicability of our algorithm in both sequential and non-sequential applications and consider various degrees of freedom, as for example increasing dynamically the number of x-particles. We contrast our approach to various competing methods, both conceptually and empirically through a detailed simulation study, included here and in a supplement, and based on particularly challenging examples.

1. Introduction

The paper addresses sequential Bayesian inference for state-space models with unknown parameters and latent states, combining particle filtering, IBIS, and PMCMC into SMC2. It establishes the algorithm’s validity and studies its use on challenging models, including dynamic particle-number calibration.

  • 1. Introduction: Particle filters efficiently explore filtering distributions and provide unbiased estimates of likelihood increments and marginal likelihoods.These estimates enable particle methods to address otherwise intractable likelihood calculations.
  • 1. Introduction: Sequential inference for parameters and latent states is important but remains substantially harder than filtering with known parameters.The difficulty arises from parameter–state dependence and the challenge of sampling latent trajectories efficiently.
  • 1. Introduction: SMC2 attaches a particle filter to each parameter particle, using unbiased marginal-likelihood estimates and PMCMC-based rejuvenation steps.The nested construction extends the roles of IBIS and PMCMC to joint sequential inference.
  • 1. Introduction: SMC2 is sequential rather than online: computational load increases over time because the target dimension grows and MCMC rejuvenation steps remain necessary.The paper notes that constant computational cost and Monte Carlo error for all state and parameter components may be unattainable in general.
  • 1. Introduction: The paper evaluates SMC2 on volatility prediction for financial assets and likelihood assessment of athletic records, alongside further simulation studies.The numerical investigations focus on multidimensional states, several parameters, and particularly challenging models.
  • 1. Introduction: SMC2 is designed as a generic black-box method whose model-specific inputs are transition simulation, likelihood evaluation, and a parameter prior.The algorithm can dynamically augment the number of state particles and calibrate move steps using current particles.

2. Preliminaries

The preliminaries develop particle filtering and IBIS as the two ingredients underlying SMC2. Particle filters supply unbiased likelihood estimates, while IBIS sequentially updates parameter particles but is otherwise theoretical for state-space models.

  • Particle filtering: A particle filter recursively approximates π_t(x_t|θ)=p(x_t|y_1:t,θ) for fixed θ using a population of N_x particles.Its operations include resampling or ancestor selection, propagation through proposal distributions, and weight computation.
  • Particle filtering: The standard proposal uses the model’s initial distribution and transition density: q_1,θ(x_1)=µ_θ(x_1) and q_t,θ(x_t|x_t−1)=f_θ(x_t|x_t−1).This is described as standard but potentially sub-optimal.
  • IBIS: IBIS provides consistent and asymptotically normal estimates of posterior expectations and likelihood increments under suitable integrability conditions.Each L_t is a consistent and asymptotically normal estimator of p(y_t|y_1:t−1).
  • IBIS: In state-space models, IBIS is theoretical because the required likelihood increments are typically intractable, but coupling it with particle filters yields a working algorithm.This coupling motivates the construction developed in the next section.

3. Sequential parameter and state estimation: the SMC2 algorithm

SMC2 combines IBIS-style parameter particles with particle filters for latent states, using unbiased likelihood estimates to support sequential inference. Its extended targets have posterior parameter marginals and preserve particle-filter genealogical structure.

  • Algorithm: SMC2 amalgamates IBIS and particle filtering by attaching an x-particle filter to each of Nθ parameter particles.The algorithm iterates particle filtering, weight updates, optional rejuvenation, and replacement by an unweighted particle system.
  • Algorithm: At each iteration, particle-filter likelihood estimates provide the incremental importance weights for the θ-particles.The construction relies on the unbiasedness of the particle-filter estimate of the relevant marginal likelihood.
  • Formal justification: At iteration 1, the θ-marginal of the extended target is p(θ|y1), so the algorithm is properly weighted for any Nx.Conditional on θ, one state particle has the filtering distribution while the others follow the proposal distribution with probability 1/Nx for each particle label.
  • Formal justification: For t≥2, πt is defined on an increasing-dimensional space containing generated variables and successive incremental weights, with normalising constant p(y1:t).The extended construction includes particle arrays, ancestor variables, and particle trajectories.
  • Formal justification: The θ-marginal of πt is p(θ|y1:t), while conditional state trajectories combine filtering draws, uniform ancestor indices, and particle-filter proposal variables.Thus, πt forms a sequence of auxiliary distributions whose marginals include the posteriors of interest.

3.2. The MCMC rejuvenation step

The MCMC rejuvenation step proposes a new parameter value and associated particle-filter system, then accepts or rejects the complete extended-state move. The resulting kernel preserves the extended target distribution πt.

  • Proposal: The rejuvenation move proposes ˜θ from a θ-dimensional kernel and generates the associated extended particle-filter variables.The move operates on the full set of variables generated through time t−1.
  • Acceptance: The proposed extended state is accepted with a Hastings–Metropolis probability; otherwise the current state remains unchanged.The proposal density combines the θ kernel with the particle-filter proposal distribution.
  • Invariance: The resulting kernel leaves πt invariant and is a particle Metropolis–Hastings update within the PMCMC framework.The invariant distribution is the extended target containing the parameter and particle-filter variables.
  • Implementation flexibility: The kernel need not be ergodic because consistency is obtained by averaging across many particles rather than along one particle path.This permits lower-dimensional updates such as Hastings-within-Gibbs.

3.3. PMCMC’s invariant distribution, state inference

SMC2 distinguishes the extended targets used for PMCMC updates from the marginal targets propagated sequentially. Marginalisation supports state inference and can improve Monte Carlo efficiency.

  • Invariant distributions: SMC2 targets the sequence (πt), using importance-sampling ratios between successive versions of the temporarily extended π⋆t distributions.The distinction from PMCMC’s invariant distribution becomes important in the sequential setting.
  • State inference: The conditional distribution of n⋆ selects particle n with probability W^n_t,θ, yielding weighted samples from p(θ,x1:t|y1:t).This selection identifies one trajectory from the particle system for joint parameter–state inference.
  • State inference: The temporarily extended system supports filtering, prediction, and smoothing under parameter uncertainty.Smoothing requires storing complete state trajectories, whereas filtering and prediction can retain only recent states.
  • State inference: Complete trajectory storage makes smoothing expensive, although memory costs and occasional trajectory reconstruction are discussed as mitigations.The standard sequential implementation can avoid carrying every historical state variable.
  • Invariant distributions: Marginalising the particle index n⋆ recovers the target used for propagation to time t+1.Before marginalisation, MCMC updates with respect to π⋆t can still be applied.

3.4. Reusing all the x−particles

SMC2 can reuse the full collection of x-particles rather than selecting a single trajectory for estimation. Rao–Blackwellisation reduces variance most when functions depend on recent states.

  • Particle reuse: The particle sample targets p(θ,x1:t|y1:t), allowing estimation of expectations for test functions h(θ,x1:t).A selected trajectory and its weight provide the basic estimator.
  • Rao–Blackwellisation: Rao–Blackwellisation marginalises the selected-particle index and reuses all x-particles in the estimator.This replaces the single-trajectory contribution with an average over the particle system.
  • Rao–Blackwellisation: The variance reduction depends on how much h(θm,xn,m1:t) varies across particle labels n.The method is more effective when the particle values used by h are diverse.
  • Rao–Blackwellisation: Rao–Blackwellisation is expected to be more efficient for recent-state functions such as h(xt) than for early-state functions such as h(x1).Particle trajectories are diverse near time t but degenerate for earlier times.

3.5. Evidence

SMC2 can estimate the model evidence sequentially by multiplying estimates of likelihood increments, with practically no extra cost at each iteration.

  • The evidence of observations through time t decomposes into a product of sequential likelihood factors.
  • SMC2 estimates the evidence p(y1:t) by multiplying estimated likelihood increments across iterations.

3.6. Automatic calibration of Nx

The calibration strategy adapts the number of x-particles to address tuning and particle-MCMC acceptance-rate difficulties. SMC2 supports exchange- and particle-Gibbs-based changes in particle-filter size, with practical and storage trade-offs.

  • Motivation: A constant Nx is difficult to tune and may produce poor particle-MCMC acceptance rates as the data horizon grows.The cited discussion motivates increasing Nx over time and potentially allowing it to vary with θ.
  • Automatic calibration: The proposed calibration starts with a small Nx, monitors PMCMC acceptance, and doubles Nx when acceptance falls below a threshold.
  • Exchange importance sampling step: Exchange importance sampling generates a new particle filter and can update all particles or only a selected subset, with corresponding weight adjustments.The exchange uses an artificial backward kernel to compute incremental importance weights.
  • Exchange importance sampling step: Changing Nx through exchange steps targets a mixture of πt distributions that share the same marginals for θ and, when extended, x1:t.The validity argument relies on density ratios known up to a constant independent of Nx.
  • Practical considerations: Varying particle-filter sizes is more cumbersome to implement but may help when the cost of sampling xt+1 conditional on xt varies strongly with θ.
  • Particle Gibbs: The particle-Gibbs alternative regenerates a filter conditionally on one retained trajectory, but changes the target distribution and its dimension.It also requires storing all state variables x1:Nx,1:Nθ, creating a memory cost.

3.7. Complexity

SMC2 can reduce its memory cost to O(NθNx), but its stability analysis yields cumulative computational cost O(Nθt^2), versus O(Nθt) for IBIS under restrictive assumptions.

  • Memory cost: O(tNθNx) variables may be generated by iteration t, but typical sequential implementations reduce memory usage to O(NθNx).Only recent state variables and the statistic Ẑt are typically retained for the main algorithm.
  • Computational cost: Step (c), which re-estimates the likelihood, costs O(tNθNx) when performed at time t.
  • Stability: ESS/Nθ < γ is used as a standard criterion for detecting weight degeneracy in sequential importance sampling.Its large-Nθ limit is the inverse second moment of normalized importance weights.
  • Stability: Under assumptions H1a and H1b, maintaining Nx > ηp controls the inverse second moment over p steps without resampling.
  • Stability and computational cost: Under restrictive assumptions, resampling and adjusting Nx at prescribed times yields cumulative cost O(Nθt^2), compared with O(Nθt) for IBIS.The assumptions are described as typical but restrictive for stability analyses of sequential algorithms.

4. Numerical illustrations

The numerical illustrations apply SMC2 to challenging volatility, financial-model, and athletic-record problems, with dynamic particle allocation and comparisons against competing methods. Results include lower Monte Carlo error than SOPF in sequential settings and favorable performance against adaptive marginal PMCMC in batch settings.

  • Experimental design: SMC2 is evaluated on challenging models using dynamically increased x-particle counts and largely black-box model inputs.The model-specific requirements are transition simulation, pointwise likelihood evaluation, and a parameter prior.
  • Applications: The study covers financial volatility prediction and likelihood assessment for athletic records with multidimensional states and several parameters.The applications include Lévy-driven stochastic volatility models and time-varying extreme-value distributions.
  • Synthetic volatility: The synthetic volatility experiment uses T = 1,000 observations, five independent runs, Nθ = 1,000, and an initial Nx = 100 that increases when acceptance falls below 20%.Posterior marginal distributions are estimated for selected parameters.
  • Method comparison: The SOPF collapses to one particle around t = 700 at N = 10^5, whereas SMC2 and L&W are compared under similar computing-time budgets.SMC2 runtimes vary because x-particle counts and resample-move steps vary across runs.
  • Method comparison: L&W exhibits systematically biased log-evidence estimates, including a large discontinuity at t = 407 attributed to underestimating predictive-distribution tails.The comparison uses five SMC2 runs as the reference for centered log evidence.
  • Athletic records: The athletic-record analysis examines Wang Junxia’s 486.11-second 1993 record against the previous 502.62-second world record using two observations per year.The conditional probability accounts for the exceptional nature of a new world record.

5. Extensions

The paper extends SMC2 toward alternative target sequences, including geometric tempering, while distinguishing its exact-marginal interpretation from the tempered construction. The tempering strategy may help in non-sequential tasks but loses key sequential and PMCMC capabilities.

  • Extensions: SMC2 is presented as an “exact approximation” of IBIS that targets the exact parameter marginals for any fixed Nx.Its target sequence is πt(θ) = p(θ|y1:t), with incremental weights given by predictive likelihood increments.
  • Tempering: A geometric bridge sequence can smoothly transition from the prior to the posterior in a non-sequential tempering construction.The sequence uses γt = t/L across L iterations.
  • Tempering: Tempering uses a particle-filter likelihood estimate raised to γt, but this quantity is not unbiased for the correspondingly tempered true likelihood when γt lies between 0 and 1.This prevents the same noisy-unbiased interpretation available for the main SMC2 construction.
  • Limitations: The tempering strategy does not support sequential analysis and cannot use conditional SMC or particle Gibbs because the required mixture representation is absent.It is therefore less flexible in available PMCMC rejuvenation steps.
  • Potential uses: Despite these restrictions, tempering may be useful in some non-sequential scenarios and for MAP or maximum-likelihood estimation as γt approaches infinity.A flat prior yields the maximum-likelihood interpretation.

Appendix A: Proof of Proposition (1)

The appendix derives the auxiliary target used by SMC2 by recursively expanding particle-filter terms and isolating state trajectories. This establishes the joint-density representation underlying the proposition.

  • Derivation: The proof starts from the auxiliary distribution and rewrites its summands using the particle-filter construction.The derivation begins from equations (7) and (3).
  • Trajectory decomposition: For a fixed particle index, the proof separates random variables associated with one state trajectory before applying recursive substitutions.The trajectory is identified through the selected particle lineage.
  • Recursive expansion: The recursive substitutions expand the particle-filter factors across times s = t − 1, …, 1.This produces the sequential product structure needed for the auxiliary target.
  • Joint-density representation: The resulting expression is interpreted through the joint model density of (θ, x1:t, y1:t) evaluated at a particle trajectory.This connects the particle representation to the model’s joint probability density.

Appendix B: Proof of Proposition 2 and discussion of assumptions

The appendix derives a non-asymptotic bound under stated assumptions and uses asymptotic conditions on the marginal posterior to establish Proposition 2. Its stability implication additionally assumes exact post-resampling samples, whereas practical PMCMC updates are only approximate and require further theory.

  • Proof and assumptions: The appendix introduces assumptions for analyzing the inner expectation and obtains a non-asymptotic bound.The bound is stated under the first set of assumptions; its explicit form is not included in the supplied passage.
  • Proof and assumptions: The particle-filter likelihood-bound proposition is adapted from Cér​​ou et al. (2011) to partial likelihood estimates over a time segment.The cited proof applies when the particle filter starts at time t + 1 and uses a mixture of Dirac masses as its initial distribution.
  • Proof and assumptions: The second assumption set concerns the asymptotic behavior of p(θ|y1:t) and is used to study IBIS weight degeneracy.These assumptions are formulated through the log marginal likelihood and include MLE convergence, positive-definite observed information, and smoothness conditions.
  • Proposition 2: Under the stated conditions, E∞ t,t+p ≥ 2γ for sufficiently large t when p = ⌈τt⌉ for some τ > 0.The result is obtained by applying Chopin’s theorem together with Proposition 2(a), and it supports Proposition 2(b) when Nx = ⌈ηt⌉ with η = 4βδ.
  • Stability discussion: The stability implication assumes exact samples from πt after resampling, although SMC^2 uses approximate PMCMC updates whose target dimension increases with time.The authors identify a theoretical bound on the PMCMC kernel’s total variation distance over time as an open research problem.
Loading 1101.1528v3…