Sampling Importance Resampling (SIR)
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2020/11/04 04:05 UTC 版)
「粒子フィルタ」の記事における「Sampling Importance Resampling (SIR)」の解説
Sampling importance resampling (SIR) アルゴリズムは、モンテカルロフィルタ（北川源四郎 1993）やブートストラップフィルタ（Gordon et al. 1993）による本来の粒子フィルタであるが、よく使われる粒子フィルタアルゴリズムである。ここではフィルタリング確率分布 p ( x k | y 0 , … , y k ) {\displaystyle p(x_{k}|y_{0},\ldots ,y_{k})} を P {\displaystyle P} 個の重みつき粒子によって近似する。 { ( w k ( L ) , x k ( L ) ) : L = 1 , … , P } {\displaystyle \{(w_{k}^{(L)},x_{k}^{(L)})~:~L=1,\ldots ,P\}} . 重み w k ( L ) {\displaystyle w_{k}^{(L)}} は以後の ∑ L = 1 P w k ( L ) = 1 {\displaystyle \sum _{L=1}^{P}w_{k}^{(L)}=1} である粒子の相対事後分布(密度)の近似となっており、 ∑ L = 1 P w k ( L ) = 1 {\displaystyle \sum _{L=1}^{P}w_{k}^{(L)}=1} を満たす。 SIRは重点サンプリング の逐次版 (つまり、再帰的) と言える。重点サンプリングにあるように、関数 f ( ⋅ ) {\displaystyle f(\cdot )} の推定値は重みつき平均 ∫ f ( x k ) p ( x k | y 0 , … , y k ) d x k ≈ ∑ L = 1 P w ( L ) f ( x k ( L ) ) {\displaystyle \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)})} で近似できる。 粒子の個数が有限である場合、このアルゴリズムの性能は提案分布 π ( x k | x 0 : k − 1 , y 0 : k ) {\displaystyle \pi (x_{k}|x_{0:k-1},y_{0:k})} の選択に依存する。最適な提案分布は目的分布 π ( x k | x 0 : k − 1 , y 0 : k ) = p ( x k | x k − 1 , y k ) {\displaystyle \pi (x_{k}|x_{0:k-1},y_{0:k})=p(x_{k}|x_{k-1},y_{k})} である。 しかしながら事前遷移確率 π ( x k | x 0 : k − 1 , y 0 : k ) = p ( x k | x k − 1 ) {\displaystyle \pi (x_{k}|x_{0:k-1},y_{0:k})=p(x_{k}|x_{k-1})} を提案分布として用いることが多い。なぜならそこからは容易に粒子をサンプルすることができるし、その後に重みを計算することもできるからである。 提案分布として事前遷移確率を用いるSIRフィルタは一般にブートストラップフィルタ・コンデンセーションアルゴリズムとして知られている。 唯一つを除いた全ての重みがゼロに近付くこと ― アルゴリズムの縮退 ― を防ぐために再サンプルが行なわれる。このアルゴリズムの性能は再サンプリング方式の選びかたにもかかっている。北川源四郎 (1993) によって提案された層化抽出法は分散の意味で最適である。 SIR法の1ステップは以下の様になる。 1) L = 1 , … , P {\displaystyle L=1,\ldots ,P} について, 提案分布から粒子をサンプルする x k ( L ) ∼ π ( x k | x 0 : k − 1 ( L ) , y 0 : k ) {\displaystyle x_{k}^{(L)}\sim \pi (x_{k}|x_{0:k-1}^{(L)},y_{0:k})} 2) L = 1 , … , P {\displaystyle L=1,\ldots ,P} について、重みを更新し、正規化定数を得る。 w ^ k ( L ) = w k − 1 ( L ) p ( y k | x k ( L ) ) p ( x k ( L ) | x k − 1 ( L ) ) π ( x k ( L ) | x 0 : k − 1 ( L ) , y 0 : k ) {\displaystyle {\hat {w}}_{k}^{(L)}=w_{k-1}^{(L)}{\frac {p(y_{k}|x_{k}^{(L)})p(x_{k}^{(L)}|x_{k-1}^{(L)})}{\pi (x_{k}^{(L)}|x_{0:k-1}^{(L)},y_{0:k})}}} このとき π ( x k ( L ) | x 0 : k − 1 ( L ) , y 0 : k ) = p ( x k ( L ) | x k − 1 ( L ) ) {\displaystyle \pi (x_{k}^{(L)}|x_{0:k-1}^{(L)},y_{0:k})=p(x_{k}^{(L)}|x_{k-1}^{(L)})} ならば更新式は w ^ k ( L ) = w k − 1 ( L ) p ( y k | x k ( L ) ) , {\displaystyle {\hat {w}}_{k}^{(L)}=w_{k-1}^{(L)}p(y_{k}|x_{k}^{(L)}),} のように簡単になる。 3) L = 1 , … , P {\displaystyle L=1,\ldots ,P} について、正規化された重みを計算する。 w k ( L ) = w ^ k ( L ) ∑ J = 1 P w ^ k ( J ) {\displaystyle w_{k}^{(L)}={\frac {{\hat {w}}_{k}^{(L)}}{\sum _{J=1}^{P}{\hat {w}}_{k}^{(J)}}}} 4) 有効粒子数の推定量を計算する。 N ^ e f f = 1 ∑ L = 1 P ( w k ( L ) ) 2 {\displaystyle {\hat {N}}_{\mathit {eff}}={\frac {1}{\sum _{L=1}^{P}\left(w_{k}^{(L)}\right)^{2}}}} 5) もし有効粒子数が与えられた閾値より少なかったら N ^ e f f < N t h r {\displaystyle {\hat {N}}_{\mathit {eff}}<N_{thr}} 再サンプルを実行する。 a) 現在の粒子の集合から、重みに比例した確率で P {\displaystyle P} 個の粒子を描く。現在の粒子の集合を新しい粒子の集合で置き換える。 b) L = 1 , … , P {\displaystyle L=1,\ldots ,P} について、 w k ( L ) = 1 / P {\displaystyle w_{k}^{(L)}=1/P} とする。 Sequential Importance Resampling 等の用語は SIR フィルターの意味で用いられることがある。
※この「Sampling Importance Resampling (SIR)」の解説は、「粒子フィルタ」の解説の一部です。
「Sampling Importance Resampling (SIR)」を含む「粒子フィルタ」の記事については、「粒子フィルタ」の概要を参照ください。
- Sampling Importance Resamplingのページへのリンク
