PaperlayerView exact revision on arXiv

Source-linked AI summary

On Particle Methods for Parameter Estimation in State-Space Models

Nikolas Kantas, Arnaud Doucet, Sumeetpal S. Singh, Jan Maciejowski, Nicolas Chopin

arXiv:1412.8695v2stat.COstat.ME

TL;DR

The paper addresses how to estimate unknown static parameters in nonlinear non-Gaussian state-space models, where standard particle methods are inadequate. It reviews Bayesian and maximum-likelihood particle methods across off-line and on-line settings, comparing their behavior and limitations. The review highlights computational trade-offs among particle implementations and persistent degeneracy challenges in on-line Bayesian methods.

  • Problem

    Unknown static parameters make nonlinear non-Gaussian state-space models difficult to infer because likelihoods and related high-dimensional integrals are intractable.

  • Method

    The paper comprehensively reviews particle methods for Bayesian and maximum-likelihood parameter inference implemented off-line or on-line.

  • Results

    Path-space estimates typically have variance increasing quadratically with T, whereas fixed-lag or exponentially weighted alternatives typically achieve linear variance growth but introduce nonvanishing asymptotic bias.

  • Takeaways & Limitations

    Forward-smoothing methods avoid the path-space method’s asymptotic bias but have O(N^2(T + 1)) complexity, with MSE behavior that is respectively variance- versus bias-dominated.

  • Takeaways & Limitations

    On-line Bayesian methods do not bypass particle degeneracy, and posterior-sequence errors can accumulate over time.

Abstract

from arXiv · show

Nonlinear non-Gaussian state-space models are ubiquitous in statistics, econometrics, information engineering and signal processing. Particle methods, also known as Sequential Monte Carlo (SMC) methods, provide reliable numerical approximations to the associated state inference problems. However, in most applications, the state-space model of interest also depends on unknown static parameters that need to be estimated from the data. In this context, standard particle methods fail and it is necessary to rely on more sophisticated algorithms. The aim of this paper is to present a comprehensive review of particle methods that have been proposed to perform static parameter estimation in state-space models. We discuss the advantages and limitations of these methods and illustrate their performance on simple models.

1. INTRODUCTION

State-space models are flexible time-series models used across diverse applications, but nonlinear non-Gaussian versions are difficult to fit. Unknown parameters make inference harder, motivating a review of particle-based estimation methods classified by Bayesian versus ML and off-line versus on-line procedures.

  • Model context: State-space models combine a latent Markov process with observations conditionally described by a parameterized density.The latent process has initial density µθ and transition density fθ, while gθ describes the conditional observation density.
  • Model context: Applications include stochastic volatility, biochemical networks, and neuroscience models with latent states and noisy observations.Examples map latent variables to asset volatility, biochemical species populations, and neural stimulus-response states.
  • Motivation: Nonlinear non-Gaussian state-space models are notoriously difficult to fit despite their flexibility and interpretability.Simulation techniques have only recently enabled fuller use of their potential.
  • Motivation: With known parameters, exact state filtering and smoothing are generally limited to simple models such as linear Gaussian systems.Approximation schemes including the Extended Kalman filter and Gaussian sum filter have been proposed for harder cases but lack rigor and can be unreliable.
  • Parameter inference: Unknown parameters must often be inferred from data, but naively augmenting the state with parameters fails because the parameter space is not explored adequately.This problem motivated many particle methods, while the paper reviews their features, advantages, and limitations.
  • Review scope: The review classifies parameter methods as Bayesian or maximum likelihood and as off-line or on-line.Bayesian methods characterize a parameter posterior, whereas ML methods maximize the likelihood; either can operate off-line or on-line.

2. COMPUTATIONAL CHALLENGES ASSOCIATED TO PARAMETER INFERENCE

Parameter inference is difficult because likelihoods, posterior normalizing constants, and associated high-dimensional integrals are typically intractable. ML therefore needs low-variance likelihood or score estimates, while Bayesian inference must approximate parameter posteriors sequentially.

  • Likelihood and posterior: The likelihood pθ(y0: n) is a central object for both maximum likelihood and Bayesian parameter inference.It is also the normalizing constant of the latent-state posterior.
  • Likelihood and posterior: The latent-state posterior can be used with Fisher’s identity to compute the score vector of the log-likelihood.The score is ∇θℓn(θ), where ℓn(θ) = log pθ(y0: n).
  • Computational challenges: In nonlinear non-Gaussian models, likelihood evaluation is intractable and requires low-variance Monte Carlo estimates or score estimates.Both routes involve approximating high-dimensional integrals.
  • Computational challenges: Bayesian inference additionally requires approximating the parameter posterior and its sequentially updated integrals.Both pθ(y0: n) and the marginal evidence p(y0: n) are intractable in this setting.

3. FILTERING AND PARTICLE APPROXIMATIONS

Filtering recursively estimates latent-state posteriors from observations and also supplies likelihood terms needed by particle-based parameter inference. Exact computation is generally restricted to linear Gaussian or finite-state models, so particle approximations are used otherwise.

  • Filtering: Known-parameter filtering provides an on-line scheme for computing the sequence of likelihood terms pθ(y0: n).These likelihood approximations are key inputs to later particle-based parameter-inference techniques.
  • Filtering: Filtering estimates the sequence of joint latent-state posteriors recursively, while filtering densities refer to their marginal state distributions.The paper adopts filtering as the broader joint-posterior task rather than only marginal estimation.
  • Filtering: The posterior and likelihood satisfy fundamental recursions for n ≥ 1.These recursions form the basis for sequential filtering and likelihood computation.
  • Particle approximations: Exact posterior and likelihood computation is available essentially for linear Gaussian models and finite-state models.For other models, the relevant densities are typically intractable and require approximation.

Algorithm 1 Auxiliary particle filtering

The auxiliary particle filtering procedure begins at time n = 0 and applies its initialization step across all N particles.

  • Algorithm 1: At time n = 0, the algorithm specifies an operation for every particle i ∈ {1,...,N}.The displayed procedure begins with particle-wise initialization.
  • Algorithm 1: The initialization step ranges over the particle indices i = 1,...,N.Each particle is included in the stated loop.
  • Algorithm 1: Algorithm 1 therefore starts with an N-particle initialization before subsequent filtering operations.The passage explicitly identifies the initial time and particle range.

3. Resample

At time n ≥1, the resampling procedure is applied across all particles indexed by i ∈ {1,...,N}.

  • At time n ≥1, the procedure operates for every particle i ∈ {1,...,N}.
  • The resampling step is specified sequentially at each time n.
  • The algorithm’s particle-level operations are indexed by i from 1 through N.

3. Resample

Particle filtering approximates filtering distributions and likelihoods with O(N) work per time step, but path degeneracy creates worsening long-time errors, especially for static-parameter inference.

  • Particle filtering: The auxiliary particle filter approximates filtering distributions and includes bootstrap filtering and SISR as special cases.Bootstrap filtering is implementable when the transition can be sampled but its density cannot be computed.
  • Particle filtering: O(N) operations per time step are sufficient for the particle filtering algorithm, including resampling.
  • Resampling: Resampling replicates high-weight particles and discards low-weight particles to focus computation on promising state-space regions.
  • Convergence results: Particle estimates have useful fixed-time convergence results, but error constants can grow exponentially with time and resampling causes path degeneracy.Successive resampling can reduce an earlier trajectory to a single unique particle as the time gap increases.
  • Convergence results: Exponential forgetting can yield uniform-in-time filtering accuracy when the model satisfies suitable mixing or informativeness conditions.This explains the effectiveness of particle filtering for applications focused on recent state segments.
  • Convergence results: The likelihood estimate is unbiased, with relative variance bounded by Dθn/N under the stated assumption, though constants can be exponential in state dimension.

4. SMOOTHING

Particle smoothing addresses latent-state inference using fixed-lag, forward–backward, and forward-only procedures, balancing degeneracy, bias, and computational cost.

  • 4.1 Fixed-lag Approximation: Fixed-lag smoothing limits later observations to a window of length L, reducing the impact of trajectory degeneracy.Choosing L too small causes approximation error; choosing it too large preserves substantial degeneracy.
  • 4.2 Forward–backward smoothing: Forward–backward smoothing decomposes the joint smoothing density into filtering distributions and backward transition densities.A forward pass computes filtering distributions, followed by a backward pass for smoothed distributions.
  • 4.2.1 FFBSa: FFBSa samples a complete smoothed path with O(N(T + 1)) operations, or O(T + 1) on average under rejection-sampling conditions.The latter requires an unweighted particle approximation and a bounded transition prior.
  • 4.2.2 FFBSm: FFBSm approximates all smoothed marginals with O(N^2(T + 1)) operations, although fast computational methods can reduce this cost.
  • 4.3 Forward smoothing: Forward smoothing computes smoothed additive functionals recursively in one forward pass and empirically outperforms naive path-space smoothing at fixed particle count.Under suitable assumptions, forward–backward estimators have variance of order n/N, while path-space estimates suffer degeneracy.
  • 4.4 Convergence Results for Particle Smoothing: Fixed-lag smoothing has variance of order n/N and a nonvanishing bias that decreases exponentially as L increases.

5. MAXIMUM LIKELIHOOD PARAMETER ESTIMATION

The paper reviews particle-based maximum-likelihood parameter estimation, using likelihood or score approximations and optimization methods. It compares computational costs, variance, bias, continuity, and numerical stability across implementations.

  • 5.1 Maximum likelihood estimation: Particle methods approximate the log-likelihood for fixed parameters, enabling maximum-likelihood estimation through Monte Carlo optimization.The estimated likelihood may be optimized directly, while gradient-based methods use score estimates.
  • 5.1.1 Likelihood function evaluation: Resampling makes common-random-number likelihood estimates discontinuous in the parameter, complicating direct optimization even when the exact likelihood is continuous.Small parameter changes can alter the resampled particle set.
  • 5.1.1 Likelihood function evaluation: O(N(T + 1)logN) operations yield a continuous likelihood estimate that can be maximized with standard optimization techniques in the one-dimensional-state construction.The method sorts particles and uses a piecewise linear approximation to the resampling c.d.f.; multivariate extensions have different guarantees or costs.
  • 5.1.2 Gradient ascent: Iterated filtering estimates gradients when the transition kernel can be sampled but its analytical expression is unavailable, with accuracy improving as artificial-noise variances shrink.As the artificial dynamic noise decreases, more particles are needed because mixing deteriorates.
  • 5.1.2–5.1.3 Gradient ascent and EM: Gradient ascent can be unstable because score components require careful scaling, whereas EM produces a nondecreasing likelihood sequence and is numerically more stable when applicable.EM computes summary statistics through smoothed additive functionals in exponential-family settings.
  • 5.1.4 Discussion of particle implementations: O(N(T + 1)) path-space estimates have variance that typically grows quadratically with T, while alternatives can reduce this to linear growth at the cost of asymptotic bias.FFBSm, forward smoothing, and generalized two-filter methods avoid that bias but require O(N^2(T + 1)) computation; fast methods can reduce the cost to O(N).

5.2 On-Line Methods

On-line parameter methods update estimates sequentially as observations arrive, using gradient, EM, and particle-smoothing procedures to avoid repeatedly processing the full data record. Their reliability depends on the chosen particle approximation and, for some methods, remains theoretically unresolved.

  • On-Line Methods: On-line inference updates the parameter estimate after each new observation, avoiding potentially prohibitive full-sequence gradient computations and accommodating real-time constraints.Recursive procedures update θ_n to θ_n+1 after receiving y_n.
  • On-Line Methods: Under regularity conditions, a time-varying-score recursion converges to a local maximum of the average log-likelihood for finite-state HMMs.The true parameter maximizes this objective under identifiability assumptions.
  • On-line Methods: On-line EM recursively updates sufficient-statistic averages, but convergence for state-space models remains unproved despite empirical evidence of good performance.Modified versions have easier-to-establish convergence results, while the presented algorithm often performs better empirically.
  • On-Line Methods: For on-line gradient ascent, particle path estimates have variance growing linearly with time, whereas forward-smoothing estimates have uniformly bounded variance under suitable regularity conditions.The forward-smoothing approach yields a stable procedure and justifies computational complexity O(N^2).

6. BAYESIAN PARAMETER ESTIMATION

Bayesian particle methods estimate posterior distributions over static parameters and latent states, using particle MCMC, artificial parameter dynamics, or MCMC rejuvenation. These methods address parameter diversity and posterior approximation but face degeneracy, bias, computational-growth, and convergence limitations.

  • Bayesian Parameter Estimation: Bayesian parameter inference targets joint posterior densities over latent trajectories and parameters, either for a fixed dataset or sequentially as observations arrive.The off-line target is p(x_0:T,θ|y_0:T), while the on-line target is a sequence of posterior densities.
  • Bayesian Parameter Estimation: MCMC is difficult to design efficiently for nonlinear non-Gaussian state-space models because single-variable Gibbs sampling mixes poorly and blocking is model-dependent.These limitations motivate particle-based alternatives.
  • Bayesian Parameter Estimation: PMMH approximates an ideal Metropolis–Hastings sampler by replacing unavailable likelihoods and smoothing distributions with particle-filter estimates.It proposes θ′, runs a particle filter, estimates p_θ′(y_0:T), and samples a trajectory from the resulting particle approximation.
  • Bayesian Parameter Estimation: PMMH preserves the exact joint posterior as its invariant distribution for any particle count N, although larger N generally lowers Monte Carlo variance at greater computational cost.A practical tuning analysis suggests selecting N so the log particle-likelihood estimate has standard deviation around 1.2–1.3 for general proposals and targets.
  • Bayesian Parameter Estimation: Particle Gibbs and related methods add parameter-particle diversity without perturbing the target distribution, but they still inherit latent-path degeneracy and can produce highly variable estimates.Empirical results show that MCMC-based particle methods may explore only a small portion of the parameter-posterior support.
  • Bayesian Parameter Estimation: Online Bayesian particle methods remain harder than online ML because they must approximate likelihoods for all parameter particles, while standard extended-state methods collapse parameter diversity over time.Artificial parameter dynamics mitigate collapse but introduce artificial variance, while fixed-lag methods introduce nonvanishing bias.
  • Bayesian Parameter Estimation: MCMC rejuvenation methods avoid perturbing the target but may require increasing computational cost or particle counts, limiting their use in truly online scenarios.Some retain fixed memory by updating only θ or a short recent state segment, but the cost per iteration is not constant.

7. EXPERIMENTAL RESULTS

Experiments compare particle estimators for smoothed additive functionals and their use in maximum-likelihood and Bayesian parameter inference. The results expose bias–variance trade-offs, computational effects, and persistent degeneracy in some Bayesian methods.

  • Experimental setup: The experiments use a scalar linear Gaussian model, where Kalman filtering supplies exact summary statistics, likelihoods, and reference posterior densities.This permits direct assessment of particle approximations and parameter estimates.
  • Maximum Likelihood Methods: The path-space estimator costs O(N) per time, whereas forward FFBSm costs O(N^2) per time and produces the same estimates as standard forward–backward FFBSm.The comparison allocates N^2 particles to the O(N) method and N particles to the O(N^2) method.
  • Maximum Likelihood Methods: For both smoothing methods, bias grows linearly with time, but the O(N^2) method has higher bias; its variance is roughly constant, while the O(N) method’s variance grows linearly.The resulting MSE is lower for the O(N) method in this scenario, while the O(N) method generally favors bias and O(N^2) favors variance.
  • Maximum Likelihood Methods: On-line EM and on-line gradient ascent require over 10,000 observations before achieving convergence in the reported setting.For smaller data sets, repeatedly processing the data can be cheaper than iterating the corresponding procedures.
  • Maximum Likelihood Methods: Within EM, the O(N) method yields less-biased but more-variable parameter estimates than the O(N^2) method.These smoothing-estimator properties translate into the resulting off-line and on-line maximum-likelihood estimates.
  • Bayesian Methods: For Bayesian inference, particle methods with MCMC steps show increasing posterior-mean variability and increasingly incomplete posterior support as the time horizon grows.The relative variance rises steeply for n ≥15,000, while the average estimated posterior variance relative to the true variance decreases with time.
  • Bayesian Methods: Particle methods with MCMC steps provide reasonable results in some settings but very unreliable results in others, whereas particle Gibbs estimates can display less variability at fixed computational complexity.The comparison becomes more favorable to particle Gibbs for higher-dimensional parameters or very vague priors.

8. CONCLUSION

The conclusion organizes particle parameter-estimation methods by inference paradigm and computational setting, emphasizing trade-offs between robustness, bias, variance, and cost. It recommends methods conditionally for batch ML, while identifying on-line Bayesian inference as an unresolved challenge because current methods still suffer degeneracy.

  • 8. CONCLUSION: Early particle methods for static parameters suffered from degeneracy, motivating artificial parameter dynamics and fixed-lag approximations with difficult-to-quantify bias.More recent methods are described as asymptotically bias-free with reasonable computational cost.
  • 8. CONCLUSION: Particle methods with MCMC steps and particle Gibbs are compared through estimated marginal posterior densities for θ = (ρ,σ2) across increasing computational settings.The figures use T = 10^3 over 50 runs, varying particle counts and particle-Gibbs iterations.
  • 8. CONCLUSION: For batch ML, forward filter backward sampler/smoother and generalized two-filter procedures are recommended when their direct O(N^2T) cost can be reduced to O(NT).Without this reduction, their benefits are limited relative to a standard particle filter using N^2 particles.
  • 8. CONCLUSION: For on-line ML, forward smoothing is crucial for gradient ascent but has limited interest for on-line EM when it costs O(N^2) per time step.The conclusion contrasts this with the computational role of standard particle filtering using N^2 particles.
  • 8. CONCLUSION: Batch Bayesian inference can use particle MCMC, but efficient PMMH implementations have computational complexity of order O(T^2) per iteration.This makes computational expense a central limitation of the batch Bayesian approach discussed.
  • 8. CONCLUSION: On-line Bayesian inference remains a challenging open problem because currently available methods, including particle methods with MCMC moves, suffer from degeneracy.The conclusion notes that these methods should not be ruled out despite this limitation.
Loading 1412.8695v2…