Monihiukkassuodatin

Monihiukkassuodatin [1] ( MPF , englanniksi hiukkassuodatin - "partikkelisuodatin", "partikkelisuodatin", "korpuskulaarinen suodatin") - peräkkäinen Monte Carlo -menetelmä - rekursiivinen algoritmi estimointiongelmien numeeriseen ratkaisemiseen ( suodatus , tasoitus ), erityisesti epälineaarisille ja ei- gaussisille tapauksille. N. Gordonin, D. Salmondin ja A. Smithin vuonna 1993 [2] julkaisemasta kuvauksesta lähtien sitä on käytetty useilla aloilla - navigoinnissa, robotiikassa , tietokonenäössä .

Verrattuna tällaisissa ongelmissa yleisesti käytettyihin menetelmiin - laajennetut Kalman-suodattimet (EKF) - monipartikkelisuodattimet eivät ole riippuvaisia linearisointi- tai approksimaatiomenetelmistä . Perinteinen EKF ei selviä hyvin oleellisesti epälineaaristen mallien kanssa, samoin kuin järjestelmän kohinan ja Gaussista hyvin poikkeavien mittausten tapauksessa, joten erilaisia modifikaatioita on kehitetty, kuten UKF ( englanniksi unscented KF ), QKF ( Englanti Quadrature KF ) jne. ][3 On huomattava, että monipartikkelisuodattimet puolestaan vaativat enemmän laskentaresursseja.

Del Moral keksi termin "hiukkassuodatin" vuonna 1996 [4] ja "peräkkäinen Monte Carlo" Liu ja Chen vuonna 1998.

Monet käytännössä käytetyt monipartikkelisuodattimet johdetaan soveltamalla peräkkäistä Monte Carlo -menetelmää kohdejakaumien sekvenssiin [ 5] .

Ongelman selvitys

FFM on suunniteltu arvioimaan piilevien muuttujien sekvenssi pisteen havaintojen perusteella . Esityksen yksinkertaisuuden vuoksi oletetaan, että tarkastelemme dynaamista järjestelmää ja ovat reaalitila- ja mittausvektoreita [1] . $x_{n}$ ${\näyttötyyli n=1,2,\pisteet }$ $y_{n}$ ${\näyttötyyli n=1,2,\pisteet }$ $x_{n}$ $y_{n}$

Järjestelmän tilan stokastinen yhtälö on muotoa:

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

jossa järjestelmän tilan muuttamisen funktio on satunnaismuuttuja , häiritsevä vaikutus. $f_{k}$ $v_{k}$

Mittausyhtälö:

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

missä on mittausfunktio, on satunnaismuuttuja, mittauskohina. ${\displaystyle h_{k))$ ${\displaystyle w_{k))$

Funktiot ja ovat yleensä epälineaarisia , ja järjestelmän kohinan ( ) ja mittausten ( ) tilastolliset ominaisuudet oletetaan tunnetuiksi. $f_{k}$ ${\displaystyle h_{k))$ $v_{k}$ ${\displaystyle w_{k))$

Suodatuksen tehtävänä on saada arvio kulloinkin tiedossa olevien mittaustulosten perusteella . ${\hat {x}}_{k}$ $k$ ${\näyttötyyli y_{1:k))$

Piilotettu Markovin malli ja Bayesin päättely

Tarkastellaan diskreettiä Markov-prosessia seuraavilla todennäköisyysjakaumilla: $\{X_{n}\}_{n\geqslant 1}$

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

ja ,

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

(yksi)

missä on todennäköisyystiheys , on ehdollinen todennäköisyystiheys ( siirtymätodennäköisyystiheys ) siirtymisessä kohteesta . $\mu (x)$ $f(x_{n}\mid x_{n-1})$ ${\näyttötyyli x_{n-1))$ $x_{n}$

Tässä merkintä tarkoittaa, että ehto jaetaan muodossa . $X\mid Y\sim f(\dots )$ $X$ $Y$ $f(\dots )$

Prosessin realisaatioita (piilotetut muuttujat ) tarkkaillaan toisen satunnaisen prosessin - mittausprosessin - kautta marginaalitiheydillä : $\{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)

missä on ehdollinen todennäköisyystiheys ( mittausten tiheys ), mittauksia pidetään tilastollisesti riippumattomina . $h(y_{n}\mid x_{n})$

Mallia voidaan havainnollistaa seuraavalla siirtymäkaaviolla:

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

Yksinkertaisuuden vuoksi oletetaan, että siirtymätiheys ja mittaustiheys eivät riipu . Mallin parametrit oletetaan annetuiksi. $n$

Näin määritelty järjestelmä ja mittausmalli tunnetaan nimellä Hidden Markov Model [6] .

Yhtälö (1) määrittelee prosessin aiemman jakauman : $\{X_{n}\}$

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

(3)

Samalla tavalla (2) määrittelee todennäköisyysfunktion :

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

(neljä)

Tässä ja alla merkintä tarkoittaa . ${\näyttötyyli x_{k:l))$ $k\leqslant l$ $(x_{k},\pisteet ,x_{l})$

Siten Bayesin päättely tunnetuille mittausten toteutuksille , joita merkitään vastaavasti ja , perustuu posteriorijakaumaan $\{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)

missä (tässä on hallitseva mitta): $dx_{1:n}$

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

Tärkeys Otanta

Katso myös tärkeysnäytteenotto .

Monte Carlo -menetelmän avulla voit arvioida melko monimutkaisten todennäköisyysjakaumien ominaisuuksia esimerkiksi laskemalla keskiarvot ja varianssi integraalin muodossa [3] :

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

missä on estimointifunktio. Esimerkiksi keskiarvoksi voit laittaa: . $\theta (x)$ ${\näyttötyyli \theta (x)=x}$

Jos analyyttinen ratkaisu on mahdoton, ongelma voidaan ratkaista numeerisesti generoimalla satunnaisotoksia, joiden tiheys on , merkitsemällä ne ja saamalla näytepisteiden aritmeettinen keskiarvo [3] : $p(x)$ ${x^{(i)}}_{1\leqslant i\leqslant N}$

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

Yleisemmässä tapauksessa, kun näytteenotto on vaikeaa, käytetään toista jakaumaa (ns. englanninkielinen instrumentaali- tai tärkeysjakauma ), ja estimaatin puolueettomuuden pitämiseksi otetaan käyttöön painokertoimet suhteessa [3] : $s$ $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)})))

ja laskee sitten painotetun keskiarvon:

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

Uudelleennäytteenotto

Vaikka apujakaumaa käytetään pääasiassa yksinkertaistamaan näytteenottoa pääjakaumasta, käytetään usein menetelmää "sampling and resampling by significance" ( englanniksi sampling tärkeä resampling, SIR ). Tämä menettely koostuu kahdesta vaiheesta: varsinainen näytteenotto merkitsevyyden mukaan painojen laskennassa ja lisänäytteenotto pisteistä, joissa nämä painot otetaan huomioon [3] . $s$ $w_{i}$

Uudelleennäytteistys on erityisen tarpeen sarjasuodattimille [3] .

Peräkkäinen Monte Carlo -menetelmä

Monihiukkassuodatus- ja tasoitusmenetelmät ovat tunnetuimpia esimerkkejä peräkkäisistä Monte Carlo ( SMC ) -algoritmeista . Siinä määrin, että kirjallisuus ei usein tee eroa niiden välillä. SMC sisältää kuitenkin laajemman luokan algoritmeja, joita voidaan soveltaa monimutkaisempien likimääräisten suodatus- ja tasoitusmenetelmien kuvaamiseen [7] .

Sekvenssiset Monte Carlo -menetelmät ovat luokka Monte Carlo -menetelmiä, jotka ottavat peräkkäin näytteitä kasvavan ulottuvuuden tavoitetodennäköisyystiheyksien sekvenssistä, jossa jokainen määritellään karteesisella potenssilla [5] . $\{f_{n}(x_{1:n})\}$ $f_{n}(x_{1:n})$ ${\mathcal {X}}^{n}$

Jos kirjoitamme tiheyden seuraavasti: [5]

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

, missä

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

tunnetaan kohdistetusti, ja

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

on siis normalisoiva, mahdollisesti tuntematon vakio

SMC - algoritmi löytää likiarvoja ja arvioita . $f_{k}(x_{1:k})$ $Z_{k}$ $k = 1,2,\pisteet$

Esimerkiksi suodatuksen tapauksessa voidaan laittaa (katso (5) ):

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

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

josta saamme:

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

Jos tulos jätetään pois, ennustaja-korjauskaava voidaan esittää seuraavasti [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})

- ennustaja,

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

- oikolukija.

Kerroin on normalisoiva vakio, jota ei vaadita normaalissa SMC-algoritmissa. ${\displaystyle (p(y_{n}\mid y_{1:n-1}))^{-1))$

Algoritmi

Tyypillinen monihiukkassuodatinalgoritmi voidaan esittää seuraavasti [3] :

MCF-algoritmi -- alustus i = 1...N: näyte osoitteesta

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

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

-- alkupainot

\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: jos VALITSE UUDELLEEN -- valitse N hiukkasen indeksit painojen mukaan = SelectByWeight( )

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

j_{1:N}

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

i = 1...N:

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

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

muuten i = 1...N:

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

i = 1...N: -- hiukkasten leviämisvaihe

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

-- mittakaavan päivitys

\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)}\ puolivälissä x_{n-1}^{(i)},y_{n})

kts -- painojen normalisointi

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

i = 1...N:

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

kts

Katso myös

Kalman-suodatin #UKF

Muistiinpanot

↑ 1 2 Mikaelyan, 2011 .
↑ Gordon, Salmond, Smith, 1993 .
↑ 1 2 3 4 5 6 7 8 Cappé, Godsill, Moulines, 2007 .
↑ Del Moral, Pierre. Ei-lineaarinen suodatus: Vuorovaikutteinen hiukkasliuos. (englanniksi) // Markovin prosessit ja niihin liittyvät kentät. - 1996. - Voi. 2 , ei. 4 . - s. 555-580 .
↑ 1 2 3 Doucet, Johansen, 2011 .
↑ Doucet, Johansen, 2011 , 2.1 Piilotetut Markovin mallit ja päättelytavoitteet.
↑ Doucet, Johansen, 2011 , 3 peräkkäistä Monte Carlo -menetelmää.

Kirjallisuus

Doucet Arnaud, Johansen Adam M. Opetusohjelma hiukkassuodatuksesta ja tasoittamisesta: viisitoista vuotta myöhemmin // 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 ja Godsill, Simon J. ja Moulines, Eric. Yleiskatsaus olemassa oleviin menetelmiin ja viimeaikaisiin edistysaskeliin peräkkäisessä Monte Carlossa // IEEE:n julkaisut. - IEEE, 2007. - T. 95 , nro 5 . - s. 899-924. — ISSN 0018-9219 . Arkistoitu alkuperäisestä 10. maaliskuuta 2016.

Doucet, Arnaud ja de Freitas, Nando ja Gordon, Neil. An Introduction to Sequential Monte Carlo Methods // Sequential Monte Carlo Methods in Practice / Doucet, Arnaud ja de Freitas, Nando ja Gordon, Neil. - Springer New York. - 3-14 p. — ISBN 978-1-4419-2887-0 .
Arulampalam, MS ja Maskell, S. ja Gordon, N. ja Clapp, T. Opetusohjelma hiukkassuodattimiin online-epälineaariseen/ei-Gaussin Bayes-seurantaan // Trans . Sig. Proc.. - IEEE Press, 2002. - Voi. 50 , ei. 2 . - s. 174-188. — ISSN 1053-587X . Katso myös aiempi versio
Gordon, NJ; Salmond, DJ; Smith, AFM Uusi lähestymistapa epälineaariseen/ei-Gaussin Bayesin tilan estimointiin // IEEE Proceedings F, Radar and Signal Processing. - IET, 1993. - Voi. 140 , ei. 2 . - s. 107-113 . - doi : 10.1049/ip-f-2.1993.0015 .
Mikaelyan S. V. Suodatusmenetelmät, jotka perustuvat arvioinnin todennäköisyystiheyden monipiste-approksimaatioon kohteen liikeparametrien määrittämisessä epälineaarisen ominaisuuden omaavalla mittarilla Nauka i obrazovanie: elektroninen painos. - MSTU im. N. E. Bauman, 2011. - ISSN 1994-0408 . Arkistoitu alkuperäisestä 4. maaliskuuta 2016.
Ristic, B., Arulampalam, S., Gordon, N. Beyond the Kalman Filter - Particle Filters for Tracking Applications. - Artech House, 2004. - 299 s. — ISBN 9781580536318 .

Simon, Dan. 15 Hiukkassuodatin // Optimaalisen tilan estimointi: Kalman, H ∞ ja epälineaariset lähestymistavat . - Wiley-Interscience, 2006. - P. 461-480 . — ISBN 0471708585 .

Linkit

Hiukkassuodatin , SciPy- keittokirja