
タイトル：
0334 Resampling Wheel

概説：

[Narrator] So, here's an idea how to make this more efficient,

and it turns out empirically it also gives better samples.

Let's represent all our particles and importance weight in a big wheel.

Each particle occupies a slice that corresponds to its importance weight.

Particles with a bigger weight, like W5, occupy more space.

Whereas particles with a smaller weight occupy less space.

Very initially let's guess a particle index uniformly from the set of all indices.

I did note this as a uniform sample at U

from the discrete set of choices of index 1 all the way to N,

and as a caveat in Python, of course, it goes from 0 to N1.

So, say we pick W6.

Then, the trick isthen you're going to construct the function better.

Then, I initialize the 0 and to which I addwhen I construct these particles

a uniformly drawn continuous value that sits between 0 and 2 times W max,

which is the largest of the importance weights in the important set.

W5 is the largest, so we're going to add a random value that might be as large as twice W5.

Suppose the value we added brings us to here.

So, this is the value we actually drew,

measured from the beginning of the sixth particle which shows an initialization.

I now then iterate the following loop:

if the importance weight of the present particle doesn't suffice

to reach all the way to beta.

So, if W index isn't as big as beta, then I subtract from beta this very value W index

and I increment index by 1.

So, what have I done? I've moved index to over here,

and I removed this part of beta so the point over here is still the same as before.

We now get to the point where beta becomes smaller than W index,

which is the case in the next situation.

Now index=7.

Then, index is the index of the particle I pick in my resampling process.

So, I picked the particle index; I now iterate I add another uniform value to beta.

Say I add this one.

This is the value I add, this is the value beta previously had.

The same iteration now will make index flow up

reducing beta by all the slice over here, which is W7,

and then jump over here, and particle 1 is picked.

It can easily happen that the uniform value is so small

that the same particle is picked twice, and it's easy to see

that each particle is now picked in proportion to the total circumference

it spans in this wheel of particles.

So, this is essentially my implementation for the resampling step.

So, I want youif you canto implement that specific resampler in Python.