粒子フィルター

統計的および確率論的な観点から見ると、粒子フィルタは分岐型／遺伝型アルゴリズムと平均場型相互作用粒子法に分類されます。これらの粒子法の解釈は、科学分野によって異なります。進化計算においては、平均場遺伝型粒子法はヒューリスティックアルゴリズムや自然探索アルゴリズム（メタヒューリスティックとも呼ばれる）としてよく用いられます。計算物理学や分子化学においては、ファインマン・カッツ経路積分問題の解決や、ボルツマン・ギブス測度、シュレーディンガー演算子の上位固有値、基底状態の計算に用いられます。生物学や遺伝学においては、ある環境下における個体群や遺伝子の進化を表すために用いられます。

平均場型の進化計算手法の起源は、1950 年と 1954 年にアラン・チューリングが行った遺伝型突然変異選択学習マシンの研究^{[ 22 ]}と、ニュージャージー州プリンストンの高等研究所のニルス・アール・バリチェリによる論文^{[ 23 ] [ 24 ]}に遡ることができます。統計的手法における粒子フィルタの最初の痕跡は1950 年代半ばに遡ります。1954年にジョン・ハマーズリーらが提案した「貧者のモンテカルロ」 ^{[ 25 ]}には、今日使用されている遺伝型粒子フィルタリング手法のヒントが含まれていました。1963 年にニルス・アール・バリチェリは、単純なゲームをプレイする個人の能力を模倣する遺伝型アルゴリズムをシミュレートしました。^{[ 26 ]}進化計算の文献では、遺伝型突然変異選択アルゴリズムは、1970年代初頭のジョン・ホランドの先駆的な研究、特に1975年に出版された彼の著書^{[ 27 ]}によって普及しました。

生物学と遺伝学において、オーストラリアの遺伝学者アレックス・フレイザーも1957年に、生物の人工選択の遺伝的タイプのシミュレーションに関する一連の論文を発表した。 ^{[ 28 ]}生物学者による進化のコンピュータシミュレーションは1960年代初頭に一般的になり、その方法はフレイザーとバーネル（1970）^{[ 29 ]およびクロスビー（1973） [ 30 ]}の著書で説明された。フレイザーのシミュレーションには、現代の突然変異選択遺伝粒子アルゴリズムの必須要素がすべて含まれていた。

数学的な観点から、いくつかの部分的かつノイズのある観測が与えられた場合の信号のランダム状態の条件付き分布は、尤度ポテンシャル関数のシーケンスで重み付けされた信号のランダムな軌跡上のファインマン・カッツ確率によって記述されます。 ^{[ 7 ] [ 8 ]}量子モンテカルロ法、より具体的には拡散モンテカルロ法は、ファインマン・カッツ経路積分の平均場遺伝的タイプの粒子近似としても解釈できます。^{[ 7 ] [ 8 ] [ 9 ] [ 13 ] [ 14 ] [ 31 ] [ 32 ]}量子モンテカルロ法の起源は、1948 年に中性子連鎖反応の平均場粒子解釈を開発したエンリコ・フェルミとロバート・リヒトマイヤーに帰せられることが多いが、^{[ 33 ]}量子システムの基底状態エネルギー (縮小行列モデル) を推定するための最初のヒューリスティックな遺伝的タイプの粒子アルゴリズム (別名リサンプリングまたは再構成モンテカルロ法) は、1984 年にジャック・H・ヘザリントンによるものである。^{[ 13 ]}また、粒子物理学における初期の先駆的な研究として、1951 年に発表された、平均場だがヒューリスティックな遺伝的方法を用いて粒子の透過エネルギーを推定したセオドア・E・ハリスとハーマン・カーンの業績を挙げることもできる。 ^{[ 34 ]}分子化学では、遺伝的ヒューリスティックのような粒子手法（別名、剪定および濃縮戦略）の使用は、1955年のマーシャル N. ローゼンブルースとアリアナ W. ローゼンブルースの先駆的な研究に遡ることができます。^{[ 12 ]}

高度な信号処理やベイズ推論における遺伝的粒子アルゴリズムの使用は比較的新しい。1993 年 1 月、北川源四郎は「モンテカルロフィルタ」を開発し^{[ 35 ]} 、この論文の若干修正されたバージョンが 1996 年に発表された^{[ 36 ]} 。1993年 4 月、Neil J. Gordon らは、彼らの先駆的な研究^{[ 37 ]}で、ベイズ統計推論における遺伝型アルゴリズムの応用を発表した。著者らは、このアルゴリズムを「ブートストラップフィルタ」と名付け、他のフィルタリング方法と比較して、ブートストラップアルゴリズムは、その状態空間やシステムのノイズに関するいかなる仮定も必要としないことを示した。独立して、1990 年代半ばに発表された粒子フィルタに関する Pierre Del Moral ^{[ 2 ]}と Himilcon Carvalho、Pierre Del Moral、André Monin、Gérard Salut ^{[ 38 ]}の研究がある。粒子フィルタは、信号処理においても、1989年から1992年初頭にLAAS-CNRSのP. Del Moral、JC Noyer、G. Rigal、G. Salutによって、STCAN（Service Technique des Constructions et Armes Navales）、IT企業DIGILOG、 LAAS-CNRS（システム分析およびアーキテクチャ研究所）との共同研究による、レーダー/ソナーおよびGPS信号処理問題に関する一連の制限付き機密研究報告書の中で開発されました。 ^{[ 39 ] [ 40 ] [ 41 ] [ 42 ] [ 43 ] [ 44 ]}

1950年から1996年にかけて、粒子フィルタや遺伝的アルゴリズムに関するすべての出版物（計算物理学や分子化学で導入された剪定法やリサンプリングモンテカルロ法を含む）は、さまざまな状況に適用される自然アルゴリズムやヒューリスティックアルゴリズムを紹介しているが、それらの一貫性の証明や、推定値のバイアス、系譜や祖先ツリーに基づくアルゴリズムについての議論は一切行われていない。

これらの粒子アルゴリズムの数学的基礎と最初の厳密な解析は、1996年にピエール・デル・モラル^{[ 2 ] [ 4 ]}によってなされました。論文^{[ 2 ]}には、尤度関数と非正規化条件付き確率測度の粒子近似の不偏性に関する証明も含まれています。この論文で紹介されている尤度関数の不偏粒子推定量は、現在、ベイズ統計推論で使用されています。

ダン・クリサン、ジェシカ・ゲインズ、テリー・ライオンズ^{[ 45 ] [ 46 ] [ 47 ]}、およびピエール・デル・モラル、テリー・ライオンズ^{[ 48 ]}は、1990年代末頃に様々な個体群サイズを持つ分岐型粒子技術を開発した。P.デル・モラル、A.ギオネ、L.ミクロ^{[ 8 ] [ 49 ] [ 50 ]は} 、2000年にこの分野でさらに進歩を遂げた。ピエール・デル・モラルとアリス・ギオネ^{[ 51 ]}は1999年に最初の中心極限定理を証明し、ピエール・デル・モラルとローラン・ミクロ^{[ 8 ]}は2000年にそれを証明した。粒子フィルタの時間パラメータに関する最初の均一収束結果は、1990年代末にピエール・デル・モラルとアリス・ギオネによって開発された。^{[ 49 ] [ 50 ]}系統樹ベースの粒子フィルタ平滑化器の最初の厳密な分析は、2001年にP. Del MoralとL. Micloによって行われた^{[ 52 ]。}

ファインマン・カッツ粒子法と関連する粒子フィルタアルゴリズムの理論は、2000年と2004年に書籍で開発されました。^{[ 8 ] [ 5 ]}これらの抽象的な確率モデルは、遺伝的アルゴリズム、粒子フィルタ、ブートストラップフィルタ、相互作用カルマンフィルタ（別名ラオ・ブラックウェル化粒子フィルタ^{[ 53 ]}）、重要度サンプリングおよびリサンプリングスタイルの粒子フィルタ技術、フィルタリングおよび平滑化問題を解決するための系譜ツリーベースおよび粒子バックワード法を包含しています。その他の粒子フィルタリング手法には、系図ツリーベースモデル^{[ 10 ] [ 5 ] [ 54 ]}、後方マルコフ粒子モデル^{[ 10 ] [ 55 ]} 、適応平均場粒子モデル^{[ 6 ]} 、島型粒子モデル[ ^{56 ] [ 57 ] 、}粒子マルコフ連鎖モンテカルロ法^{[ 58 ] [ 59 ]} 、逐次モンテカルロサンプラー^{[ 60 ] [ 61 ] [ 62 ]}、逐次モンテカルロ近似ベイズ計算法^{[ 63 ]}、および逐次モンテカルロABCベースベイズブートストラップ^{[ 64 ]などがあります。}

粒子フィルタの目的は、観測変数が与えられた場合に状態変数の事後確率密度を推定することです。粒子フィルタは、隠れマルコフモデルで使用することを想定しており、このモデルではシステムに隠れ変数と観測変数の両方が含まれます。観測変数（観測過程）は、既知の関数形式を介して隠れ変数（状態過程）と結び付けられています。同様に、状態変数の進化を定義する動的システムの確率的記述も既知です。

一般的なパーティクルフィルタは、観測測定プロセスを用いて隠れ状態の事後分布を推定します。以下のような状態空間に関して：

${\displaystyle {\begin{array}{cccccccccc}X_{0}&\to &X_{1}&\to &X_{2}&\to &X_{3}&\to &\cdots &{\text{信号}}\\\downarrow &&\downarrow &&\downarrow &&\downarrow &&\cdots &\\Y_{0}&&Y_{1}&&Y_{2}&&Y_{3}&&\cdots &{\text{観測値}}\end{array}}}$

フィルタリング問題とは、隠れ状態の値を順次推定することである。${\displaystyle X_{k}}$観測過程の値を考慮すると${\displaystyle Y_{0},\cdots ,Y_{k},}$任意の時間ステップkにおいて。

すべてのベイズ推定値${\displaystyle X_{k}}$事後密度から追う${\displaystyle p(x_{k}|y_{0},y_{1},...,y_{k})}$粒子フィルタ法は、遺伝的粒子アルゴリズムに関連付けられた経験的尺度を用いて、これらの条件付き確率の近似値を提供する。一方、マルコフ連鎖モンテカルロ法または重点サンプリング法は、事後確率全体をモデル化する。${\displaystyle p(x_{0},x_{1},...,x_{k}|y_{0},y_{1},...,y_{k})}$。

粒子法では、多くの場合、${\displaystyle X_{k}}$そして観察結果${\displaystyle Y_{k}}$次のような形式でモデル化できます。

• ${\displaystyle X_{0},X_{1},\cdots }$はマルコフ過程である$\displaystyle \mathbb {R} ^{d_{x}}}$（一部の人にとって）$d_x ≥ 1$遷移確率密度に従って進化する${\displaystyle p(x_{k}|x_{k-1})}$このモデルは、合成的な方法で記述されることもよくあります。

  ${\displaystyle X_{k}|X_{k-1}=x_{k}\sim p(x_{k}|x_{k-1})}$

初期確率密度${\displaystyle p(x_{0})}$。

• 観察結果${\displaystyle Y_{0},Y_{1},\cdots }$ 状態空間で値を取る$\displaystyle \mathbb {R} ^{d_{y}}}$（一部の人にとって）$d_y ≥ 1$）は、以下の条件を満たす場合に条件付き独立である。${\displaystyle X_{0},X_{1},\cdots }$は既知である。言い換えれば、それぞれ${\displaystyle Y_{k}}$のみに依存する${\displaystyle X_{k}}$さらに、条件付き分布を仮定します。${\displaystyle Y_{k}}$与えられた${\displaystyle X_{k}=x_{k}}$それらは完全に連続しており、総合的に言えば、

  ${\displaystyle Y_{k}|X_{k}=y_{k}\sim p(y_{k}|x_{k})}$

これらの特性を持つシステムの例としては、次のものが挙げられます。

${\displaystyle X_{k}=g(X_{k-1})+W_{k-1}}$

${\displaystyle Y_{k}=h(X_{k})+V_{k}}$

両方${\displaystyle W_{k}}$そして${\displaystyle V_{k}}$これらは既知の確率密度関数を持つ相互に独立したシーケンスであり、gとhは既知の関数です。これら 2 つの方程式は状態空間方程式と見なすことができ、カルマンフィルタの状態空間方程式と似ています。上記の例の関数gとh が線形であり、かつ両方とも${\displaystyle W_{k}}$そして${\displaystyle V_{k}}$分布がガウス分布の場合、カルマンフィルターは正確なベイズフィルタリング分布を見つけます。そうでない場合、カルマンフィルターに基づく手法は、一次近似（EKF）または二次近似（一般的にはUKFですが、確率分布がガウス分布の場合は三次近似も可能です）となります。

マルコフ連鎖の初期分布と遷移がルベーグ測度に関して連続であるという仮定は緩和できます。粒子フィルタを設計するには、遷移をサンプリングできると仮定するだけで十分です。${\displaystyle X_{k-1}\to X_{k}}$マルコフ連鎖の${\displaystyle X_{k},}$尤度関数を計算する${\displaystyle x_{k}\mapsto p(y_{k}|x_{k})}$（例えば、以下に示す粒子フィルタの遺伝的選択突然変異の説明を参照）。マルコフ遷移に関する連続的な仮定${\displaystyle X_{k}}$これは、条件付き密度に対するベイズの定理を使用して、事後分布間の異なる式を非公式に（そしてかなり乱暴な）方法で導出するためにのみ使用されます。

特定の問題では、信号のランダムな状態が与えられた場合の観測値の条件付き分布は密度を持たない場合があります。後者は計算不可能または計算が複雑すぎる場合があります。^{[ 19 ]}このような状況では、追加の近似レベルが必要になります。1つの戦略は、信号を置き換えることです。${\displaystyle X_{k}}$マルコフ連鎖による${\displaystyle {\mathcal {X}}_{k}=\left(X_{k},Y_{k}\right)}$そして、次のような仮想観測を導入する

${\displaystyle {\mathcal {Y}}_{k}=Y_{k}+\epsilon {\mathcal {V}}_{k}\quad {\mbox{for some parameter}}\quad \epsilon \in [0,1]}$

独立な確率変数の列${\displaystyle {\mathcal {V}}_{k}}$既知の確率密度関数を持つ。中心となる考え方は、

${\displaystyle {\text{Law}}\left(X_{k}|{\mathcal {Y}}_{0}=y_{0},\cdots ,{\mathcal {Y}}_{k}=y_{k}\right)\approx _{\epsilon \downarrow 0}{\text{Law}}\left(X_{k}|Y_{0}=y_{0},\cdots ,Y_{k}=y_{k}\right)}$

マルコフ過程に関連する粒子フィルタ${\displaystyle {\mathcal {X}}_{k}=\left(X_{k},Y_{k}\right)}$部分的な観測結果を考慮すると${\displaystyle {\mathcal {Y}}_{0}=y_{0},\cdots ,{\mathcal {Y}}_{k}=y_{k},}$は、進化する粒子の観点から定義される${\displaystyle \mathbb {R} ^{d_{x}+d_{y}}}$明らかに不適切な表記法で与えられた尤度関数を用いて${\displaystyle p({\mathcal {Y}}_{k}|{\mathcal {X}}_{k})}$これらの確率的手法は、近似ベイズ計算(ABC)と密接に関連しています。粒子フィルタの文脈では、これらの ABC 粒子フィルタリング手法は、1998 年に P. Del Moral、J. Jacod、および P. Protter によって導入されました。^{[ 65 ]}これらは、P. Del Moral、A. Doucet、および A. Jasra によってさらに発展しました。^{[ 66 ] [ 67 ]}

条件付き確率に関するベイズの定理は次のようになる。

${\displaystyle p(x_{0},\cdots ,x_{k}|y_{0},\cdots ,y_{k})={\frac {p(y_{0},\cdots ,y_{k}|x_{0},\cdots ,x_{k})p(x_{0},\cdots ,x_{k})}{p(y_{0},\cdots ,y_{k})}}}$

どこ

${\displaystyle {\begin{aligned}p(y_{0},\cdots ,y_{k})&=\int p(y_{0},\cdots ,y_{k}|x_{0},\cdots ,x_{k})p(x_{0},\cdots ,x_{k})dx_{0}\cdots dx_{k}\\p(y_{0},\cdots ,y_{k}|x_{0},\cdots ,x_{k})&=\prod _{l=0}^{k}p(y_{l}|x_{l})\\p(x_{0},\cdots ,x_{k})&=p_{0}(x_{0})\prod _{l=1}^{k}p(x_{l}|x_{l-1})\end{aligned}}}$

粒子フィルタも近似ですが、十分な数の粒子があれば、はるかに正確になります。^{[ 2 ] [ 4 ] [ 5 ] [ 49 ] [ 50 ]}非線形フィルタリング方程式は、次の漸化式で与えられます。

大会と共に${\displaystyle p(x_{0}|y_{0},\cdots ,y_{k-1})=p(x_{0})}$k = 0の場合。非線形フィルタリング問題は、これらの条件付き分布を順次計算することから成ります。

時間範囲nと一連の観測値を固定する。${\displaystyle Y_{0}=y_{0},\cdots ,Y_{n}=y_{n}}$、そして各k = 0, ..., nに対して、以下のように設定します。

${\displaystyle G_{k}(x_{k})=p(y_{k}|x_{k}).}$

この表記では、軌道の集合上の任意の有界関数Fに対して、${\displaystyle X_{k}}$原点k = 0 から時刻k = nまで、ファインマン・カッツの公式が成り立つ。

${\displaystyle {\begin{aligned}\int F(x_{0},\cdots ,x_{n})p(x_{0},\cdots ,x_{n}|y_{0},\cdots ,y_{n})dx_{0}\cdots dx_{n}&={\frac {\int F(x_{0},\cdots ,x_{n})\left\{\prod \limits _{k=0}^{n}p(y_{k}|x_{k})\right\}p(x_{0},\cdots ,x_{n})dx_{0}\cdots dx_{n}}{\int \left\{\prod \limits _{k=0}^{n}p(y_{k}|x_{k})\right\}p(x_{0},\cdots ,x_{n})dx_{0}\cdots dx_{n}}}\\&={\frac {E\left(F(X_{0},\cdots ,X_{n})\prod \limits _{k=0}^{n}G_{k}(X_{k})\right)}{E\left(\prod \limits _{k=0}^{n}G_{k}(X_{k})\right)}}\end{aligned}}}$

ファインマン・カッツ経路積分モデルは、計算物理学、生物学、情報理論、コンピュータ科学など、さまざまな科学分野で出現します。^{[ 8 ] [ 10 ] [ 5 ]}その解釈は応用分野に依存します。たとえば、指示関数を選択した場合${\displaystyle G_{n}(x_{n})=1_{A}(x_{n})}$状態空間のある部分集合において、それらはマルコフ連鎖が特定のチューブ内に留まるという条件付き分布を表します。つまり、次のようになります。

${\displaystyle E\left(F(X_{0},\cdots ,X_{n})|X_{0}\in A,\cdots ,X_{n}\in A\right)={\frac {E\left(F(X_{0},\cdots ,X_{n})\prod \limits _{k=0}^{n}G_{k}(X_{k})\right)}{E\left(\prod \limits _{k=0}^{n}G_{k}(X_{k})\right)}}}$

そして

${\displaystyle P\left(X_{0}\in A,\cdots ,X_{n}\in A\right)=E\left(\prod \limits _{k=0}^{n}G_{k}(X_{k})\right)}$

正規化定数が厳密に正の値になった時点で。

最初は、このようなアルゴリズムはN個の独立したランダム変数から始まります。${\displaystyle \left(\xi _{0}^{i}\right)_{1\leqslant i\leqslant N}}$共通の確率密度関数${\displaystyle p(x_{0})}$遺伝的アルゴリズムの選択-突然変異遷移^{[ 2 ] [ 4 ]}

${\displaystyle \xi _{k}:=\left(\xi _{k}^{i}\right)_{1\leqslant i\leqslant N}{\stackrel {\text{selection}}{\longrightarrow }}{\widehat {\xi }}_{k}:=\left({\widehat {\xi }}_{k}^{i}\right)_{1\leqslant i\leqslant N}{\stackrel {\text{mutation}}{\longrightarrow }}\xi _{k+1}:=\left(\xi _{k+1}^{i}\right)_{1\leqslant i\leqslant N}}$

最適フィルタ進化の更新予測遷移を模倣/近似する（式1）：

• 選択更新遷移中に、N 個の（条件付き）独立な確率変数をサンプリングします。${\displaystyle {\widehat {\xi }}_{k}:=\left({\widehat {\xi }}_{k}^{i}\right)_{1\leqslant i\leqslant N}}$共通の（条件付き）分布

${\displaystyle \sum _{i=1}^{N}{\frac {p(y_{k}|\xi _{k}^{i})}{\sum _{j=1}^{N}p(y_{k}|\xi _{k}^{j})}}\delta _{\xi _{k}^{i}}(dx_{k})}$

どこ${\displaystyle \delta _{a}}$は、特定の状態 a におけるディラック測度を表します。

• 突然変異予測の遷移中、選択された各粒子から${\displaystyle {\widehat {\xi }}_{k}^{i}}$我々は遷移を独立してサンプリングする

${\displaystyle {\widehat {\xi }}_{k}^{i}\longrightarrow \xi _{k+1}^{i}\sim p(x_{k+1}|{\widehat {\xi }}_{k}^{i}),\qquad i=1,\cdots ,N.}$

上記の数式において ${\displaystyle p(y_{k}|\xi _{k}^{i})}$尤度関数を表す${\displaystyle x_{k}\mapsto p(y_{k}|x_{k})}$評価された${\displaystyle x_{k}=\xi _{k}^{i}}$、 そして${\displaystyle p(x_{k+1}|{\widehat {\xi }}_{k}^{i})}$条件付き密度を表す${\displaystyle p(x_{k+1}|x_{k})}$評価された${\displaystyle x_{k}={\widehat {\xi }}_{k}^{i}}$。

各時刻kにおいて、粒子近似は次のようになる。

${\displaystyle {\widehat {p}}(dx_{k}|y_{0},\cdots ,y_{k}):={\frac {1}{N}}\sum _{i=1}^{N}\delta _{{\widehat {\xi }}_{k}^{i}}(dx_{k})\approx _{N\uparrow \infty }p(dx_{k}|y_{0},\cdots ,y_{k})\approx _{N\uparrow \infty }\sum _{i=1}^{N}{\frac {p(y_{k}|\xi _{k}^{i})}{\sum _{i=1}^{N}p(y_{k}|\xi _{k}^{j})}}\delta _{\xi _{k}^{i}}(dx_{k})}$

そして

${\displaystyle {\widehat {p}}(dx_{k}|y_{0},\cdots ,y_{k-1}):={\frac {1}{N}}\sum _{i=1}^{N}\delta _{\xi _{k}^{i}}(dx_{k})\approx _{N\uparrow \infty }p(dx_{k}|y_{0},\cdots ,y_{k-1})}$

遺伝的アルゴリズムと進化的計算のコミュニティでは、上述の突然変異選択マルコフ連鎖は、比例選択を伴う遺伝的アルゴリズムと呼ばれることが多い。ランダムな個体群サイズを含むいくつかの分岐バリアントも論文で提案されている。^{[ 5 ] [ 45 ] [ 48 ]}

粒子法は、すべてのサンプリングベースのアプローチ（例：マルコフ連鎖モンテカルロ法）と同様に、フィルタリング密度を近似するサンプルセットを生成します。

${\displaystyle p(x_{k}|y_{0},\cdots ,y_{k}).}$

例えば、近似事後分布からN個のサンプルが得られるかもしれない。${\displaystyle X_{k}}$ここで、サンプルは上付き文字で次のようにラベル付けされています。

${\displaystyle {\widehat {\xi }}_{k}^{1},\cdots ,{\widehat {\xi }}_{k}^{N}.}$

次に、フィルタリング分布に関する期待値は次のように近似されます。

と

${\displaystyle {\widehat {p}}(dx_{k}|y_{0},\cdots ,y_{k})={\frac {1}{N}}\sum _{i=1}^{N}\delta _{{\widehat {\xi }}_{k}^{i}}(dx_{k})}$

どこ${\displaystyle \delta _{a}}$は、与えられた状態 a におけるディラック測度を表します。関数fは、モンテカルロ法の通常の方法で、ある近似誤差を除いて分布のすべてのモーメントなどを与えることができます。任意の有界関数fに対して近似方程式 (式 2 ) が満たされる場合、次のように記述します。

${\displaystyle p(dx_{k}|y_{0},\cdots ,y_{k}):=p(x_{k}|y_{0},\cdots ,y_{k})dx_{k}\approx _{N\uparrow \infty }{\widehat {p}}(dx_{k}|y_{0},\cdots ,y_{k})={\frac {1}{N}}\sum _{i=1}^{N}\delta _{{\widehat {\xi }}_{k}^{i}}(dx_{k})}$

粒子フィルタは、突然変異と選択の遷移によって進化する遺伝的タイプの粒子アルゴリズムとして解釈できます。祖先系統を追跡することができます。

${\displaystyle \left({\widehat {\xi }}_{0,k}^{i},{\widehat {\xi }}_{1,k}^{i},\cdots ,{\widehat {\xi }}_{k-1,k}^{i},{\widehat {\xi }}_{k,k}^{i}\right)}$

粒子の${\displaystyle i=1,\cdots ,N}$ランダムな状態${\displaystyle {\widehat {\xi }}_{l,k}^{i}}$（添え字l=0,...,kは個体の祖先を表す）${\displaystyle {\widehat {\xi }}_{k,k}^{i}={\widehat {\xi }}_{k}^{i}}$レベル l=0,...,k において、近似式は次のようになります。

経験的尺度を用いて

${\displaystyle {\widehat {p}}(d(x_{0},\cdots ,x_{k})|y_{0},\cdots ,y_{k}):={\frac {1}{N}}\sum _{i=1}^{N}\delta _{\left({\widehat {\xi }}_{0,k}^{i},{\widehat {\xi }}_{1,k}^{i},\cdots ,{\widehat {\xi }}_{k,k}^{i}\right)}(d(x_{0},\cdots ,x_{k}))}$

ここで、F は信号の経路空間上の任意の基礎関数を表します。より簡潔な形式では、（式 3）は以下と同等です。

${\displaystyle {\begin{aligned}p(d(x_{0},\cdots ,x_{k})|y_{0},\cdots ,y_{k})&:=p(x_{0},\cdots ,x_{k}|y_{0},\cdots ,y_{k})\,dx_{0}\cdots dx_{k}\\&\approx _{N\uparrow \infty }{\widehat {p}}(d(x_{0},\cdots ,x_{k})|y_{0},\cdots ,y_{k})\\&:={\frac {1}{N}}\sum _{i=1}^{N}\delta _{\left({\widehat {\xi }}_{0,k}^{i},\cdots ,{\widehat {\xi }}_{k,k}^{i}\right)}(d(x_{0},\cdots ,x_{k}))\end{aligned}}}$

粒子フィルタはさまざまな方法で解釈できます。確率論的な観点からは、非線形フィルタリング方程式の平均場粒子解釈と一致します。最適フィルタ進化の更新予測遷移は、個体の古典的な遺伝的型選択と突然変異の遷移として解釈することもできます。逐次重要度リサンプリング手法は、重要度サンプリングとブートストラップリサンプリングステップを組み合わせたフィルタリング遷移の別の解釈を提供します。最後に、粒子フィルタは、リサイクル機構を備えた受容拒否手法と見なすことができます。^{[ 10 ] [ 5 ]}

粒子フィルタの収束の解析は、1996年に^{[ 2 ] [ 4 ]}、2000年に書籍^{[ 8 ]}および一連の記事^{[ 48 ] [ 49 ] [ 50 ] [ 51 ] [ 52 ] [ 68 ] [ 69 ]}で開始されました。より最近の展開は、書籍^{[ 10 ] [ 5 ]に記載されています。}フィルタリング方程式が安定している場合 (誤った初期条件を修正するという意味で)、粒子粒子推定値のバイアスと分散は、

${\displaystyle I_{k}(f):=\int f(x_{k})p(dx_{k}|y_{0},\cdots ,y_{k-1})\approx _{N\uparrow \infty }{\widehat {I}}_{k}(f):=\int f(x_{k}){\widehat {p}}(dx_{k}|y_{0},\cdots ,y_{k-1})}$

非漸近一様推定値によって制御される

${\displaystyle \sup _{k\geqslant 0}\left\vert E\left({\widehat {I}}_{k}(f)\right)-I_{k}(f)\right\vert \leqslant {\frac {c_{1}}{N}}}$

${\displaystyle \sup _{k\geqslant 0}E\left(\left[{\widehat {I}}_{k}(f)-I_{k}(f)\right]^{2}\right)\leqslant {\frac {c_{2}}{N}}}$

1 で制限される任意の関数fおよびいくつかの有限定数に対して${\displaystyle c_{1},c_{2}.}$ さらに、${\displaystyle x\geqslant 0}$:

${\displaystyle \mathbf {P} \left(\left|{\widehat {I}}_{k}(f)-I_{k}(f)\right|\leqslant c_{1}{\frac {x}{N}}+c_{2}{\sqrt {\frac {x}{N}}}\land \sup _{0\leqslant k\leqslant n}\left|{\widehat {I}}_{k}(f)-I_{k}(f)\right|\leqslant c{\sqrt {\frac {x\log(n)}{N}}}\right)>1-e^{-x}}$

いくつかの有限定数に対して${\displaystyle c_{1},c_{2}}$これは、粒子推定値の漸近バイアスと分散、および有限定数cに関連しています。1 ステップ最適予測器を最適フィルタ近似に置き換えても、同じ結果が得られます。

祖先の系譜をたどる

${\displaystyle \left({\widehat {\xi }}_{0,k}^{i},{\widehat {\xi }}_{1,k}^{i},\cdots ,{\widehat {\xi }}_{k-1,k}^{i},{\widehat {\xi }}_{k,k}^{i}\right),\quad \left(\xi _{0,k}^{i},\xi _{1,k}^{i},\cdots ,\xi _{k-1,k}^{i},\xi _{k,k}^{i}\right)}$

個人の${\displaystyle {\widehat {\xi }}_{k}^{i}\left(={\widehat {\xi }}_{k,k}^{i}\right)}$そして${\displaystyle \xi _{k}^{i}\left(={\xi }_{k,k}^{i}\right)}$各時間ステップkにおいて、粒子近似も得られます。

${\displaystyle {\begin{aligned}{\widehat {p}}(d(x_{0},\cdots ,x_{k})|y_{0},\cdots ,y_{k})&:={\frac {1}{N}}\sum _{i=1}^{N}\delta _{\left({\widehat {\xi }}_{0,k}^{i},\cdots ,{\widehat {\xi }}_{0,k}^{i}\right)}(d(x_{0},\cdots ,x_{k}))\\&\approx _{N\uparrow \infty }p(d(x_{0},\cdots ,x_{k})|y_{0},\cdots ,y_{k})\\&\approx _{N\uparrow \infty }\sum _{i=1}^{N}{\frac {p(y_{k}|\xi _{k,k}^{i})}{\sum _{j=1}^{N}p(y_{k}|\xi _{k,k}^{j})}}\delta _{\left(\xi _{0,k}^{i},\cdots ,\xi _{0,k}^{i}\right)}(d(x_{0},\cdots ,x_{k}))\\&\ \\{\widehat {p}}(d(x_{0},\cdots ,x_{k})|y_{0},\cdots ,y_{k-1})&:={\frac {1}{N}}\sum _{i=1}^{N}\delta _{\left(\xi _{0,k}^{i},\cdots ,\xi _{k,k}^{i}\right)}(d(x_{0},\cdots ,x_{k}))\\&\approx _{N\uparrow \infty }p(d(x_{0},\cdots ,x_{k})|y_{0},\cdots ,y_{k-1})\\&:=p(x_{0},\cdots ,x_{k}|y_{0},\cdots ,y_{k-1})dx_{0},\cdots ,dx_{k}\end{aligned}}}$

これらの経験的近似は粒子積分近似と同等である。

${\displaystyle {\begin{aligned}\int F(x_{0},\cdots ,x_{n}){\widehat {p}}(d(x_{0},\cdots ,x_{k})|y_{0},\cdots ,y_{k})&:={\frac {1}{N}}\sum _{i=1}^{N}F\left({\widehat {\xi }}_{0,k}^{i},\cdots ,{\widehat {\xi }}_{0,k}^{i}\right)\\&\approx _{N\uparrow \infty }\int F(x_{0},\cdots ,x_{n})p(d(x_{0},\cdots ,x_{k})|y_{0},\cdots ,y_{k})\\&\approx _{N\uparrow \infty }\sum _{i=1}^{N}{\frac {p(y_{k}|\xi _{k,k}^{i})}{\sum _{j=1}^{N}p(y_{k}|\xi _{k,k}^{j})}}F\left(\xi _{0,k}^{i},\cdots ,\xi _{k,k}^{i}\right)\\&\ \\\int F(x_{0},\cdots ,x_{n}){\widehat {p}}(d(x_{0},\cdots ,x_{k})|y_{0},\cdots ,y_{k-1})&:={\frac {1}{N}}\sum _{i=1}^{N}F\left(\xi _{0,k}^{i},\cdots ,\xi _{k,k}^{i}\right)\\&\approx _{N\uparrow \infty }\int F(x_{0},\cdots ,x_{n})p(d(x_{0},\cdots ,x_{k})|y_{0},\cdots ,y_{k-1})\end{aligned}}}$