FANDOM


File:Particle filter example small.png

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, \beta_k

for k=0,1,2,3, \cdots

, based only observed data y_k

for k=0,1,2,3, \cdots

. This method requires:

  • \beta_0, \beta_1, \cdots
is a Markov process such that
  • \beta_k|\beta_{k-1} \sim p_{\beta_k|\beta_{k-1}}(\beta|\beta_{k-1})
  • y_0, y_1, \cdots
are conditionally independent provided that \beta_0, \beta_1, \cdots
are known
  • Each y_k
only depends on \beta_k
  • y_k|\beta_k \sim p_{y|\beta}(y|\beta_k)


One example form of this scenario is

\beta_k = f(\beta_{k-1}) + w_k
y_k = h(\beta_k) + x_k


where both w_k

and x_k
are independent and identitically distributed sequences with known probability density functions and f()
& g()
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 \beta

at k
from p_{\beta_k|y_{1:k}}(\beta|y_{1:k})
1) Set p=1
2) Uniformly generate L from [0, P]


3) Generate a test \hat{\beta}
from its distribution p_{\beta_k|\beta_{k-1}}(\beta|\beta_{k-1|k-1}^{(L)})


4) Generate the probability of \hat{y}
using \hat{\beta}
from p_{y|\beta}(y_k|\hat{\beta})
where y_k
is the measured value
5) Generate another uniform u from [0, m_k]


6) Compare u and \hat{y}


6a) If u is larger then repeat from step 2
6b) If u is smaller then save \hat{\beta}
as \beta{k|k}^{(p)}
and increment p
7) If p > P then quit

The goal is to generate P "particles" at k

using only the particles from k-1

. This requires that a Markov equation can be written (and computed) to generate a \beta_k

based only upon \beta_{k-1}

. This algorithm uses composition of the P particles from k-1

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 \beta

is viewed as a two-dimensional array.

One dimension is k

and the other dimensions is the particle number.

For example, \beta(k,L)

would be the Lth particle at k
and can also be written \beta_k^{(L)}
(as done above in the algorithm).

Step 3 generates a potential \beta_k

based on a randomly chosen particle (\beta_{k-1}^{(L)}

) at time k-1

and rejects or accepts it in step 6.

In other words, the \beta_k

values are generated using the previously generated \beta_{k-1}

.


Generally, this algorithm is repeated iteratively for a specific number of k

values (call this N

). Initializing \beta_k=0|_{k=0}

for all particles provides a starting place to generate \beta_1

, which can then be used to generate \beta_2 , which can be used to generate \beta_3

and so on up to k=N

. When done, the mean of \beta_k

over all the particles (or \frac{1}{P}\sum_{L=1}^P \beta_k^{(L)}

) is approximately the actual value of \beta_k .

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

Ad blocker interference detected!


Wikia is a free-to-use site that makes money from advertising. We have a modified experience for viewers using ad blockers

Wikia is not accessible if you’ve made further modifications. Remove the custom ad blocker rule(s) and the page will load as expected.