Zeitreihenanalyse mit Hidden Markov Modellen€¦ · Andrei Andreyevich Markov * 14. Juni 1856 † 20 . Juli 1922 Professor in Sankt Petersbur g für Theorie der stochastischen Pr

Elektrotechnik und Informationstechnik Institut für Automatisierungstechnik, Professur Prozessleittechnik

Zeitreihenanalyse mit Zeitreihenanalyse mit Hidden Markov Modellen

(nach http://www.cs.cmu.edu/~awm/tutorials)

VL PLT2Professur für Prozessleittechnik

Übersicht

• Wiederholung Markov ModelleModellierungsansatz & Markov Eigenschaft– Modellierungsansatz & Markov Eigenschaft

• Beispiel: „Robot-Human-Spiel“– Typische Fragestellungen an ein Markov Modell– Einführung Dynamic Programming

• Hidden Markov ModelleModellierungsansatz– Modellierungsansatz

– 3 Problemstellungen

• Schätzen: Backward-Forward Verfahren

• Suchen: Viterbi Pfade

• Lernen: Baum-Welch Verfahren

13.06.2012 PLT2 (c) 2009-2012, Urbas, Pfeffer, Krause Folie 2

Andrei Andreyevich Markov

* 14. Juni 1856† 20 Juli 1922† 20. Juli 1922

Professor in Sankt Petersburg gfür

Theorie der stochastischen Prozesseo esse

Leonard E. Baum:

1960er erste Veröffentlichung über Hidden Markov Modelle. Entwickelt für die S h k


Spracherkennung


Wiederholung Markov Modelle

Wiederholung Markov Modelle

• Ein System habe– N Zustände s1, s2, …, sn

– Zeitschritte t=1, t=2,…

• Im Zeitschritt t ist das System in genau • Im Zeitschritt t ist das System in genau einem Zustand qt {s1, s2, …, sn }

• Zu jedem Zeitschritt wird der nächste • Zu jedem Zeitschritt wird der nächste Zustand zufällig „gewählt“

• Die Wahrscheinlichkeitsverteilung für den • Die Wahrscheinlichkeitsverteilung für den nächsten Zustand wird nur vom aktuellen Zustand bestimmt (und nicht vom Weg dahin)


Beispiel Markov Modelles

• 3 Zustände s1, s2, s3• Übergangswahrscheinlichkeiten aus s1

s1

1/2

1/3

Übergangswahrscheinlichkeiten aus s1– P(qt+1=s1|qt=s1)=0– P(qt+1=s2|qt=s1)=0– P(qt+1=s3|qt=s1)=1

s2

1

1/2

P(qt+1 s3|qt s1) 1• Übergangswahrscheinlichkeiten aus s2

– P(qt+1=s1|qt=s2)=1/2– P(q 1=s2|q =s2)=1/2 s

12/3

P(qt+1 s2|qt s2) 1/2– P(qt+1=s3|qt=s2)=0

• Übergangswahrscheinlichkeiten aus s3– P(q =s |q =s )=1/3

s3

100– P(qt+1=s1|qt=s3)=1/3

– P(qt+1=s2|qt=s3)=2/3– P(qt+1=s3|qt=s3)=0

0323102121100

=A


03231

Markov Eigenschafts

• qt+1 ist bei gegebenem qt bedingt

s1

1/2

1/3

unabhängig* von den vorher eingenommenen Zuständen{ }

s2

1

1/2

{qt-1, qt-2,…,q1}• Formal

P(q s |q s ) P(q s |q s beliebiger Weg nach s ) s

12/3

P(qt+1=sj|qt=si) = P(qt+1=sj|qt=si, beliebiger Weg nach si)

* a und b sind bedingt unabhängig bei gegebenem c

s3

a und b sind bedingt unabhängig bei gegebenem c wenn giltDiese Aussage ist äquivalent caP=cbaP |,|

cbPcaPcbaP |||,



Beispiel Robot-Human-Spielp p

Beispiel von A. Moore(http://www.cs.cmu.edu/~awm/tutorials)(http://www.cs.cmu.edu/ awm/tutorials)

• Ein Roboter (R) und ein Mensch (H) bewegen i h fälli f i S i lf ld it 18 sich zufällig auf einem Spielfeld mit 18

Feldern.• Der Systemzustand sei definiert als das Tupel• Der Systemzustand sei definiert als das Tupel

<Feld R, Feld H> 18*18=324 Zustände!z.B. <4,8>z.B. <4,8>

• In jedem Zeitschrittbewegen sich R und Hgauf ein benachbartesFeld.


Typische Fragen

1.Wie lange dauert es durchschnittlich bis R d H k llidi ?und H kollidieren?

2.Wie groß ist die Wahrscheinlichkeit dass R gegen die linke Wand rennt bevor er mit H gegen die linke Wand rennt, bevor er mit H zusammenstößt?

3 Wie wahrscheinlich3.Wie wahrscheinlichist es, dass H und R imnächsten Schritt zusammenstoßen?


Kollisionswahrscheinlichkeit im nächsten SchrittSchritt• Geg.: Aktuelle Zeit = t, H lebt noch• Ges : Wahrscheinlichkeit dass H im nächsten • Ges.: Wahrscheinlichkeit, dass H im nächsten

Schritt platt ist?• R ist blindR ist blind

– Berechenbar -> Thema der nächsten Folien

• R ist allwissend– R kennt Zustand, direkt berechenbar

• R mit Sensoren aberunvollständiger Information

– Hidden Markov Modell!


Wahrscheinlichkeit des Zustands qt = sj

• Es gibt viele Pfade Q = q1q2q3…qt zu einem Zustand q =sZustand qt sj

• Wie kann ein bestimmtes P(Q) berechnet werden?

– Wir kennen den Startzustand q1, d.h. P(q1)=1– Es gilt: P(q1q2q3…qt) = P(q1q2q3…qt-1)P(qt|q1q2q3…qt-1)

= P(q q q q )P(q |q )= P(q1q2q3…qt-1)P(qt|qt-1)= P(q1)P(q2|q1)P(q3|q2)…P(qt|qt-1)

• Naiver Ansatz: Summiere Wahrscheinlichkeit aller Wege Q* mit der Länge t, die in sj enden

– P(qt = sj|q1) = ΣQ* P(Q*)A f and e ponentiell in t O(Nt) ngeeignet!


– Aufwand exponentiell in t, O(Nt) ungeeignet!

Einfach ist zu teuer! Geht das besser?

• Zerlegung in leichter lösbare Teilprobleme D i P iDynamic Programming

• Definiere für jeden Zustand si(i) WS d S t Z it i i t d h – pt(i) : WS, dass System zur Zeit t in si ist, d.h.

– pt(i) = P(qt = si)

• Rekursiver Ansatz zur Berechnung von p (i)• Rekursiver Ansatz zur Berechnung von pt(i)

?)P((j)j?=(i)pi 1

?=)s=P(q=(j)pj j+t+t 11


Berechnung P(qt = s)

ndStartzusta für11 =s=(i)pi i

sonst0

)s=P(q=(j)pj

1

2

)s=qs=P(q=

)s=P(q=(j)pj

itj+t

j+t+t

1

11

,

(i)pa=

)s=)P(qs=q|s=P(q=

tij

ititj+t 1

Nis=q|s=qP=a itj+tij und mit 1

• Aufwand für alle Zustände s : O(t N²) !

(i)pa tij Nisq|sqPa itj+tij und mit 1


( )

HR-Spiel, reduziertes 2x2 Spielfeld

• 4*4=16 ZuständeKodie e Z stand als <F F >

H

1 2

Gilt nur für blinde – Kodiere Zustand si als <FH,FR>– FH: Feld auf dem H ist– FR: Feld auf dem R ist

R3 4

(=zufällige) Züge!

R

• Übergangswahrscheinlichkeitenfür FH(si)=FH(sj) v FR(si)=FR(sj)

P( | ) 0

11 12 13 14

21 22 23 24aij=P(qt+1=sj|qt=si) = 0 sonstaij=P(qt+1=sj|qt=si) = 1/9

21 22 23 24

31 32 3433

ij t 1 j t i

• Berechnungsbeispiel– PIV_MM-2x2HRSpiel.xls

41 42 43 44

Mögliche Zustandsübergänge


g g gnach <2,2>

Kollisionswahrscheinlichkeit im nächsten Schritt mit SensorinformationenSchritt mit Sensorinformationen

• Geg.: Aktuelle Zeit = t, H lebt noch• Ges.: Wahrscheinlichkeit, dass H im nächsten

Schritt platt ist?bl d• R ist blind

• R ist allwissendk d d k b h b– R kennt Zustand, direkt berechenbar

• R mit Sensoren aberunvollständiger Infounvollständiger Info

– Hidden Markov Modell!


Versteckte Zustände

• Bislang: Schätzung von P(qt=sj) ohne BeobachtungA h B b ht fü b di d • Annahme: Beobachtung verfügbar, die von dem wahren Zustand beeinflusst wird.

• Beispiel HR-Spiel:p p– Umgebungssensor für 8 umgebende Felder– Beispiel (W=Wand)


Sensor + Rauschen• Umgebungssensor ist nicht perfekt

– Messrauschen, Fehlklassifikation, …

• Annahmen• Annahmen– Beobachtung Ot wird nur von Systemzustand qt +

Zufallskomponente bestimmt– Ot sei bedingt unabhängig von {qt 1,..q1,Ot 1,..O1} bei gegebenem qtOt sei bedingt unabhängig von {qt-1,..q1,Ot-1,..O1} bei gegebenem qt

– bi (k)=P(Ot=k|qt=si) = P(Ot=k|qt=si, beliebiger Weg nach si)

+Fehler13.06.2012 PLT2 (c) 2009-2012, Urbas, Pfeffer, Krause Folie 18

= +Fehler


Hidden Markov Modelle

Modellierungsansatz

Einsatz von HMMs

• Roboterplanung & -sensorik unter U i h h itUnsicherheit

• Spracherkennungk• Gestenerkennung

• Nutzer- und Entscheidungsmodellierung• Gensequenzierung• Marktmodelle• Fehlermodelle in der Prozessautomatisierung• …


Formale Definition des HMM

• Ein HMM ist ein 5-Tupel aus– N Anzahl der Zustände– M Anzahl der möglichen Beobachtungen

{π π } Anfangsws π = P(q = s )– {π1… πn} Anfangsws. πi = P(q1= si)– aij Matrix der Zustandsübergangsws.

aij = P(qt+1= sj|qt=si) i,j[1…N]j j

– bi(k) Matrix der Beobachtungsws.bi(k) = P(Ot= k|qt=si) i[1…N], k[1…M]


Hidden Markov Modell (1/2) (Rabiner 1989) http://ieeexplore.ieee.org/iel5/5/698/00018626.pdf?arnumber=18626http://ieeexplore.ieee.org/iel5/5/698/00018626.pdf?arnumber 18626

• Spezifikation eines HMM

– λ = <N,M,{πi},{aij},{bi(k)}>– Andere Notation: λ = (π,A,B)

• N: Anzahl der Zustände s1, s2, …, sN

• M: Anzahl der Beobachtungen 1…M: Initialverteilung• π: Initialverteilung

• A: Zustandsübergangsmatrix• B: Zustands-Symbolmatrix• B: Zustands Symbolmatrix


Hidden Markov Modell (2/2) (Rabiner 1989)http://ieeexplore.ieee.org/iel5/5/698/00018626.pdf?arnumber=18626http://ieeexplore.ieee.org/iel5/5/698/00018626.pdf?arnumber 18626

• T: Länge der Beobachtungssequenz • O: Sequenz der Beobachtungen

– O = O1 O2 O3 … OT

• Q: Pfad durch die Zustände– Q = q1 q2 q3 … qT


Beispiel für ein HMM

• Das Modell startet zufällig im Zustand s oder sim Zustand s1 oder s2

• In jedem Zustand wird zufällig eines der eingezeichneten Symbole X, Y, Z ausgegeben

23

31 33

21

31


Beispiel Beobachtung (1/3)

• Gegeben: Q=s1s3s3, O=X X Z• Gesucht: Wie hoch ist P(O)?

– P(O1O2O3) = P(O1=X Λ O2=X Λ O3=Z)Di kt (l ) A t– Direkter (langsamer) Ansatz

Summiere über alle Pfade Q der Länge 3:P(O) = ΣQ P(OΛ Q) = Σ P(O|Q) P(Q)( ) Q ( Q) ( |Q) (Q)

• wir brauchen– P(Q) für einen beliebigen Pfad Q– P(O|Q) für einen beliebigen Pfad Q



• Berechnung P(Q) für einen beliebigen Pfad QP(Q) = P(q1,q2,q3)

= P(q2,q3|q1) P(q1)= P(q3|q2) P(q2|q1) P(q1)(q3|q2) (q2|q1) (q1)= P(q1) P(q2|q1) P(q3|q2)

• Beispiel Q=s1s3s3 : P(Q) = P(q1=s1)P(q2=s3|q1=s1)P(q3=s3|q2=s3)

* *= π1 * a13 * a23

= 1/2 * 2/3 * 1/3 = 1/9



• Berechnung P(O|Q) für einen Pfad QP(O1O2O3 | q1,q2,q3) = P(O1|q1) P(O2|q2) P(O3|q3)

• Beispiel Q=s s s : • Beispiel Q=s1s3s3 : P(X|q1=s1) P(X|q2=s3) P(Z|q3=s3) = 1/2 * 1/2 * 1/2 = 1/8

• P(O) = ΣQ P(O Λ Q) = Σ P(O|Q) P(Q)– 27 (NT) Berechnungen von P(Q) und P(O|Q)– Bei 20 Beobachtungen: je 3.5 Mrd Berechnungen

von P(Q) und P(O|Q)! Zu aufwändig! D P Ansatz?


– Zu aufwändig! D.P.-Ansatz?


Hidden Markov Modelle

Typische Fragestellungen

Hidden Markov Modell (HMM)

• Typische Fragen an HMM bei gegebenen B b ht O O O OBeobachtungen O1O2O3…Ot

– Zustand: In welchem Zustand sind wir jetzt?P(q =s |O O O O ) Forward-Backward-AlgorithmusP(qt=si|O1O2O3…Ot), Forward Backward Algorithmus

– Pfad: Welcher Weg wurde wahrscheinlich eingeschlagen?

Q* = argmaxQ P(Q|O), Viterbi-Algorithmus

– Lernen von HMMs: Wie sieht ein HMM λ aus, das diese Beobachtungen generiert haben könntediese Beobachtungen generiert haben könnteλ* = argmaxλ P(λ|O), Baum-Welch-Algorithmus


Frage 1: Aktueller Zustand P(qt=si|O)

• Geg.: Beobachtungen O1O2O3 … OT

G Z t d • Ges.: Zustand qt

• Definiere αt(i) als die WS, dassdas durch λ spezifizierte Hidden Markov Modell – das durch λ spezifizierte Hidden Markov Modell zum Zeitpunkt t im Zustand si ist,

UND– auf einem zufälligen Pfad dorthin t Beobachtungen

O1O2 … Ot ausgegeben wurden

αt(i) = P(O1O2O3 … Ot ∧ qt = si|λ); 1 ≤ t ≤ Tαt(i) P(O1O2O3 … Ot ∧ qt si|λ); 1 ≤ t ≤ T• Rekursive Definition von αt(i):α1(i), αt+1(j)


1( ), t+1(j)

Rekursive Definition von αt(i)

α1(i) = P(O1 ∧ q1 = si) P( ) P(O | )= P(q1 = si) P(O1 | q1 = si)

= πi bi(O1) (j) P(O O O O ∧ q s )αt+1(j) = P(O1O2…OtOt+1 ∧ qt+1=sj)

= Σi=1,N P(O1O2…Ot ∧ qt=si ∧Ot+1 ∧ qt+1=sj)= Σ P(O q =s |O O O ∧ q =s ) = Σi=1,N P(Ot+1,qt+1=sj|O1O2…Ot ∧ qt=si) P(O1O2…Ot ∧ qt=si)= Σi=1 N P(Ot+1,qt+1=sj|qt=si) αt(i)i=1,N ( t+1,qt+1 j|qt i) t( )= Σi=1,N P(qt+1=sj|qt=si) P(Ot+1|qt+1=sj) αt(i)= Σi=1,N aij bj(Ot+1) αt(i)


i 1,N ij j t+1 t

Beispiel

αt(i) = P(O1O2…Ot∧qt = si|λ) (i) b (O ) α1(i) = bi(O1) πi

αt+1(j) = Σ aij bj(Ot+1) αt(i)23

31 33

21

• Gegeben: O=X X Z

α1(1)=1/4 α1(2)=0 α1(3)=0α2(1)=0 α2(2)=0 α2(3)=1/12α3(1)=0 α3(2)=1/72 α3(3)=?


Übergang zu P(qt=si|O1O2O3 … Ot) ?

αt(i) = P(O1O2O3 … Ot Λ qt = Si|λ)

P(O1O2…Ot) = Σi=1,N αt(i)

P(qt=Si|O1O2…Ot) = αt(i) / Σj=1,N αt(j)


Frage 2: Wahrscheinlichster Pfad Q|O

• Gegeben: Beobachtungen O1O2O3 … OT

G ht W h h i li h t Pf d Q• Gesucht: Wahrscheinlichster Pfad Q– argmaxQ P(Q| O1O2O3 … OT)

• Direkter Weg wieder zu aufwändig:argmaxQ P(Q|O1O2O3 … OT) = g Q (Q| 1 2 3 T)argmaxQ P(O1O2O3 … OT|Q)P(Q) / P(O1O2O3 … OT) =argmaxQ P(O1O2O3 … OT|Q)P(Q)

• Das geht besser!


Partiell beste Pfade im Trellisdiagramm

• Für jeden Zustand qt=si gibt es einen h h i li h t Pf d

state

wahrscheinlichsten Pfad

X

t


X X Z

Partielle beste Pfade

• Unterschied zu Forward-Algorithmus W h h i li hk it d EINEN h h i li h t

state

Wahrscheinlichkeit des EINEN wahrscheinlichsten Pfades zum Zustand

X t13.06.2012 PLT2 (c) 2009-2012, Urbas, Pfeffer, Krause Folie 36

X X Zt

Partieller bester Pfad

• δt(i)= max P(q1q2...qt-1 Λ qt = Si Λ O1...Ot)q1 qt-1q1…qt 1

• WS des Pfades q1q2 qt 1 der Länge t-1 mit • WS des Pfades q1q2..qt-1 der Länge t 1 mit der größten Chance folgende Bedingungen zu erfüllen:

– Pfad Q ist möglich q1q2...qt-1

UND– endet zum Zeitpunkt t in Si qt=Siendet zum Zeitpunkt t in Si qt Si

UND– produziert O O1...Ot


Ansatz

• δt(i)= max P(q1q2...qt-1 Λ qt = Si Λ O1...Ot)q1 qt-1q1…qt 1

• WS des Pfades q1q2..qt-1 der Länge t-1 mit der größten Chance folgende Bedingungen zu g g g gerfüllen:

– Pfad Q ist möglich q1q2...qt-1

UNDUND– endet zum Zeitpunkt t in Si qt=Si

UND– produziert O O1...Ot

• Def: mppt(i) = dieser Pfad, δt(i)=P(mppt(i))


VITERBI Algorithmus

• δt(i)= max P(q1..qt-1 Λ qt=Si Λ O1...Ot)q1 qt-1q1…qt 1

• mppt(i)= argmax P(q1..qt-1 Λ qt=Si Λ O1...Ot)q1…qt-1

• Start: t=1– δ1(i)= max P(q1=Si Λ O1)

q1q1

= P(q1=Si)P(O1|q1=Si) = πi bi(O1)i i( 1)

Angenommen, wir kennen δt(i) und mppt(i)Wie kommen wir zu δt+1(i) und mppt+1(i) ?


VITERBI Algorithmus

• t > 1– Angenommen, wir kennen δt(i) und mppt(i)– Wie kommen wir zu δt+1(i) und mppt+1(i) ?

Der WSste Pfad • Der WSste Pfad – dessen letzten beiden Zustände Si und Sj sind istist– Der WSste Pfad zu Si, gefolgt von einem Übergang

von Si nach Sj

• δt(i) P(SiSj Λ Ot+1) = δt(i)aijbj(Ot+1)• δt+1(j) = maxi(δt(i)aijbj(Ot+1))


Backpointer

• Wir kennen die partiellen WS δt(i) • Wir brauchen den WSten Pfad, d.h. wir

müssen uns die δt(i) merken

state

t13.06.2012 PLT2 (c) 2009-2012, Urbas, Pfeffer, Krause Folie 41

X X Z t

Backpointer

• Wir kennen die partiellen WS δt(i) • Wir brauchen den WSten Pfad, d.h. wir

müssen uns die δt(i) merkenh f d d• Es reicht für jeden Zustand ein

Rückwärtszeiger (Backpointer Ф) aufzuheben von dem wir am besten hier aufzuheben, von dem wir am besten hier angelangt sind

• Фt(i) = argmaxj(δt 1(j)aji)• Фt(i) = argmaxj(δt-1(j)aji)


3. Frage: Modelllernen

• Geg.: OT, N, MA t D fi i• Ansatz: Definiere

– γt(i) = P(qt=si | O1O2…OT , λ )– εt(i,j) = P(qt = si Λ qt+1 = sj | O1O2…OT ,λ )t( ,j) (qt i qt+1 j | 1 2 T , )– γt(i) and εt(i,j) können i,j,t effizient berechnet werden

• SuchverfahrenB h WS i i hä M d ll i i – Berechne WS mit einem geschätzten Modell in einen Zustand zu gelangen, bewerte die Übereinstimmung mit den Beobachtungen, verändere anschließend die M d ll tModellparameter

• Details Rabiner (1989)


Zusammenfassung der Problemstellungen

• Evaluation (Auswertung, Schätzen)– Gegeben ist ein HMM λ und eine Beobachtungssequenz OT.T– Berechne die Wahrscheinlichkeit, dass OT von λ erzeugt

wurde.

• Decoding (Entschlüsseln Suchen)• Decoding (Entschlüsseln, Suchen)– Gegeben ist ein HMM λ und eine Beobachtungssequenz OT.– Berechne die Folge von verborgenen Zuständen, die OT

it d hö h t W h h i li hk it t h tmit der höchsten Wahrscheinlichkeit erzeugt hat.

• Learning (Lernen)– Für ein HMM λ ist die Zahl der sichtbaren und

unsichtbaren Zustände bekannt, sowie ein oder mehrere Beobachtungssequenzen (Trainingssequenzen).

– Berechne die Parameter aij und bj(k).


Berechne die Parameter aij und bj(k).

Literatur & Bibliotheken

• Literatur– Rabiner (1989) A Tutorial on Hidden Markov Models and Selected

A li ti i S h R iti P f th IEEE V l 77 N 2 Applications in Speech Recognition, Proc. of the IEEE, Vol.77, No.2, pp.257--286, 1989.http://ieeexplore.ieee.org/iel5/5/698/00018626.pdf?arnumber=18626

– Moore, A. (o.J.) Hidden Markov Models. http://www.cs.cmu.edu/~awm/tutorials

– Boyle, R. (o.J.) Hidden Markov Models.http://www.comp.leeds.ac.uk/roger/HiddenMarkovModels/html_dev/main.html

– Fraser, A. (2008) HMM & Dynamical Systems. SIAM

• Bibliotheken– MATLAB: http://people.cs.ubc.ca/~murphyk/Software/HMM/hmm.htmlp //p p / p y / / /– R: http://cran.r-project.org/web/packages/HMM/index.html– Gestenerkennung GT2K: http://gt2k.cc.gatech.edu/


13.06.2012 PLT2 (c) 2009-2012, Urbas, Pfeffer, Krause 46

Documents

Zeitreihenanalyse mit Hidden Markov Modellen€¦ · Andrei Andreyevich Markov * 14. Juni 1856 † 20 . Juli 1922 Professor in Sankt Petersbur g für Theorie der stochastischen Pr