おべんきょうwiki - [パーティクルフィルタ]の変更点

 * パーティクルフィルタ
 
 時系列フィルタの一種．
 最適解を求めるためにモンテカルロ法を用いるのが特徴．
 分野によっては別の名前で呼ばれたりする．
 理論については下の北川先生の解説が詳しい．
 
 http://www.ism.ac.jp/editsec/toukei/pdf/44-1-031.pdf
 
 が，理論を説明するよりも実装がかなり簡単である．
 実装例としては例えば下記のページ．
 
 http://mist.suenaga.cse.nagoya-u.ac.jp/trac/wiki/Tutorial/Practice0
 
 単純なアルゴリズムでありながら適用できる問題が多いので各方面で大人気．
 
 
 * アルゴリズム
 
 アルゴリズムは非常に簡単．
 
 ** リサンプリング
 
 パーティクルを撒きなおす．
 初期状態では一様に撒く．
 前の状態である重み付きパーティクルを元に撒きなおす．
 大きな重みの付いたパーティクルの周囲には多くの点を配置する．
 当然配置の際には乱数を加える．
 
 ** 予測
 
 各パーティクルを状態方程式に基づいて移動させる．
 速度項がなければ何もしなくていい．
 速度が十分遅ければ速度項を無視してもうまくいくことが多い．
 
 ** 重み付け
 
 現在の観測とパーティクルの状態を元に尤度（ゆうど）を計算する．
 尤度とはそのパーティクルがどれだけもっともらしいかということで，
 全体の計算がやっていることは確率的な尤度の最大化である．
 尤度がすなわちそのパーティクルの重みとなるが，
 ここで正規化しておくとリサンプリングのときに
 全体のパーティクルの何割を撒くかが直ちに決定できて便利
 
 ** 状態推定
 
 パーティクルフィルタが計算するのは
 パーティクルの分布によって表される確率密度である．
 ので，現在の状態をそこから計算しなければいけない．
 重み付き平均を取る，最大重みを持つパーティクルを使う，
 など方法は色々ある．
 
 
 * 尤度関数の設計
 
 尤度関数を設計するときには，
 - 確実に最適解付近で尤度が最大化されること
 - 現在の観測に対してロバストであること
 に気をつける．
 
 前者はそもそもこの条件が満たされていないと正しい解が得られるはずがない．
 後者については観測には外れ値が含まれるという前提を置けば必須．
 誤差の二乗和を単にとるのではなく，M-estimatorを使ったり中央値を取ればよい．
 
 
 * 他の時系列フィルタとの関係は？
 
 カルマンフィルタ，拡張カルマンフィルタと比較する．
 
 カルマンフィルタはシステムの状態方程式が線形で表せる必要があった．
 拡張カルマンフィルタは状態方程式が非線形でもよいように拡張されている．
 これに対し，パーティクルフィルタはぶっちゃけ尤度関数さえ定義できればなんでも解ける．
 誤差共分散行列やヤコビアンの準備も要らないので非常に簡単に実装できる．
 
 ただし，（拡張）カルマンフィルタが決定論的にひとつの解を出力する，i.e.計算が一回でよいのに対し．
 パーティクルフィルタはパーティクルの数だけ尤度を計算しなければならない．
 つまりパーティクル数をnとすると計算時間はO(n)に従う．
+
+* 関連
+
+高速な非復元抽出を行う Walker's alias method
+http://d.hatena.ne.jp/koiti_yano/20070826/p1
+http://d.hatena.ne.jp/higotakayuki2/20070826/p1