Date post: | 05-Apr-2015 |
Category: |
Documents |
Upload: | alf-hemmerling |
View: | 105 times |
Download: | 0 times |
1
PG 520 Intelligence Service – gezielte Informationen aus dem
Internet
Seminarthema: Hidden Markov Model
Von Wei CAI09.10.2007
2
Überblick
• Markov Models• Eins der Erweiterbaren Markov Models
=> Hidden Markov Model• drei klassischen Probleme • Forward und Backward-Algorithmus• Viterbi-Algorithmus• Baum-Welch-Algorithmus
3
Markov Models• Prozeß bewegt von einem Zustand zu einem anderen, der eine
Reihenfolge der Zustände erzeugt• Markoveigenschaft: Wahrscheinlichkeit jedes folgenden Zustandes
hängt nur von dem vorhergehenden Zustand ab
• Um Markov Modell zu definieren, müssen die folgenden Wahrscheinlichkeiten spezifiziert werden:
die Menge der Zustände Übergangswahrscheinlichkeiten
Anfangswahrscheinlichkeiten
4
Beispiel von Markov Model
• Zwei Zustände : ‘Regen’ and ‘Sonne’.• Übergangswahrscheinlichkeiten : P(‘Regen’|‘Regen’)=0.3 , P(‘Sonn
e’|‘Regen’)=0.7 , P(‘Regen’|‘Sonne’)=0.2, P(‘Sonne’|‘Sonne’)=0.8• Anfangswahrscheinlichkeiten : P(‘Regen’)=0.4 , P(‘Sonne’)=0.6 .
Regen Sonne
0.70.3
0.2 0.8
5
Beispiel von Markov Model
Nehmen wir an, dass wir eine Beobachtungsfolge der Zustände in unserem Beispiel errechnen möchten, {' Sonne', ,' Sonne',' Regen', Regen'}.
P({‘Sonne’,’Sonne’,’Regen’, ’Regen’}| Wetter ) =P(‘Sonne’) P(‘Sonne’|’Sonne’) P(‘Regen’|’Sonne’)
P(‘Regen’|’Regen’) = 0.6*0.8*0.2*0.3= 0.0288
6
Einführung
• Zustände Markovkette, Übergangswahrscheinlichkeiten durch stochastische Matrix beschrieben.
• Zustände selbst nicht sichtbar(d.h. „hidden“), erzeugen Beobachtungen.
Markov eigenschaft
7
Einführung
EigenschaftenSolide statistische Grundlagelernen möglichModular, d.h. Gut erweiterbar, leicht zu
verknüpfenAnwendungsgebieteBioinformatik z.B. Gen-vorhersage, neurobiologie
Datamining z.B. Named Entity Recognition
Spracherkennung, Mustererkennung
8
Definition
ein HMM als Fünftupel λ = (S,A,B,π,V) mit : die Menge der Zustände, die Zustandsvariable annehmen kann : das Ausgabealphabet, das die Beobachtungsfolge annehmen kann π : die Menge der anfangswahrscheinlichkeiten mit
Wahrscheinlichkeit, dass der Startzustand ist
9
Definition : Zustandsübergangsmatrix, wobei die Wahrscheinlichkeit angibt, dass vom Zustand zum Zustand gewechselt wird
: die Menge der Ausgabe-wahrscheinlichkeiten
Wahrscheinlichkeit im Zustand die Beobachtung k zu machen
10
Realisierung einer Beobachtungs-folgeGegeben: N, M, A, B, π ① wähle Anfangszustand entsprechend
Anfangszustandverteilung π ② Setze t = 1③ Wähle entsprechend W-keitsverteilung der
Beobachtungssymbole im Zustand , ④ Wechsle in den nächsten Zustand entsprechend
übergangswahrscheinlichkeitsverteilung für Zustand⑤ setze t = t + 1 , wiederhole Schritt 3, falls t < T, sonst endet dies
Verfahren
11
Beispiel von HMM
niedrig hoch
0.70.3
0.2 0.8
0.60.4 0.4
0.6
SonneRegen
12
Beispiel von HMM • Zwei Zustände : ‘niedrig’ oder ‘hoch’ Luftdruck• Zwei Beobachtungen : ‘Regen’ and ‘Sonne’• Übergangswahrscheinlichkeiten : P(‘niedrig’|‘niedri
g’)=0.3 , P(‘hoch’|‘niedrig’)=0.7 , P(‘niedrig’|‘hoch’)=0.2, P(‘hoch’|‘hoch’)=0.8
• Ausgabewahrscheinlichkeiten : P(‘Regen’|‘niedrig’)=0.6 , P(‘Sonne’|‘niedrig’)=0.4 , P(‘Regen’|‘hoch’)=0.4 , P(‘Sonne’|‘hoch’)=0.3
• anfangswahrscheinlichkeiten : P(‘niedrig’)=0.4 , P(‘hoch’)=0.6
13
Beispiel von HMM Nehmen wir alle mögliche Sequenze der verstec
kten Zustände an: P({‘Sonne’,’Regen’} ) = P({‘Sonne’,’Regen’} , {‘ni
edrig’,’niedrig’}) + P({‘Sonne’,’Regen’} , {‘niedrig’,’hoch’}) + P({‘Sonne’,’Regen’} , {‘hoch’,’niedrig’}) + P({‘Sonne’,’Regen’} , {‘hoch’,’hoch’})
Im ersten TermP({‘Sonne’,’Regen’} , {‘niedrig’,’niedrig’})= P({‘Sonne’,’Regen’} | {‘niedrig’,’niedrig’}) P({‘niedrig’,’niedrig’}) = P(‘Sonne’|’niedrig’)P(‘Regen’|’niedrig’) P(‘niedrig’)P(‘niedrig’|’niedrig’)= 0.4*0.6*0.4*0.3 = 0.01152
14
Problemstellungen
1. gegeben Modellλ = (A,B,π) soll die wahrschlichkeit einer speziellen Ausgabesequenz bestimmt werden.
2. gegeben Modellλ = (A,B,π) soll die wahrscheinlichste Sequenz der versteckten Zustände bestimmt werden, die eine vorgegebene Ausgabesequenz erzeugt hat.
3. gegeben eine Beobachtungsfolge sollen die Übergangs/Ausgabe-Wahrscheinlichkeiten des HMM bestimmt werden, durch die am wahrscheinlichsten die Ausgabesequenz erzeugt wird. => Named Entity Recognition
15
Evaluationsproblem
nutzt Forward-Backward Algorithms für effiziente Berechnung
Die Forward-Variable , d.h. die Wahrscheinlichkeit zum Zeitpunkt t bei gegebener Beobachtung im Zustand zu sein, ist
Die Forward-Variable wird zusammen mit der Backward-Variable für den Baum-Welch-Algorithmus zur Lösung des mit HMM gegebenen Lernproblems benötigt.
16
Matrix von einem HMM o1 ot ot+1 oT = Beobachtungen
t = 1 t t+1 T
s1
s2
si
sN
s1
s2
si
sN
a2j
a1j
aij
aNj
s1
s2
sj
sN
s1
s2
si
sN
17
Forward Rekursion
Initialisierung
Induktion
Terminierung
18
Backward Rekursion
Initialisierung
Induktion
Terminierung
19
Decodierungsproblem
Gesucht: optimale Zustandsfolge an der Beobachtungsfolge anpäßt, dann Anzahl der Korrekten Zustände maximieren
Mit dem Viterbi-Algorithmus lösbar
20
Viterbi-Algorithmus
s1
si
sN
sjaij
aNj
a1j
q t-1 qt
•Idee war, wenn optimalen Weg im qt= sj endet und über qt-1= si durchgegangen ist, soll die Zustandsfolge dann auch mit dem optimalen Weg im qt-1= si zum Schluss sein können.
•Induktion:
21
Viterbi-Algorithmus• Initialisierung
•Induktion
•Terminierung: optimaler Weg zum Zeitpunkt T endet
• Zustandsfolge zurückverfolgen.
22
Lernproblem
• Zu gegebener endlicher Beobachtungssequenz gibt es keinen optimalen Weg, die Modellparametern abzuschätzen.
• hier nutzt expectation-maximization Algorithmus(Baum-Welch-Algorithmus), dadurch local maximum von P(O | M) gefunden werden kann.
23
Baum-Welch-Algorithmus
• Methode zur Bestimmung neuer Parameter eines HMM
24
Baum-Welch-Algorithmus(E1)•Im Zustand si zum Zeitpunkt t und im Zustand sj zum Zeitpunk
t t+1, die Beobachtungsfolge o1, o2, ..., ot .
t(i,j)= P(qt= si , qt+1= sj | o1 o2 ... oT)
P(qt= si , qt+1= sj , o1 o2 ... oT) P(o1 o2 ... oT)
t(i,j)= =
P(qt= si , o1 o2 ... oT) aij bj (ot+1 ) P(ot+2 ... oT | qt+1= sj ) P(o1 o2 ... ok)
t(i) aij bj (ot+1 ) t+1(j)
i j t(i) aij bj (ot+1 ) t+1(j)
25
Baum-Welch-Algorithmus(E2)• Definiert Variable t(i) als die W-keit im Zustand si zum Zeitp
unkt t, die Beobachtungsfolge o1 o2 ... ot .
t(i)= P(qt= si | o1, o2, ... ot)
t(i)=P(qt= si , o1 o2 ... ot) P(o1 o2 ... ot)
= t(i) t(i)
i t(i) t(i)
26
Baum-Welch-Algorithmus(E3)•berechnet t(i,j) = P(qt= si , qt+1= sj | o1 o2 ... oT) und t(i)= P(qk= si | o1 o2 ... oT)
• erwarteter Wert der Übergange von Zustand si nach Zustand sj
= t t(i,j)
• erwarteter Wert der Übergänge ausserhalb des Zustands si = t t(i)
• erwarteter Wert des vm im Zustand si = t t(i) , also ot= vm
• erwartete Anfangswahrscheinlichkeit im Zustand si zum Zeitpunt t=1: 1(i) .
27
Baum-Welch-Algorithmus(Max)
aij =k k(i,j)
k k(i)
bi(vm ) = k k(i,j)
k,ok= vm k(i)
i = (im Zustand si zum Zeitpunkt t=1) = 1(i).