1
$\begingroup$

I've recently been implementing some particle filter algorithms and I've realized there is a small detail I might have been doing incorrectly. Unfortunately the descriptions of the algorithms in papers seem a bit ambiguous (at least to me) and if I try to simulate it to see which way might be correct, both ways of doing it perform reasonably well.

So here is the question specifically, at time $t$ we are approximating an expectation with a weighted sum, let $M$ denote the number of particles and $t$ denote the time step:

$$\psi_t = \sum_{i=1}^M w_t^{(i)}(x_i)f_t^{(i)}(x_i)$$

now my question is about the propagation of this approximation, on time $t+1$ do I now set all particles equal to $\psi_t$ and continue on with the other computations for $t+1$, or is the weighted sum only used "at the end"?

That might not make sense as my explanations are not the best so maybe it's clearly in pseudocode in it's algorithmic form: 

# tf() is the transition function that generates new particles
# it is t(x_t | x_{t-1}) where x's are particles
# lik() is the function that calculates the importance weights

set y = [y_1, ... y_N] # observations

for time = 1:N
    # assume these are all vector operations so all paticles 1:M are
    # being updated below
    new_particles_{time} = tf(old_particles_{time-1})
    weights_{time} = lik(y_{time}, new_particles_{time})
    new_particles_{time} = systematic_resample(new_particles_{time}, weights_{time})
    expectation = sum(new_particles_{time} * weights_{time})
    # do I do this below:
    old_particles_{time} = [expectation for particle_idx = 1:M]  #(1)
    # or do I do this: 
    old_particles_{time} = new_particles_{time} * weights_{time}  #(2)
    # or maybe I do none and just do:
    old_particles_{time} = new_particles_{time}  #(3)
end

so in the code above, the question is do I do #(1), #(2), or #(3) Additionally, should I be computing the expectation before the re sampling step or after?

Improve this question
$\endgroup$
3
  • $\begingroup$ What does $f$ mean in the equation above? $\endgroup$ – Zach Sep 11 '18 at 2:03
  • $\begingroup$ A good practical introduction to particle filters in robotics is Probabilistic Robotics by Thrun, Burgard, and Fox $\endgroup$ – Zach Sep 11 '18 at 2:04
  • $\begingroup$ @atomsmasher when you write $\psi_t = \sum_{i=1}^M w_t^{(i)}(x_i)f_t^{(i)}(x_i)$, why does $f$ depend both on the particle and on time? That's unusual. And how you use your particles shouldn't affect how you update them (propogate, reweight, resample, etc). Those are two separate things $\endgroup$ – Taylor Sep 11 '18 at 3:15
1
$\begingroup$

I believe #3 is closest to the correct answer, but it is not completely correct. If you do not use resampling, the same particles are passed through the transition function over and over again. In this case without resampling, you must keep updating the weights by multiplying the previous weight with the likelihood of the current observation, so the weight update line would look something like.

weights_{time} = weights_{time-1} * lik(y_{time}, new_particles_{time})

In almost all cases this will result in extremely small weights (this is the particle depletion problem). Thus in nearly all real cases Resampling is important!

Improve this answer
$\endgroup$
1
  • $\begingroup$ so say I perform systematic resampling, 1. do i do this before computing the expectation, and 2. does #3 then become the correct way to do it? $\endgroup$ – atomsmasher Sep 11 '18 at 3:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.