粒子フィルタ

出典: フリー百科事典『ウィキペディア（Wikipedia）』

この項目「粒子フィルタ」は途中まで翻訳されたものです（原文：en:Particle Filter 15:26, 20 September 2007）。
翻訳作業に協力して下さる方を求めています。詳細はこの項目のノートや履歴、翻訳のガイドラインなどを参照してください。翻訳情報の要約欄への記入をお忘れなく。
このタグは2007年10月に貼付されました。

粒子フィルタ、または逐次モンテカルロ法 (Sequential Monte Carlo: SMC)とは、シミュレーションに基づく複雑なモデルの推定法である。

この手法はベイズモデルを推定するのに用いられ、バッチ処理であるマルコフ連鎖モンテカルロ法 (MCMC) の逐次 (オンライン) 版である。うまく設計すると、粒子フィルタはMCMCよりも高速である。拡張カルマンフィルタや無香カルマンフィルタ (Unscented カルマンフィルタ) に対して、十分なサンプル点があればベイズ最適推定に近付くためにより精度が高くなることから、これらの代わりに用いられることがある。また、カルマンフィルタを粒子フィルタの分布として使うことで組み合わせることができる。

[編集] 目的

粒子フィルタの目的は、隠れたパラメータ列 $x k$ $(k=0,1,2,3, \ldots)$ を観測値 $y k$ $(k=0,1,2,3, \ldots)$ のみから推定することである。ベイズ推定値 $x k$ は一つ過去の確率分布 $p(x_k|y_0,y_1,\ldots,y_k)$ から得られるのに対し、マルコフ連鎖法では過去の全てを含む確率分布 $p(x_0,x_1,\ldots,x_k|y_0,y_1,\ldots,y_k)$ より求められる.

[編集] モデル

as粒子モデルはパラメータ $x k$ と観測値 $y k$ は以下のように表せる。

$x_0, x_1, \ldots$ は以下を満たす1次のマルコフ過程

$x_k|x_{k-1} \sim p_{x_k|x_{k-1}}(x|x_{k-1})$

ただし初期確率分布 $p (x 0)$ を持つものとする。

観測データ列 $y_0, y_1, \ldots$ は $x_0, x_1, \ldots$ が既知であるという条件の下で独立である。

換言すると、それぞれの

y k

は

x k

のみに従属である。

y k | x k ˜ p y | x (y | x k)

一例として以下を考える。

$x_k = f(x_{k-1}) + v_k \,$

$y_k = h(x_k) + w_k \,$

ただし $v k$ も $w k$ も異なる $k$ について互いに独立であり、かつ $k$ によらず同じ確率密度関数にしたがうものとする。また、 $f(\cdot)$ と $h(\cdot)$ は既知の関数である。この2つの方程式は状態方程式とみなすことができ、カルマンフィルタの状態方程式と類似している。もし関数 $f(\cdot)$ と $h(\cdot)$ が線形かつ $v k$ および $w k$ がガウス分布だとすると、カルマンフィルタによってベイズ推定と厳密に一致する解が得られる。そうでない場合はカルマンフィルタは1次近似に過ぎない。粒子フィルタも近似には変わりないが、十分な数の粒子があれば高い精度が得られる。

[編集] モンテカルロ近似

粒子法は他のサンプル点手法と同様に、フィルタの確率分布を近似する点列 $p(x_k|y_0,\dots,y_k)$ を生成する。したがって $P$ 個のサンプル点があれば、フィルタの確率分布による推定は

$\int f(x_k)p(x_k|y_0,\dots,y_k)dx_k\approx\frac1P\sum_{L=1}^Pf(x_k^{(L)})$

によって近似される。そして $f(\cdot)$ は通常のモンテカルロ法と同様に, 近似の程度に応じた次数までのモーメントを持っている。

一般に計算は $k$ 回の反復を行う(これを $N$ と呼ぶ). 全ての粒子を $x k = 0 | k = 0$ で初期化することで $x 1$ が生成され、これが $x 2$ を生成するのに使われ、それがまた $x 3$ を生成するのに使われ、同様に $k = N$ までが生成される。全て終わった時点で $x k$ の全粒子にわたる平均値 (or $\frac{1}{P}\sum_{L=1}^P x_k^{(L)}$ ) は $x k$ の実際の値を近似する。

[編集] Sampling Importance Resampling (SIR)

Sampling importance resampling (SIR) アルゴリズムはよく使われる粒子フィルタアルゴリズムであり、フィルタの確率分布 $p(x_k|y_0,\ldots,y_k)$ を以下の重みつき粒子によってよく近似する。

$\{(w^{(L)}_k,x^{(L)}_k)~:~L=1,\ldots,P\}$ .

重み $w^{(L)}_k$ は以後の $\sum_{L=1}^P w^{(L)}_k = 1$ である粒子の相対確率密度の近似となっている。are SIR importance sampling の逐次版と言える。importance sampling にあるように、関数 $f(\cdot)$ の推定値は重みつき平均

$\int f(x_k) p(x_k|y_0,\dots,y_k) dx_k \approx \sum_{L=1}^P w^{(L)} f(x_k^{(L)}).$

によって近似できる。

アルゴリズムの特性はimportance distributionの選びかたに依存する。

$\pi(x_k|x_{0:k-1},y_{0:k})\,$ .

最適な importance distribution は

$\pi(x_k|x_{0:k-1},y_{0:k}) = p(x_k|x_{k-1},y_{k}). \,$

によって与えられる。

しかしながら、transition prior はしばしば importance function として用いられる。粒子を描いたり後の importance weight を計算するのが簡単だからである:

$\pi(x_k|x_{0:k-1},y_{0:k}) = p(x_k|x_{k-1}). \,$

Sampling Importance Resampling (SIR) フィルター transition prior を importance function として用いた　は一般にbootstrap filter および condensation algorithm として知られる。

Resampling はアルゴリズムの縮退を防ぐために用いられる。すなわち、全ての importance weights がゼロに近付く場合である。このアルゴリズムの性能は resampling method の選びかたにもかかっている。北川によって提案されたstratified resampling 分散を最適化する。

逐次 importance resampling 法の1ステップは以下の様になる。

1) $L=1,\ldots,P$ についてimportance distributionsを描く

$x^{(L)}_k \sim \pi(x_k|x^{(L)}_{0:k-1},y_{0:k})$

2) $L=1,\ldots,P$ について importance weights を正規化定数まで評価する。

$\hat{w}^{(L)}_k = w^{(L)}_{k-1} \frac{p(y_k|x^{(L)}_k) p(x^{(L)}_k|x^{(L)}_{k-1})} {\pi(x_k^{(L)}|x^{(L)}_{0:k-1},y_{0:k})}.$

3) For $L=1,\ldots,P$ 正規化された importance wieghts を計算する。

$w^{(L)}_k = \frac{\hat{w}^{(L)}_k}{\sum_{J=1}^P \hat{w}^{(J)}_k}$

4) 有効な粒子の数を数える

$\hat{N}_\mathit{eff} = \frac{1}{\sum_{L=1}^P\left(w^{(L)}_k\right)^2}$

5) もし有効な粒子の数が閾値より少なかったら $\hat{N}_\mathit{eff} < N_{thr}$ resampling を実行する。

a) 現在の粒子の集合から、重みに比例した確率で

P

個の粒子を描く。新しい粒子の集合で置き換える。

b) $L=1,\ldots,P$ について $w^{(L)}_k = 1/P$ とする。

逐次的な Importance Resampling 等の用語は SIR フィルターの意味で用いられることがある。

[編集] 逐次的 Importance Sampling (SIS)

Resampling が無い点を除いて SIR と同様である。

[編集] 直説法

直説法は他の粒子フィルタに比べて簡単で、composition と rejection を利用する。 $k$ 番目の一つのサンプル $x$ を $p_{x_k|y_{1:k}}(x|y_{1:k})$ から生成するのに以下の手順を踏む。

1) p=1

2) 一様分布

{1,..., P}

を生成

3) $\hat{x}$ をその確率分布 $p_{x_k|x_{k-1}}(x|x_{k-1|k-1}^{(L)})$ から生成する

4) $\hat{y}$ の確率を $\hat{x}$ を用いて $p_{y|x}(y_k|\hat{x})$ から生成する。ただし、

y k

は観測値

5) 別の一様分布

[0, m k]

を生成

6) u と $\hat{y}$ を比較

6a) u が大きければ step 2 以降を繰り返す

6b) u が小さかったら $\hat{x}$ を

x k | k (p)

として保存して p を1増やす

7) p > P ならば終了

目的は $k$ における P 個の粒子を、 $k - 1$ だけから生成することである。これにはマルコフ方程式が $x k - 1$ だけから $x k$ を生成できるように記述できなければならない。このアルゴリズムは $k - 1$ から $k$ における粒子を生成するために P 個の粒子の合成を利用しており、 $k$ のいて P 個の粒子が生成されるまでステップ 2-6 以降を繰り返す。

これは $x$ が2次元配列とみなせるときより視覚的に理解できる。一つの次元は $k$ であり、もう一つの次元は粒子数である。例えば $x (k, L)$ は $k$ における L 番目の粒子であり、 $x_k^{(L)}$ と書ける。ステップ3 は $k - 1$ においてランダムに選ばれた粒子 $x_{k-1}^{(L)}$ からポテンシャル $x k$ を生成し、ステップで成否の判定が行われる。言い替えれば、 $x k$ の値はそれまでに生成された $x k - 1$ を用いて生成される。

[編集] その他の粒子フィルタ

Auxiliary particle filter
Gaussian particle filter
Unscented particle filter
Monte Carlo particle filter
Gauss-Hermite particle filter
Cost Reference particle filter

[編集] 関連項目

アンサンブルカルマンフィルタ
カルマンフィルタ、ガウス分布の解析的な推定器
反復ベイズ推定

[編集] 参考文献

Sequential Monte Carlo Methods in Practice, by A Doucet, N de Freitas and N Gordon. Springer, 2001. ISBN 978-0387951461
On Sequential Monte Carlo Sampling Methods for Bayesian Filtering, by A Doucet, C Andrieu and S. Godsill, Statistics and Computing, vol. 10, no. 3, pp. 197-208, 2000 CiteSeer link
Tutorial on Particle Filters for On-line Nonlinear/Non-Gaussian Bayesian Tracking (2001); S. Arulampalam, S. Maskell, N. Gordon and T. Clapp; CiteSeer link
Particle Methods for Change Detection, System Identification, and Control, by Andrieu C., Doucet A., Singh S.S., and Tadic V.B., Proceedings of the IEEE, Vol 92, No 3, March 2004. SMC Homepage link
A Tutorial on Bayesian Estimation and Tracking Techniques Applicable to Nonlinear and Non-Gaussian Processes, A.J. Haug, The MITRE Corporation; Mitre link
Distributed Implementations of Particle Filters, Anwer Bashi, Vesselin Jilkov, Xiao Rong Li, Huimin Chen, Available from the University of New Orleans
A survey of convergence results on particle filtering methods for practitioners, Crisan, D. and Doucet, A., IEEE Transactions on Signal Processing 50(2002)736-746 doi:10.1109/78.984773
Beyond the Kalman Filter: Particle Filters for Tracking Applications, by B Ristic, S Arulampalam, N Gordon. Artech House, 2004. ISBN 1-58053-631-x

[編集] 外部リンク

Sequential Monte Carlo Methods (Particle Filtering) homepage on University of Cambridge
Dieter Fox's MCL Animations
Nando de Freitas' free software
Rob Hess' free software

カテゴリ: 翻訳中途 - 2007年10月 | Estimation theory | Monte Carlo methods | Non-parametric statistics | Non-linear filters

See also ebooksgratis.com: no banners, no cookies, totally FREE.