Source-linked AI summary
Iterated filtering
Edward L. Ionides, Anindya Bhadra, Yves Atchadé, Aaron King
TL;DR
Inference for partially observed Markov process models requires likelihood maximization when latent dynamics are nonlinear and stochastic. The paper develops convergence theory for iterated filtering and introduces iterated importance sampling as a simpler theoretical case. Under stated conditions, the recursive estimates converge almost surely to the maximum likelihood estimate, while experiments show variance growing approximately linearly with the number of observations rather than exponentially.
Problem
Likelihood-based inference for partially observed Markov process models is methodologically challenging, despite their importance in scientific and engineering applications.
Method
The paper analyzes iterated filtering implemented with sequential Monte Carlo and first develops a Taylor-series-based iterated importance sampling theory for latent variable models.
Results
The recursive estimates converge almost surely to the maximum likelihood estimate under stated conditions, while filtering variance increases approximately linearly with the number of observations in an experiment.
Takeaways & Limitations
Iterated filtering has theoretical support as a plug-and-play likelihood-inference strategy for partially observed Markov process models.
Takeaways & Limitations
The convergence theory does not address how iterated filtering behaves as the number of observations increases under mixing assumptions.
Abstract
from arXiv · showhide
Inference for partially observed Markov process models has been a longstanding methodological challenge with many scientific and engineering applications. Iterated filtering algorithms maximize the likelihood function for partially observed Markov process models by solving a recursive sequence of filtering problems. We present new theoretical results pertaining to the convergence of iterated filtering algorithms implemented via sequential Monte Carlo filters. This theory complements the growing body of empirical evidence that iterated filtering algorithms provide an effective inference strategy for scientific models of nonlinear dynamic systems. The first step in our theory involves studying a new recursive approach for maximizing the likelihood function of a latent variable model, when this likelihood is evaluated via importance sampling. This leads to the consideration of an iterated importance sampling algorithm which serves as a simple special case of iterated filtering, and may have applicability in its own right.
1. Introduction.
The paper studies iterated filtering as a likelihood-based inference method for partially observed Markov process models and develops theory for its convergence. It first analyzes a simpler iterated importance sampling approach for latent variable models.
- POMP models support applications across science and engineering, including ecology, economics, epidemiology, finance, meteorology, neuroscience, and target tracking.
- Iterated filtering repeatedly filters at increasingly local scales to explore a likelihood surface and seek its maximum.
- The paper’s theory begins with a Taylor-series analysis for general latent variable models before extending the results to POMP models.
- Iterated importance sampling provides a simpler recursive likelihood-maximization problem that also illustrates the broader methodological approach.
- Iterated filtering and iterated importance sampling require only simulation of the unobserved process at arbitrary parameter values, enabling plug-and-play inference.
2. Iterated importance sampling.
The paper formulates iterated importance sampling for latent variable models and analyzes it as a stochastic approximation procedure. Under stated regularity and stability conditions, the recursive estimate converges to the maximum likelihood estimate.
- The latent variable framework defines a likelihood from observed data with unobserved variables, and seeks its maximum likelihood estimate.
- Iterated importance sampling perturbs the current parameter, simulates latent variables, weights them by the measurement model, and updates the estimate recursively.
- The method approximates the log-likelihood derivative through conditional moments of perturbed parameters and importance sampling.
- Monte Carlo derivative estimates involve a bias–variance trade-off, while iterated importance sampling averages numerical error across iterations.
- The convergence result is local rather than global when the iterates are constrained near a unique local maximum, and global convergence is beyond the paper’s scope.
- Theorem 2 proves almost-sure convergence to the maximum likelihood estimate under regularity, stochastic-approximation, and sequence conditions.
3. Iterated filtering for POMP models.
The paper extends iterated filtering theory to POMP models by using stochastic parameter perturbations and sequential Monte Carlo to approximate likelihood derivatives. Under regularity and rate conditions, the resulting recursive estimator converges almost surely to the maximum likelihood estimate.
- Stochastically perturbed POMP model: Iterated filtering augments a POMP with time-varying perturbed parameters, then uses filtering distributions to approximate the likelihood gradient.The perturbations are generated from a compactly supported, zero-mean density and are incorporated into an auxiliary POMP model.
- Gradient approximation: Theorem 3 bounds the approximation of ∇ℓ_N(θ) obtained from filtering means and prediction variances as the perturbation scale τ decreases.The theorem assumes σ(τ)/τ → 0 and establishes the result uniformly over compact parameter sets.
- Sequential Monte Carlo implementation: Sequential Monte Carlo implements the perturbed and unperturbed models while preserving plug-and-play simulation of the state process.The procedure uses the augmented state (X_n, Θ_n) for the perturbed model; drawing directly from the transition density is the choice that retains plug-and-play applicability.
- Scope and numerical behavior: The theory formally supports limit random-walk perturbations without mixing conditions, although future work is needed to study mixing when the number of observations increases.Experiments indicate approximately linear variance growth with the number of observations, contrasting with the exponential bound from Theorem 7.
- Monte Carlo requirements: Theorem 4 requires Monte Carlo sample sizes J_m that increase faster than τ_m^-1, while derivative-estimator variability can still grow as τ_m decreases.This motivates the stochastic-approximation recursion used to define iterated filtering.
- Convergence: Under conditions on the perturbation, step-size, and Monte Carlo sequences, the iterated filtering estimates converge almost surely to the maximum likelihood estimate.Each recursion step applies the sequential Monte Carlo filtering procedure, and the convergence result is stated in Theorem 5.
4. Discussion.
The discussion compares practical particle-filter optimization with alternative stochastic methods and examines numerical stability of the derivative estimate. Simulations show variance growing approximately linearly with observations, while bias depends on perturbation size and parameter proximity.
- Iterated filtering differs from direct likelihood optimization because particle filtering simultaneously explores parameter space while evaluating approximate likelihood information.
- Monte Carlo variance increases approximately linearly with N, substantially improving on the exponential bound guaranteed by Theorem 7.
- Variance increases as σ decreases, while bias diminishes as σ decreases and remains small when θ is close to θ∗.
- When θ is distant from θ∗, perturbed parameters migrate toward θ∗ during filtering, causing the derivative estimate to target θ∗ rather than θ.
- The resulting bias may aid iterated-filtering convergence because updates average filtered means of perturbed parameters after they locate a neighborhood of θ∗.
- The appendix combines standard sequential Monte Carlo and stochastic approximation results with the paper’s theorems to develop its theoretical understanding.
A.1. A version of a standard stochastic approximation theorem.
This appendix states a stochastic approximation result for recursive updates driven by Monte Carlo derivative estimates. Under boundedness, variance, bias, and nondivergence conditions, the proof controls the recursion through martingale arguments.
- Theorem 6 analyzes recursive updates ˆθm+1 = ˆθm + amDm(ˆθm) using independent Monte Carlo estimators of ∇ℓ(θ).
- The theorem requires Monte Carlo variance to remain uniformly controlled on bounded parameter regions and estimator bias to converge uniformly to zero.
- The proof defines centered Monte Carlo errors as martingale differences and applies the Doob–Kolmogorov martingale inequality.
- Nondivergence of the recursive sequence, together with bounds on the error events, yields convergence of their probabilities to zero.
A.2. Some standard results on sequential Monte Carlo and importance sampling.
This appendix collects sequential Monte Carlo bounds and derives a latent-variable importance-sampling corollary. The results provide particle-number-dependent control of filtered estimates and identify importance sampling as the one-step, no-resampling case.
- The general theorem is applied to both unperturbed and stochastically perturbed models, requiring uniform bounds over approximation parameters.
- The theorem’s POMP formulation uses a latent Markov process, observations, data, and particle-filter estimates of filtered means.
- Theorem 7 provides constants independent of particle number J that bound sequential Monte Carlo filtered-mean error under bounded observation densities.
- The proof expresses sequential Monte Carlo constants through recursively defined quantities and derives the required assertion by algebraic reformulation.
- Importance sampling is a special case of sequential Monte Carlo with N = 1 and no resampling step.
- For bounded functions, normalized importance-sampling estimators are compared with self-normalized estimators, with an unbiased estimator variance bounded using the likelihood contribution.