Többrészecske szűrő

Többrészecskeszűrő [1] ( MPF , angol részecskeszűrő - "partticle filter", "partticle filter", "corpuscular filter") - szekvenciális Monte Carlo módszer - rekurzív algoritmus becslési problémák numerikus megoldására ( szűrés , simítás ), különösen nemlineáris és nem Gauss esetekre. N. Gordon, D. Salmond és A. Smith 1993-as leírása [2] óta különféle területeken használták – navigáció, robotika , számítógépes látás .

Az ilyen problémákra általánosan használt módszerekhez képest - kiterjesztett Kálmán -szűrők (EKF) - a többrészecskeszűrők nem függenek a linearizációs vagy közelítési módszerektől . A hagyományos EKF nem birkózik meg jól a lényegében nemlineáris modellekkel, valamint a rendszerzaj és a Gauss-tól erősen eltérő mérések esetén, ezért különféle módosításokat fejlesztettek ki, mint például az UKF ( angolul unscented KF ), a QKF ( Angol Quadrature KF ), stb. ][3 Meg kell jegyezni, hogy viszont a többrészecskeszűrők nagyobb igénybevételt jelentenek a számítási erőforrásokkal szemben.

A "részecskeszűrő" kifejezést Del Moral 1996-ban [4] , a "szekvenciális Monte Carlo" kifejezést Liu és Chen 1998-ban alkotta meg.

A gyakorlatban használt sok részecskeszűrőt egy szekvenciális Monte Carlo módszer alkalmazásával származtatják céleloszlások sorozatára [ 5] .

A probléma leírása

Az FFM-et úgy tervezték, hogy megbecsülje a látens változók sorrendjét a következő időpontban végzett megfigyelések alapján . A bemutatás egyszerűsítése érdekében feltételezzük, hogy dinamikus rendszerről van szó , és valós állapot és mérési vektorok [1] . $x_{n}$ $n=1,2,\pontok$ $y_{n}$ $n=1,2,\pontok$ $x_{n}$ $y_{n}$

A rendszer állapotának sztochasztikus egyenlete a következő:

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

ahol a rendszer állapotának megváltoztatásának függvénye egy valószínűségi változó , a perturbáló hatás. $f_{k}$ $v_{k}$

Mérési egyenlet:

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

ahol a mérési függvény, egy valószínűségi változó, mérési zaj. ${\displaystyle h_{k))$ ${\displaystyle w_{k))$

A és függvények általában nemlineárisak , és a rendszerzaj ( ) és a mérések ( ) statisztikai jellemzői ismertnek tekinthetők. $f_{k}$ ${\displaystyle h_{k))$ $v_{k}$ ${\displaystyle w_{k))$

A szűrés feladata, hogy az akkor ismert mérési eredmények alapján becslést kapjunk . ${\hat {x}}_{k}$ $k$ ${\displaystyle y_{1:k))$

Rejtett Markov-modell és Bayes-i következtetés

Tekintsünk egy diszkrét Markov-folyamatot a következő valószínűségi eloszlással: $\{X_{n}\}_{n\geqslant 1}$

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

és ,

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

(egy)

ahol a valószínűségi sűrűség , a feltételes valószínűségi sűrűség ( átmeneti valószínűségi sűrűség) az átmenetben -ból -be . $\mu (x)$ $f(x_{n}\mid x_{n-1})$ ${\displaystyle x_{n-1))$ $x_{n}$

Itt a jelölés azt jelenti, hogy a feltétel a következőképpen van elosztva . $X\mid Y\sim f(\dots )$ $x$ $Y$ $f(\dots )$

A folyamat megvalósulását (rejtett változók ) egy másik véletlenszerű folyamaton – a mérési folyamaton – keresztül figyeljük meg , határsűrűségekkel : $\{X_{n}\}$ $x_{n}$ ${\displaystyle \{Y_{n}\}_{n\geqslant 1))$

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

(2)

ahol a feltételes valószínűségi sűrűség ( mérés sűrűsége ), a mérések statisztikailag függetlennek minősülnek . $h(y_{n}\közép x_{n})$

A modell a következő átmenet diagrammal szemléltethető:

{\begin{array}{cccccccccc}X_{1}&\rightarrow &X_{2}&\rightarrow &X_{3}&\rightarrow &X_{4}&\rightarrow &\ldots &\\\downarrow &&\ lefelé mutató nyíl &&\downarrow &&\downarrow &&\lpontok &\\Y_{1}&&Y_{2}&&Y_{3}&&Y_{4}&&\lpontok &\end{array}}

Az egyszerűség kedvéért feltételezzük, hogy az átmeneti sűrűség és a mérési sűrűség nem függ -től . Feltételezzük, hogy a modell paraméterei adottak. $n$

Az így definiált rendszer és mérési modell Rejtett Markov-modellként ismert [6] .

Az (1) egyenlet meghatározza a folyamat előzetes eloszlását : $\{X_{n}\}$

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

(3)

Hasonlóképpen (2) határozza meg a valószínűségi függvényt :

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

(négy)

Itt és lent a jelölések jelölése . ${\displaystyle x_{k:l))$ $k\leqslant l$ $(x_{k},\pontok,x_{l})$

Így a mérések ismert megvalósításaira vonatkozó Bayes -i következtetés , amelyet rendre és jelöl , a utólagos eloszláson fog alapulni. $\{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)

ahol (itt a domináns mérték): $dx_{1:n}$

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

Fontossági mintavétel

Lásd még: Fontossági mintavétel .

A Monte Carlo módszer lehetővé teszi meglehetősen bonyolult valószínűségi eloszlások tulajdonságainak értékelését, például az átlagok és a variancia integrál formájában történő kiszámításával [3] :

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

hol van a becslés függvénye. Például az átlaghoz a következőket teheti: . $\az adó)$ $\theta (x)=x$

Ha az analitikus megoldás nem lehetséges, a probléma numerikusan megoldható úgy, hogy sűrűségű véletlenszerű mintákat generálunk , jelöljük őket , és megkapjuk a mintapontok számtani átlagát [3] : $p(x)$ ${x^{(i)}}_{1\leqslant i\leqslant N}$

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

Általánosabb esetben, amikor a mintavételezés nehézkes, más eloszlást alkalmaznak (az úgynevezett angol instrumentális vagy fontossági eloszlást ), és a becslés torzítatlanságának megőrzése érdekében súlyozási együtthatókat vezetnek be az arány alapján [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)})))

majd kiszámítja a súlyozott átlagot:

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

Újramintavétel

Bár a segédeloszlást főként a fő eloszlásból történő mintavétel egyszerűsítésére használják , gyakran használják a „sampling and resampling by significance” ( angol mintavételezési fontosság resampling, SIR ) eljárást. Ez az eljárás két szakaszból áll: tényleges mintavétel a szignifikancia alapján a súlyok kiszámításával , és további mintavételezés olyan pontokból, amelyek figyelembe veszik ezeket a súlyokat [3] . $p$ $w_{i}$

Az újramintavételezés különösen a soros szűrők esetében szükséges [3] .

Szekvenciális Monte Carlo módszer

A szekvenciális Monte Carlo ( SMC ) algoritmusok legismertebb példái a többrészecskés szűrési és simítási módszerek . Amennyire a szakirodalom sokszor nem tesz különbséget köztük. Az SMC azonban az algoritmusok szélesebb osztályát tartalmazza, amelyek bonyolultabb közelítő szűrési és simítási módszerek leírására alkalmazhatók [7] .

A szekvenciális Monte Carlo módszerek a Monte Carlo módszerek egy osztálya, amelyek szekvenciálisan mintát vesznek a növekvő dimenziójú célvalószínűségi sűrűségek sorozatából, ahol mindegyik egy derékszögű hatványon van definiálva [5] . $\{f_{n}(x_{1:n})\}$ $f_{n}(x_{1:n})$ ${\mathcal {X}}^{n}$

Ha a sűrűséget így írjuk: [5]

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

, ahol

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

pontszerűen ismert, és

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

akkor egy normalizálódó, esetleg ismeretlen állandó

Az SMC algoritmus közelítéseket és becsléseket talál a -ra . $f_{k}(x_{1:k})$ $Z_{k}$ $k=1,2,\pontok$

Például a szűrés esetére feltehetjük (lásd (5) ):

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

és

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

amiből nekünk lesz:

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})

A kimenet kihagyásával a prediktor-korrektor séma a következőképpen ábrázolható [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})

- előrejelző,

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})}}

- korrektor.

A szorzó egy normalizáló állandó, amely nem szükséges a normál SMC algoritmushoz. ${\displaystyle (p(y_{n}\mid y_{1:n-1}))^{-1))$

Algoritmus

Egy tipikus többrészecskeszűrő algoritmus a következőképpen ábrázolható [3] :

MCF algoritmus -- inicializálás ha i = 1...N: minta innen

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

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

-- kezdeti súlyok

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

kts n = 1...T esetén: ha RESELECT akkor -- N részecske indexének kiválasztása a súlyok szerint = SelectByWeight( )

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

j_{1:N}

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

ha i = 1...N:

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

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

másképp ha i = 1...N:

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

ha i = 1...N: -- részecsketerjedési lépés

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

-- skála frissítés

\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)}\ közepe x_{n-1}^{(i)},y_{n})

kts -- a súlyok normalizálása

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

ha i = 1...N:

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

kts

Lásd még

Kálmán szűrő#UKF

Jegyzetek

↑ 1 2 Mikaelyan, 2011 .
↑ Gordon, Salmond, Smith, 1993 .
↑ 1 2 3 4 5 6 7 8 Cappé, Godsill, Moulines, 2007 .
↑ Del Moral, Pierre. Nem lineáris szűrés: kölcsönható részecske-oldat. (angol) // Markov Processes and Related Fields. - 1996. - 1. évf. 2 , sz. 4 . - P. 555-580 .
↑ 1 2 3 Doucet, Johansen, 2011 .
↑ Doucet, Johansen, 2011 , 2.1 Rejtett Markov-modellek és következtetési célok.
↑ Doucet, Johansen, 2011 , 3 szekvenciális Monte Carlo-módszer.

Irodalom

Doucet Arnaud, Johansen Adam M. Oktatóanyag a részecskeszűrésről és a simításról: tizenöt évvel később // 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 és Godsill, Simon J. és Moulines, Eric. A szekvenciális Monte Carlo meglévő módszereinek és legújabb fejlesztéseinek áttekintése // Proceedings of the IEEE. - IEEE, 2007. - T. 95 , 5. sz . - P. 899-924. — ISSN 0018-9219 . Az eredetiből archiválva: 2016. március 10.

Doucet, Arnaud és de Freitas, Nando és Gordon, Neil. Bevezetés a szekvenciális Monte Carlo-módszerekbe // Szekvenciális Monte Carlo-módszerek a gyakorlatban / Doucet, Arnaud és de Freitas, Nando és Gordon, Neil. — Springer New York. - 3-14 p. — ISBN 978-1-4419-2887-0 .
Arulampalam, MS and Maskell, S. and Gordon, N. and Clapp, T. A Tutorial on Particle Filters for Online Nonlinear/non-Gaussian Bayesian Tracking // Trans . Sig. Proc.. - IEEE Press, 2002. - Vol. 50 , sz. 2 . - P. 174-188. — ISSN 1053-587X . Lásd még a korábbi verziót
Gordon, NJ; Salmond, DJ; Smith, AFM Újszerű megközelítés a nemlineáris/nem Gauss-féle Bayes-féle állapotbecsléshez // IEEE Proceedings F, Radar and Signal Processing. - IET, 1993. - 1. évf. 140 , sz. 2 . - 107-113 . o . - doi : 10.1049/ip-f-2.1993.0015 .
Mikaelyan S. V. A becslés valószínűségi sűrűségének többpontos közelítésén alapuló szűrési módszerek a célpont mozgásának paramétereinek nemlineáris karakterisztikával rendelkező mérővel történő meghatározásának problémájában Nauka i obrazovanie: elektronikus kiadás. - MSTU im. N. E. Bauman, 2011. - ISSN 1994-0408 . Az eredetiből archiválva: 2016. március 4.
Ristic, B., Arulampalam, S., Gordon, N. Beyond the Kalman Filter - Particle Filters for Tracking Applications. - Artech Ház, 2004. - 299 p. — ISBN 9781580536318 .

Simon, Dan. 15 A részecskeszűrő // Optimális állapotbecslés: Kalman, H ∞ és nemlineáris megközelítések . - Wiley-Interscience, 2006. - P. 461-480 . — ISBN 0471708585 .

Linkek

Részecskeszűrő , SciPy Szakácskönyv