Particle filter methods, also known as Sequential Monte Carlo (SMC), are sophisticated model estimation techniques based on simulation.
They are usually used to estimate Bayesian models and are the sequential ('on-line') analogue of Markov Chain Monte Carlo (MCMC) batch methods.
GoalEdit
The particle filter aims to estimate the hidden parameters,
for
, based only observed data
for
. This method requires:
is a Markov process such that
are conditionally independent provided that are known
- Each
only depends on
One example form of this scenario is
where both
and are independent and identitically distributed sequences with known probability density functions and & are known functions.
These two equations can be viewed as state space equations and looks similar to the state space equations for the Kalman filter.
"Direct version" algorithmEdit
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 p=1
- 2) Uniformly generate L from
- 3) Generate a test
from its distribution
- 4) Generate the probability of
using from where is the measured value
- 5) Generate another uniform 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 p
- 7) If p > 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 L^{th} 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
.
Generally, this algorithm is repeated iteratively for a specific number of
values (call this
). Initializing
for all particles provides a starting place to generate
, which can then be used to generate , which can be used to generate
and so on up to
. When done, the mean of
over all the particles (or
) is approximately the actual value of .
See alsoEdit
ReferencesEdit
- Sequential Monte Carlo Methods in Practice, by A Doucet, N de Freitas and N Gordon. Published by Springer.
- Tutorial on Particle Filters for On-line Nonlinear/Non-Gaussian Bayesian Tracking (2001); S. Arulampalam, S. Maskell, N. Gordon and T. Clapp; CiteSeer link