パーティクル・フィルタをやさしく解説

パーティクル・フィルタの原理

ざっくり言うと、パーティクル・フィルタは適者生存の原理に基づく動的最大値探索法です。

パーティクル (particle) とは小さな粒つぶのことですので、日本では「粒子フィルタ」ともいいますが、ここでは解りやすくパーティクルを「生き物」と考えて、その動作原理をやさしく解説致します。

確率や統計の知識がなくても解るように書きましたので、関数とベクトルを御存知であれば、たぶん「ははあ、パーティクル・フィルタというのは、こういうものか」と、ご納得いただけると思います。

エサの数と子供の数

自然界にはエサの多い所と少ない所があり、天敵がいなければ、生き物の分布は大体エサの分布に一致すると考えてよいでしょう。 エサの多い所にいるものほど沢山の「子孫」を作り、エサの少ない所にいるものは子孫を残すこともできぬまま消えてゆきます。

子供は親の近くで生活しますが、親よりもっとエサの多い場所を見つけたものは、親よりさらに多くの子(親から見ると孫)を産むでしょう。 すると親が自分の周囲に均等に子供たちを産んだとしても、その孫たちはエサの多い場所でちょっと多目に、エサの少ない場所でちょっと少な目になると考えられます。 これが何世代も繰り返されると、群れは少しずつエサが多い方へ移動してゆき、長い年月の後にはエサが最も多い場所に辿り着くだろう … これがパーティクル・フィルタの考え方です。

この世界では、同じ親から生まれた子供でも、エサが相対的に少ない場所にいる子供は (かわいそうですが) 淘汰されます。 エサの多い地域が子沢山になるので、エサの少ない地域を淘汰しないと個体数が際限なく増えて歯止めが効かなくなり、エサが足りなくなって全体が滅んでしまうのです。

個体数は常に一定に保たねばなりません。 全体として「増えもせず、減りもせず」だから、生存競争でエサの一番多い場所に集まるのです。

式で表すと

前項では解りやすく生き物たちの栄枯盛衰をエサの数で説明しましたが、実際のパーティクル・フィルタで「エサの数」に相当するものは「尤度（ゆうど）関数」と呼ばれています。

【参考】 尤度とは「尤（もっと）もらしさ」を表す確率・統計分野の言葉ですが、あまり気にせず、ここでは「エサの数」と考えて読み進めて下さい。

親の位置を \(\boldsymbol{x}\)、そこのエサの数を \(L(\boldsymbol{x})\)、その子供の数 \(c\) が \(L(\boldsymbol{x})\) に比例すると仮定すると \begin{eqnarray} c &\propto& L(\boldsymbol{x}) \end{eqnarray} 比例定数を \(\alpha\) とすれば \begin{eqnarray} c &=& \alpha L(\boldsymbol{x}) \end{eqnarray} この関係が全ての個体で成り立つとすると、\(n\) 番目の親の子供の数は次のように表せます。 \begin{eqnarray} c_n &=& \alpha L(\boldsymbol{x}_n) \label{cn} \end{eqnarray} 話を単純化するため、親は一斉に子供を産んで、すぐに死んでしまうと考えることにしましょう。すると全ての世代で守るべき個体数を \(N\) とすると \begin{eqnarray} N &=& \sum_{n=0}^{N-1} c_n \label{N} \end{eqnarray} が成り立たねばなりません (次世代を担う子供の合計数は常に \(N\) でなければならない)。式(\ref{cn})を式(\ref{N})に代入すると \begin{eqnarray} N &=& \sum_{n=0}^{N-1} \alpha L(\boldsymbol{x}_n) \\ &=& \alpha \sum_{n=0}^{N-1} L(\boldsymbol{x}_n) \end{eqnarray} より比例定数は \begin{eqnarray} \alpha &=& \frac{N}{\displaystyle\sum_{n=0}^{N-1} L(\boldsymbol{x}_n)} \end{eqnarray} となり、これを式(\ref{cn})に代入すれば、\(n\) 番目の親の子供の数 \(c_n\) は、そこのエサの数 \(L(\boldsymbol{x}_n)\) によって、次のように決定されます。 \begin{eqnarray} c_n &=& \frac{N}{\displaystyle\sum_{n=0}^{N-1} L(\boldsymbol{x}_n)} L(\boldsymbol{x}_n) \label{cn2} \end{eqnarray}

シミュレーション例

数式で書かれてもイメージが湧かないと思いますので、生き物がエサを求めて移動してゆく様子をシミュレーション動画にしてみました。動画の 1 コマが 1 世代を表しています。

曲面の高さはその場所のエサの数を表しています。

白い ○ が生き物で、集団の中で相対的にエサが多いものは大きな ○、相対的にエサが少ないものは小さな ○ で表現されています (エサを沢山食べたものは大きく太り、食べられないものは小さく痩せこけているイメージ)。

その 1

エサの多い場所 (図で山になっているところ) を 3 箇所作り、集団の近くに囮（おとり）として低い山を配置しました。 最初、手前にあるなだらかな平地に白く固まっているのが生き物の群れです。

囮に引っかからずに、群れはエサが沢山ある一番高い山に辿り着けるでしょうか?

動画を再生すると、パーティクルの群れは、まず中央付近の小山 (前進を阻むために仕掛けた囮) に辿り着きますが、ほどなく散らばった子供たちがもっと高い場所を発見し、集団がそちらに移動していって、最終的に全員が一番エサの多い、一番高い右の山頂に到達しました。

右にある高い山に移住した小さな集落が、低い山の頂上と同じ高さ付近で、しばらく「様子見」になるところが面白いですね。 「右の山の方がエサが多い」という確信が得られるまで多数派が動こうとしない慎重さも、種が絶滅しないための、ひとつの「知恵」なのでしょう。

子供が親からあまり遠くに行かないように、子の散らばりを小さくしたらどうなるでしょう?

もっと高い山があることを発見できず、結局、群れは小さく固まって低い小山に安住してしまいました。

群れから離れるアウトローの存在を許さない社会が、いずれ行き詰まることを示唆しているようで、興味深い実験結果ですね。

散らばりが小さい集団は「歩幅」が狭いため、動きも遅いようです。

動きがあまり遅いと、急激な環境変化にはついて行けないかもしません。

その 2

先程と同じ地形ですが、今度は広い範囲に分布した1万匹の群れが「ヨーイ、ドン!」で一斉に競争したらどうなるか見てみましょう。

ただし最初から高い所にいるものの一人勝ちになってはつまらないので、わざと全員低いところからスタートするようにしました。

はじめのうちは、一番高い右の山ではなく、高さが中程度の左の山にパーティクルが集中しています。

図2-2 : はじめのうちは、左の山に人気が集中

何故こうなったかというと、左の山は高さはそれほどでもないのですが、実は斜面の傾斜をキツく設定してあったからです。

【参考】 傾斜がキツいということは、斜面を登る方向にちょっと動いただけで沢山のエサにありつける訳ですから、短期に大きく増やせる投資話みたいなもので、みんな左の山に殺到してしまったのです。 誰一人てっぺんまで登ったことがない時点では、「左の山が一番高い」と勘違いしてしまったとしても、致し方ないことです。

この世界では、少しでも高い山に登ったものが繁殖に有利ですので、左の山を知らず、少し遅れて一番高い右の山に登った集団が最後には繁栄し、一時の栄華を誇った左の山はさびれて誰もいなくなりました。

左の山のあっけない最期には、しみじみとした味わいがありますね。

その 3

これまではエサの分布が変化しないと仮定したシミュレーションでしたが、今度はエサの分布がダイナミックに変化する場合を見てみましょう。

生き物たちはエサの多い所にちゃんとついていけるでしょうか?

ヒダに沿って広がり、尾根伝いに頂上に着いた後は、環境の変化に翻弄されつつも、大体エサが一番多い所について行けたようです (置いて行かれてしまった場面もちらほらありましたが…)。

ある時点で最高の位置にいたとしても、環境が激変すると簡単に低地に転落するケースが多々見られます。 逆に下の方にいたものがタナボタ式に頂点に立つこともあり、パーティクルの世の浮き沈みも知れぬものですね。

ここでも大事なのは、集団が一箇所に固まらず、ある程度散らばっていることです。 変化が急で激しいほど広い範囲に散らばっていないと、動きの速いエサの居場所を見失ってしまいます。

パーティクル・フィルタの作り方

作ってみたい方のためにプログラムのアウトラインと注意点を述べます (このままコンパイルできるわけではありません)。

アウトライン

先に式(\ref{cn2})で導いた子供の数の式を使い、パーティクル・フィルタを C++ っぽく、大雑把に書くと次のようになります。

シミュレーションでもご覧いただいたとおり、親の居場所にランダムな微小変位を加え、子パーティクルを親の近くに散らばらせるところがポイントです。

【参考】 ランダムな変位を加えないと世代交代しても同じ場所から動かず、いつまで経ってもエサの多い所を見つけることができません。

注意点

お気づきかもしれませんが、先程の C++ コードもどきには問題があります。

この式の右辺は実数なのに左辺が整数であるため、毎回 int \(c_n\) への代入時に小数点以下が切り捨てられ、全パーティクルの子供の合計数が \(N\) にならないのです。

【参考】 小数点以下切り捨てなので、子供の合計数は \(N\) の半分くらいになってしまうことが多いです。

【注意】切り捨てで駄目なら四捨五入にすればいいじゃないか、と思われるかもしれませんが、四捨五入しても \(N\) に近くはなるものの、ちょっきり \(N\) になることは稀ですし、悪いことに \(N\) より多くなってしまうケースも頻繁に生じます。 そうなると、\(N\) 個しかパーティクル配列を確保していない場合、メモリへの不正書き込みでエラー終了してしまいます。

この問題を解決する方法はいくつか考えられますが、「やさしい解説」を逸脱し、パーティクル・フィルタの本質部分でもありませんので、今回は省略させていただきます。

【ヒント】 たとえば右辺の式の計算結果を double のまま積算してゆき、積算結果を int に四捨五入して、前回の int 化された積算値との差 (これも int になる) を \(c_n\) にするとか…。

まとめ

できるだけやさしくパーティクル・フィルタを解説してみました。パーティクル・フィルタは:

• 子供の数は親の位置に対する尤度関数の値 (本文ではエサの数) で決まる
• 親パーティクルは子パーティクルを自分の回りにわざと散らばらせる
• 各世代のパーティクル数を一定に保つ

なお、パーティクル・フィルタには様々なバリエーション(改良)があるため、複数の資料文献を見比べると頭がこんがらがることがありますが、エッセンスはここに書いたシンプルな考え方です。 尤度関数を確率的に考えなければ、意外と簡単だったでしょう?