Flerpartikelfilter

Multipartikelfilter [1] ( MPF , engelsk partikelfilter - "partikelfilter", "partikelfilter", "korpuskulärt filter") - en sekventiell Monte Carlo-metod - en rekursiv algoritm för att numeriskt lösa uppskattningsproblem ( filtrering , utjämning ), speciellt för icke-linjära och icke- gaussiska fall. Sedan beskrivningen 1993 [2] av N. Gordon, D. Salmond och A. Smith, har den använts inom olika områden - navigering, robotik , datorseende .

Jämfört med de metoder som vanligtvis används för sådana problem - utökade Kalman-filter (EKF) - är flerpartikelfilter inte beroende av linjäriserings- eller approximationsmetoder . Konventionell EKF klarar sig inte bra med väsentligen icke-linjära modeller, liksom i fallet med systembrus och mätningar som skiljer sig mycket från Gaussiska, därför har olika modifieringar utvecklats, såsom UKF ( engelska unscented KF ), QKF ( English Quadrature KF ), etc. ][3 Det bör noteras att flerpartikelfilter i sin tur kräver mer datorresurser.

Termen "partikelfilter" myntades av Del Moral 1996 [4] och "sekventiellt Monte Carlo" av Liu och Chen 1998.

Många multipartikelfilter som används i praktiken härleds genom att tillämpa en sekventiell Monte Carlo-metod på en sekvens av målfördelningar [ 5] .

Förklaring av problemet

FFM är utformad för att uppskatta sekvensen av latenta variabler för baserat på observationer vid . För enkelhetens skull kommer vi att anta att vi överväger ett dynamiskt system , och och är verkliga tillstånds- respektive mätvektorer [1] . $x_{n}$ $n=1,2,\dots$ $y_{n}$ $n=1,2,\dots$ $x_{n}$ $y_{n}$

Den stokastiska ekvationen för systemets tillstånd har formen:

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

där funktionen att ändra systemets tillstånd är en slumpmässig variabel , den störande effekten. $f_{k}$ $v_{k}$

Mätningsekvation:

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

var är mätfunktionen, är en slumpvariabel, mätbrus. ${\displaystyle h_{k))$ ${\displaystyle w_{k))$

Funktionerna och är i allmänhet olinjära och de statistiska egenskaperna för systembruset ( ) och mätningar ( ) antas vara kända. $f_{k}$ ${\displaystyle h_{k))$ $v_{k}$ ${\displaystyle w_{k))$

Filtreringens uppgift är att få en uppskattning baserad på de mätresultat som var kända vid tillfället . ${\hat {x}}_{k}$ $k$ ${\displaystyle y_{1:k))$

Hidden Markov Model and Bayesian Inference

Betrakta en diskret Markov-process med följande sannolikhetsfördelningar: $\{X_{n}\}_{n\geqslant 1}$

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

och ,

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

(ett)

där är sannolikhetstätheten , är den villkorade sannolikhetstätheten ( övergångssannolikhetstätheten ) i övergången från till . $\mu (x)$ $f(x_{n}\midt x_{n-1})$ ${\displaystyle x_{n-1))$ $x_{n}$

Här betyder notationen att villkoret är fördelat som . $X\mid Y\sim f(\dots )$ $X$ $Y$ $f(\dots )$

Realiseringar av processen (dolda variabler ) observeras genom en annan slumpmässig process - mätprocessen - med marginella tätheter : $\{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)

där är den villkorade sannolikhetstätheten ( mättäthet ), mätningar anses vara statistiskt oberoende . $h(y_{n}\mid x_{n})$

Modellen kan illustreras med följande övergångsdiagram:

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

För enkelhetens skull antar vi att övergångstätheten och mättätheten inte beror på . Modellparametrarna antas vara givna. $n$

Systemet och mätmodellen som sålunda definieras är känd som Hidden Markov Model [6] .

Ekvation (1) definierar den tidigare fördelningen för processen : $\{X_{n}\}$

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

(3)

På liknande sätt definierar (2) sannolikhetsfunktionen :

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

(fyra)

Här och nedan betecknar notationen för . ${\displaystyle x_{k:l))$ $k\leqslant l$ $(x_{k},\dots,x_{l})$

Således kommer den Bayesianska slutsatsen för kända implementeringar av mätningar , betecknade med respektive , att baseras på den bakre fördelningen $\{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)

där (här är det dominerande måttet): $dx_{1:n}$

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

Sampling av betydelse

Se även Viktighetsprovtagning .

Monte Carlo-metoden låter dig utvärdera egenskaperna hos ganska komplexa sannolikhetsfördelningar, till exempel genom att beräkna medelvärdet och variansen i form av en integral [3] :

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

var är funktionen för uppskattning. Till exempel, för genomsnittet, kan du sätta: . $\theta (x)$ $\theta (x)=x$

Om en analytisk lösning är omöjlig kan problemet lösas numeriskt genom att generera slumpmässiga prover med en densitet , beteckna dem som , och erhålla det aritmetiska medelvärdet över provpunkterna [3] : $p(x)$ ${x^{(i)}}_{1\leqslant i\leqslant N}$

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

I ett mer generellt fall, när sampling från är svårt, tillämpas en annan fördelning (den så kallade engelska instrumental- eller betydelsefördelningen ), och för att hålla skattningen opartisk införs viktningskoefficienter baserade på förhållandet [3] : $sid$ $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)})))

och beräknar sedan det viktade medelvärdet:

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

Omsampling

Även om hjälpfördelningen främst används för att förenkla sampling från huvudfördelningen , används ofta proceduren ”sampling and resampling by significance” ( engelska sampling betydelse resampling, SIR ). Denna procedur består av två steg: faktisk provtagning efter signifikans med beräkning av vikter och ytterligare provtagning av punkter som tar hänsyn till dessa vikter [3] . $sid$ $w_{i}$

Omsampling är särskilt nödvändig för seriella filter [3] .

Sekventiell Monte Carlo-metod

Flerpartikelfiltrering och utjämningsmetoder är de mest kända exemplen på sekventiella Monte Carlo ( SMC ) algoritmer . I den mån litteraturen ofta inte skiljer mellan dem. Emellertid inkluderar SMC en bredare klass av algoritmer som är tillämpliga för att beskriva mer komplexa ungefärliga filtrering och utjämningsmetoder [7] .

Sekventiella Monte Carlo-metoder är en klass av Monte Carlo-metoder som sekventiellt samplar från en sekvens av målsannolikhetstätheter med ökande dimension, där var och en definieras på en kartesisk potens [5] . $\{f_{n}(x_{1:n})\}$ $f_{n}(x_{1:n})$ ${\mathcal {X}}^{n}$

Om vi skriver densiteten som: [5]

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

, var

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

är känd punktvis, och

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

är alltså en normaliserande, möjligen okänd, konstant

SMC-algoritmen hittar approximationer och uppskattningar för . $f_{k}(x_{1:k})$ $Z_{k}$ $k=1,2,\prickar$

Till exempel, för fallet med filtrering, kan man sätta (se (5) ):

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

och

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

från vilken vi kommer att ha:

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

Om utdata utelämnas kan prediktor-korrigeringsschemat representeras enligt följande [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})

— prediktor,

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

- korrekturläsare.

Multiplikatorn är en normaliseringskonstant som inte krävs för den normala SMC-algoritmen. ${\displaystyle (p(y_{n}\mid y_{1:n-1}))^{-1))$

Algoritm

En typisk multipartikelfilteralgoritm kan representeras enligt följande [3] :

MCF-algoritm -- initiering för i = 1...N: prov från

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

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

-- initialvikter

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

kts för n = 1...T: om ÅTERVÄLJ då -- välj index för N partiklar enligt vikter = SelectByWeight( )

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

j_{1:N}

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

för i = 1...N:

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

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

annat för i = 1...N:

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

för i = 1...N: -- steg för förökning av partiklar

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

-- uppdatering av skalan

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

kts -- Normalisering av vikter

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

för i = 1...N:

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

kts

Se även

Kalman filter#UKF

Anteckningar

↑ 1 2 Mikaelyan, 2011 .
↑ Gordon, Salmond, Smith, 1993 .
↑ 1 2 3 4 5 6 7 8 Cappé, Godsill, Moulines, 2007 .
↑ Del Moral, Pierre. Icke linjär filtrering: Interagerande partikellösning. (engelska) // Markov Processer och relaterade fält. - 1996. - Vol. 2 , nr. 4 . - S. 555-580 .
↑ 1 2 3 Doucet, Johansen, 2011 .
↑ Doucet, Johansen, 2011 , 2.1 Hidden Markov Models and Inference Aims.
↑ Doucet, Johansen, 2011 , 3 Sekventiella Monte Carlo-metoder.

Litteratur

Doucet Arnaud, Johansen Adam M. En handledning om partikelfiltrering och utjämning: Femton år senare // The Oxford Handbook of Nolinear Filtering / D. Crisan, B. Rozovsky. - Oxford: Oxford University Press, 2011. - P. 656-704. — ISBN 978-0-19-953290-2 .
Cappe, Olivier och Godsill, Simon J. och Moulines, Eric. En översikt över befintliga metoder och senaste framsteg i sekventiell Monte Carlo // Proceedings of the IEEE. - IEEE, 2007. - T. 95 , nr 5 . - s. 899-924. — ISSN 0018-9219 . Arkiverad från originalet den 10 mars 2016.

Doucet, Arnaud och de Freitas, Nando och Gordon, Neil. En introduktion till sekventiella Monte Carlo-metoder // Sekventiella Monte Carlo-metoder i praktiken / Doucet, Arnaud och de Freitas, Nando och Gordon, Neil. — Springer New York. - 3-14 sid. — ISBN 978-1-4419-2887-0 .
Arulampalam, MS och Maskell, S. och Gordon, N. och Clapp, T. En handledning om partikelfilter för online-ickelinjär/icke-Gaussian Bayesian Tracking // Trans . Sig. Proc.. - IEEE Press, 2002. - Vol. 50 , nej. 2 . - S. 174-188. — ISSN 1053-587X . Se även tidigare version
Gordon, NJ; Salmond, DJ; Smith, AFM Nytt tillvägagångssätt för icke-linjär/icke-Gaussian Bayesian state estimering // IEEE Proceedings F, Radar and Signal Processing. - IET, 1993. - Vol. 140 , nr. 2 . - S. 107-113 . - doi : 10.1049/ip-f-2.1993.0015 .
Mikaelyan S. V. Filtreringsmetoder baserade på flerpunktsapproximation av sannolikhetstätheten för uppskattning i problemet med att bestämma parametrarna för målets rörelse med hjälp av en mätare med en icke-linjär karakteristik Nauka i obrazovanie: elektronisk utgåva. - MSTU im. N. E. Bauman, 2011. - ISSN 1994-0408 . Arkiverad från originalet den 4 mars 2016.
Ristic, B., Arulampalam, S., Gordon, N. Beyond the Kalman Filter - Partikelfilter för spårningstillämpningar. - Artech House, 2004. - 299 sid. — ISBN 9781580536318 .

Simon, Dan. 15 Partikelfiltret // Optimal State Estimation: Kalman, H ∞ , och ickelinjära tillvägagångssätt . - Wiley-Interscience, 2006. - P. 461-480 . — ISBN 0471708585 .

Länkar

Partikelfilter , SciPy kokbok