Particle filter

# Particle filter

Overview

Discussion

Recent Discussions
Encyclopedia

In statistics
Statistics
Statistics is the study of the collection, organization, analysis, and interpretation of data. It deals with all aspects of this, including the planning of data collection in terms of the design of surveys and experiments....

, particle filters, also known as Sequential Monte Carlo method
Monte Carlo method
Monte Carlo methods are a class of computational algorithms that rely on repeated random sampling to compute their results. Monte Carlo methods are often used in computer simulations of physical and mathematical systems...

s
(SMC), are sophisticated model estimation
Estimation
Estimation is the calculated approximation of a result which is usable even if input data may be incomplete or uncertain.In statistics,*estimation theory and estimator, for topics involving inferences about probability distributions...

techniques based on simulation
Simulation
Simulation is the imitation of some real thing available, state of affairs, or process. The act of simulating something generally entails representing certain key characteristics or behaviours of a selected physical or abstract system....

. Particle filters have important applications in econometrics
Econometrics
Econometrics has been defined as "the application of mathematics and statistical methods to economic data" and described as the branch of economics "that aims to give empirical content to economic relations." More precisely, it is "the quantitative analysis of actual economic phenomena based on...

, and in other fields.

Particle filters are usually used to estimate Bayesian models in which the latent variable
Latent variable
In statistics, latent variables , are variables that are not directly observed but are rather inferred from other variables that are observed . Mathematical models that aim to explain observed variables in terms of latent variables are called latent variable models...

s are connected in a Markov chain
Markov chain
A Markov chain, named after Andrey Markov, is a mathematical system that undergoes transitions from one state to another, between a finite or countable number of possible states. It is a random process characterized as memoryless: the next state depends only on the current state and not on the...

— similar to a hidden Markov model
Hidden Markov model
A hidden Markov model is a statistical Markov model in which the system being modeled is assumed to be a Markov process with unobserved states. An HMM can be considered as the simplest dynamic Bayesian network. The mathematics behind the HMM was developed by L. E...

(HMM), but typically where the state space of the latent variables is continuous rather than discrete, and not sufficiently restricted to make exact inference tractable (as, for example, in a linear dynamical system
Linear dynamical system
Linear dynamical systems are a special type of dynamical system where the equation governing the system's evolution is linear. While dynamical systems in general do not have closed-form solutions, linear dynamical systems can be solved exactly, and they have a rich set of mathematical properties...

, where the state space of the latent variables is restricted to Gaussian distributions and hence exact inference can be done efficiently using a Kalman filter
Kalman filter
In statistics, the Kalman filter is a mathematical method named after Rudolf E. Kálmán. Its purpose is to use measurements observed over time, containing noise and other inaccuracies, and produce values that tend to be closer to the true values of the measurements and their associated calculated...

). In the context of HMMs and related models, "filtering" refers to determining the distribution of a latent variable at a specific time, given all observations up to that time; particle filters are so named because they allow for approximate "filtering" (in the sense just given) using a set of "particles" (differently-weighted samples of the distribution).

Particle filters are the sequential
Sequential estimation
In statistics, sequential estimation refers to estimation methods in sequential analysis where the sample size is not fixed in advance. Instead, data is evaluated as it is collected, and further sampling is stopped in accordance with a pre-defined stopping rule as soon as significant results are...

("on-line") analogue of Markov chain Monte Carlo
Markov chain Monte Carlo
Markov chain Monte Carlo methods are a class of algorithms for sampling from probability distributions based on constructing a Markov chain that has the desired distribution as its equilibrium distribution. The state of the chain after a large number of steps is then used as a sample of the...

(MCMC) batch methods and are often similar to importance sampling
Importance sampling
In statistics, importance sampling is a general technique for estimating properties of a particular distribution, while only having samples generated from a different distribution rather than the distribution of interest. It is related to Umbrella sampling in computational physics...

methods. Well-designed particle filters can often be much faster than MCMC. They are often an alternative to the Extended Kalman filter (EKF) or Unscented Kalman filter (UKF) with the advantage that, with sufficient samples, they approach the Bayesian optimal estimate, so they can be made more accurate than either the EKF or UKF. However, when the simulated sample is not sufficiently large, they might suffer from sample impoverishment. The approaches can also be combined by using a version of the Kalman filter as a proposal distribution for the particle filter.

## Goal

The particle filter aims to estimate the sequence of hidden parameters, xk for k = 0,1,2,3,…, based only on the observed data yk for k = 0,1,2,3,…. All Bayesian estimates of xk follow from the posterior distribution p(xk | y0,y1,…,yk). In contrast, the MCMC or importance sampling approach would model the full posterior p(x0,x1,…,xk | y0,y1,…,yk).

## Model

Particle methods assume and the observations can be modeled in this form:
• is a first order Markov process
Markov process
In probability theory and statistics, a Markov process, named after the Russian mathematician Andrey Markov, is a time-varying random phenomenon for which a specific property holds...

such that

and with an initial distribution .
• The observations are conditionally independent provided that are known
In other words, each only depends on

One example form of this scenario is

where both and are mutually independent and identically distributed sequences with known probability density function
Probability density function
In probability theory, a probability density function , or density of a continuous random variable is a function that describes the relative likelihood for this random variable to occur at a given point. The probability for the random variable to fall within a particular region is given by the...

s and and are known functions.
These two equations can be viewed as state space
State space (controls)
In control engineering, a state space representation is a mathematical model of a physical system as a set of input, output and state variables related by first-order differential equations...

equations and look similar to the state space equations for the Kalman filter. If the functions and are linear, and if both and are Gaussian
GAUSSIAN
Gaussian is a computational chemistry software program initially released in 1970 by John Pople and his research group at Carnegie-Mellon University as Gaussian 70. It has been continuously updated since then...

, 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 probability distribution is Gaussian a third-order approximation is possible). Particle filters are also an approximation, but with enough particles they can be much more accurate.

## Monte Carlo approximation

Particle methods, like all sampling-based approaches (e.g., MCMC), generate a set of samples that approximate the filtering distribution . So, with samples, expectations with respect to the filtering distribution are approximated by

and , in the usual way for Monte Carlo, can give all the moments
Moment (mathematics)
In mathematics, a moment is, loosely speaking, a quantitative measure of the shape of a set of points. The "second moment", for example, is widely used and measures the "width" of a set of points in one dimension or in higher dimensions measures the shape of a cloud of points as it could be fit by...

etc. of the distribution up to some degree of approximation.

## Sequential Importance Resampling (SIR)

Sequential importance resampling
Resampling (statistics)
In statistics, resampling is any of a variety of methods for doing one of the following:# Estimating the precision of sample statistics by using subsets of available data or drawing randomly with replacement from a set of data points # Exchanging labels on data points when performing significance...

(SIR)
, the original particle filtering algorithm (Gordon et al. 1993), is a very commonly used
particle filtering algorithm, which approximates the filtering
distribution by a weighted set
of P particles
.

The importance weights are approximations to
the relative posterior probabilities (or densities) of the particles
such that .

SIR is a sequential (i.e., recursive) version of importance sampling
Importance sampling
In statistics, importance sampling is a general technique for estimating properties of a particular distribution, while only having samples generated from a different distribution rather than the distribution of interest. It is related to Umbrella sampling in computational physics...

.
As in importance sampling, the expectation of a function
can be approximated as a weighted average

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

The optimal proposal distribution is given as the target distribution

However, the transition prior is often used as importance function, since it is easier to draw particles (or samples) and perform subsequent importance weight calculations:

Sequential Importance Resampling (SIR) filters with transition prior as importance function are commonly known as bootstrap filter and condensation algorithm
Condensation algorithm
The condensation algorithm is a computer vision algorithm. The principal application is to detect and track the contour of objects moving in a cluttered environment. Object tracking is one of the more basic and difficult aspects of computer vision and is generally a prerequisite to object...

.

Resampling is used to avoid the problem of degeneracy of the
algorithm, that is, avoiding the situation that all but one of the
importance weights are close to zero. The performance of the algorithm
can be also affected by proper choice of resampling method. The
stratified sampling
Stratified sampling
In statistics, stratified sampling is a method of sampling from a population.In statistical surveys, when subpopulations within an overall population vary, it is advantageous to sample each subpopulation independently. Stratification is the process of dividing members of the population into...

proposed by Kitagawa (1996) is optimal in
terms of variance.

A single step of sequential importance resampling is as follows:
1) For draw samples from the proposal distribution

2) For update the importance weights up to a normalizing constant:

Note that when we use the transition prior as the importance function, , this simplifies to the following :

3) For compute the normalized importance weights:

4) Compute an estimate of the effective number of particles as

5) If the effective number of particles is less than a given threshold , then perform resampling:

a) Draw particles from the current particle set with probabilities proportional to their weights. Replace the current particle set with this new one.

b) For set

The term Sampling Importance Resampling is also sometimes used when referring to SIR filters.

## Sequential Importance Sampling (SIS)

• Is the same as Sequential Importance Resampling, but without the resampling stage.

## "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 at from :
1) Set n=0 (This will count the number of particles generated so far)

2) Uniformly choose an index L from the range

3) Generate a test from the distribution

4) Generate the probability of using from where is the measured value

5) Generate another uniform
Uniform distribution (continuous)
In probability theory and statistics, the continuous uniform distribution or rectangular distribution is a family of probability distributions such that for each member of the family, all intervals of the same length on the distribution's support are equally probable. The support is defined by...

u from

6) Compare u and

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

6b) If u is smaller then save as and increment n

7) If n P then quit

The goal is to generate P "particles" at using only the particles from .
This requires that a Markov equation can be written (and computed) to generate a based only upon .
This algorithm uses composition of the P particles from to generate a particle at and repeats (steps 2-6) until P particles are generated at .

This can be more easily visualized if is viewed as a two-dimensional array.
One dimension is and the other dimensions is the particle number.
For example, would be the Lth particle at and can also be written (as done above in the algorithm).
Step 3 generates a potential based on a randomly chosen particle () at time and rejects or accepts it in step 6.
In other words, the values are generated using the previously generated .
Other Particle Filters