In
statisticsStatistics 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 methodMonte 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
estimationEstimation 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
simulationSimulation 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
econometricsEconometrics 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 variableIn 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 chainA 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 modelA 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 systemLinear 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 filterIn 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
sequentialIn 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 CarloMarkov 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 samplingIn 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 processIn 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 functionIn 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 spaceIn 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
GaussianGaussian 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
momentsIn 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 resamplingIn 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 samplingIn 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 algorithmThe 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 samplingIn 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
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
- Auxiliary particle filter
The auxiliary particle filter is a particle filtering algorithm introduced by Pitt and Shephard in 1999 to improve some deficiencies of the sequential importance resampling algorithm when dealing with tailed observation densities....
- Gaussian particle filter
- Unscented particle filter
- Monte Carlo particle filter
- Gauss-Hermite particle filter
- Cost Reference particle filter
- Rao-Blackwellized particle filter
External links