Neue Herausforderungen für die Stochastik aus dem Bereich ... fileFachbereich Mathematik TU Darmstadt October 18, 2006. Einleitung Optimale Filter in diskreter Zeit Teilchenﬁlter

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


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


Weitere Anwendungen

Objektverfolgung Erkundung

Quellen: Prof. Ji, RPI, New York Prof. Fox, Univ. of Washington


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 ]


Beispiel


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)


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


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....


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)


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)


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


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


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(·)


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


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


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)


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)


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 )


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


Asymptotische Stabilitat des optimalen Filters

ηY1:tt = T (Yt , ·) ◦ . . . ◦ T (Y1,PX0)

hangt von der Anfangsverteilung PX0 des Signals ab

Unbekannt!


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


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


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


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)


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


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)


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)


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


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


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)


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


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


Vielen Dank fur Ihre Aufmerksamkeit!

Documents

Neue Herausforderungen für die Stochastik aus dem Bereich ... fileFachbereich Mathematik TU Darmstadt October 18, 2006. Einleitung Optimale Filter in diskreter Zeit Teilchenﬁlter