English 字幕

← 03-34 Resampling Wheel


Showing Revision 2 created 06/07/2017 by Udacity Robot.

  1. [Narrator] So, here's an idea how to make this more efficient,
  2. and it turns out empirically it also gives better samples.
  3. Let's represent all our particles and importance weight in a big wheel.
  4. Each particle occupies a slice that corresponds to its importance weight.
  5. Particles with a bigger weight, like W5, occupy more space.
  6. Whereas particles with a smaller weight occupy less space.
  7. Very initially let's guess a particle index uniformly from the set of all indices.
  8. I did note this as a uniform sample at U
  9. from the discrete set of choices of index 1 all the way to N,
  10. and as a caveat in Python, of course, it goes from 0 to N-1.
  11. So, say we pick W6.
  12. Then, the trick is--then you're going to construct the function better.
  13. Then, I initialize the 0 and to which I add--when I construct these particles--
  14. a uniformly drawn continuous value that sits between 0 and 2 times W max,
  15. which is the largest of the importance weights in the important set.
  16. W5 is the largest, so we're going to add a random value that might be as large as twice W5.
  17. Suppose the value we added brings us to here.
  18. So, this is the value we actually drew,
  19. measured from the beginning of the sixth particle which shows an initialization.
  20. I now then iterate the following loop:
  21. if the importance weight of the present particle doesn't suffice
  22. to reach all the way to beta.
  23. So, if W index isn't as big as beta, then I subtract from beta this very value W index
  24. and I increment index by 1.
  25. So, what have I done? I've moved index to over here,
  26. and I removed this part of beta so the point over here is still the same as before.
  27. We now get to the point where beta becomes smaller than W index,
  28. which is the case in the next situation.
  29. Now index=7.
  30. Then, index is the index of the particle I pick in my resampling process.
  31. So, I picked the particle index; I now iterate I add another uniform value to beta.
  32. Say I add this one.
  33. This is the value I add, this is the value beta previously had.
  34. The same iteration now will make index flow up
  35. reducing beta by all the slice over here, which is W7,
  36. and then jump over here, and particle 1 is picked.
  37. It can easily happen that the uniform value is so small
  38. that the same particle is picked twice, and it's easy to see
  39. that each particle is now picked in proportion to the total circumference
  40. it spans in this wheel of particles.
  41. So, this is essentially my implementation for the resampling step.
  42. So, I want you--if you can--to implement that specific resampler in Python.