The bootstrap particle filter

A cloud that follows the state

A particle filter keeps the belief about the hidden state as a cloud of $N$ particles. Each particle is one possible value of the state, and it carries a weight that says how plausible it is. No bell curve is assumed, so the cloud can take any shape. Each day goes through the same cycle. Propagate: move every particle forward with the model's own random motion. Weight: give each particle a weight equal to the likelihood of today's observation given that particle. Estimate: the filtered mean is the weighted average of the particles. Resample: draw a fresh cloud in which good particles are copied and poor ones disappear.

x_t^{(i)}=x_{t-1}^{(i)}+\sqrt q\,z^{(i)},\quad w^{(i)}=p(y_t\mid x_t^{(i)}),\quad \hat m_t=\sum_i\tilde w^{(i)}x_t^{(i)},\quad \hat p(y_t)=\frac1N\sum_i w^{(i)}

(1)

This is called the bootstrap filter because the proposal is the simplest one: the model's own transition. That makes the weight of a particle exactly the likelihood. The recipe works for any model that you can simulate forward and whose observation likelihood you can evaluate, so it handles non-linear states, fat tails and hidden volatility, where the Kalman filter has no exact answer. The price is randomness. Two runs with different random numbers give slightly different answers, and the error shrinks like $1/\sqrt N$ . In practice you fix the random seed so that a run can be reproduced.

One cycle with four particlesAfter propagation the four particles sit at

-1,0,1,2

, and we observe

y=1

with

r=1

. The likelihoods are

0.054,\ 0.242,\ 0.399,\ 0.242

(the normal density with an extra

1/\sqrt{2\pi}

), and the weights are

0.058,\ 0.258,\ 0.426,\ 0.258

. The filtered mean is

0.885

. The average likelihood,

0.234

, estimates how probable the observation was, and the sum of the logs of these averages over all days is the log-likelihood of the model. To resample, draw uniform numbers

0.05,\ 0.5,\ 0.6,\ 0.9

and look them up in the cumulative weights

0.058,\ 0.316,\ 0.742,\ 1

. They pick particles

1,3,3,4

, so the new cloud is

-1,1,1,2

with equal weights

0.25

and mean

0.75

Four steps a day: propagate, weight, estimate, resample.
Weight = likelihood: only the weighting step looks at today's observation.
Any model you can simulate: it handles non-linear and non-Gaussian cases at the price of random error of order $1/\sqrt N$ .

How close to Kalman?On the Apple beta model, where Kalman is exact, a bootstrap filter with

500

particles differs from it by

0.016

on average, and with

2000

particles by

0.0065

. Quadrupling the particles cut the error roughly in half, as

1/\sqrt N

predicts.

Lab · what's graded

A particle's weight15 pts
The filtered mean15 pts
Likelihood of the observation15 pts
After resampling10 pts
Which step uses the data10 pts
The daily cycle10 pts
Match the vocabulary10 pts
Why particles beat Kalman here15 pts

A cloud that follows the state

x_t^{(i)}=x_{t-1}^{(i)}+\sqrt q\,z^{(i)},\quad w^{(i)}=p(y_t\mid x_t^{(i)}),\quad \hat m_t=\sum_i\tilde w^{(i)}x_t^{(i)},\quad \hat p(y_t)=\frac1N\sum_i w^{(i)}

(1)

One cycle with four particlesAfter propagation the four particles sit at

-1,0,1,2

, and we observe

y=1

with

r=1

. The likelihoods are

0.054,\ 0.242,\ 0.399,\ 0.242

(the normal density with an extra

1/\sqrt{2\pi}

), and the weights are

0.058,\ 0.258,\ 0.426,\ 0.258

. The filtered mean is

0.885

. The average likelihood,

0.234

, estimates how probable the observation was, and the sum of the logs of these averages over all days is the log-likelihood of the model. To resample, draw uniform numbers

0.05,\ 0.5,\ 0.6,\ 0.9

and look them up in the cumulative weights

0.058,\ 0.316,\ 0.742,\ 1

. They pick particles

1,3,3,4

, so the new cloud is

-1,1,1,2

with equal weights

0.25

and mean

0.75

Four steps a day: propagate, weight, estimate, resample.
Weight = likelihood: only the weighting step looks at today's observation.
Any model you can simulate: it handles non-linear and non-Gaussian cases at the price of random error of order $1/\sqrt N$ .

How close to Kalman?On the Apple beta model, where Kalman is exact, a bootstrap filter with

500

particles differs from it by

0.016

on average, and with

2000

particles by

0.0065

. Quadrupling the particles cut the error roughly in half, as

1/\sqrt N

predicts.

Lab · what's graded

A particle's weight15 pts
The filtered mean15 pts
Likelihood of the observation15 pts
After resampling10 pts
Which step uses the data10 pts
The daily cycle10 pts
Match the vocabulary10 pts
Why particles beat Kalman here15 pts

A cloud that follows the state

Lab · what's graded

Log in to run your code.

The bootstrap particle filter

A cloud that follows the state

Lab · what's graded

Log in to run your code.