View
7
Download
0
Category
Preview:
Citation preview
11.05.2002 1Karin Haenelt, Viterbi-Algorithmus
Der Viterbi-Algorithmus im Part-of-Speech Tagging
Kursfolien
Karin Haenelt
Letzte Änderung 18.07.2002
11.05.2002 2Karin Haenelt, Viterbi-Algorithmus
Zweck
Finden der besten Pfadsequenzder verborgenen Zuständein einem Hidden Markov Modelzu einer gegebenen Beobachtung
11.05.2002 3Karin Haenelt, Viterbi-Algorithmus
Beispielanwendungen
• Sprachverarbeitung– Part-of-Speech Tagging– Worterkennung
– …
• Kryptographie
• …
11.05.2002 4Karin Haenelt, Viterbi-Algorithmus
SjiaA ij ∈= ,,
Hidden Markov Model
Formal spezifiziert durch Fünf-Tupel
Menge der Zustände
Ausgabe-Alphabet
Wahrscheinlichkeitender Startzustände
Wahrscheinlichkeitender Zustandsübergänge
Wahrscheinlichkeitender Symbolemissionen
Manning/Schütze, 2000: 326
( )BAKS ,,,, Π
Sii ∈=Π ,π
,..., 1 NssS =,...,1,..., 1 MkkK M ==
KkSjibB ijk ∈∈= ,,,
11
=∑=
N
j
ija
11
=∑=
M
k
ijkb
11.05.2002 5Karin Haenelt, Viterbi-Algorithmus
HMM [Aufgabe]:Beste Pfadsequenz finden
gegeben eine Sequenz von Beobachtungen
ein Modell
AdjeAuxV KopVNomn Part g‘schicktwerden wir
AuxVKopVNomnPart
Adje.1 .1 .4 .2 .2 0 0.2 .3.2 .2 .2 .2 0 .3 0.2 .2.2 .2 .3 .1 0 .5 0.2 .1.4 .3 .1 .1 0 0 .2.1 .3.1 .2 .1 .3 .4 0 0.3 .1
O=(wir,werden,geschickt)
gesucht die wahrscheinlichste Pfadsequenz
π),,( Π= BAµ
),...,( 1 TooO =
)|(maxarg µOPx)|,,( µgeschicktwerdenwirP
11.05.2002 6Karin Haenelt, Viterbi-Algorithmus
HMM [Aufgabe]:Beste Pfadsequenz finden
Modellvariante: mit Startsymbol
statt mit Tabelle der Startwahrscheinlichkeiten)
AdjeAuxV KopVNomn Part g‘schicktwerden wir
AuxVKopVNomnPart
Adje.1 .1 .4 .2 .2 0 0.2.2 .2 .2 .2 0 .3 0.2.2 .2 .3 .1 0 .5 0.2.4 .3 .1 .1 0 0 .2.1.1 .2 .1 .3 .4 0 0.3.2 .1 .3 .1 0 0 0.3
.000001
000000Ω
Ω
11.05.2002 7Karin Haenelt, Viterbi-Algorithmus
Ineffiziente Lösung1 wir | Adje werden | Adje geschickt | Adje2 geschickt | AuxV3 geschickt | KopV4 geschickt | Nom5 geschickt | Part6 werden | AuxV geschickt | Adje7 geschickt | AuxV.. ….. … … …85 wir | Nomn werden | AuxV geschickt | Part86 wir | Nomn werden | KopV geschickt | Adje.. …125 wir | Part werden | Part geschickt | Part
Für 3 Beobachtungen und 5 Kategorien 53 Schritte
→Ω → →
→
→→
→
→→
→
11.05.2002 8Karin Haenelt, Viterbi-Algorithmus
Beispiel
ineffiziente Suche der besten Lösung
.3 x .2 x .3 x .5 x .2 x .2 =0.000360
.3 x .2 x .4 x .3 x .2 x .4 =0.000576
=0.0
=0.0
P(Adje Adje Adje | wir,werden,geschickt, μ)P(Adje Adje AuxV | wir,werden,geschickt, μ)…P(Nomn AuxV Part | wir,werden,geschickt, μ)…P(Nomn KopV Adje | wir,werden,geschickt, μ)…P(Part Part Part | wir,werden,geschickt, μ)
11.05.2002 9Karin Haenelt, Viterbi-Algorithmus
Viterbi-Lösung
wir|Adje
wir|Nomn
wir|AuxV
wir|KopV
wir|Part
werden|Adje
werden|Nomn
werden|AuxV
werden|KopV
werden|Part
geschickt|Adje
geschickt|Nomn
geschickt|AuxV
geschickt|KopV
geschickt|Part
• Kompakte Darstellung der Pfade als Gitter (Trellis)• Wiederverwendung partieller Ergebnisse statt
Neuberechnung• Speichert für jeden Zeitpunkt t
– die Wahrscheinlichkeit des wahrscheinlichsten Pfades, der zu einem Knoten führt
– den Vorgängerknoten auf diesem Pfad
Ω|.
11.05.2002 10Karin Haenelt, Viterbi-Algorithmus
Daten 1: Wahrscheinlichkeit des wahrscheinlichsten Pfades
wir|Nomn
werden|Adje
werden|Nomn
werden|AuxVwerden|KopV
werden|Part0.06
geschickt|Adje
geschickt|Nomn
geschickt|AuxVgeschickt|KopV
geschickt|Part
00.00720.00900
0.0003600000.000576
wir|KopV 0
wir|Part 0
wir|AuxV 0wir|Adje 0
wir|Nomn Knoten
>0 Wahrscheinlichkeit des wahrscheinlichsten Pfades
0 unwahrscheinlicher Pfad
Ω|.
11.05.2002 11Karin Haenelt, Viterbi-Algorithmus
Daten 2: Vorgängerknoten auf wahrscheinlichstem Pfad
wir|Nomn
werden|Adje
werden|Nomn
werden|AuxVwerden|KopV
werden|Part
geschickt|Adje
geschickt|Nomn
geschickt|AuxVgeschickt|KopV
geschickt|Part
0NomnNomn00
KopV000AuxV
wir|KopV 0
wir|Part 0
wir|AuxV 0wir|Adje 0
wir|Nomn Knoten
Vorgänger-Knoten auf wahrscheinlichstem Pfad
0 Vorgänger-Knoten auf wahrscheinlichstem Pfadbei P(Xi) = 0 (= unwahrscheinlicher Pfad)
Ω|.
Ω
Ω
11.05.2002 12Karin Haenelt, Viterbi-Algorithmus
Daten 1 und 2:Übersicht
wir|Nomn
werden|Adje
werden|Nomn
werden|AuxVwerden|KopV
werden|Part0.06
geschickt|Adje
geschickt|Nomn
geschickt|AuxVgeschickt|KopV
geschickt|Part
00.00720.00900
0.0003600000.000576
wir|Nomn
werden|Adje
werden|Nomn
werden|AuxVwerden|KopV
werden|Part
geschickt|Adje
geschickt|Nomn
geschickt|AuxVgeschickt|KopV
geschickt|Part
0NomnNomn00
KopV000AuxV
wir|KopV 0
wir|Part 0
wir|AuxV 0wir|Adje 0
wir|KopV 0
wir|Part 0
wir|AuxV 0wir|Adje 0
Ω|.
Ω|.Ω
11.05.2002 13Karin Haenelt, Viterbi-Algorithmus
Tracing (1): Initialisierung
Setzen der Startknoten für Verfolgung - Wahrscheinlichkeit der wahrscheinlichsten Pfade- Vorgängerknoten auf den wahrscheinlichsten Pfaden
Ω|.
Ω|.
11.05.2002 14Karin Haenelt, Viterbi-Algorithmus
Tracing (2): 1. Iteration
wir|Nomn0.06
wir|Nomn
wir|KopV 0
wir|Part 0
wir|AuxV 0wir|Adje 0
wir|KopV 0
wir|Part 0
wir|AuxV 0wir|Adje 0
Berechnung der Wahrscheinlichkeit des wahrscheinlichsten Pfades
Ermittlung des Vorgängerknotens auf dem wahrscheinlichsten Pfad
Ω|.
Ω|.
δFunktion
ψFunktion
Ω
11.05.2002 15Karin Haenelt, Viterbi-Algorithmus
Tracing (3): 2. Iteration
wir|Nomn
werden|Adje
werden|Nomn
werden|AuxVwerden|KopV
werden|Part0.06
00.00720.00900
wir|Nomn
werden|Adje
werden|Nomn
werden|AuxVwerden|KopV
werden|Part
0NomnNomn00
Ω|.
Ω|.Ω
11.05.2002 16Karin Haenelt, Viterbi-Algorithmus
Tracing (4): 3. Iteration
wir|Nomn
werden|Adje
werden|Nomn
werden|AuxVwerden|KopV
werden|Part0.06
geschickt|Adje
geschickt|Nomn
geschickt|AuxVgeschickt|KopV
geschickt|Part
00.00720.00900
0.0003600000.000576
wir|Nomn
werden|Adje
werden|Nomn
werden|AuxVwerden|KopV
werden|Part
geschickt|Adje
geschickt|Nomn
geschickt|AuxVgeschickt|KopV
geschickt|Part
0NomnNomn00
KopV000AuxV
ΩΩ|.
Ω|.
11.05.2002 17Karin Haenelt, Viterbi-Algorithmus
Tracing (5): Terminierung und Pfadausgabe
wir|Nomn
werden|Adje
werden|Nomn
werden|AuxVwerden|KopV
werden|Part0.06
geschickt|Adje
geschickt|Nomn
geschickt|AuxVgeschickt|KopV
geschickt|Part
00.00720.00900
0.0003600000.000576
wir|Nomn
werden|Adje
werden|Nomn
werden|AuxVwerden|KopV
werden|Part
geschickt|Adje
geschickt|Nomn
geschickt|AuxVgeschickt|KopV
geschickt|Part
0NomnNomn00
KopV000AuxV
Ω
Ω|.
Ω|.
11.05.2002 18Karin Haenelt, Viterbi-Algorithmus
Spezifikation des Algorithmus1 comment: Given: a sentence of length n2 comment: Initialization345 comment: Induction6 for i := 1 to n step 1 do7 for all tags tj do8910 end11 end12 comment: Termination and path-readout1314 for j := n to 1 step -1 do1516 end17
Manning/Schütze, 2000: 350
0.1)(1 =ΩδΩ≠= tt for 0.0)(1δ
)]|()|()([max:)( 111kjj
ik
iTkj
i ttPtwPtt ××= +≤≤+ δδ)]|()|()([maxarg:)( 111kjj
ik
iTkj
i ttPtwPtt ××= +≤≤+ δψ
)(maxarg 111 jX nTjn +≤≤+ = δ
)( 11 ++= jjj XX ψ
)(max),...,( 111j
nTjn tXXP +≤≤= δ
11.05.2002 19Karin Haenelt, Viterbi-Algorithmus
Funktion
berechnet für jeden Punkt im Gitter (trellis)die Wahrscheinlichkeit des wahrscheinlichsten Pfades,der zu diesem Knoten führt
)]|()|()([max:)( 111kjj
ik
iTkj
i ttPtwPtt ××= +≤≤+ δδ
δ
11.05.2002 20Karin Haenelt, Viterbi-Algorithmus
Funktion undDatenstruktur SEQSCORE
j 1 2 3 4 5 6 i Adje AuxV KopV Nomn Part Ω 1 . 0.0 0.0 0.0 0.0 0.0 1.0 2 wir 0.0 0.0 0.0 0.06 0.0 0.0 3 werden 0.0 0.0072 0.009 0.0 0.0 0.0 4 geschickt 0.000360 0.0 0.0 0.0 0.000576 0.0
SEQSCORE(j,i): Speicherung der Ergebnisse von
wir|Nomn
werden|Adje
werden|Nomn
werden|AuxVwerden|KopV
werden|Part0.06
geschickt|Adje
geschickt|Nomn
geschickt|AuxVgeschickt|KopV
geschickt|Part
00.00720.00900
0.0003600000.000576
wir|KopV 0
wir|Part 0
wir|AuxV 0wir|Adje 0
δ
δ
Ω|.
11.05.2002 21Karin Haenelt, Viterbi-Algorithmus
Funktion
ermittelt für jeden Punkt im Gitter (trellis)den Vorgängerknoten auf dem wahrscheinlichsten Pfad,der zu diesem Knoten führt
)]|()|()([maxarg:)( 111kjj
ik
iTkj
i ttPtwPtt ××= +≤≤+ δψ
ψ
11.05.2002 22Karin Haenelt, Viterbi-Algorithmus
Funktion undDatenstruktur BACKPTR
BACKPTR(j,i): Speicherung der Ergebnisse von ψ
wir|Nomn
werden|Adje
werden|Nomn
werden|AuxVwerden|KopV
werden|Part
geschickt|Adje
geschickt|Nomn
geschickt|AuxVgeschickt|KopV
geschickt|Part
0NomnNomn00
KopV000AuxV
wir|KopV 0
wir|Part 0
wir|AuxV 0wir|Adje 0
j 1 2 3 4 5 6 i Adje AuxV KopV Nomn Part Ω 1 . 2 wir 0 0 0 6 0 0 3 werden 0 4 4 0 0 0 4 geschickt 3 0 0 0 2 0
Ω|.Ω
ψ
11.05.2002 23Karin Haenelt, Viterbi-Algorithmus
DatenstrukturenSEQSCORE und BACKPTR
j 1 2 3 4 5 6 i Adje AuxV KopV Nomn Part Ω 1 . 0.0 0.0 0.0 0.0 0.0 1.0 2 wir 0.0 0.0 0.0 0.06 0.0 0.0 3 werden 0.0 0.0072 0.009 0.0 0.0 0.0 4 geschickt 0.000360 0.0 0.0 0.0 0.000576 0.0
j 1 2 3 4 5 6 i Adje AuxV KopV Nomn Part Ω 1 . 2 wir 0 0 0 6 0 0 3 werden 0 4 4 0 0 0 4 geschickt 3 0 0 0 2 0
SEQSCORE(j,i): Speicherung der Ergebnisse von
BACKPTR(j,i): Speicherung der Ergebnisse von
δ
ψ
11.05.2002 24Karin Haenelt, Viterbi-Algorithmus
Initialisierung
j 1 2 3 4 5 6 i Adje AuxV KopV Nomn Part Ω 1 . 0.0 0.0 0.0 0.0 0.0 1.0
SEQSCORE(j,i): Speicherung der Ergebnisse von
0.1)(1 =ΩδΩ≠= tt for 0.0)(1δ
Ω|.
δ
11.05.2002 25Karin Haenelt, Viterbi-Algorithmus
Berechnung: Funktion
(tj) := max 1≤k≤T )([ ki tδ )|( 1
ji twP +× )|( kj ttP
Vorgängerknoten aktueller Knoten max. Prob. Emissions-Prob. Transition-Prob. Adje - Adje )(1 Adjeδ 0.0 P(wir|Adje) 0.0 P(Adje|Adje) 0.0
- AuxV )(1 AuxVδ 0.0 0.0 P(Adje|AuxV) 0.2
- KopV )(1 KopVδ 0.0 0.0 P(Adje|KopV) 0.2
- Nomn )(1 Nomnδ 0.0 0.0 P(Adje|Nomn) 0.1
- Part )(1 Partδ 0.0 0.0 P(Adje|Part) 0.3
- Ω )(1 Ωδ 1.0 0.0 P(Adje|Ω ) 0.2
… - … … … P(wir|Auxv) 0.0 … … Nomn - Adje )(1 Adjeδ 0.0 P(wir|Nomn) 0.2 P(Nomn|Adje) 0.4
- AuxV )(1 AuxVδ 0.0 0.2 P(Nomn|AuxV) 0.2
- KopV )(1 KopVδ 0.0 0.2 P(Nomn|KopV) 0.3
- Nomn )(1 Nomnδ 0.0 0.2 P(Nomn|Nomn) 0.1
- Part )(1 Partδ 0.0 0.2 P(Nomn|Part) 0.1
0.06 Ω )(1 Ωδ 1.0 0.2 P(Nomn|Ω ) 0.3
Wort2 = „wir“
δ)]|( )|( )([max:)( 111kjj
ik
iTkj
i ttPtwPtt ××= +≤≤+ δδ
11.05.2002 26Karin Haenelt, Viterbi-Algorithmus
)]|( )|( )([maxarg:)( 111kjj
ik
iTkj
i ttPtwPtt ××= +≤≤+ δψ
Berechnung: Funktion
(tj) := max 1≤k≤T )([ ki tδ )|( 1
ji twP +× )|( kj ttP
Vorgängerknoten aktueller Knoten max. Prob. Emissions-Prob. Transition-Prob. Adje - Adje )(1 Adjeδ 0.0 P(wir|Adje) 0.0 P(Adje|Adje) 0.0
- AuxV )(1 AuxVδ 0.0 0.0 P(Adje|AuxV) 0.2
- KopV )(1 KopVδ 0.0 0.0 P(Adje|KopV) 0.2
- Nomn )(1 Nomnδ 0.0 0.0 P(Adje|Nomn) 0.1
- Part )(1 Partδ 0.0 0.0 P(Adje|Part) 0.3
- Ω )(1 Ωδ 1.0 0.0 P(Adje|Ω ) 0.2
… - … … … P(wir|Auxv) 0.0 … … Nomn - Adje )(1 Adjeδ 0.0 P(wir|Nomn) 0.2 P(Nomn|Adje) 0.4
- AuxV )(1 AuxVδ 0.0 0.2 P(Nomn|AuxV) 0.2
- KopV )(1 KopVδ 0.0 0.2 P(Nomn|KopV) 0.3
- Nomn )(1 Nomnδ 0.0 0.2 P(Nomn|Nomn) 0.1
- Part )(1 Partδ 0.0 0.2 P(Nomn|Part) 0.1
0.06 Ω )(1 Ωδ 1.0 0.2 P(Nomn|Ω ) 0.3
Wort2 = „wir“ψ
11.05.2002 27Karin Haenelt, Viterbi-Algorithmus
DatenstrukturenSEQSCORE und BACKPTR
nach der 1. Iteration
j 1 2 3 4 5 6 i Adje AuxV KopV Nomn Part Ω 1 . 0.0 0.0 0.0 0.0 0.0 1.0 2 wir 0.0 0.0 0.0 0.06 0.0 0.0
j 1 2 3 4 5 6 i Adje AuxV KopV Nomn Part Ω 1 . 2 wir 0 0 0 6 0 0
SEQSCORE(j,i): Speicherung der Ergebnisse von
BACKPTR(j,i): Speicherung der Ergebnisse von
δ
ψ
11.05.2002 28Karin Haenelt, Viterbi-Algorithmus
Terminierung, Pfadausgabe
12 comment: Termination and path-readout1314 for j := n to 1 step -1 do1516 end
)(maxarg 111 jX nTjn +≤≤+ = δ
)( 11 ++= jjj XX ψ
11.05.2002 29Karin Haenelt, Viterbi-Algorithmus
Terminierung und Pfadausgabe
j 1 2 3 4 5 6 i Adje AuxV KopV Nomn Part Ω 1 . 0.0 0.0 0.0 0.0 0.0 1.0 2 wir 0.0 0.0 0.0 0.06 0.0 0.0 3 werden 0.0 0.0072 0.009 0.0 0.0 0.0 4 geschickt 0.000360 0.0 0.0 0.0 0.000576 0.0
j 1 2 3 4 5 6 i Adje AuxV KopV Nomn Part Ω 1 . 2 wir 0 0 0 6 0 0 3 werden 0 4 4 0 0 0 4 geschickt 3 0 0 0 2 0
SEQSCORE(j,i): Speicherung der Ergebnisse von
BACKPTR(j,i): Speicherung der Ergebnisse von
δ
ψ
11.05.2002 30Karin Haenelt, Viterbi-Algorithmus
Spezifikation des Algorithmus1 comment: Given: a sentence of length n2 comment: Initialization345 comment: Induction6 for i := 1 to n step 1 do7 for all tags tj do8910 end11 end12 comment: Termination and path-readout1314 for j := n to 1 step -1 do1516 end17
Manning/Schütze, 2000: 350
0.1)(1 =ΩδΩ≠= tt for 0.0)(1δ
)]|()|()([max:)( 111kjj
ik
iTkj
i ttPtwPtt ××= +≤≤+ δδ)]|()|()([maxarg:)( 111kjj
ik
iTkj
i ttPtwPtt ××= +≤≤+ δψ
)(maxarg 111 jX nTjn +≤≤+ = δ
)( 11 ++= jjj XX ψ
)(max),...,( 111j
nTjn tXXP +≤≤= δ
11.05.2002 31Karin Haenelt, Viterbi-Algorithmus
Literatur
• Allen, James (1995): Natural Language Understanding. 2nd edition. Addison-Wesley Publishing Co.
• Haenelt, Karin: Der Viterbi-Algorithmus. Eine Erläuterung der formalen Spezifikation am Beispiel des Part-of-Speech Tagging. Kursskript. 11.05.2002 http://kontext.fraunhofer.de/haenelt/kurs/folien/Viterbi-Tutor.dochttp://kontext.fraunhofer.de/haenelt/kurs/folien/Viterbi-Tutor.htm
• Manning, Christopher D.; Schütze, Hinrich (1999): Foundations of Statistical Natural Language Processing. Cambridge, Mass., London: The MIT Press. (vgl.: http://www.sultry.arts.usyd.edu.au/fsnlp)
• Viterbi, Andrew J. (1967): Error bounds for convolutional codes and an asymptotically optimum decoding algorithm. In: IEEE Transactions on Information Theory IT-13, S. 1260-1269.
Recommended