The particle filter aims to estimate the hidden parameters,
, based only observed data
. This method requires:
is a Markov process such that
are conditionally independent provided that are known
only depends on
One example form of this scenario is
and are independent and identitically distributed sequences with known probability density functions and & are known functions.
"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
- 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.
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
Generally, this algorithm is repeated iteratively for a specific number of
values (call this
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 .
- 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