Particle filters, also known as sequential Monte Carlo methods, are a set of Monte Carlo algorithms used to find approximate solutions for filtering problems for nonlinear state-space systems, such as signal processing and Bayesian statistical inference. The filtering problem consists of estimating the internal states in dynamical systems when partial observations are made and random perturbations are present in the sensors as well as in the dynamical system. The objective is to compute the posterior distributions of the states of a Markov process, given the noisy and partial observations. The term "particle filters" was first coined in 1996 by Pierre Del Moral about mean-field interacting particle methods used in fluid mechanics since the beginning of the 1960s. The term "Sequential Monte Carlo" was coined by Jun S. Liu and Rong Chen in 1998.

Particle filtering uses a set of particles (also called samples) to represent the posterior distribution of a stochastic process given the noisy and/or partial observations. The state-space model can be nonlinear and the initial state and noise distributions can take any form required. Particle filter techniques provide a well-established methodology for generating samples from the required distribution without requiring assumptions about the state-space model or the state distributions. However, these methods do not perform well when applied to very high-dimensional systems.

Particle filters update their prediction in an approximate (statistical) manner. The samples from the distribution are represented by a set of particles; each particle has a likelihood weight assigned to it that represents the probability of that particle being sampled from the probability density function. Weight disparity leading to weight collapse is a common issue encountered in these filtering algorithms. However, it can be mitigated by including a resampling step before the weights become uneven. Several adaptive resampling criteria can be used including the variance of the weights and the relative entropy concerning the uniform distribution. In the resampling step, the particles with negligible weights are replaced by new particles in the proximity of the particles with higher weights.

From the statistical and probabilistic point of view, particle filters may be interpreted as mean-field particle interpretations of Feynman-Kac probability measures. These particle integration techniques were developed in molecular chemistry and computational physics by Theodore E. Harris and Herman Kahn in 1951, Marshall N. Rosenbluth and Arianna W. Rosenbluth in 1955, and more recently by Jack H. Hetherington in 1984. Feynman-Kac interacting particle methods are also strongly related to mutation-selection genetic algorithms currently used in evolutionary computation to solve complex optimization problems.

The particle filter methodology is used to solve Hidden Markov Model (HMM) and nonlinear filtering problems. With the notable exception of linear-Gaussian signal-observation models (Kalman filter) or wider classes of models (Benes filter), Mireille Chaleyat-Maurel and Dominique Michel proved in 1984 that the sequence of posterior distributions of the random states of a signal, given the observations (a.k.a. optimal filter), has no finite recursion. Various other numerical methods based on fixed grid approximations, Markov Chain Monte Carlo techniques, conventional linearization, extended Kalman filters, or determining the best linear system (in the expected cost-error sense) are unable to cope with large-scale systems, unstable processes, or insufficiently smooth nonlinearities.

Particle filters and Feynman-Kac particle methodologies find application in signal and image processing, Bayesian inference, machine learning, risk analysis and rare event sampling, engineering and robotics, artificial intelligence, bioinformatics, phylogenetics, computational science, economics and mathematical finance, molecular chemistry, computational physics, pharmacokinetics, quantitative risk and insurance and other fields.

History

Heuristic-like algorithms

From a statistical and probabilistic viewpoint, particle filters belong to the class of branching/genetic type algorithms, and mean-field type interacting particle methodologies. The interpretation of these particle methods depends on the scientific discipline. In Evolutionary Computing, mean-field genetic type particle methodologies are often used as heuristic and natural search algorithms (a.k.a. Metaheuristic). In computational physics and molecular chemistry, they are used to solve Feynman-Kac path integration problems or to compute Boltzmann-Gibbs measures, top eigenvalues, and ground states of Schrödinger operators. In Biology and Genetics, they represent the evolution of a population of individuals or genes in some environment.

The origins of mean-field type evolutionary computational techniques can be traced back to 1950 and 1954 with Alan Turing's work on genetic type mutation-selection learning machines and the articles by Nils Aall Barricelli at the Institute for Advanced Study in Princeton, New Jersey. The first trace of particle filters in statistical methodology dates back to the mid-1950s; the 'Poor Man's Monte Carlo', that was proposed by John Hammersley et al., in 1954, contained hints of the genetic type particle filtering methods used today. In 1963, Nils Aall Barricelli simulated a genetic type algorithm to mimic the ability of individuals to play a simple game. In evolutionary computing literature, genetic-type mutation-selection algorithms became popular through the seminal work of John Holland in the early 1970s, particularly his book published in 1975.

In Biology and Genetics, the Australian geneticist Alex Fraser also published in 1957 a series of papers on the genetic type simulation of artificial selection of organisms. The computer simulation of the evolution by biologists became more common in the early 1960s, and the methods were described in books by Fraser and Burnell (1970) and Crosby (1973). Fraser's simulations included all of the essential elements of modern mutation-selection genetic particle algorithms.

From the mathematical viewpoint, the conditional distribution of the random states of a signal given some partial and noisy observations is described by a Feynman-Kac probability on the random trajectories of the signal weighted by a sequence of likelihood potential functions. The origins of Quantum Monte Carlo methods are often attributed to Enrico Fermi and Robert Richtmyer who developed in 1948 a mean-field particle interpretation of neutron chain reactions, but the first heuristic-like and genetic type particle algorithm (a.k.a. Resampled or Reconfiguration Monte Carlo methods) for estimating ground state energies of quantum systems (in reduced matrix models) is due to Jack H. Hetherington in 1984. In molecular chemistry, the use of genetic heuristic-like particle methodologies (a.k.a. pruning and enrichment strategies) can be traced back to 1955 with the seminal work of Marshall N. Rosenbluth and Arianna W. Rosenbluth. a slightly modified version of this article appeared in 1996. In April 1993, Neil J. Gordon et al., published in their seminal work an application of genetic type algorithm in Bayesian statistical inference. The authors named their algorithm 'the bootstrap filter', and demonstrated that compared to other filtering methods, their bootstrap algorithm does not require any assumption about that state space or the noise of the system. Independently, the ones by Pierre Del Moral on particle filters published in the mid-1990s. Particle filters were also developed in signal processing in early 1989–1992 by P. Del Moral, J.C. Noyer, G. Rigal, and G. Salut in the LAAS-CNRS in a series of restricted and classified research reports with STCAN (Service Technique des Constructions et Armes Navales), the IT company DIGILOG, and the LAAS-CNRS (the Laboratory for Analysis and Architecture of Systems) on RADAR/SONAR and GPS signal processing problems.

Mathematical foundations

From 1950 to 1996, all the publications on particle filters, and genetic algorithms, including the pruning and resample Monte Carlo methods introduced in computational physics and molecular chemistry, present natural and heuristic-like algorithms applied to different situations without a single proof of their consistency, nor a discussion on the bias of the estimates and genealogical and ancestral tree-based algorithms.

The mathematical foundations and the first rigorous analysis of these particle algorithms are due to Pierre Del Moral as well as Pierre Del Moral, and Terry Lyons, created branching-type particle techniques with various population sizes around the end of the 1990s. P. Del Moral, A. Guionnet, and L. Miclo proved the first central limit theorems in 1999, and Pierre Del Moral and Laurent Miclo The first rigorous analysis of genealogical tree-based particle filter smoothers is due to P. Del Moral and L. Miclo in 2001

The theory on Feynman-Kac particle methodologies and related particle filter algorithms was developed in 2000 and 2004 in the books.), importance sampling and resampling style particle filter techniques, including genealogical tree-based and particle backward methodologies for solving filtering and smoothing problems. Other classes of particle filtering methodologies include genealogical tree-based models, backward Markov particle models, adaptive mean-field particle models, particle Markov chain Monte Carlo methodologies, Sequential Monte Carlo samplers and Sequential Monte Carlo Approximate Bayesian Computation methods and Sequential Monte Carlo ABC based Bayesian Bootstrap.

The filtering problem

Objective

A particle filter's goal is to estimate the posterior density of state variables given observation variables. The particle filter is intended for use with a hidden Markov Model, in which the system includes both hidden and observable variables. The observable variables (observation process) are linked to the hidden variables (state-process) via a known functional form. Similarly, the probabilistic description of the dynamical system defining the evolution of the state variables is known.

A generic particle filter estimates the posterior distribution of the hidden states using the observation measurement process. With respect to a state-space such as the one below:

:<math>\begin{array}{cccccccccc}

X_0&\to &X_1&\to &X_2&\to&X_3&\to &\cdots&\text{signal}\\

\downarrow&&\downarrow&&\downarrow&&\downarrow&&\cdots&\\

Y_0&&Y_1&&Y_2&&Y_3&&\cdots&\text{observation}

\end{array}</math>

the filtering problem is to estimate sequentially the values of the hidden states <math>X_k</math>, given the values of the observation process <math>Y_0,\cdots,Y_k,</math> at any time step k.

All Bayesian estimates of <math>X_k</math> follow from the posterior density <math>p(x_k|y_0,y_1,...,y_k)</math>. The particle filter methodology provides an approximation of these conditional probabilities using the empirical measure associated with a genetic type particle algorithm. In contrast, the Markov Chain Monte Carlo or importance sampling approach would model the full posterior <math>p(x_0,x_1,...,x_k|y_0,y_1,...,y_k)</math>.

The Signal-Observation model

Particle methods often assume <math>X_k</math> and the observations <math>Y_k</math> can be modeled in this form:

  • <math>X_0, X_1, \cdots</math> is a Markov process on <math>\mathbb R^{d_x}</math> (for some <math>d_x\geqslant 1</math>) that evolves according to the transition probability density <math>p(x_k|x_{k-1})</math>. This model is also often written in a synthetic way as
  • :<math>X_k|X_{k-1}=x_k \sim p(x_k|x_{k-1})</math>

:with an initial probability density <math>p(x_0)</math>.

  • The observations <math>Y_0, Y_1, \cdots</math> take values in some state space on <math>\mathbb{R}^{d_y}</math> (for some <math>d_y\geqslant 1</math>) and are conditionally independent provided that <math>X_0, X_1, \cdots</math> are known. In other words, each <math>Y_k</math> only depends on <math>X_k</math>. In addition, we assume conditional distribution for <math>Y_k</math> given <math>X_k=x_k</math> are absolutely continuous, and in a synthetic way we have
  • :<math>Y_k|X_k=y_k \sim p(y_k|x_k)</math>

An example of system with these properties is:

:<math>X_k = g(X_{k-1}) + W_{k-1}</math>

:<math>Y_k = h(X_k) + V_k</math>

where both <math>W_k</math> and <math>V_k</math> are mutually independent sequences with known probability density functions and g and h are known functions. These two equations can be viewed as state space equations and look similar to the state space equations for the Kalman filter. If the functions g and h in the above example are linear, and if both <math>W_k</math> and <math>V_k</math> are Gaussian, the Kalman filter finds the exact Bayesian filtering distribution. If not, Kalman filter-based methods are a first-order approximation (EKF) or a second-order approximation (UKF in general, but if the probability distribution is Gaussian a third-order approximation is possible).

The assumption that the initial distribution and the transitions of the Markov chain are continuous for the Lebesgue measure can be relaxed. To design a particle filter we simply need to assume that we can sample the transitions <math>X_{k-1} \to X_k</math> of the Markov chain <math>X_k,</math> and to compute the likelihood function <math>x_k\mapsto p(y_k|x_k)</math> (see for instance the genetic selection mutation description of the particle filter given below). The continuous assumption on the Markov transitions of <math>X_k</math> is only used to derive in an informal (and rather abusive) way different formulae between posterior distributions using the Bayes' rule for conditional densities.

Approximate Bayesian computation models

In certain problems, the conditional distribution of observations, given the random states of the signal, may fail to have a density; the latter may be impossible or too complex to compute. They were further developed by P. Del Moral, A. Doucet and A. Jasra.

The nonlinear filtering equation

Bayes' rule for conditional probability gives:

:<math>p(x_0, \cdots, x_k|y_0,\cdots,y_k) =\frac{p(y_0,\cdots,y_k|x_0, \cdots, x_k) p(x_0,\cdots,x_k)}{p(y_0,\cdots,y_k)}</math>

where

:<math>\begin{align}

p(y_0,\cdots,y_k) &=\int p(y_0,\cdots,y_k|x_0,\cdots, x_k) p(x_0,\cdots,x_k) dx_0\cdots dx_k \\

p(y_0,\cdots, y_k|x_0,\cdots ,x_k) &=\prod_{l=0}^{k} p(y_l|x_l) \\

p(x_0,\cdots, x_k) &=p_0(x_0)\prod_{l=1}^{k} p(x_l|x_{l-1})

\end{align}</math>

Particle filters are also an approximation, but with enough particles they can be much more accurate. More recent developments can be found in the books,

Some convergence results

We shall assume that filtering equation is stable, in the sense that it corrects any erroneous initial condition.

In this situation, the particle approximations of the likelihood functions are unbiased and the relative variance is controlled by

:<math>E\left(\widehat{p}(y_0,\cdots,y_n)\right)= p(y_0,\cdots,y_n), \qquad E\left(\left[\frac{\widehat{p}(y_0,\cdots,y_n)}{p(y_0,\cdots,y_n)}-1\right]^2\right)\leqslant \frac{cn}{N},</math>

for some finite constant c. In addition, for any <math>x\geqslant 0</math>:

:<math>\mathbf{P} \left ( \left\vert \frac{1}{n}\log{\widehat{p}(y_0,\cdots,y_n)}-\frac{1}{n}\log{p(y_0,\cdots,y_n)}\right\vert \leqslant c_1 \frac{x}{N}+c_2 \sqrt{\frac{x}{N \right ) > 1-e^{-x} </math>

for some finite constants <math>c_1, c_2</math> related to the asymptotic bias and variance of the particle estimate, and for some finite constant c.

The bias and the variance of the particle particle estimates based on the ancestral lines of the genealogical trees

:<math>\begin{align}

I^{path}_k(F) &:=\int F(x_0,\cdots,x_k) p(d(x_0,\cdots,x_k)|y_0,\cdots,y_{k-1}) \\

&\approx_{N\uparrow\infty} \widehat{I}^{path}_k(F) \\

&:=\int F(x_0,\cdots,x_k) \widehat{p}(d(x_0,\cdots,x_k)|y_0,\cdots,y_{k-1}) \\

&=\frac{1}{N}\sum_{i=1}^N F\left(\xi^i_{0,k},\cdots,\xi^i_{k,k}\right)

\end{align}</math>

are controlled by the non asymptotic uniform estimates

:<math>\left| E\left(\widehat{I}^{path}_k(F)\right)-I_k^{path}(F)\right|\leqslant \frac{c_1 k}{N}, \qquad E\left(\left[\widehat{I}^{path}_k(F)-I_k^{path}(F)\right]^2\right)\leqslant \frac{c_2 k}{N},</math>

for any function F bounded by 1, and for some finite constants <math>c_1, c_2.</math> In addition, for any <math>x\geqslant 0</math>:

:<math>\mathbf{P} \left ( \left| \widehat{I}^{path}_k(F)-I_k^{path}(F)\right | \leqslant c_1 \frac{kx}{N}+c_2 \sqrt{\frac{kx}{N \land \sup_{0\leqslant k\leqslant n}\left| \widehat{I}_k^{path}(F)-I^{path}_k(F)\right| \leqslant c \sqrt{\frac{xn\log(n)}{N \right ) > 1-e^{-x}</math>

for some finite constants <math>c_1, c_2</math> related to the asymptotic bias and variance of the particle estimate, and for some finite constant c. The same type of bias and variance estimates hold for the backward particle smoothers. For additive functionals of the form

:<math>\overline{F}(x_0,\cdots,x_n):=\frac{1}{n+1}\sum_{0\leqslant k\leqslant n}f_k(x_k)</math>

with

:<math>I^{path}_n(\overline{F}) \approx_{N\uparrow\infty} I^{\flat, path}_n(\overline{F}):=\int \overline{F}(x_0,\cdots,x_n) \widehat{p}_{backward}(d(x_0,\cdots,x_n)|(y_0,\cdots,y_{n-1}))</math>

with functions <math>f_k</math> bounded by 1, we have

:<math>\sup_{n\geqslant 0}{\left\vert E\left(\widehat{I}^{\flat,path}_n(\overline{F})\right)-I_n^{path}(\overline{F})\right\vert} \leqslant \frac{c_1}{N}</math>

and

:<math>E\left(\left[\widehat{I}^{\flat,path}_n(F)-I_n^{path}(F)\right]^2\right)\leqslant \frac{c_2}{nN}+ \frac{c_3}{N^2}</math>

for some finite constants <math>c_1,c_2,c_3.</math> More refined estimates including exponentially small probability of errors are developed in.), are also commonly applied filtering algorithms, which approximate the filtering probability density <math>p(x_k|y_0,\cdots,y_k)</math> by a weighted set of N samples

: <math> \left \{ \left (w^{(i)}_k,x^{(i)}_k \right ) \ : \ i\in\{1,\cdots,N\} \right \}.</math>

The importance weights <math>w^{(i)}_k</math> are approximations to the relative posterior probabilities (or densities) of the samples such that

:<math>\sum_{i=1}^N w^{(i)}_k = 1.</math>

Sequential importance sampling (SIS) is a sequential (i.e., recursive) version of importance sampling. As in importance sampling, the expectation of a function f can be approximated as a weighted average

: <math> \int f(x_k) p(x_k|y_0,\dots,y_k) dx_k \approx \sum_{i=1}^N w_k^{(i)} f(x_k^{(i)}).</math>

For a finite set of samples, the algorithm performance is dependent on the choice of the proposal distribution

: <math>\pi(x_k|x_{0:k-1},y_{0:k})\, </math>.

The "optimal" proposal distribution is given as the target distribution

: <math>\pi(x_k|x_{0:k-1},y_{0:k}) = p(x_k|x_{k-1},y_{k})=\frac{p(y_k|x_k)}{\int p(y_k|x_k)p(x_k|x_{k-1})dx_k}~p(x_k|x_{k-1}).</math>

This particular choice of proposal transition has been proposed by P. Del Moral in 1996 and 1998.

Sequential importance sampling (SIS)

Sequential importance sampling (SIS) is the same as the SIR algorithm but without the resampling stage. This version often exhibits particle weight collapse, where all the probability gets concentrated on one or two particles, and the rest of the particle weights correspond to very small probability. The introduction of resampling alleviates this problem.

"Direct version" algorithm

The "direct version" algorithm is rather simple (compared to other particle filtering algorithms) and it uses composition and rejection. To generate a single sample x at k from <math>p_{x_k|y_{1:k(x|y_{1:k})</math>:

:1) Set n = 0 (This will count the number of particles generated so far)

:2) Uniformly choose an index i from the range <math>\{1,..., N\}</math>

:3) Generate a test <math>\hat{x}</math> from the distribution <math>p(x_k|x_{k-1})</math> with <math> x_{k-1}=x_{k-1|k-1}^{(i)}</math>

:4) Generate the probability of <math>\hat{y}</math> using <math>\hat{x}</math> from <math>p(y_k|x_k),~\mbox{with}~x_k=\hat{x}</math> where <math>y_k</math> is the measured value

:5) Generate another uniform u from <math>[0, m_k]</math> where <math>m_k = \sup_{x_k} p(y_k|x_k) </math>

:6) Compare u and <math>p\left(\hat{y}\right)</math>

::6a) If u is larger then repeat from step 2

::6b) If u is smaller then save <math>\hat{x}</math> as <math>x_{k|k}^{(i)}</math> and increment n

:7) If n == N then quit

The goal is to generate P "particles" at k using only the particles from <math>k-1</math>. This requires that a Markov equation can be written (and computed) to generate a <math>x_k</math> based only upon <math>x_{k-1}</math>. This algorithm uses the composition of the P particles from <math>k-1</math> to generate a particle at k and repeats (steps 2–6) until P particles are generated at k.

This can be more easily visualized if x is viewed as a two-dimensional array. One dimension is k and the other dimension is the particle number. For example, <math>x(k,i)</math> would be the i<sup>th</sup> particle at <math>k</math> and can also be written <math>x_k^{(i)}</math> (as done above in the algorithm). Step 3 generates a potential <math>x_k</math> based on a randomly chosen particle (<math>x_{k-1}^{(i)}</math>) at time <math>k-1</math> and rejects or accepts it in step 6. In other words, the <math>x_k</math> values are generated using the previously generated <math>x_{k-1}</math>.

Applications

Particle filters and Feynman-Kac particle methodologies find application in several contexts, as an effective mean for tackling noisy observations or strong nonlinearities, such as:

  • Bayesian inference, machine learning, risk analysis and rare event sampling
  • Bioinformatics
  • Engineering
  • Infectious disease epidemiology where they have been applied to a number of epidemic forecasting problems, for example predicting seasonal influenza epidemics
  • Fault detection and isolation: in observer-based schemas a particle filter can forecast expected sensors output enabling fault isolation
  • Molecular chemistry and computational physics
  • Pharmacokinetics
  • Phylogenetics
  • Robotics, artificial intelligence: Monte Carlo localization is a de facto standard in mobile robot localization
  • Signal and image processing: visual localization, tracking, feature recognition

Other particle filters

  • Auxiliary particle filter
  • Cost Reference particle filter
  • Exponential Natural Particle Filter
  • Feynman-Kac and mean-field particle methodologies
  • Nudged particle filter
  • Particle Markov-Chain Monte-Carlo, see e.g. pseudo-marginal Metropolis–Hastings algorithm.
  • Rao–Blackwellized particle filter
  • Rejection-sampling based optimal particle filter
  • Unscented particle filter
  • Online particle smoother