[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 N-1.
So, say we pick W6.
Then, the trick is--then you're going to construct the function better.
Then, I initialize the 0 and to which I add--when 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 you--if you can--to implement that specific resampler in Python.
これが効率的にするアイデアの1つで
よりよいサンプルを
実験的に与えてくれることも分かります
すべての粒子と重要度重みを
大きな輪で表しましょう
各粒子がその重要度重みに相当する
1つのスペースを占めます
W5のような重さが大きい粒子は
より多くのスペースを占めます
一方で重みが小さい粒子は
さらに小さなスペースを占めます
まず最初にすべてのインデックスから均等に
粒子のインデックスを推測します
1からNの個々の選択肢から
Uの均一なサンプルであることに気づきました
Pythonでは0からN-1であることに注意します
W6を選ぶとします
これで関数を上手に構築できるようになるでしょう
そして0を初期化して粒子を構築する時に
この0と2×最大重みWの間に位置する
均一に抽出された連続値を加えます
重要度の集合において重さが一番大きいものです
W5は最も大きいので
W5の2倍の乱数を加えます
加えた値はこの位置まで導いてくれます
これが実際に抽出した値で
初期化を示す6番目の粒子から観測されます
そして次のループを繰り返します
この粒子の重要度重みが
βに到達するのに足りないとします
インデックスWがβほど大きくない場合は
βからこのWの値を引いて
1だけ増加させます
これでインデックスをここに動かしました
βのこの部分を取り除いたので
位置は前と同じままです
これでβがインデックスWよりも
小さくなる位置に到達しました
次の状況における場合でインデックス=7です
インデックスは再サンプリングステップで選んだ
粒子のものです
粒子インデックスを選んだら
別の均一な値をβに加えます
ここでβの前回の値を加えます
同じ繰り返しによってインデックスが増え
W7のこの部分すべてにおいてβが減ります
そしてジャンプして粒子1が選ばれるのです
均一の値がとても小さいので
同じ粒子が
2度選ばれるということがよく起こります
各粒子は全外周に比例して選ばれ
この粒子の輪の中まで及びます
これが再サンプリングステップの基本的な実装です
もし可能ならPythonで
特定の再サンプリングを実装してみてください