cars - Particle filter

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.

Contents

1 Goal

2 "Direct version" algorithm

3 See also

4 References

Goal

The particle filter aims to estimate the hidden parameters, $β 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 $β k$
$y_k|\beta_k \sim p_{y|\beta}(y|\beta_k)$

One example form of this scenario is

β k = f (β k - 1) + w k

y k = h (β 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" 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 $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

β 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 $β k$ based only upon $β 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 $β$ is viewed as a two-dimensional array. One dimension is $k$ and the other dimensions is the particle number. For example, $β(k, L)$ would be the L^th particle at $k$ and can also be written $\beta_k^{(L)}$ (as done above in the algorithm). Step 3 generates a potential $β 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 $β k$ values are generated using the previously generated $β k - 1$ .

Generally, this algorithm is repeated iteratively for a specific number of $k$ values (call this $N$ ). Initializing $β k = 0 | k = 0$ for all particles provides a starting place to generate $β 1$ , which can then be used to generate $β 2$ , which can be used to generate $β 3$ and so on up to $k = N$ . When done, the mean of $β k$ over all the particles (or $\frac{1}{P}\sum_{L=1}^P \beta_k^{(L)}$ ) is approximately the actual value of $β k$ .

References

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

Categories: Estimation theory | Computer vision