Filtru multiparticule

Filtru multiparticule [1] ( MPF , filtru de particule în engleză - "filtru de particule", "filtru de particule", "filtru corpuscular") - o metodă Monte Carlo secvențială - un algoritm recursiv pentru rezolvarea numerică a problemelor de estimare ( filtrare , netezire ), în special pentru cazurile neliniare și non- gaussiene . De la descrierea din 1993 [2] de către N. Gordon, D. Salmond și A. Smith, a fost folosită în diverse domenii - navigație, robotică , viziune computerizată .

În comparație cu metodele utilizate în mod obișnuit pentru astfel de probleme - filtrele Kalman extinse (EKF) - filtrele cu particule multiple nu depind de metodele de liniarizare sau de aproximare . EKF convențional nu se descurcă bine cu modelele în esență neliniare, precum și în cazul zgomotului de sistem și măsurătorilor care sunt foarte diferite de Gaussian, prin urmare, au fost dezvoltate diverse modificări, cum ar fi UKF ( English unscented KF ), QKF ( English Quadrature KF ), etc ][3 Trebuie remarcat faptul că, la rândul lor, filtrele multiparticule sunt mai solicitante în ceea ce privește resursele de calcul.

Termenul „filtru de particule” a fost inventat de Del Moral în 1996 [4] și „Monte Carlo secvenţial” de Liu și Chen în 1998.

Multe filtre multiparticule utilizate în practică sunt derivate prin aplicarea unei metode Monte Carlo secvenţiale la o secvenţă de distribuţii ţintă [5] .

Enunțul problemei

FFM este conceput pentru a estima secvența variabilelor latente pe baza observațiilor de la . Pentru simplitatea prezentării, vom presupune că luăm în considerare un sistem dinamic și și sunt vectori de stare reală și respectiv de măsură [1] . $x_{n}$ $n=1,2,\dots$ $y_{n}$ $n=1,2,\dots$ $x_{n}$ $y_{n}$

Ecuația stocastică a stării sistemului are forma:

x_{k}=f_{k}(x_{k-1},v_{k})

unde funcția de modificare a stării sistemului este o variabilă aleatorie , efectul perturbator. $f_{k}$ $v_{k}$

Ecuația de măsurare:

y_{k}=h_{k}(x_{k},w_{k})

unde este funcția de măsurare, este o variabilă aleatorie, zgomotul de măsurare. $h_{k)$ $w_{k)$

Funcțiile și sunt în general neliniare , iar caracteristicile statistice ale zgomotului sistemului ( ) și măsurătorilor ( ) se presupune că sunt cunoscute. $f_{k}$ $h_{k)$ $v_{k}$ $w_{k)$

Sarcina de filtrare este de a obține o estimare bazată pe rezultatele măsurătorilor cunoscute la momentul respectiv . ${\pălărie {x}}_{k}$ $k$ $y_{1:k)$

Modelul Markov ascuns și inferența bayesiană

Luați în considerare un proces Markov discret cu următoarele distribuții de probabilitate: $\{X_{n}\}_{n\geqslant 1}$

X_{1}\sim \mu (x_{1})\quad

și ,

X_{n}\mid (X_{n-1}=x_{n-1})\sim f(x_{n}\mid x_{n-1})

(unu)

unde este densitatea de probabilitate , este densitatea de probabilitate condiționată ( densitatea de probabilitate de tranziție ) în tranziția de la la . $\mu (x)$ $f(x_{n}\mid x_{n-1})$ $x_{n-1)$ $x_{n}$

Aici notația înseamnă că condiția este distribuită ca . $X\mid Y\sim f(\dots )$ $X$ $Y$ $f(\dots )$

Realizările procesului (variabile ascunse ) sunt observate printr-un alt proces aleator - procesul de măsurare - cu densități marginale : $\{X_{n}\}$ $x_{n}$ $\{Y_{n}\}_{n\geqslant 1)$

Y_{n}\mid (X_{n}=x_{n})\sim h(y_{n}\mid x_{n})

(2)

unde este densitatea de probabilitate condiționată ( densitatea măsurătorilor ), măsurătorile sunt considerate independente statistic . $h(y_{n}\mid x_{n})$

Modelul poate fi ilustrat prin următoarea diagramă de tranziție:

{\begin{array}{cccccccccc}X_{1}&\rightarrow &X_{2}&\rightarrow &X_{3}&\rightarrow &X_{4}&\rightarrow &\ldots &\\\downarrow &&\ jos &&\downarrow &&\downarrow &&\ldots &\\Y_{1}&&Y_{2}&&Y_{3}&&Y_{4}&&\ldots &\end{array}}

Pentru simplitate, presupunem că densitatea de tranziție și densitatea de măsurare nu depind de . Se presupune că parametrii modelului sunt dați. $n$

Sistemul și modelul de măsurare astfel definite sunt cunoscute sub denumirea de Hidden Markov Model [6] .

Ecuația (1) definește distribuția anterioară a procesului : $\{X_{n}\}$

p(x_{1:n})=\mu (x_{1})\prod _{k=2}^{n}f(x_{k}\mid x_{k-1})

(3)

În mod similar (2) definește funcția de probabilitate :

p(y_{1:n}\mid x_{1:n})=\prod _{k=1}^{n}h(y_{k}\mid x_{k})

(patru)

Aici și mai jos, notația pentru denotă . $x_{k:l)$ $k\leqslant l$ $(x_{k},\dots,x_{l})$

Astfel, inferența bayesiană pentru implementări cunoscute de măsurători , notate respectiv cu și , se va baza pe distribuția posterioară $\{X_{1:n}}\}$ $\{Y_{1:n}}\}$ $\{x_{1:n}}\}$ $\{y_{1:n}}\}$

p(x_{1:n}\mid y_{1:n})={\frac {p(x_{1:n})p(y_{1:n}\mid x_{1:n})}{ p(y_{1:n})}}

(5)

unde (aici este măsura dominantă): $dx_{1:n}$

p(y_{1:n})=\int p(x_{1:n})p(y_{1:n}\mid x_{1:n})\,dx_{1:n}

Eșantionarea importanței

Vezi și Eșantionarea importanței .

Metoda Monte Carlo vă permite să evaluați proprietățile distribuțiilor de probabilitate destul de complexe, de exemplu, calculând mediile și varianța sub forma unei integrale [3] :

{\bar {\theta }}=\int \theta (x)p(x)\,dx

unde este funcția de estimare. De exemplu, pentru medie, puteți pune: . $\taxa)$ $\theta (x)=x$

Dacă o soluție analitică este imposibilă, problema poate fi rezolvată numeric prin generarea de eșantioane aleatorii cu o densitate , notați-le ca , și obținerea mediei aritmetice asupra punctelor eșantionului [3] : $p(x)$ ${x^{(i)}}_{1\leqslant i\leqslant N}$

{\bar {\theta }}\aprox {\frac {1}{N}}\sum _{i=1}^{N}\theta (x^{(i)})

Într-un caz mai general, când eșantionarea de la este dificilă, se aplică o altă distribuție (așa-numita distribuție instrumentală sau de importanță engleză ), iar pentru a menține estimarea nepărtinitoare, se introduc coeficienți de ponderare pe baza raportului [3] : $p$ $q$ $w_{i}$ $r(x^{(i)})=p(x^{(i)})/q(x^{(i)})$

w_{i}={\frac {r(x^{(i)})}{\sum _{j=1}^{N}r(x^{(j)})))

și apoi calculează media ponderată:

{\bar {\theta}}=\int \theta (x)r(x)q(x)\,dx\aprox \sum _{i=1}^{N}w_{i}\theta (x^{(i)})

Reeșantionare

Deși distribuția auxiliară este utilizată în principal pentru a simplifica eșantionarea din distribuția principală , procedura de „sampling and resampling by signification” ( în engleză sampling importance resampling, SIR ) este adesea folosită. Această procedură constă în două etape: eșantionarea efectivă după semnificație cu calculul greutăților și eșantionarea suplimentară a punctelor care iau în considerare aceste greutăți [3] . $p$ $w_{i}$

Reeșantionarea este necesară în special pentru filtrele seriale [3] .

Metoda Monte Carlo secvenţială

Metodele de filtrare a particulelor multiple și de netezire sunt cele mai cunoscute exemple de algoritmi Monte Carlo ( SMC ) secvenţiali . În măsura în care literatura de multe ori nu face distincție între ele. Cu toate acestea, SMC include o clasă mai largă de algoritmi aplicabili pentru a descrie metode aproximative mai complexe de filtrare și netezire [7] .

Metodele Monte Carlo secvenţiale sunt o clasă de metode Monte Carlo care eşantionează secvenţial dintr-o secvenţă de densităţi de probabilitate ţintă de dimensiune crescătoare, unde fiecare este definită pe o putere carteziană [5] . $\{f_{n}(x_{1:n})\}$ $f_{n}(x_{1:n})$ ${\mathcal {X}}^{n}$

Dacă scriem densitatea ca: [5]

f_{n}(x_{1:n})={\frac {\phi _{n}(x_{1:n})}{Z_{n))}

, Unde

\phi _{n}\colon {\mathcal {X}}^{n}\la \mathbb {R} ^{+}

este cunoscut punctual și

Z_{n}=\int \phi _{n}(x_{1:n})\,dx_{1:n}

este o constantă normalizantă, posibil necunoscută, atunci

Algoritmul SMC va găsi aproximări și estimări pentru . $f_{k}(x_{1:k})$ $Z_{k}$ $k=1,2,\dots$

De exemplu, pentru cazul filtrării, se poate pune (vezi (5) ):

\phi _{n}(x_{1:n})=p(x_{1:n})p(y_{1:n}\mid x_{1:n})

și

Z_{n}=p(y_{1:n})

din care vom avea:

f_{n}(x_{1:n})={\frac {p(x_{1:n})p(y_{1:n}\mid x_{1:n})}{p(y_{1 :n})}}=p(x_{1:n}|y_{1:n})

Omițând rezultatul, schema predictor-corector poate fi reprezentată după cum urmează [3] :

p(x_{1:n}\mid y_{1:n-1})=p(x_{1:n-1}\mid y_{1:n-1})f(x_{n} \mid x_{n-1})

- predictor,

p(x_{1:n}\mid y_{1:n})={\frac {h(y_{n}\mid x_{n})p(x_{1:n}\mid y_{ 1:n-1})}{p(y_{n}\mid y_{1:n-1})}}

- corector.

Multiplicatorul este o constantă de normalizare care nu este necesară pentru algoritmul SMC normal. $(p(y_{n}\mid y_{1:n-1}))^{-1)$

Algoritm

Un algoritm tipic de filtru multiparticule poate fi reprezentat după cum urmează [3] :

algoritmul MCF -- inițializare pentru i = 1...N: mostra din

\xi _{0}^{(i))

q_{0}(x_{0}\mid y_{0})

-- greutăți inițiale

\omega _{0}^{(i)}:=h(y_{0}\mid \xi _{0}^{(i)})\mu (\xi _{0}^{( i)})\ /\ q_{0}(\xi _{0}^{(i)}\mid y_{0})

kts pentru n = 1...T: dacă RESELECTARE atunci -- selectați indici de N particule în funcție de greutăți = SelectByWeight( )

j_{i}\in \{1,\dots ,N\}

j_{1:N}

\{w_{n-1}^{(j)}\}

pentru i = 1...N:

{\displaystyle x_{n-1}^{(i)}:=\xi _{n-1}^{(j_{i)))))

w_{n-1}^{(i)}:=1/N

in caz contrar pentru i = 1...N:

x_{n-1}^{(i)}:=\xi _{n-1}^{(i))

pentru i = 1...N: -- etapa de propagare a particulelor

\xi _{n}^{(i)}\sim q_{n}(\xi _{n}^{(i)}\mid \xi _{n-1}^{(i)} ,y_{n})

-- actualizare la scară

\omega _{n}^{(i)}:=w_{n-1}^{(i)}h(y_{n}\mid \xi _{n}^{(i)}) f(\xi _{n}^{(i)}\mid x_{n-1}^{(i)})\ /\ q_{n}(\xi _{n}^{(i)}\ mijlocul x_{n-1}^{(i)},y_{n})

kts -- normalizarea greutăților

s:=\sum _{j=1}^{N}\omega _{n}^{(j))

pentru i = 1...N:

w_{n}^{(i)}:=\omega _{n}^{(i)}/s

kts

Vezi și

Filtru Kalman #UKF

Note

↑ 1 2 Mikaelyan, 2011 .
↑ Gordon, Salmond, Smith, 1993 .
↑ 1 2 3 4 5 6 7 8 Cappé, Godsill, Moulines, 2007 .
↑ Del Moral, Pierre. Filtrare neliniară: soluție de particule care interacționează. (Engleză) // Procese Markov și câmpuri conexe. - 1996. - Vol. 2 , nr. 4 . - P. 555-580 .
↑ 1 2 3 Doucet, Johansen, 2011 .
^ Doucet , Johansen, 2011 , 2.1 Hidden Markov Models and Inference Aims.
↑ Doucet, Johansen, 2011 , 3 Sequential Monte Carlo Methods.

Literatură

Doucet Arnaud, Johansen Adam M. A Tutorial on Particle Filtering and Smoothing: Fifteen Years Later // The Oxford Handbook of Nonlinear Filtering / D. Crisan, B. Rozovsky. - Oxford: Oxford University Press, 2011. - P. 656-704. — ISBN 978-0-19-953290-2 .
Cappe, Olivier și Godsill, Simon J. și Moulines, Eric. O prezentare generală a metodelor existente și a progreselor recente în Monte Carlo secvenţial // Proceedings of IEEE. - IEEE, 2007. - T. 95 , nr. 5 . - P. 899-924. — ISSN 0018-9219 . Arhivat din original pe 10 martie 2016.

Doucet, Arnaud și de Freitas, Nando și Gordon, Neil. O introducere în metodele Monte Carlo secvențiale // Metodele Monte Carlo secvențiale în practică / Doucet, Arnaud și de Freitas, Nando și Gordon, Neil. — Springer New York. - 3-14 p. — ISBN 978-1-4419-2887-0 .
Arulampalam, MS și Maskell, S. și Gordon, N. și Clapp, T. A Tutorial on Particle Filters for Online Nonlinear/non-Gauss Bayesian Tracking // Trans . Sig. Proc.. - IEEE Press, 2002. - Vol. 50 , nr. 2 . - P. 174-188. — ISSN 1053-587X . Vezi și versiunea anterioară
Gordon, NJ; Salmond, DJ; Smith, AFM Abordare nouă a estimării stării neliniare/non-Gaussian Bayesian // IEEE Proceedings F, Radar and Signal Processing. - IET, 1993. - Vol. 140 , nr. 2 . - P. 107-113 . - doi : 10.1049/ip-f-2.1993.0015 .
Mikaelyan S. V. Metode de filtrare bazate pe aproximarea multipunct a densității de probabilitate a estimării în problema determinării parametrilor mișcării țintei folosind un metru cu o caracteristică neliniară Nauka i obrazovanie: ediție electronică. - MSTU im. N. E. Bauman, 2011. - ISSN 1994-0408 . Arhivat din original pe 4 martie 2016.
Ristic, B., Arulampalam, S., Gordon, N. Dincolo de filtrul Kalman - Filtre de particule pentru aplicații de urmărire. - Casa Artech, 2004. - 299 p. — ISBN 9781580536318 .

Simon, Dan. 15 Filtrul de particule // Estimarea stării optime: Kalman, H ∞ și Abordări neliniare . - Wiley-Interscience, 2006. - P. 461-480 . — ISBN 0471708585 .

Link -uri

Filtru de particule , Carte de bucate SciPy