View
1
Download
0
Category
Preview:
Citation preview
Einleitung Optimale Filter in diskreter Zeit Teilchenfilter Asymptotische Stabilitat Optimale Filter in stetiger Zeit
Neue Herausforderungenfur die Stochastik
aus dem Bereich der Signalverarbeitung
Wilhelm StannatFachbereich Mathematik
TU Darmstadt
October 18, 2006
Einleitung Optimale Filter in diskreter Zeit Teilchenfilter Asymptotische Stabilitat Optimale Filter in stetiger Zeit
Grundaufgabe der Signalverarbeitung
Schatzung eines verrauschten Signals X (∈ S)
Y = G (X , e) (1)
I e - Messfehler
I Y - Beobachtung (∈ Rp)
typische Anwendung Positionsbestimmung mit GPS
I X - Systemzustand (etwa: Position, Geschw., Beschl.)
I Y - Messung der Position des Vehikels durch GPS
Einleitung Optimale Filter in diskreter Zeit Teilchenfilter Asymptotische Stabilitat Optimale Filter in stetiger Zeit
Weitere Anwendungen
Objektverfolgung Erkundung
Quellen: Prof. Ji, RPI, New York Prof. Fox, Univ. of Washington
Einleitung Optimale Filter in diskreter Zeit Teilchenfilter Asymptotische Stabilitat Optimale Filter in stetiger Zeit
Bayes Schatzer
in den genannten Beispielen sind bekannt:
I PX (dx) - a-priori Verteilung von X
I P [Y ∈ dy | X = x ] - die Verteilung des Messfehlers
Ann P [Y ∈ dy | X = x ] = g(y , x) dy
liefert auf der Grundlage des Bayesschen Theorems die a-posteriori Verteilung
ηY (dx) =g(Y , x)PX (dx)∫g(Y , x) PX (dx)
∝ g(Y , x)PX (dx)
= (regulare) bedingte Verteilung von X gegeben Y
= P [X ∈ dx | Y = y ]
Einleitung Optimale Filter in diskreter Zeit Teilchenfilter Asymptotische Stabilitat Optimale Filter in stetiger Zeit
Beispiel
Einleitung Optimale Filter in diskreter Zeit Teilchenfilter Asymptotische Stabilitat Optimale Filter in stetiger Zeit
Bayes Schatzer
S ⊂ Rd
X =
∫xηy (dx) ∝
∫xg(Y , x) PX (dx)
= (regulare) bedingte Erwartung von X gegeben Y
= E [X | Y = y ]
minimiert den mittleren quadratischen Fehler∫‖x − X‖2 dηy (x) = min
α∈Rd
∫‖x − α‖2 dηy (x)
fur allgemeine S∫f (x) dηY (x) = E [f (X ) | Y = y ] f ∈ Bb(S)
Einleitung Optimale Filter in diskreter Zeit Teilchenfilter Asymptotische Stabilitat Optimale Filter in stetiger Zeit
Zum Bayesschen Ansatz
I math. schwer zu handhaben
I nur wenig uber die a-posteriori Verteilung bekannt
prominente Ausnahme Gaußsche Modelle
(Y , X ) gemeinsam Gaußsch verteilt - Grundlage des Kalman Filters
I die gestiegene Rechenleistung von Computern ermoglichtzunehmend zeitkritische Approximationen der a-posterioriVerteilung in hinreichender Gute
hat zu einer starken Ausweitung Bayesscher Methoden gefuhrtStichwort: Bayessche Revolution
Einleitung Optimale Filter in diskreter Zeit Teilchenfilter Asymptotische Stabilitat Optimale Filter in stetiger Zeit
Dynamische Modelle
Yt = G (Xt , et) (2)
mit unabhangigen Messfehlern et
P [Yt ∈ dy | Xt ] = g(y ,Xt) dy
t bedeutet hierbei: diskrete Zeit (spater kontinuierliche Zeit)
Bedeutung von t in hierarchischen Modellen:
I Feldparameter (zB Bildausschnitt)
I geordnete Menge von Frequenzindizes, etc....
Einleitung Optimale Filter in diskreter Zeit Teilchenfilter Asymptotische Stabilitat Optimale Filter in stetiger Zeit
a-posteriori Verteilung
ηY1:tt = a-posteriori Verteilung von Xt gegeben Y1:t = (Ys)0≤s≤t
=⇒∫
f dηY1:tt =
E[f (Xt)
∏ts=0 g(Ys ,Xs)
]E
[∏ts=1 g(Ys ,Xs)
]=
∫P(fg(Yt , ·)) dη
Y1:t−1
t−1∫P(g(Yt , ·)) dη
Y1:t−1
t−1
falls (Xt) Markovsch, dh
P[Xt+1 ∈ dx | X0:t ] = P [Xt+1 ∈ dx | Xt ] = P(Xt , dx)
Einleitung Optimale Filter in diskreter Zeit Teilchenfilter Asymptotische Stabilitat Optimale Filter in stetiger Zeit
also
ηY1:tt = T (Yt , ·) ◦ T (Yt−1, ·) ◦ . . . ◦ T (Y1,PX0)
mit dem (nichtlinearen) Transferoperator
T (Y , η)(dx) ∝∫
g(Y , x)P(x , dx) dη(x)
Einleitung Optimale Filter in diskreter Zeit Teilchenfilter Asymptotische Stabilitat Optimale Filter in stetiger Zeit
Teilchenfilter
fixiere beliebige Folge Y1,Y2, . . .
Grundidee Approximiere die a-posteriori Verteilung durch dieempirische Verteilung eines Teilchensystems
ηt ∼ ηNt =
1
N
N∑i=1
δXt(i) ∈M1(S)
wobei Xt(i) Position des i-ten Teilchens
Insbes
∫f dηt ∼
∫f dηN
t =1
N
N∑i=1
f (Xt(i))
iterative Berechnung von (Xt+1(i))i aus (Xt(i))i
Einleitung Optimale Filter in diskreter Zeit Teilchenfilter Asymptotische Stabilitat Optimale Filter in stetiger Zeit
1. Schritt: Vorhersage
ziehe N unabhangige Stichproben
X ′t+1(1), . . . ,X ′
t+1(N)
gemaß der Verteilung
1
N
N∑i=1
P(Xt(i), ·)
dh simuliere N-mal einen Schritt des Signalprozesses
Einleitung Optimale Filter in diskreter Zeit Teilchenfilter Asymptotische Stabilitat Optimale Filter in stetiger Zeit
2. Schritt: Korrektur
berechne zu gegebener Beobachtung Yt+1 die Werte derLikelihoodfunktion
wt+1(i) = g(Yt+1,X′t+1(i))
ziehe N unabhangige neue Positionen X ′t+1(i) gemaß
P[Xt+1(i) = X ′
t+1(j)]
=wt+1(j)∑k wt+1(k)
, j = 1, . . . ,N
dh selektiere die neuen Teilchen mit einer Wkeit proportional zurFitnessfunktion wt+1(·)
Einleitung Optimale Filter in diskreter Zeit Teilchenfilter Asymptotische Stabilitat Optimale Filter in stetiger Zeit
Genetische Algorithmen
I entspricht einem Mutations/Selektions-Algorithmus
I variationeller Zugang zu Mutations/Selektions-Algorithmenauch fur interaktive Selektion in
[St, ’04] On the convergence of geneticalgorithms - a variational approach
Einleitung Optimale Filter in diskreter Zeit Teilchenfilter Asymptotische Stabilitat Optimale Filter in stetiger Zeit
Gesetz der großen Zahlen
Theorem
1 Schwache KonvergenzP Feller (dh f stetig ⇒ Pf stetig), g stetig und beschrankt
=⇒ limN→∞
∫f dηN
t =
∫f dηt ∀f ∈ Cb(S)
2 Konvergenz im quadr. Mittel [Crisan, Doucet ’00]∀Y g(Y , ·) beschrankt ⇒ ∃ ct mit
E
[(∫f dηN
t −∫
f dηt
)2]≤ ct
N‖f ‖2∞ ∀f ∈ Bb(S)
I Konvergenzrate unabhangig von der DimensionI ct typischerweise exponentiell anwachsend bzgl. tI Erweiterungen auf diverse Resampling Schemata
Einleitung Optimale Filter in diskreter Zeit Teilchenfilter Asymptotische Stabilitat Optimale Filter in stetiger Zeit
3 glm. Konv. im quadr. Mittel [LeGland, Oudjane ’02]
I gP mischend mit ελ ≤ g(Yt , ·)P(xt−1, ·) ≤ ε−1λ
I ρt :=supx∈S g(Yt ,xt)
infµ∈M1(S)
∫g(Yt ,xt)P(xt−1,dxt)µ(dxt−1)
≤ ρ < ∞
=⇒ E
[(∫f dηN
t −∫
f dηt
)2]≤ c(ε, ρ)
N‖f ‖2∞ ∀f ∈ Bb(S)
Einleitung Optimale Filter in diskreter Zeit Teilchenfilter Asymptotische Stabilitat Optimale Filter in stetiger Zeit
4 exakte Konvergenzrate [DelMoral, Guionnet ’98]
I S lokalkompakter, separabler metrischer RaumI P FellerI additiver Messfehler
Yt = G (Xt) + et et ∼ r(x) dx
mit G , r stetig und beschrankt
=⇒ P[ηNt ∈ A
]� e−N infµ∈A It(µ)
mit
It(µ) = supf∈Cb(S)
(∫f dµ
+ infν∈M1(S)
(It−1(ν)− log
(∫P(e f g(Yt−1, ·)
)dν∫
Pg(Yt−1, ·) dν
)))und I0(µ) = H(µ | η0)
Einleitung Optimale Filter in diskreter Zeit Teilchenfilter Asymptotische Stabilitat Optimale Filter in stetiger Zeit
Zentraler Grenzwertsatz
Theorem [Chopin ’04, Kunsch ’05]
Fur alle t existiere δ > 0 mit∫‖Pg(Yt , ·)‖2+δ dηt−1 < ∞
=⇒√
N
(∫f dηN
t −∫
f dηt
)w−→ N(0,Vt(f ))
mit
I (Resampling) Vt(f ) = Vt(f ) + Varηt (f )
I (Korrektur) Vt(f ) = V ′t
(g(Yt , ·)
(f −
∫f dηt−1
))mit g(Yt , x) = g(Yt ,x)∫
Pg(Yt ,·) dηt−1
I (Vorhersage) V ′t (f ) = Vt−1(Pf )
I V0(f ) = Varη0(f )
Einleitung Optimale Filter in diskreter Zeit Teilchenfilter Asymptotische Stabilitat Optimale Filter in stetiger Zeit
Zusatz schwache Konvergenz der endlichdim. Randverteilungendes zufalligen Feldes(√
N
(∫f dηN
t −∫
f dηt
))f ∈Bb(S)
gegen zentriertes Gaußsches Feld mit Kovarianzoperator
Vt(f , g) =1
2(Vt(f + g)− Vt(f )− Vt(g))
weitestgehend offen Asymptotik der Varianz fur t →∞einziges veroffentlichtes Resultat im Fall Xt ≡ X0 ∈ Rd :
‖Vt(f )‖ � ctd2
Einleitung Optimale Filter in diskreter Zeit Teilchenfilter Asymptotische Stabilitat Optimale Filter in stetiger Zeit
Asymptotische Stabilitat des optimalen Filters
ηY1:tt = T (Yt , ·) ◦ . . . ◦ T (Y1,PX0)
hangt von der Anfangsverteilung PX0 des Signals ab
Unbekannt!
Einleitung Optimale Filter in diskreter Zeit Teilchenfilter Asymptotische Stabilitat Optimale Filter in stetiger Zeit
Heuristik
(Xt) ergodisch (dh limt→∞ E [f (Xt)] =∫
f dν ∀f ∈ Cb(S))
⇒ Xt vergisst Anfangsverteilung PX0 fur große t
⇒ ηY1:tt vergisst PX0 ebenfalls fur große t
⇒ ηY1:tt stabil
Allerdings Ergodizitat nicht notwendig fur asymptotische Stabilitat
Einleitung Optimale Filter in diskreter Zeit Teilchenfilter Asymptotische Stabilitat Optimale Filter in stetiger Zeit
Beispiel: AR(1)-Prozesse
(S) Xt = B(Xt−1) + C (Xt−1) Wt auf Rd
(O) Yt = G (Xt) + ε Wt auf Rd
mit
I (Wt) iid N(0, I )
I (Wt) iid, PWt= r dx , r log-konkav
I B beschrankt oder Lipschitz
I G bijektiv, G und G−1 Lipschitz
Einleitung Optimale Filter in diskreter Zeit Teilchenfilter Asymptotische Stabilitat Optimale Filter in stetiger Zeit
Theorem [St ’06] Unter obigen Annahmen existiertε0 > 0, so dass fur |ε| < ε0
lim supt→∞
1
tlog ‖ηY1:t
t,1 − ηY1:tt,2 ‖var < 0 f .s.
fur Anfangsbedingungen (PX0)i , i = 1, 2, mit∫‖B(x)‖2 (PX0)i (dx) < ∞
Bem wesentliche Einschrankung: dim Yt = dim Xt
Einleitung Optimale Filter in diskreter Zeit Teilchenfilter Asymptotische Stabilitat Optimale Filter in stetiger Zeit
Signale in stetiger Zeit
(S) dXt = B(Xt) dt + C (Xt) dWt auf Rd
wobei (Wt) Brownsche Bewegung
(Xt) ist Markovprozess mit Generator
Af (x) =1
2
d∑i,j=1
(CCT )ij(x)∂ij f (x) +d∑
i=1
Bi (x)∂i f (x)
Einleitung Optimale Filter in diskreter Zeit Teilchenfilter Asymptotische Stabilitat Optimale Filter in stetiger Zeit
Additiver Messfehler
(O) Yt = G (Xt) + et
wobei (et)t≥0 Brownsche Bewegung, unabhangig von (Xt)t≥0
ηt = die a-posteriori Verteilung von (S) gegeben Y0:t
= bedingte Verteilung P [Xt ∈ dx | Y0:t ]
mit Y0:t = (Ys)0≤s≤t
Einleitung Optimale Filter in diskreter Zeit Teilchenfilter Asymptotische Stabilitat Optimale Filter in stetiger Zeit
Zakai-Gleichung
die a-priori Verteilung des Signalprozesses ist Losung von
dηt = Aηt dt (Fokker-Planck) (3)
A - dualer Operator zu A
bedingt auf die Beobachtung (Yt) andert sich dies zu
d ηt = Aηt dt + G ηt dYt (Zakai) (4)
Einleitung Optimale Filter in diskreter Zeit Teilchenfilter Asymptotische Stabilitat Optimale Filter in stetiger Zeit
die Zakai-Gleichung kann direkt gelost werden∫f d ηt = E
[f (Xt) exp
(∫ t
0
G(Xs) dYs −1
2
∫ t
0
‖G(Xs)‖2 ds
)]
so dass ∫f dηt =
E[f (Xt) exp
(∫ t
0G(Xs) dYs − 1
2
∫ t
0‖G(Xs)‖2 ds
)]E[exp
(∫ t
0G(Xs) dYs − 1
2
∫ t
0‖G(Xs)‖2 ds
)](Kallianpur-Striebel Formel)
(5)
Einleitung Optimale Filter in diskreter Zeit Teilchenfilter Asymptotische Stabilitat Optimale Filter in stetiger Zeit
Robuste Version von (5)
partielle Integration∫ t
0G (Xs) dYs = Yt · G (Xt)−
∫ t
0Ys dG (Xs) f .s.
und Ito-Formel liefern Darstellung von (5) als ren. Feynman-KacHalbgruppe
∫f dηt =
E[f (Xt) exp
(Yt · G (Xt)
)exp
(∫ t0 G (Ys , Xs) ds
)]E
[exp
(Yt · G (Xt)
)exp
(∫ t0 G (Ys , Xs) ds
)]mit
I (Xt) - Markovprozess mit Generator A− Yt · CCTDG · ∇I G(Y , ·) = exp (Y · G)A exp (−Y · G)− 1
2‖G‖2
Einleitung Optimale Filter in diskreter Zeit Teilchenfilter Asymptotische Stabilitat Optimale Filter in stetiger Zeit
Teilchenapproximation
zu N ≥ 2 betrachte unabhangige Kopien
Xt(1), . . . , Xt(N)
Paar-Wechselwirkung
I jedes Teilchen Xt(i) besitzt exp. Lebenszeit mit Rate 1N
I stirbt ein Teilchen wird es ersetzt durch die Kopie eines der ubrigen N − 1Teilchen mit Wkeit proportional zu G(Yt , Xt(j))
erhalte dadurch einen neuen Prozess
Yt(1), . . . , Yt(N)
und nehme ηNt = 1
N
∑Ni=1 δYt (i) als Approximation fur ηt ∝ e−Yt ·G ηt
Einleitung Optimale Filter in diskreter Zeit Teilchenfilter Asymptotische Stabilitat Optimale Filter in stetiger Zeit
Theorem [DelMoral, Miclo ’00] CCT ∈ C 4p (Rd), B ∈ C 3
p (Rd)
1 Konvergenz im quadr. Mittel
E
[(∫f d ηN
t −∫
f d ηt
)2]≤ ct
N‖f ‖2∞ ∀f ∈ Bb(Rd)
2 Zentraler Grenzwertsatz
√N
(∫f d ηN
t −∫
f d ηt
)w−→ N(0,Vt(f )) fur geeignete f
Vt(f ) = Varηt (f ) + 2
∫ t
0
∫f 2s,t G(Ys , ·) d ηs ds
mit
fs,t =Es,x
[f (Xt) exp
(∫ t
sG(Yu, Xu) du
)]∫Es,x
[exp
(∫ t
sG(Yu, Xu) du
)]d ηs(x)
Einleitung Optimale Filter in diskreter Zeit Teilchenfilter Asymptotische Stabilitat Optimale Filter in stetiger Zeit
Asymptotische Stabilitat
(S) dXt = ∇ϕϕ (Xt) dt + dWt auf Rd
(O) dYt = GXt dt + det , Y0 = 0 auf Rp
mit
I (Wt)t≥0, (et)t≥0 unab. Brownsche Bewegungen
I ϕ ∼ ϕ0 mit ϕ0 beschrankt und log-konkav
I W (x) := ‖Gx‖2 + ∆ϕϕ
(x) glm. strikt konvex
∃ κ∗ > 0 mit W ′′ ≥ κ2∗ · I
Einleitung Optimale Filter in diskreter Zeit Teilchenfilter Asymptotische Stabilitat Optimale Filter in stetiger Zeit
Theorem [St ’04] Es gelte
I Y ∈ C ([0,∞[; Rp), Y (0) = 0
I (PX0)i ∼ ν(x) dx mit −(log ν)′′ ≥ κ∗ · I
dann folgtlim supt→∞
eκ∗2
t‖η1,Y0:tt − η2,Y0:t
t ‖var < ∞
Bem
I Rate unabhangig von Y
I prazise quantitative Abschatzungen
I Stabilitat auch fur nichtergodisches Signal
Recommended