Partikelfilter
Die Partikelfilter , auch als Methoden der Monte-Carlo- Sequenz bekannt , sind ausgefeilte Techniken zur Schätzung von Modellen, die auf Simulationen basieren .
Partikelfilter werden im Allgemeinen verwendet, um Bayes'sche Netzwerke abzuschätzen und stellen "Online" -Methoden analog zu Monte-Carlo-Methoden von Markov-Ketten dar, die "Offline" -Methoden (daher a posteriori ) sind und häufig bevorzugten Probenahmemethoden ähneln .
Bei korrekter Auslegung können Partikelfilter schneller sein als Monte-Carlo-Markov-Kettenmethoden. Sie sind oft eine Alternative zu erweiterten Kalman-Filtern mit dem Vorteil, dass sie sich mit genügend Stichproben der optimalen Bayes'schen Schätzung nähern. Sie können daher präziser gemacht werden als Kalman-Filter. Die Ansätze können auch unter Verwendung eines Kalman-Filters als Verteilungsvorschlag für den Partikelfilter kombiniert werden.
Tor
Das Ziel eines Partikels Filters ist es, die posterior Dichte der Zustandsvariablen berücksichtigt Variablen die Beobachtung unter abzuschätzen. Der Partikelfilter ist für ein verstecktes Markov-Modell ausgelegt , bei dem das System aus versteckten und beobachtbaren Variablen besteht. Beobachtbare Variablen (Beobachtungsprozess) sind durch eine bekannte funktionale Form mit versteckten Variablen (Zustandsprozess) verbunden. Ebenso ist das dynamische System, das die Entwicklung von Zustandsvariablen beschreibt, auf probabilistische Weise bekannt.
Ein generischer Partikelfilter schätzt die posteriore Verteilung der verborgenen Zustände unter Verwendung der Beobachtungsmessmethode. Betrachten Sie einen im folgenden Diagramm gezeigten Zustandsraum
X.0⟶X.1⟶X.2⟶X.3⟶...sichGnichtbeiml↓↓↓...Y.0Y.1Y.2Y.3...ÖbservbeimtichÖnicht{\ displaystyle {\ begin {matrix} X_ {0} & \ longrightarrow & X_ {1} & \ longrightarrow & X_ {2} & \ longrightarrow & X_ {3} & \ longrightarrow & ... & signal \\\ downarrow && \ downarrow && \ downarrow && ... \\ Y_ {0} && Y_ {1} && Y_ {2} && Y_ {3} && ... & Beobachtung \ Ende {Matrix}}}
Das Filterproblem besteht darin, die Werte der verborgenen Zustände unter Berücksichtigung der Werte des Beobachtungsprozesses in jedem Stadium nacheinander zu schätzen .
X.k{\ displaystyle X_ {k}}Y.0,...,Y.k{\ displaystyle Y_ {0}, ..., Y_ {k}}k{\ displaystyle k}
Alle Bayes'schen Schätzungen der posterioren Dichte folgen . Die Partikelfiltermethode liefert eine Annäherung dieser bedingten Wahrscheinlichkeiten unter Verwendung der empirischen Messung, die mit einem genetischen Algorithmus verbunden ist. Andererseits würde die Monte-Carlo-Methode von Markov oder der Stichprobenansatz für Wichtigkeitsketten den gesamten posterioren Bereich modellieren .
X.k{\ displaystyle X_ {k}}p((xk∣y0,y1,...,yk){\ displaystyle p (x_ {k} \ mid y_ {0}, y_ {1}, ..., y_ {k})}p((x0,x1,...,xk∣y0,y1,...,yk){\ displaystyle p (x_ {0}, x_ {1}, ..., x_ {k} \ mid y_ {0}, y_ {1}, ..., y_ {k})}
Das Signalbeobachtungsmodell
Partikelmethoden gehen oft davon aus, dass Beobachtungen in folgender Form modelliert werden können:
X.k{\ displaystyle X_ {k}}Y.k{\ displaystyle Y_ {k}}
-
X.0,X.1,...{\ displaystyle X_ {0}, X_ {1}, ...}ist ein Markov - Prozeß auf (für einige ) , die nach der Übergangswahrscheinlichkeitsdichte entwickelt . Dieses Modell wird auch oft synthetisch geschrieben alsR.dx{\ displaystyle \ mathbb {R} ^ {d_ {x}}}dx⩾1{\ displaystyle d_ {x} \ geqslant 1}p((xk|xk- -1){\ displaystyle p (x_ {k} | x_ {k-1})}
X.k|X.k- -1=xk∼p((xk|xk- -1){\ displaystyle X_ {k} | X_ {k-1} = x_ {k} \ sim p (x_ {k} | x_ {k-1})}Mit einer anfänglichen Wahrscheinlichkeitsdichte .p((x0){\ displaystyle p (x_ {0})}
- Beobachtungen nehmen Werte in einem bestimmten Zustandsraum an, die (für einige ) bedingt unabhängig sind, sofern sie bekannt sind. Mit anderen Worten, jeder hängt nur von ab . Ferner nehmen wir an, dass eine bedingte Verteilung für gegeben absolut kontinuierlich und synthetisch ist
Y.0,Y.1,⋯{\ displaystyle Y_ {0}, Y_ {1}, \ cdots}R.dy{\ displaystyle \ mathbb {R} ^ {d_ {y}}}dy⩾1{\ displaystyle d_ {y} \ geqslant 1}X.0,X.1,⋯{\ displaystyle X_ {0}, X_ {1}, \ cdots}Y.k{\ displaystyle Y_ {k}}X.k{\ displaystyle X_ {k}}Y.k{\ displaystyle Y_ {k}}X.k=xk{\ displaystyle X_ {k} = x_ {k}}Y.k|X.k=yk∼p((yk|xk){\ displaystyle Y_ {k} | X_ {k} = y_ {k} \ sim p (y_ {k} | x_ {k})}
Ein Beispiel für ein System mit diesen Eigenschaften ist:
X.k=G((X.k- -1)+W.k{\ displaystyle X_ {k} = g (X_ {k-1}) + W_ {k}}
Y.k=h((X.k)+V.k{\ displaystyle Y_ {k} = h (X_ {k}) + V_ {k}}
Wobei die beiden und voneinander unabhängige Sequenzen mit der Wahrscheinlichkeitsdichtefunktion s und und bekannt sind, sind bekannte Funktionen. Diese beiden Gleichungen können als Zustandsraumgleichungen betrachtet werden und ähneln den Zustandsraumgleichungen für den Kalman-Filter. Wenn die Funktionen g und h in dem obigen Beispiel linear sind, und beide und sind Gaussian , finden die Kalman - Filter die genauen Bayesian Filterverteilung. Andernfalls sind die auf dem Kalman-Filter basierenden Methoden eine Näherung erster Ordnung (EKF) oder eine Näherung zweiter Ordnung (UKF im Allgemeinen, aber wenn die Wahrscheinlichkeitsverteilung Gaußsch ist, ist eine Näherung dritter Ordnung möglich).
W.k{\ displaystyle W_ {k}}V.k{\ displaystyle V_ {k}}G{\ displaystyle g}h{\ displaystyle h}W.k{\ displaystyle W_ {k}}V.k{\ displaystyle V_ {k}}
Die Annahme, dass die anfängliche Verteilung und die Markov-Kettenübergänge in Bezug auf das Lebesgue-Maß absolut kontinuierlich sind, kann gelockert werden. Um einen Partikelfilter zu entwerfen, müssen wir nur annehmen, dass wir die Markov-Kettenübergänge abtasten und die Funktionswahrscheinlichkeit berechnen können (siehe zum Beispiel die Beschreibung der genetischen Selektionsauswahl des Partikelfilters unten). Die absolut kontinuierliche Hypothese zu Markov-Übergängen dient nur dazu, informell (und ziemlich missbräuchlich) unterschiedliche Formeln zwischen posterioren Verteilungen unter Verwendung der Bayes-Regel für bedingte Dichten abzuleiten.
X.k- -1→X.k{\ displaystyle X_ {k-1} \ rightarrow X_ {k}}X.k,{\ displaystyle X_ {k},}xk↦p((yk|xk){\ displaystyle x_ {k} \ mapsto p (y_ {k} | x_ {k})}X.k{\ displaystyle X_ {k}}
Modellierung
Partikelfilter gehen davon aus, dass Zustände und Beobachtungen wie folgt modelliert werden können:
xk{\ displaystyle x_ {k}}yk{\ displaystyle y_ {k}}
- Die Folge von Parametern bildet eine Markov-Kette erster Ordnung, so dass und mit einer anfänglichen Verteilung .x0,x1,...{\ displaystyle x_ {0}, x_ {1}, \ dots}xk|xk- -1∼pxk|xk- -1((x|xk- -1){\ displaystyle x_ {k} | x_ {k-1} \ sim p_ {x_ {k} | x_ {k-1}} (x | x_ {k-1})}p((x0){\ displaystyle p (x_ {0})}
- Beobachtungen sind bedingt unabhängig, sofern sie bekannt sind. Mit anderen Worten, jede Beobachtung hängt nur vom Parameter ab :y0,y1,...{\ displaystyle y_ {0}, y_ {1}, \ dots}x0,x1,...{\ displaystyle x_ {0}, x_ {1}, \ dots}yk{\ displaystyle y_ {k}}xk{\ displaystyle x_ {k}}yk|xk∼py|x((y|xk){\ displaystyle y_ {k} | x_ {k} \ sim p_ {y | x _ {}} (y | x_ {k})}
Ein Beispiel für dieses Szenario ist {xk=f((xk- -1)+vkyk=h((xk)+wk{\ displaystyle \ left \ {{\ begin {matrix} x_ {k} = f (x_ {k-1}) + v_ {k} \\ y_ {k} = h (x_ {k}) + w_ {k } \ end {matrix}} \ right.}
wobei beide und voneinander unabhängige und identisch verteilte Sequenzen mit bekannten Wahrscheinlichkeitsdichtefunktionen sind und wo und sind bekannte Funktionen. Diese beiden Gleichungen können als Zustandsraumgleichungen angesehen werden und ähneln denen des Kalman-Filters .
vk{\ displaystyle v_ {k}}wk{\ displaystyle w_ {k}}f((⋅){\ displaystyle f (\ cdot)}h((⋅){\ displaystyle h (\ cdot)}
Wenn die Funktionen und linear waren, und wenn beide und waren Gaussians , dann wird der Kalman - Filter findet die genaue Bayesian Filterung Verteilung . Andernfalls liefern die auf Kalman-Filtern basierenden Methoden eine Schätzung erster Ordnung. Partikelfilter geben auch Annäherungen an, aber mit genügend Partikeln können die Ergebnisse noch genauer sein.
f((⋅){\ displaystyle f (\ cdot)}h((⋅){\ displaystyle h (\ cdot)}vk{\ displaystyle v_ {k}}wk{\ displaystyle w_ {k}}
Monte-Carlo-Näherung
Partikelmethoden erstellen wie alle auf Stichproben basierenden Methoden (z. B. MCMC ) eine Reihe von Stichproben, die sich der Filterverteilung annähern . Somit werden bei Proben die erwarteten Werte in Bezug auf die Filterverteilung angenähert durch:
wo ist das (L) -te Teilchen im Moment ; und kann auf die übliche Weise von Monte-Carlo-Methoden alle Daten der Verteilung ( Momente usw.) bis zu einem gewissen Grad an Annäherung liefern .
p((xk|y0,...,yk){\ displaystyle p (x_ {k} | y_ {0}, \ dots, y_ {k})}P.{\ displaystyle P}∫f((xk)p((xk|y0,...,yk)dxk≈1P.∑L.=1P.f((xk((L.)){\ displaystyle \ int f (x_ {k}) p (x_ {k} | y_ {0}, \ dots, y_ {k}) dx_ {k} \ approx {\ frac {1} {P}} \ sum _ {L = 1} ^ {P} f (x_ {k} ^ {(L)})}xk((L.){\ displaystyle x_ {k} ^ {(L)}}k{\ displaystyle k}f((⋅){\ displaystyle f (\ cdot)}
Im Allgemeinen wird der Algorithmus iterativ für eine bestimmte Anzahl von Werten wiederholt (was wir bemerken werden ).
k{\ displaystyle k}NICHT{\ displaystyle N}
" Für alle Partikel initialisieren" bietet eine Startposition zum Erstellen , die zum Erstellen , zum Erstellen usw. verwendet werden kann .
xk=0|k=0{\ displaystyle x_ {k} = 0 | _ {k = 0}}x1{\ displaystyle x_ {1}}x2{\ displaystyle x_ {2}}x3{\ displaystyle x_ {3}}k=NICHT{\ displaystyle k = N}
Sobald dies geschehen ist, der Durchschnitt der über alle Teilchen (oder ist) etwa der wahre Wert .
xk{\ displaystyle x_ {k}}1P.∑L.=1P.xk((L.){\ displaystyle {\ frac {1} {P}} \ sum _ {L = 1} ^ {P} x_ {k} ^ {(L)}}xk{\ displaystyle x_ {k}}
Probenahme mit Resampling nach Wichtigkeit (SIR)
Das Sampling mit Resampling-Wichtigkeit oder Sampling Importance Resampling (SIR) ist ein sehr häufig verwendeter Filteralgorithmus. Er nähert sich der Filterverteilung durch eine Reihe gewichteter Partikel : .
p((xk|y0,...,yk){\ displaystyle p (x_ {k} | y_ {0}, \ ldots, y_ {k})}{((wk((L.),xk((L.)) :: L.=1,...,P.}}{\ displaystyle \ {(w_ {k} ^ {(L)}, x_ {k} ^ {(L)}) ~: ~ L = 1, \ ldots, P \}}
Bedeutung Gewichte sind Annäherungen der relativen posterior Wahrscheinlichkeiten (oder Dichte) von Partikeln , wie beispielsweise .
wk((L.){\ displaystyle w_ {k} ^ {(L)}}∑L.=1P.wk((L.)=1{\ displaystyle \ sum _ {L = 1} ^ {P} w_ {k} ^ {(L)} = 1}
Der SIR-Algorithmus ist eine rekursive Version der Wichtigkeitsabtastung . Wie bei der Stichprobenerhebung kann die Erwartung der Funktion als gewichteter Durchschnitt angenähert werden:f((⋅){\ displaystyle f (\ cdot)}∫f((xk)p((xk|y0,...,yk)dxk≈∑L.=1P.w((L.)f((xk((L.)).{\ displaystyle \ int f (x_ {k}) p (x_ {k} | y_ {0}, \ dots, y_ {k}) dx_ {k} \ approx \ sum _ {L = 1} ^ {P} w ^ {(L)} f (x_ {k} ^ {(L)}).}
Die Leistung des Algorithmus hängt von der Wahl der Größenverteilungen ab : .
π((xk|x0::k- -1,y0::k){\ displaystyle \ pi (x_ {k} | x_ {0: k-1}, y_ {0: k})}
Die optimale Wichtigkeitsverteilung wird angegeben als:π((xk|x0::k- -1,y0::k)=p((xk|xk- -1,yk).{\ displaystyle \ pi (x_ {k} | x_ {0: k-1}, y_ {0: k}) = p (x_ {k} | x_ {k-1}, y_ {k}).}
Die Übergangswahrscheinlichkeit wird jedoch häufig als Wichtigkeitsfunktion verwendet, da sie einfacher zu berechnen ist und auch die Berechnung nachfolgender Wichtigkeitsgewichte vereinfacht:
π((xk|x0::k- -1,y0::k)=p((xk|xk- -1).{\ displaystyle \ pi (x_ {k} | x_ {0: k-1}, y_ {0: k}) = p (x_ {k} | x_ {k-1}).}
Resampling-Filter nach Wichtigkeit (CRS) mit Wahrscheinlichkeiten von Übergängen als Wichtigkeitsfunktion werden allgemein als Priming-Filter ( Bootstrap- Filter) oder Kondensationsalgorithmus bezeichnet .
Das Resampling vermeidet das Problem der Degeneration des Algorithmus. Dies vermeidet Situationen, in denen alle bis auf eines der Wichtigkeitsgewichte nahe Null sind. Die Leistung des Algorithmus kann auch durch die Wahl der geeigneten Resampling-Methode beeinflusst werden. Das von Kitagawa (1996) vorgeschlagene geschichtete Resampling ist hinsichtlich der Varianz optimal.
Ein einzelner Schritt des Resamplings von sequentieller Bedeutung läuft wie folgt ab:
- Denn wir ziehen die Stichproben der Wichtigkeitsverteilungen :L.=1,...,P.{\ displaystyle L = 1, \ ldots, P}xk((L.)∼π((xk|x0::k- -1((L.),y0::k){\ displaystyle x_ {k} ^ {(L)} \ sim \ pi (x_ {k} | x_ {0: k-1} ^ {(L)}, y_ {0: k})}
- Denn wir bewerten die Wichtigkeitsgewichte mit einer Normalisierungskonstante:L.=1,...,P.{\ displaystyle L = 1, \ ldots, P}w^k((L.)=wk- -1((L.)p((yk|xk((L.))p((xk((L.)|xk- -1((L.))π((xk((L.)|x0::k- -1((L.),y0::k).{\ displaystyle {\ hat {w}} _ {k} ^ {(L)} = w_ {k-1} ^ {(L)} {\ frac {p (y_ {k} | x_ {k} ^ { (L)}) p (x_ {k} ^ {(L)} | x_ {k-1} ^ {(L)})} {\ pi (x_ {k} ^ {(L)} | x_ {0 : k-1} ^ {(L)}, y_ {0: k})}}.}
- So berechnen Sie die normalisierten Wichtigkeitsgewichte:L.=1,...,P.{\ displaystyle L = 1, \ ldots, P}wk((L.)=w^k((L.)∑J.=1P.w^k((J.){\ displaystyle w_ {k} ^ {(L)} = {\ frac {{\ hat {w}} _ {k} ^ {(L)}} {\ sum _ {J = 1} ^ {P} { \ hat {w}} _ {k} ^ {(J)}}}
- Wir berechnen eine Schätzung der effektiven Partikelanzahl als NICHT^eff=1∑L.=1P.((wk((L.))2{\ displaystyle {\ hat {N}} _ {\ mathit {eff}} = {\ frac {1} {\ sum _ {L = 1} ^ {P} \ left (w_ {k} ^ {(L) } \ right) ^ {2}}}}
- Wenn die effektive Anzahl von Partikeln kleiner als ein bestimmter Schwellenwert ist , wird das Resampling durchgeführt:
NICHT^eff<NICHTthr{\ displaystyle {\ hat {N}} _ {\ mathit {eff}} <N_ {thr}}
- Zeichnen Sie Partikel aus dem aktuellen Partikelsatz mit den zu ihrem Gewicht proportionalen Wahrscheinlichkeiten und ersetzen Sie den aktuellen Partikelsatz durch diesen neuen Satz.P.{\ displaystyle P}
- Für das Ganze .L.=1,...,P.{\ displaystyle L = 1, \ ldots, P}wk((L.)=1/.P.{\ displaystyle w_ {k} ^ {(L)} = 1 / P}
Der Begriff Resampling Sequential Important (Sequential Importance Resampling) wird manchmal auch für SIR-Filter verwendet.
Sequential Importance Sampling (SIS)
Die sequentielle Abtastung nach Größe oder sequentielle Wichtigkeitsabtastung (SIS) ähnelt der Abtastung mit Resampling-Wichtigkeit (SIR), jedoch ohne den Resampling-Schritt.
Direkte Version des Algorithmus
Die einfache Version des Algorithmus ist im Vergleich zu anderen Partikelfilterungsalgorithmen relativ einfach und verwendet Zusammensetzung und Zurückweisung. Um eine einzelne Probe produzieren zu von :
x{\ displaystyle x}k{\ displaystyle k}pxk|y1::k((x|y1::k){\ displaystyle p_ {x_ {k} | y_ {1: k}} (x | y_ {1: k})}
(1) Setze p = 1
(2) Erstellen Sie
einheitlich L aus
{1,...,P.}}{\ displaystyle \ {1, ..., P \}}
(3) Erstellen Sie einen Test aus seiner Verteilung
x^{\ displaystyle {\ hat {x}}}pxk|xk- -1((x|xk- -1|k- -1((L.)){\ displaystyle p_ {x_ {k} | x_ {k-1}} (x | x_ {k-1 | k-1} ^ {(L)})}
(4) Erstellen Sie die Verwendungswahrscheinlichkeiten, aus denen der gemessene Wert stammt
y^{\ displaystyle {\ hat {y}}}x^{\ displaystyle {\ hat {x}}}py|x((yk|x^){\ displaystyle p_ {y | x} (y_ {k} | {\ hat {x}})}yk{\ displaystyle y_ {k}}
(5) Erstellen Sie ein weiteres
einheitliches u aus
[0,mk]]{\ displaystyle [0, m_ {k}]}
(6) Vergleiche u und
y^{\ displaystyle {\ hat {y}}}
(a) Wenn u größer ist, wiederholen Sie ab Schritt (2)
(b) Wenn u kleiner ist, speichern Sie als und erhöhen Sie p
x^{\ displaystyle {\ hat {x}}}xk|k((p){\ displaystyle x {k | k} ^ {(p)}}
(c) Wenn p> P, dann hör auf
Das Ziel besteht darin, P- Partikel im Schritt zu erzeugen, indem nur die Partikel des Schritts verwendet werden . Dies erfordert, dass eine Markovsche Gleichung geschrieben (und berechnet) werden kann, um eine zu erstellen, die nur auf basiert . Dieser Algorithmus verwendet die Zusammensetzung von P-Partikeln , um zu erstellen .
k{\ displaystyle k}k- -1{\ displaystyle k-1}xk{\ displaystyle x_ {k}}xk- -1{\ displaystyle x_ {k-1}}k- -1{\ displaystyle k-1}k{\ displaystyle k}
Dies kann leichter visualisiert werden, wenn es als zweidimensionales Array betrachtet wird. Eine Dimension ist und die andere Dimension ist die Anzahl der Partikel. Zum Beispiel wäre das L- te Teilchen im Schritt und kann daher geschrieben werden (wie zuvor im Algorithmus ausgeführt).
x{\ displaystyle x}k{\ displaystyle k}x((k,L.){\ displaystyle x (k, L)}k{\ displaystyle k}xk((L.){\ displaystyle x_ {k} ^ {(L)}}
Schritt (3) erzeugt ein Potential basierend auf einem zufällig ausgewählten Teilchen ( ) in der Zeit und lehnt dieses Teilchen in Schritt (6) ab oder akzeptiert es. Mit anderen Worten werden die Werte unter Verwendung der zuvor berechneten berechnet.
xk{\ displaystyle x_ {k}}xk- -1((L.){\ displaystyle x_ {k-1} ^ {(L)}}k- -1{\ displaystyle k-1}xk{\ displaystyle x_ {k}}xk- -1{\ displaystyle x_ {k-1}}
Anmerkungen und Referenzen
-
(in) Herr Sanjeev Arulampalam, " Ein Tutorial zu Partikelfiltern für die nichtlineare / nicht-gaußsche Bayes'sche Online-Verfolgung " , IEEE TRANSACTIONS ON SIGNAL PROCESSING, VOL. 50, NO. 2 ,Februar 2002
-
(de) " Partikelfilter "
-
Siehe auch
Literaturverzeichnis
-
Sequentielle Monte-Carlo-Methoden in der Praxis von A Doucet, N de Freitas und N Gordon. Gepostet von Springer.
-
Über sequentielle Monte-Carlo-Probenahmemethoden für die Bayes'sche Filterung von A Doucet, C Andrieu und S. Godsill, Statistics and Computing, vol. 10, nein. 3, p. 197-208 , 2000 CiteSeer-Link
-
Tutorial zu Partikelfiltern für nichtlineares / nicht-Gaußsches Bayes'sches Online-Tracking (2001) ; S. Arulampalam, S. Maskell, N. Gordon und T. Clapp; CiteSeer-Link
Externe Links
<img src="https://fr.wikipedia.org/wiki/Special:CentralAutoLogin/start?type=1x1" alt="" title="" width="1" height="1" style="border: none; position: absolute;">