Embed Size (px)
Citation preview
KI 15-Zeit 1
Zeitliches probabilistisches Schließen
KI 15-Zeit 2
Überblick
•Zeit und Unsicherheit, Markov-Prozesse
•Inferenz:
- Filtern, Vorhersage, Glättung
- Wahrscheinlichste Erklärung (Viterbi-Algorithmus)
•Hidden-Markov-Modelle
•Kalman-Filter
•Dynamische Bayes-Netze (kurz)
KI 15-Zeit 3
Zeit und Unsicherheit
Ziel: Zeitabläufe verfolgen und vorhersagen
Beispiele: Motormanagement; Einstellung von Medikamenten
Idee: Kopiere Zustand und Evidenzvariable für jeden Zeitschritt
Xt = Menge unbeobachtbarer Zustandsvariabler zur Zeit t
z.B. Blutzuckert, Mageninhaltt, etc.
Et = Menge beobachtbarer Evidenzvariabler zur Zeit t
z.B. GemessenerBlutzuckert, Pulst, VerzehrteNahrungt
Hierbei wird diskrete Zeit angenommen; Schrittweite problemabhängig.
Notation: Xa:b= Xa, Xa+1, … , Xb-1, Xb
KI 15-Zeit 4
Markov-Prozesse
Konstruiere Bayes-Netz aus diskret zeitabhängigen Variablen:
Was sind die Elternknoten?
Markov-Annahme: Xt hängt nur von beschränkter Teilmenge der Variablen X0:t-1 ab (Markov-Prozess oder Markov-Kette)
Markov-Prozess 1. Ordnung: P(Xt | X0:t-1) = P(Xt | Xt-1)
Markov-Prozess 2. Ordnung: P(Xt | X0:t-1) = P(Xt | Xt-2,Xt-1)
1. Ordnung
2. Ordnung
KI 15-Zeit 5
Markov-Prozesse
Markov-Annahme für Sensoren:
Sensorwert hängt nur vom aktuellen Wert der beobachteten Größe ab.
P(Et | X0:t, E0:t-1) = P(Et | Xt)
Beispiel: Tachowert Et hängt nur von aktueller Geschwindigkeit Xt ab, aber nicht
von vergangener Xt-1.
Gegenbeispiel: Wasserstandsanzeiger bei Hydrokultur
• Variable: Wasserstand Xt
• Evidenz (Beobachtungsgröße): Angezeigte Höhe Et
• Kein Markov-Sensor, denn falls X 10 Tage über Maximum ist, bilden
sich Algen und Anzeiger klebt fest.
KI 15-Zeit 6
Markov-Prozesse
Stationärer Prozess:
Welt verändert sich, aber Gesetze dieser Änderung und ihrer Beobachtung sind konstant:
• Übergangsmodell P(Xt | Xt-1) und
• Sensormodell (Beobachtungsmodell) P(Et | Xt)
sind beide fest für alle t.
KI 15-Zeit 7
Markov-Prozesse
Beispiel für konstantes Übergangsmodell:
• X ist Wasserstand.
• Gieße jede Woche ca. 1l rein, Menge ist Gauss-verteilt mit
Standardabweichung 0.2 l.
Gegenbeispiel:
• Nachdem eine Pflanze vertrocknet ist, wird Mittelwert auf 1.2 l erhöht.
Beispiel für konstantes Sensormodell:
• Waage, X ist Gewicht, E mit Gauss-verteiltem Fehler behaftete Anzeige.
Gegenbeispiel:
• Feder der Waage leiert allmählich aus.
KI 15-Zeit 8
Realwelt:
Annahme eines Markov-Prozesses 1. Ordnung stimmt meist nicht exakt !
Mögliche Verbesserungen:
1. Markov-Prozesse höherer Ordnung
2. Erweitere Zustand um andere Evidenzen (Meßgrößen)
Beispiel: Bewegung eines Roboters
Erweitere Zustandsbeschreibung (Position, Geschwindigkeit) um Batteriet
Markov-Prozesse
KI 15-Zeit 9
Inferenz
Ausgangspunkt:
• Stationärer Markov-Prozess 1. Ordnung mit geg.
Übergangsmodell P(Xt | Xt-1)
• Markov-Sensor mit geg. Sensormodell P(Et | Xt)
Inferenz:
Verschiedene Problemtypen, die unterschiedliche Mischungen aus zwei Grundproblemen sind:
• Ableitung der Zufallsvariablen X aus den Evidenzen
• Vorhersage
KI 15-Zeit 10
InferenzArten der Inferenz unterscheiden sich darin, für welche Zeitpunkte die
Wahrscheinlichkeitsverteilung für X aus welchen Evidenzen e berechnet wird:
1. Filtern: P(XT | e1:T)
Berechne aktuellen Zustand XT aus aktueller Evidenz eT und vergangenen Evidenzen e1:T-1 (aber x1 … xT-1 sind unbekannt).
2. Vorhersage: P(XT+K | e1:T), k>0 Sage zukünftigen Zustand XT+K aus Evidenzen e1:T (ohne Kenntnis von X1 …
XT+K) voraus. Wie Filtern, aber die jüngsten Evidenzen eT+1:T+K sind unbekannt.
3. Glättung: P(XK | e1:T), Berechne vergangenen Zustand XK aus früheren Evidenzen e1:K-1 und späteren Evidenzen eK+1:T.
4. Wahrscheinlichste Erklärung: arg maxX1:T P(X1:T | e1:T)
Berechne alle X1:T aus allen Evidenzen e1:T. Bsp.: Worterkennung.
Tk 0
Inferenz: Filtern
Gegeben: Übergangsmodell P(Xt | Xt-1) und Sensormodell P(Et | Xt)
Gesucht: XT aus e1:T
Idee: Suche Rekursionsbeziehung der Zustandsschätzungen, so dass,
beginnend mit Annahme für X0 , aus t auch t+1 berechnet werden kann.
Für t = 0, 1, … T-1:
P(Xt+1 | e1:t+1) = P(Xt+1 | e1:t,et+1)
= α P(et+1 | Xt+1,e1:t) P(Xt+1 | e1:t) (Bayes)
= α P(et+1 | Xt+1) P(Xt+1 | e1:t) (Markov-Sensor)
= α P(et+1 | Xt+1) Σxt P(Xt+1 | xt,e1:t) P(xt | e1:t) (Xt aussummieren)
= α P(et+1 | Xt+1) Σxt P(Xt+1 | xt) P(xt | e1:t) (Markov-Prozess)
= α Sensormodellt+1 Σxt Übergangsmodellt+1,t Zustandsverteilungt
Struktur der Rekursionsbeziehung:
f1:t+1 = Forward(f1:t, et+1) mit f1:t = P(Xt | e1:t)
Zeit- und Speicherbedarf konstant für jeden Schritt von t-1 t (d.h. unabhängig von t).
KI 15-Zeit 12
Filtern: Beispiel
Leben im Bunker:
• Keine direkte Beobachtung der Außenwelt
• Regen X wird nur daraus erschlossen, ob Chef
Regenschirm E dabei hat (Chef darf raus)
• Zeitschritte: Tage
KI 15-Zeit 13
Übergangsmodell:
P(Xt | Xt-1) = P(Regent | Regent-1) mit P(Xt | Xt-1= wahr) = <0.7, 0.3>
P(Xt | Xt-1= falsch) = <0.3, 0.7>
Sensormodell:
P(Et | Xt) = P(Schirmt | Regent) mit P(Et | Xt = wahr) = <0.9, 0.1>
P(Et | Xt = falsch) = <0.2, 0.8>
Frage:
Was ist Regenwahrscheinlichkeit P(X2) am zweiten Tag (T=2), wenn
• Tag 1: Regenschirm, d.h. e1 = w.
• Tag 2: Regenschirm, d.h. e2 = w.
• Annahme über Regenwahrscheinlichkeit am Tag 0: P(X0) = <0.5, 0.5>
Filtern: Beispiel
KI 15-Zeit 14
P(Xt+1|e1:t+1) = α P(et+1 | Xt+1) Σxt P(Xt+1 | xt) P(xt | e1:t)
P(X2 | e1:2) = α P(e2 | X2) Σx1 P(X2 | x1) P(x1 | e1)
P(X1 | e1) = α P(e1 | X1) Σx0 P(X1 | x0) P(x0)
= α P(e1 | X1) [ P(X1 | x0 =w) P(x0=w) + P(X1 | x0 =f) P(x0=f) ]
= α P(e1 | X1) [ <0.7, 0.3> 0.5 + <0.3, 0.7> 0.5 ] = α P(e1 | X1) <0.5, 0.5>
= α <0.9, 0.2> <0.5, 0.5> = α <0.45, 0.1> = <0.818, 0.182>
P(X2 | e1:2) = α P(e2 | X2) Σx1 P(X2 | x1) P(x1 | e1)
= α P(e2 | X2) [ P(X2 | x1=w) 0.818 + P(X2 | x1=f) 0.182 ]
= α <0.9, 0.2> [ <0.7, 0.3> 0.818 + <0.3, 0.7> 0.182 ]
= α <0.9, 0.2> <0.627, 0.373> = α < 0.565, 0.075 >
= < 0.883, 0.117>
Filtern: Beispiel
KI 15-Zeit 15
Filtern: Beispiel
KI 15-Zeit 16
VorhersageGegeben: Übergangsmodell P(Xt | Xt-1) und Sensormodell P(Et | Xt)
Gesucht: XT+K aus e1:T
Idee:
• Filterung bis T
• Dann K weitere Schritte ohne neue Evidenzen (eT+1:T+K fehlen!)
• Dafür Rekursionsformel: T+k T+k+1
Für k = 0, 1, … K-1:
P(XT+k+1 | e1:T) = ΣxT+k P(XT+k+1 | xT+k) P(xT+k | e1:T)
= ΣxT+k ÜbergangsmodellT+k+1,T+k ZustandsverteilungT+k
Je weiter über letzte Evidenz hinaus vorausberechnet wird, desto mehr wird Verteilung allein vom Übergangsmodell bestimmt.
KI 15-Zeit 17
Glättung
Gegeben: Übergangsmodell P(Xt | Xt-1) und Sensormodell P(Et | Xt)
Gesucht: XK aus e1:T wobei 1 <= K < T
Idee: „Vorwärts-Rückwärts-Algorithmus“:
Filterung von 1 bis K und „Rückwärtsfilterung“ von T bis K.
KI 15-Zeit 18
GlättungTeile Evidenzen e1:T in Evidenzen bis K und nach K: e1:K, eK+1:T
P(XK | e1:T) = P(XK | e1:K, eK+1:T)
= α P(XK | e1:K) P(eK+1:T | XK, e1:K) (Bayes)
= α P(XK | e1:K) P(eK+1:T | XK) (Markov-Sensor)
= α f1:K bK+1:T
Rückwärts-Rekursion für k = T-1, T-2, ... K+1, K:
P(ek+1:T | Xk) = xk+1 P(ek+1:T | Xk, xk+1) P(xk+1 | Xk)
= xk+1 P(ek+1:T | xk+1) P(xk+1 | Xk) (bed. unabh.)
= xk+1 P(ek+1, ek+2:T | xk+1) P(xk+1 | Xk)
= xk+1 P(ek+1 | xk+1) P(ek+2:T | xk+1) P(xk+1 | Xk)
bk+1:T = Backward(bk+2:T, ek+1:T) mit bk+1:T = P(ek+1:T | Xk)
19
Wie bisher:
P(Xt | Xt-1= wahr) = <0.7, 0.3> P(Et | Xt = wahr) = <0.9, 0.1>
P(Xt | Xt-1= falsch) = <0.3, 0.7> P(Et | Xt = falsch) = <0.2, 0.8>
P(X0) = <0.5, 0.5>, e1 = w, e2 = w. P(X1 | e1:2) = ?
Allg.: P(XK | e1:T) = α P(XK | e1:K) P(eK+1:T | XK), hier: T=2, K=1
Hier: P(X1 | e1:2) = α P(X1 | e1) P(e2 | X1)
Aus Filterung: P(X1 | e1) = <0.818, 0.182>
P(ek+1:T | Xk) = xk+1 P(ek+1 | xk+1) P(ek+2:T | xk+1) P(xk+1 | Xk)
P(e2 | X2) = x2 P(e2 | x2) P(e3:2 | x2) P(x2 | X1) mit P(e3:2 | x2) = 1
= 0.9 x 1 x <0.7, 0.3> + 0.2 x 1 x <0.3, 0.7> = <0.69, 0.41>
P(X1 | e1:2) = α <0.818, 0.182> x <0.69, 0.41> = <0.833, 0.177>
Glättung: Beispiel
KI 15-Zeit 20
Glättung: Beispiel
KI 15-Zeit 21
Wahrscheinlichste Erklärung
• Problem: Finde die wahrscheinlichste Erklärung für beobachtete Ereignisse
• Genauer: Finde wahrscheinlichste Folge versteckter Zustände, die eine
beobachtete Folge von Evidenzen bewirkt.
• Für T Schritte gibt es 2T mögliche Zustandsfolgen (für boolesche Zustände)
• Naiver Ansatz: Berechne durch Glättung jede Wahrscheinlichkeit einzeln.
• Aber: Wahrscheinlichste Folge verlangt Maximierung gemeinsamer
Wahrscheinlichkeit !
• D.h. wahrscheinlichste Folge ist nicht Folge der wahrscheinlichsten Zustände !
• Lösung: Viterbi-Algorithmus
• Anwendungen: Entzerrung und Korrektur fehlerhafter Signale, z.B. bei Handys,
WLAN, Festplatten; Spracherkennung
KI 15-Zeit 22
Wahrscheinlichste ErklärungWahrscheinlichster Pfad zu xt+1 =
wahrscheinlichster Pfad zu xt plus ein weiterer Schritt.
max x1 … xt P(x1, …, xt, Xt+1 | e1:t+1) =
P(et+1 | Xt+1) max xt [ P(Xt+1 | xt) max x1 … xt-1
P(x1,…,xt-1,xt | e1:t) ]
Wie Filtern (f1:t+1 = α P(et+1 | Xt+1) Σxt P(Xt+1 | xt) f1:t),
aber:
1. f1:t = P(Xt | e1:t) wird ersetzt durch
m1:t = max x1 … xt-1 P(x1,…,xt-1,Xt | e1:t),
d.h. m1:t(i) ist die Wahrscheinlichkeit des wahrscheinlichsten Pfades zu Zustand i.
2. Ersetze Summation über xt durch Maximierung über xt (Viterbi-Algorithmus):
m1:t+1 = P(et+1 | Xt+1) maxxt [ P(Xt+1 | xt) m1:t ]
KI 15-Zeit 23
Viterbi-Algorithmus
1. Berechne sukzessive alle m1:t. Speichere dabei jeweils „besten Vorgänger“ für jeden Zustand (dicke Pfeile).
2. Wähle den wahrscheinlichsten Zustand zur Zeit t.
3. Gehe von dort zurück zum besten Vorgänger etc.
KI 15-Zeit 24
Hidden-Markov-ModelleBisher keine formale Beschreibung für Übergangs- und Sensormodelle.
Modell für Markov-Prozess mit Zuständen, die durch eine Variable beschrieben werden: Hidden-Markov-Modell (HMM).
Xt sei eine diskrete Variable, Et die zugehörige Evidenz (meist ebenfalls eine einzelne Variable).
Domäne von Xt sei {1 … S}.
Übergangsmatrix: Tij = P(Xt = j | Xt-1= i), z.B.
Sensormatrix Ot für jeden Zeitschritt, Diagonalelemente sind P(et | Xt = i) :
z.B. mit E1= wahr O1=
7.03.0
3.07.0
2.00
09.0
KI 15-Zeit 25
Hidden-Markov-Modelle
Mit
Übergangsmatrix Tij = P(Xt = j | Xt-1= i) und
Sensormatrix (Ot)ii = P(et | Xt = i) :
ergibt sich Matrix-Schreibweise, z.B. für Glättung:
f1:t+1 = α Ot+1TT f1:t (statt P(Xt+1 | e1:t+1) = α P(et+1 | Xt+1) Σxt P(Xt+1 | xt) P(xt | e1:t) )
bk+1:t = TOk+1 bk+2:t (statt P(ek+1:T | Xk) = xk+1P(ek+1 | xk+1) P(ek+2:T | xk+1) P(xk+1| Xk) )
KI 15-Zeit 26
Country-Dance-Algorithmus
Vorwärts-Rückwärts Algorithmus
P(Xk | e1:T) = α f1:k bk+1:T mit f1:t+1 = α Ot+1TT f1:t (1)
bk+1:t = TOk+1 bk+2:t (2)
braucht Zeit O(S2 T) und Speicher O(S T) um die gesamte Folge zu glätten, denn alle f müssen beim Vorwärts-Durchgang gespeichert werden.
Vermeide bei Glättung die Speicherung aller f, indem auch der Vorwärts-Algorithmus rückwärts angewandt wird:
f1:t+1 = α Ot+1TT f1:t
O-1t+1 f1:t+1 = α TT f1:t
α´(TT) -1 O-1t+1 f1:t+1 = f1:t (3)
Verbesserter Algorithmus:
• Vorwärts-Durchgang berechnet f1:T (also das letzte f) mit Gl. (1).
• Rückwärts-Durchgang berechnet jeweils f1:k mittels Gl. (3) und bk+1:T mit Gl. (2).
KI 15-Zeit 27
Country-Dance-Algorithmus
f1
b1
e1
fT
bT
eT
KI 15-Zeit 28
Country-Dance-Algorithmus
f1
b1
e1
fT
bT
eT
KI 15-Zeit 29
Country-Dance-Algorithmus
f1
b1
e1
fT
bT
eT
KI 15-Zeit 30
Country-Dance-Algorithmus
f1
b1
e1
fT
bT
eT
KI 15-Zeit 31
Country-Dance-Algorithmus
f1
b1
e1
fT
bT
eT
KI 15-Zeit 32
Country-Dance-Algorithmus
f1
b1
e1
fT
bT
eT
KI 15-Zeit 33
Country-Dance-Algorithmus
f1
b1
e1
fT
bT
eT
KI 15-Zeit 34
Country-Dance-Algorithmus
f1
b1
e1
fT
bT
eT
KI 15-Zeit 35
Country-Dance-Algorithmus
f1
b1
e1
fT
bT
eT
KI 15-Zeit 36
Country-Dance-Algorithmus
f1
b1
e1
fT
bT
eT
KI 15-Zeit 37
Kalman-FilterModellierung von Systemen, die durch eine Menge stetiger (insb. zeitabhängiger) Variabler beschrieben werden.
Z.B. Trajektorienverfolgung: Zufallsvariable sind Ortskoordinaten und deren Zeitableitung.
Bsp.: Vogel fliegt durch Wald, teilweise von Bäumen verdeckt. Versuche Trajektorie vorherzusagen.
Weitere Beipiele: Planeten, Roboter, Ökosystem, Volkswirtschaft, Flugzeuge (insb. Fusion GPS - Trägheitsnavigation), …
Bayes-Netz für lineares dynamischesSystem mit Position Xt und Positions-messung Zt:
KI 15-Zeit 38
Kalman-Filter
Bsp. 1D-Trajektorie:
• Beobachte X-Koordinate
• Zeitabstand der Beobachtungen: t
• Annahme: Geschwindigkeit näherungsweise konstant
Einfache Trajektorien-Vorhersage:
Um Meßfehler und nicht konstante Geschwindigkeit zu berücksichtigen, wird Gauß-verteilter Fehler angenommen:
tXXX ttt
20
21
0 e),,(mit
),,(),|(
xx
tttttttttttt
xxN
xtxxNxXxXxXP
KI 15-Zeit 39
Anpassen der Gauß-Verteilungen
Annahme: Gaußsche a-priori Verteilung, lineares Gaußsches Übergangsmodell, lineares Gaußsches Sensormodell.
Vorhersageschritt:
Wenn P(Xt | e1:t) Gauß-verteilt ist, dann ist die vorhergesagte Verteilung
P(Xt+1 | e1:t) = P(Xt+1 | xt) P(xt | e1:t) dxt
ebenfalls eine Gaußverteilung. Mit P(Xt+1 | e1:t) ist dann auch
P(Xt+1 | e1:t+1) = α P(et+1 | Xt+1) P(Xt+1 | e1:t)
Gauß-verteilt.
Daher ist P(Xt | e1:t) eine (multivariate) Gaußverteilung N(t,t) für alle t mit Mittelwertmatrix und Kovarianzmatrix .
tx
KI 15-Zeit 40
Interpretation
• P(Xt | e1:t) ist (und bleibt) Gaußverteilung, deren Parameter
(Mittelwerte, Kovarianzen) sich mit der Zeit ändern.
• D.h. P(Xt | e1:t) kann für alle t mit der gleichen Anzahl Parameter
beschrieben werden.
• Da sich die Gaußverteilung beliebig verbreitern kann, ist ggf. nur noch
sehr wenig nutzbare Information über X vorhanden, aber …
• … diese kann zumindest durch eine konstante Zahl von Parametern
ausgedrückt werden !
• Dies gilt im allgemeinen (d.h. nichtlinearen, nicht-Gaußschen) Fall
nicht:
Im allgemeinen wächst der Aufwand zur Beschreibung einer a-
posteriori Verteilung mit der Zeit unbegrenzt !
41
1-D Beispiel: Random Walk• Gaußscher „Random Walk“ auf der X-Achse (z.B. krabbelnder Käfer):
Zufallsvariable Xtt
• A-priori Verteilung (Käfer wird mit begrenzter Genauigkeit in Startposition gebracht):
P(x0) = N(0, 0, x0)
• Übergangsmodell (Käfer krabbelt auf Zufallspfad):
P(xt+1 | xt) = N(xt, x, xt+1)
• Sensormodell (Positionsmessung mit begrenzter Genauigkeit):
P(zt | xt) = N(zt, z, xt)
• Erste Beobachtung: z1
P(x1 | z1) = N(1, 1, x1) mit
• Allgemein:
222
0
02
122
01
)(
zx
zx z
222
0
22202
1
)(
zx
zx
222
21
22
1
)(
zxt
tztxtt
z
222
2222
1
)(
zxt
zxtt
KI 15-Zeit 42
1-D Beispiel: Random Walk
• Startverteilung: 0 = 0, 0 = 1
• Übergang ist Rauschen mit x = 2
• Sensorrauschen z = 1
• Erste Beobachtung: z1 = 2.5
• Vorhersage P(x1) ist flacher als P(x0) wegen Übergangsrauschen
• Mittelwert 1 von P(x1 | z1)
kleiner als 2.5, da Vorhersage P(x1) berücksichtigt wird.
KI 15-Zeit 43
Kalman-Filter: Allgemeiner Fall
n Zufallsvariable, zusammengefasst als Vektorx.
Vektor der n Sensorwerte: z.
Übergangsmodell: P(xt+1 | xt) = N(F xt, x, xt+1)
Sensormodell: P(zt | xt) = N(H xt, z, zt)
F: n x n - Matrix des linearen Übergangsmodells
H: n x n - Matrix des linearen Sensormodells
x: n x n - Kovarianzmatrix des Übergangsrauschens
z: n x n - Kovarianzmatrix des Sensorrauschens
Gaußverteilung mit n Variablen:
N(, , x) = exp ( -½ (x-)T (x-) )
KI 15-Zeit 44
Kalman-Filter: Allgemeiner Fall
Aktualisierung:
t+1 = F t + Kt+1 (zt+1– H F t )
t+1 = (1 – Kt+1) L
wobei
L = F t FT + x
Kt+1 = L HT (H L HT + z)-1
K heißt Kalman-Gain(-Matrix).
Interpretation:
F t : Gemäß lin. Modell vorhergesagtes
H F t : Vorhergesagte Beobachtung
zt+1– HFt: Differenz Vorhersage – Beob.
Kt+1: Bewertet Vertrauenswürdigkeit der Beobachtung (dient als Gewicht gegenüber linearer Vorhersage).
t und Kt sind unabhängig von der beobachteten Sequenz Offline-Berechnung.
KI 15-Zeit 45
2-D Tracking Beispiel: Filterung
),,,( X YXYX
KI 15-Zeit 46
2-D Tracking Beispiel: Glättung
47
Grenzen des Kalman-FiltersEinfacher Kalman-Filter nicht anwendbar, falls Übergangsmodell nichtlinear.
Erweiterter Kalman-Filter:
• Behandlung von Nichtlinearitäten durch Annahme lokaler Linearität in der Umgebung von xt = t
• Versagt, falls System wesentliche Nichtlinearität bei xt = t hat.
• Bsp.: Vogel fliegt auf Baum zu.
Lösung: Switching-Kalman-Filter
• mehrere parallele Filter
• Spezialfall der DBNs
KI 15-Zeit 48
Dynamische Bayes-Netze• DBN ist temporales Wahrscheinlichkeitsmodell …
• … mit beliebiger Anzahl von Zustandsvariablen Xt, und Evidenzvariablen Et …
• … für jeden Zeitschritt.
• Beispiele: Regenschirmnetz; Robotersteuerung
KI 15-Zeit 49
DBNs und HMMsJedes HMM ist ein DBN mit einer Variablen.
Jedes DBN mit diskreten Variablen kann als HMM dargestellt werden:
• Fasse alle Variablen des DBN zu einer HMM-Variablen zusammen
• HMM-Variable hat für jede DBN-Wertekombination einen Wert
Vorteil DBN: „Zerlegte“ Zustände Exponentiell weniger Parameter !
Bsp: 20 boolsche Zustandsvariable mit je 3 Eltern
DBN hat 20 x 23 = 160 Parameter, HMM dagegen 220 x 220
KI 15-Zeit 50
DBNs und Kalman-FilterJeder Kalman-Filter ist ein DBN, aber nur wenige DBNs sind Kalman-Filter.
Realwelt erfordert nicht-Gaußsche Wahrscheinlichkeiten.
KI 15-Zeit 51
Exakte Inferenz in DBNsNaive Methode: „Aufrollen“, d.h. explizite Repräsentation aller Zeitschritte, dann Algorithmus für statische Bayes-Netze anwenden.
Problem: Speicher und Zeit wachsen mit O(t).
Rollup filtering: Zeitschritt t+1 hinzufügen, dann Variablen von Zeitschritt t „aussummieren“ Konstanter Zeit- und Speicherbedarf, aber Aufwand wächst exponentiell in # Zustandsvariablen.
Näherungsverfahren erforderlich, z.B. particle filtering.
KI 15-Zeit 52
Zusammenfassung
• In temporalen Modellen wird die Welt durch Zustands- und Sensorvariablen für jeden Zeitschritt repräsentiert.
• Markov-Annahmen für Zustandsübergänge und Sensoren sowie Annahme eines stationären Prozesses ermöglichen Beschreibung durch:
Übergangsmodell P(Xt | Xt-1) beschreibt Veränderung der Welt
Sensormodell P(Et | Xt) beschreibt Beobachtung der Welt
• Typische Aufgaben: Filtern, Vorhersage, Glättung, wahrscheinlichste Folge …
• … sind mit konstanten Kosten pro Zeitschritt möglich.
• HMMs haben nur eine diskrete Zustandsvariable; Anwendung: Spracherkennung
• Kalman-Filter erlauben n Zustandsvariable
• Dynamische Bayes-Netze subsummieren HMMs und Kalman-Filters; exakte Inferenz ist jedoch nicht realisierbar (hoher Aufwand)
• Particle filtering ist eine gute Näherung für Filterung mit DBNs.
KI 15-Zeit 53
Spracherkennung
KI 15-Zeit 54
Überblick
• Sprache als probabilistische Inferenz
• Phonologie
• Sprachlaute
• Wortaussprache
• Wortfolgen
KI 15-Zeit 55
Spracherkennung
• Spracherkennung:
Erkenne Folge von Wörtern aus dem Signal
• Sprachverstehen:
• Interpretation der Wortfolge
• Stelle Beziehung zwischen Wortfolge und anderen Daten her, z.B. anderen Sensordaten oder WB.
• Sprachsignale sind höchst variabel, mehrdeutig, verrauscht, etc.
• Besonderes Problem: Im Gegensatz zu gewöhnlichen Klassifikationsaufgaben (Schema: Signal Merkmalsextraktion Klassifikator Symbole) ist Sprachsignal so komplex, dass Erkennung auf mehreren Abstraktionsebenen gleichzeitig erfolgen muss.
KI 15-Zeit 56
Spracherkennung als probabilistische Inferenz
Aufgabe:
Was ist die wahrscheinlichste Wortfolge für ein gegebenes Sprachsignal?
D.h. wähle Wörter so, dass P(Wörter | Signal) maximiert wird.
Anwendung der Bayes-Regel:
P(Wörter | Signal) = α P(Signal | Wörter) P(Wörter)
Damit wird Dekomposition in akustisches Modell + Sprachmodell erreicht.
Die Wörter sind die (versteckte) Zustandsfolge, das Signal ist die
Beobachtungsfolge.
KI 15-Zeit 57
Phone und PhonemePhonologie:
• Menschliche Sprache besteht aus 40 – 50 Phonen (Lauten)
• Phone werden durch die Artikulatoren (Lippen, Zähne, Zunge, Stimmbänder, Luftdruck) gebildet
• Phoneme: Kleinste bedeutungsunterscheidende Einheiten (d.h. ein einzelnes Phonem hat selbst keine Bedeutung, aber Austausch eines Phonems ändert die Wortbedeutung).
• Phoneme ≠ Buchstaben: Vgl. rasten – rasten
• Allophone: Lautliche Varianten eines Phonems
• Phoneme sind eine von den Phonen abstrahierte Repräsentationsebene, die zwischen Signal und Wörtern liegt.
• Damit Aufteilung in
Akustisches Modell = Signalmodell + Aussprachemodell
KI 15-Zeit 58
Phone und Phoneme
DARPA-Alphabet (ARPAbet) für American English:
Z.B. „ceiling“: [s iy l ich ng] / [s iy l ix ng] / [s iy l en]
KI 15-Zeit 59
Sprachlaute
• Signal: Auslenkung der Mikrofon-Membran als Funktion der Zeit.
• Repräsentation: 8-16 kHz Abtastrate, 8-12 Bit Quantisierung
• Verarbeitung erfolgt in überlappenden Frames von 30 ms.
• Datenreduktion: Jedes Frame wird durch Merkmale repräsentiert.
• Merkmale: Z.B. Peaks im Leistungsspektrum
Analogsignal
Abgetastetes, digitalisiertes
Signal
Frames mit Merkmalen
KI 15-Zeit 60
Lautmodelle
• Merkmale der Frames in P(Merkmale | Laute) werden kompakter repräsentiert durch
- eine natürliche Zahl, z.B. in [0…255] (nach erfolgter Vektorquantisierung)
- die Parameter eines Gaußschen Mischungsmodells
• Darstellung der inneren Struktur von Lauten durch Dreizustands-Lautmodell:
- Jeder Laut besteht aus Onset, Mid, End.
- Z.B. [t] hat stummen Anfang, explosive Mitte, Zischen am Ende
- P(Merkmale | Laute, Phase)
KI 15-Zeit 61
Lautmodelle
• Problem: Laute klingen je nach Kontext, d.h. in einer Umgebung von
anderen Lauten, unterschiedlich (Koartikulationseffekt)
• Koartikulationseffekt entsteht, weil Artikulatoren nicht instantan ihre
Position verändern können.
• Kontext-Erfassung durch Triphone-Modell:
- Jeder von n Lauten wird durch n2 verschiedene Laute
repräsentiert, die von den beiden benachbarten Lauten abhängen.
- Z.B. [t] in „star“ wird repräsentiert durch [t(s,aa)]
• Kombination aus Dreizustands-Modell und Triphone-Modell vergrößert
Repräsentation von n auf 3n3.
• Aufwand lohnt sich !
KI 15-Zeit 62
Lautmodelle: Beispiel
Laut-HMM für [m]:
Zu jedem der drei Zustände des Laut-HMMs gehören die Ausgabewahrscheinlichkeiten für die Merkmale (z.B. VQ-Clusterzentren):
KI 15-Zeit 63
Aussprachemodelle für Wörter
Jedes Wort wird durch eine Wahrscheinlichkeitsverteilung über einer Lautfolge dargestellt, diese wird durch ein HMM repräsentiert:
P([towmeytow] | „tomato“) = P([towmaatow] | „tomato“) = 0.1
P([tahmeytow] | „tomato“) = P([tahmaatow] | „tomato“) = 0.4
• Struktur wird manuell erstellt
• Übergangswahrscheinlichkeiten werden gelernt.
KI 15-Zeit 64
Wortmodelle
Wortmodell besteht aus Lautmodell und Aussprachemodell.
Wortmodell für Tomato:
Zustand eines Wort-HMM = Laut + Lautzustand
Z.B. hat Wort-HMM für Tomato den Zustand [m]Mid.
KI 15-Zeit 65
Erkennung einzelner Wörter
Lautmodelle + Wortmodelle bestimmen P(e1:t | Wort) für einzelne Wörter.
Erkennung eines Wortes bedeutet Maximierung von
P(Wort | e1:t) = α P(e1:t | Wort) P(Wort).
Die a priori Wahrscheinlichkeit P(Wort) ergibt sich aus der Worthäufigkeit.
P(e1:t | Wort) wird rekursiv berechnet. Sei
l1:t = P(Xt, e1:t).
Verwende Rekursion
l1:t+1 = VORWÄRTS(l1:t, et+1)
und dann P(e1:t | Wort) = xt l1:t(xt).
Einzel-Wort Erkennung erreicht mit Training 95 – 99 % Genauigkeit.
KI 15-Zeit 66
Erkennung fortlaufender Sprache
Erkennung fortlaufender Sprache ≠ Folge von Einzel-Wort-Erkennungen !
• Benachbarte Wörter sind stark korreliert
• Folge wahrscheinlichster Wörter ≠ wahrscheinlichste Wortfolge
• Segmentierung von Wörtern: Schwierig, da kaum Pausen zwischen den Wörtern, die sich unmittelbar im Signal abzeichnen.
• Koartikulation zwischen Wörtern, z.B. „next thing“
Systeme zur Erkennung fortlaufender Sprache haben 60 – 80 % Genauigkeit.
KI 15-Zeit 67
Sprachmodell
Sprachmodell spezifiziert die a priori Wahrscheinlichkeit jeder Wortfolge, diese ist gegeben durch die Kettenregel:
P(w1…wn) = i=1
n P(wi | w1…wi-1)
Die meisten Terme sind schwer zu schätzen, daher Näherung durch
Bigram Modell:
P(wi | w1…wi-1) ≈ P(wi | wi-1),
d.h. Markov-Annahme 1. Stufe.
Training: Zähle alle Wort-Paare in einem großen Text-Korpus.
Kompliziertere Modelle wie Trigrams (d.h. P(wi | w1…wi-1) ≈ P(wi | wi-1, wi-2) oder Grammatik-Modelle bringen gewisse Verbesserungen.
KI 15-Zeit 68
Erkennung von Wortfolgen:
Kombiniertes HMM
• Kombiniere Wortmodell und Bigram-Sprachmodell zu einem HMM.
• Zustände des kombinierten HMM sind gegeben durch das Wort, den Laut und den Lautzustand.
Bsp.: [m]TomatoMid
• Übergänge:
• Lautzustand – Lautzustand (innerhalb eines Lautes)
• Laut – Laut (innerhalb eines Wortes)
• Wort-Endzustand – Wort-Anfangszustand
• Repräsentationsaufwand: Für W Wörter mit durchschnittlich L Dreizustandslauten hat kombiniertes HMM 3LW Zustände.
KI 15-Zeit 69
Erkennung von Wortfolgen:Kombiniertes HMM
• Wahrscheinlichste Lautfolge wird durch den Viterbi-Algorithmus
ermittelt, damit ist auch eine Wortfolge bestimmt.
• Zugleich wird auch Wort-Segmentierungsproblem gelöst.
• Aber: Die aus der wahrscheinlichsten Lautfolge ermittelte Wortfolge ist
nicht unbedingt die wahrscheinlichste Wortfolge.
• Grund: Wahrscheinlichkeit einer Wortfolge = Summe der
Wahrscheinlichkeiten aller zugehörigen Zustandsfolgen !
• Lösung: A*-Decoder (Jelinek 1969)
70
A*-Decoder
• Verwende A*-Suche um wahrscheinlichste Wortfolge zu finden
• Repräsentation durch Graph:
- Wort = Knoten in Graph
- Wortfolge = Pfad in Graph
- Nachfolger eines Knotens = Mögliche nachfolgende Wörter
- Graph für Satzlänge S hat S Ebenen
• Erinnerung A*: Geschätzte Kosten über n zum Ziel = f(n) = g(n)+h(n),
wobei g(n) = bisher angefallene Kosten bis n,
h(n) = geschätzte Kosten von n zum Ziel.
• Hier: Für Bigram-Modelle ist g(wi-1, wi) = – log P(wi | wi-1)
• Gesamte Pfadkosten K einer Wortfolge:
K(w1 … wS) = i=1
S – log P(wi | wi-1) = – log i=1
S P(wi | wi-1)
• Damit: Kürzester Pfad = wahrscheinlichste Wortfolge
• Heuristikfunktion h:
KI 15-Zeit 71
DBN für die Spracherkennung
Weitere Variable können leicht hinzugefügt werden, z.B. Akzent, Geschlecht, Alter, Geschwindigkeit.
Zweig und Russell (1998) erreichten bis 40 % Fehlerreduktion gegenüber HMMs.
Übergang
Phonem
Artikulatoren
Beobachtung
Deterministisch,fest
Stochastisch,gelernt
Deteministisch,fest
Stochastisch,gelernt
Stochastisch,gelernt
KI 15-Zeit 72
Zusammenfassung
• Seit den 70ern wird Spracherkennung als probabilistische
Inferenz formuliert.
• Evidenz = Sprachsignal
• Versteckte Variable = Lautfolgen und Wörter
• „Kontext-Effekte“ wie Koartikulation werden durch
Zustandserweiterung behandelt.
KI 15-Zeit 73
Zusammenfassung
• Standard-Ansatz: Lautmodell + Aussprachemodell ergibt Wortmodell. Wortmodelle werden mit Bigram-Sprachmodellen zu gemeinsamem HMM vereint.
• Ermittlung der wahrscheinlichten Lautfolge durch Viterbi-Algorithmus
• Wahrscheinlichste Wortfolge mit A*-Decoder
• Die kontinuierliche Erkennung von Sprache ist ein ungelöstes Problem, die größten Schwierigkeiten liegen in der Variabilität natürlicher Sprache (Dialekt, Geschwindigkeit etc. etc.) und den Hintergrundgeräuschen in natürlicher Umgebung.
