Particle Filter

particle-filtersequential-monte-carlostate-spacefilteringsimulationbayesian

Definition

A particle filter (sequential Monte Carlo, SMC) is a simulation method for on-line filtering in a non-linear / non-Gaussian state-space model — recursively approximating the filtering distribution f(αt∣Ft)f(\alpha_t\mid\mathcal F_t) of a Markovian latent state αt\alpha_t given the data Ft=(y1,…,yt)\mathcal F_t=(y_1,\dots,y_t) observed so far. The continuous state is represented by a swarm of MM weighted particles {αtj,πtj}j=1M\{\alpha_t^j,\pi_t^j\}_{j=1}^M — a discrete distribution with random support that converges to the true filtering density as M→∞M\to\infty. As each new observation arrives, the particles are propagated through the state transition, reweighted by the likelihood, and resampled, so the data can be processed in a single forward sweep. It is the Monte Carlo counterpart of the Kalman filter, which is exact only in the linear-Gaussian case.

Key Ideas

How It Works

The bootstrap / SIR filter (Gordon–Salmond–Smith 1993). Treat 1M∑jf(αt+1∣αtj)\tfrac1M\sum_j f(\alpha_{t+1}\mid\alpha_t^j) as a prior: (1) draw a parent jj with probability πtj\pi_t^j and propagate αt+1∼f(⋅∣αtj)\alpha_{t+1}\sim f(\cdot\mid\alpha_t^j); (2) reweight by the likelihood f(yt+1∣αt+1)f(y_{t+1}\mid\alpha_{t+1}); (3) resample MM particles with those weights. Simple, but it propagates before seeing where the data are, so a surprising observation or a sharp likelihood leaves almost all particles with negligible weight.

The auxiliary particle filter (APF; Pitt–Shephard 1999). Augment the target with an auxiliary index kk for the parent particle and resample before propagating, using a look-ahead at the next observation: pre-weight each parent by the likelihood evaluated at a representative point of its predictive distribution (e.g. its mean μt+1j\mu_{t+1}^j), select promising parents, propagate them, then apply a second-stage correction weight. This adapts the proposal to the incoming data and dramatically reduces degeneracy when observations are informative or extreme.

Full adaptation. A filter is fully adapted if it produces i.i.d. draws from the exact one-step target f(αt+1∣Ft+1)f(\alpha_{t+1}\mid\mathcal F_{t+1}) — the ideal proposal. The APF approximates full adaptation cheaply (and achieves it exactly in conditionally-Gaussian cases). One-step sampling can use sampling/importance-resampling, rejection sampling, or MCMC.

Why It Matters

Open Questions

Related