Embed Size (px)
Citation preview
EinführungHidden Markov Models
Der Algorithmus
Der Viterbi Algorithmus
M. Trognitz
23.Juli.2007
Trognitz Der Viterbi Algorithmus
EinführungHidden Markov Models
Der Algorithmus
Gliederung
1 Einführung
2 Hidden Markov Models
3 Der Algorithmus
Trognitz Der Viterbi Algorithmus
EinführungHidden Markov Models
Der Algorithmus
Erfinder
Andrew J. Viterbi1967 zur Dekodierung von Faltungscodes entwickeltAuf Basis von Hidden Markov Models entwickelt
Trognitz Der Viterbi Algorithmus
EinführungHidden Markov Models
Der Algorithmus
Erfinder
Andrew J. Viterbi1967 zur Dekodierung von Faltungscodes entwickeltAuf Basis von Hidden Markov Models entwickelt
Trognitz Der Viterbi Algorithmus
EinführungHidden Markov Models
Der Algorithmus
Erfinder
Andrew J. Viterbi1967 zur Dekodierung von Faltungscodes entwickeltAuf Basis von Hidden Markov Models entwickelt
Trognitz Der Viterbi Algorithmus
EinführungHidden Markov Models
Der Algorithmus
Funktion
Findet die beste Pfadsequenz in einem HMM zu einergegebenen Beobachtungsogenannter Viterbi-Pfad
Trognitz Der Viterbi Algorithmus
EinführungHidden Markov Models
Der Algorithmus
Funktion
Findet die beste Pfadsequenz in einem HMM zu einergegebenen Beobachtungsogenannter Viterbi-Pfad
Trognitz Der Viterbi Algorithmus
EinführungHidden Markov Models
Der Algorithmus
Anwendungsbereiche
Vielfältige Anwendungmöglichkeiten wie zum Beispiel:WorterkennungPOS-TaggingEntzerrung und Fehlerkorretur bei Datenübertragung,Beispielsweise bei MobilfunkgerätenKryptografieMustererkennung
Trognitz Der Viterbi Algorithmus
EinführungHidden Markov Models
Der Algorithmus
Anwendungsbereiche
Vielfältige Anwendungmöglichkeiten wie zum Beispiel:WorterkennungPOS-TaggingEntzerrung und Fehlerkorretur bei Datenübertragung,Beispielsweise bei MobilfunkgerätenKryptografieMustererkennung
Trognitz Der Viterbi Algorithmus
EinführungHidden Markov Models
Der Algorithmus
Anwendungsbereiche
Vielfältige Anwendungmöglichkeiten wie zum Beispiel:WorterkennungPOS-TaggingEntzerrung und Fehlerkorretur bei Datenübertragung,Beispielsweise bei MobilfunkgerätenKryptografieMustererkennung
Trognitz Der Viterbi Algorithmus
EinführungHidden Markov Models
Der Algorithmus
Anwendungsbereiche
Vielfältige Anwendungmöglichkeiten wie zum Beispiel:WorterkennungPOS-TaggingEntzerrung und Fehlerkorretur bei Datenübertragung,Beispielsweise bei MobilfunkgerätenKryptografieMustererkennung
Trognitz Der Viterbi Algorithmus
EinführungHidden Markov Models
Der Algorithmus
Anwendungsbereiche
Vielfältige Anwendungmöglichkeiten wie zum Beispiel:WorterkennungPOS-TaggingEntzerrung und Fehlerkorretur bei Datenübertragung,Beispielsweise bei MobilfunkgerätenKryptografieMustererkennung
Trognitz Der Viterbi Algorithmus
EinführungHidden Markov Models
Der Algorithmus
Wiederholung von HMMs I
Ein HMM ist ein Fünftupel λ = (S,K , π,A,B)
S = {s1, ..., sN}Menge aller ZuständeK = {k1, ..., kM}Ausgabealphabetπ = {πi}, i ∈ S
∑Ni=1 πi = 1
Wahrscheinlichkeiten der StartzuständeA = {aij}, i , j ∈ S
∑Nj=1 aij = 1
Wahrscheinlichkeiten der ZustandsübergängeB = {bijk}, i , j ∈ S, k ∈ K
∑Mk=1 bijk = 1
Wahrscheinlichkeiten der Symbolemissionen
Trognitz Der Viterbi Algorithmus
EinführungHidden Markov Models
Der Algorithmus
Wiederholung von HMMs I
Ein HMM ist ein Fünftupel λ = (S,K , π,A,B)
S = {s1, ..., sN}Menge aller ZuständeK = {k1, ..., kM}Ausgabealphabetπ = {πi}, i ∈ S
∑Ni=1 πi = 1
Wahrscheinlichkeiten der StartzuständeA = {aij}, i , j ∈ S
∑Nj=1 aij = 1
Wahrscheinlichkeiten der ZustandsübergängeB = {bijk}, i , j ∈ S, k ∈ K
∑Mk=1 bijk = 1
Wahrscheinlichkeiten der Symbolemissionen
Trognitz Der Viterbi Algorithmus
EinführungHidden Markov Models
Der Algorithmus
Wiederholung von HMMs I
Ein HMM ist ein Fünftupel λ = (S,K , π,A,B)
S = {s1, ..., sN}Menge aller ZuständeK = {k1, ..., kM}Ausgabealphabetπ = {πi}, i ∈ S
∑Ni=1 πi = 1
Wahrscheinlichkeiten der StartzuständeA = {aij}, i , j ∈ S
∑Nj=1 aij = 1
Wahrscheinlichkeiten der ZustandsübergängeB = {bijk}, i , j ∈ S, k ∈ K
∑Mk=1 bijk = 1
Wahrscheinlichkeiten der Symbolemissionen
Trognitz Der Viterbi Algorithmus
EinführungHidden Markov Models
Der Algorithmus
Wiederholung von HMMs I
Ein HMM ist ein Fünftupel λ = (S,K , π,A,B)
S = {s1, ..., sN}Menge aller ZuständeK = {k1, ..., kM}Ausgabealphabetπ = {πi}, i ∈ S
∑Ni=1 πi = 1
Wahrscheinlichkeiten der StartzuständeA = {aij}, i , j ∈ S
∑Nj=1 aij = 1
Wahrscheinlichkeiten der ZustandsübergängeB = {bijk}, i , j ∈ S, k ∈ K
∑Mk=1 bijk = 1
Wahrscheinlichkeiten der Symbolemissionen
Trognitz Der Viterbi Algorithmus
EinführungHidden Markov Models
Der Algorithmus
Wiederholung von HMMs I
Ein HMM ist ein Fünftupel λ = (S,K , π,A,B)
S = {s1, ..., sN}Menge aller ZuständeK = {k1, ..., kM}Ausgabealphabetπ = {πi}, i ∈ S
∑Ni=1 πi = 1
Wahrscheinlichkeiten der StartzuständeA = {aij}, i , j ∈ S
∑Nj=1 aij = 1
Wahrscheinlichkeiten der ZustandsübergängeB = {bijk}, i , j ∈ S, k ∈ K
∑Mk=1 bijk = 1
Wahrscheinlichkeiten der Symbolemissionen
Trognitz Der Viterbi Algorithmus
EinführungHidden Markov Models
Der Algorithmus
Wiederholung von HMMs I
Ein HMM ist ein Fünftupel λ = (S,K , π,A,B)
S = {s1, ..., sN}Menge aller ZuständeK = {k1, ..., kM}Ausgabealphabetπ = {πi}, i ∈ S
∑Ni=1 πi = 1
Wahrscheinlichkeiten der StartzuständeA = {aij}, i , j ∈ S
∑Nj=1 aij = 1
Wahrscheinlichkeiten der ZustandsübergängeB = {bijk}, i , j ∈ S, k ∈ K
∑Mk=1 bijk = 1
Wahrscheinlichkeiten der Symbolemissionen
Trognitz Der Viterbi Algorithmus
EinführungHidden Markov Models
Der Algorithmus
Wiederholung von HMMs II
Es gibt arc-emission HMMs und state-emission HMMs:arc-emission: Das ausgegebene Symbol hängt von denZeitpunkten t und t − 1 ab.state-emission: Das ausgegebene Smbol hängt nur vomZeitpunkt t ab.
Beispiel für ein state-emission Modell aus Wikipedia
x: hidden states
y: Ausgabe
a: Übergangswahrscheinlichkeit
b: Ausgabewahrscheinlichkeit
Trognitz Der Viterbi Algorithmus
EinführungHidden Markov Models
Der Algorithmus
Wiederholung von HMMs II
Es gibt arc-emission HMMs und state-emission HMMs:arc-emission: Das ausgegebene Symbol hängt von denZeitpunkten t und t − 1 ab.state-emission: Das ausgegebene Smbol hängt nur vomZeitpunkt t ab.
Beispiel für ein state-emission Modell aus Wikipedia
x: hidden states
y: Ausgabe
a: Übergangswahrscheinlichkeit
b: Ausgabewahrscheinlichkeit
Trognitz Der Viterbi Algorithmus
EinführungHidden Markov Models
Der Algorithmus
Wiederholung von HMMs II
Es gibt arc-emission HMMs und state-emission HMMs:arc-emission: Das ausgegebene Symbol hängt von denZeitpunkten t und t − 1 ab.state-emission: Das ausgegebene Smbol hängt nur vomZeitpunkt t ab.
Beispiel für ein state-emission Modell aus Wikipedia
x: hidden states
y: Ausgabe
a: Übergangswahrscheinlichkeit
b: Ausgabewahrscheinlichkeit
Trognitz Der Viterbi Algorithmus
EinführungHidden Markov Models
Der Algorithmus
Wiederholung von HMMs II
Es gibt arc-emission HMMs und state-emission HMMs:arc-emission: Das ausgegebene Symbol hängt von denZeitpunkten t und t − 1 ab.state-emission: Das ausgegebene Smbol hängt nur vomZeitpunkt t ab.
Beispiel für ein state-emission Modell aus Wikipedia
x: hidden states
y: Ausgabe
a: Übergangswahrscheinlichkeit
b: Ausgabewahrscheinlichkeit
Trognitz Der Viterbi Algorithmus
EinführungHidden Markov Models
Der Algorithmus
Die Problemstellung
Wir wollen wissen, welches der wahrscheinlichste Pfad ineiner Sequenz von verborgenen Zuständen ist, der zuunserer Eingabe führt.
Das könnte man lösen, indem alle Pfade ausprobiertwerden und aus dieser Menge der wahrscheinlichsteherausgefiltert wird.Mittels Rekursion kann man dies verbessern.
Trognitz Der Viterbi Algorithmus
EinführungHidden Markov Models
Der Algorithmus
Die Problemstellung
Wir wollen wissen, welches der wahrscheinlichste Pfad ineiner Sequenz von verborgenen Zuständen ist, der zuunserer Eingabe führt.
Das könnte man lösen, indem alle Pfade ausprobiertwerden und aus dieser Menge der wahrscheinlichsteherausgefiltert wird.Mittels Rekursion kann man dies verbessern.
Trognitz Der Viterbi Algorithmus
EinführungHidden Markov Models
Der Algorithmus
Die Problemstellung
Wir wollen wissen, welches der wahrscheinlichste Pfad ineiner Sequenz von verborgenen Zuständen ist, der zuunserer Eingabe führt.
Das könnte man lösen, indem alle Pfade ausprobiertwerden und aus dieser Menge der wahrscheinlichsteherausgefiltert wird.Mittels Rekursion kann man dies verbessern.
Trognitz Der Viterbi Algorithmus
EinführungHidden Markov Models
Der Algorithmus
Beispiel I
Time flies like arrows.Die Zeit vergeht so schnell, wie Pfeile fliegen.Zeitfliegen mögen Pfeile.Miss die Zeit, die Fliegen brauchen, so schnell wie Pfeile.etc.
Trognitz Der Viterbi Algorithmus
EinführungHidden Markov Models
Der Algorithmus
Beispiel I
Time flies like arrows.Die Zeit vergeht so schnell, wie Pfeile fliegen.Zeitfliegen mögen Pfeile.Miss die Zeit, die Fliegen brauchen, so schnell wie Pfeile.etc.
Trognitz Der Viterbi Algorithmus
EinführungHidden Markov Models
Der Algorithmus
Beispiel I
Time flies like arrows.Die Zeit vergeht so schnell, wie Pfeile fliegen.Zeitfliegen mögen Pfeile.Miss die Zeit, die Fliegen brauchen, so schnell wie Pfeile.etc.
Trognitz Der Viterbi Algorithmus
EinführungHidden Markov Models
Der Algorithmus
Beispiel I
Time flies like arrows.Die Zeit vergeht so schnell, wie Pfeile fliegen.Zeitfliegen mögen Pfeile.Miss die Zeit, die Fliegen brauchen, so schnell wie Pfeile.etc.
Trognitz Der Viterbi Algorithmus
EinführungHidden Markov Models
Der Algorithmus
Beispiel II
Symbolemissionen
Time flies like arrowsNom 0.4 0.25 0 0.35
NomC 0.3 0.45 0 0.25Verb 0 0.76 0.24 0Prep 0 0 1 0
Das Trellis-Diagramm für den Beispielsatz.
Trognitz Der Viterbi Algorithmus
EinführungHidden Markov Models
Der Algorithmus
Beispiel III
Zustandsübergangs- und Startwahrscheinlichkeiten
Nom NomC Verb Prepπ 0.35 0.2 0.25 0.2
Nom 0.1 0.3 0.45 0.15NomC 0.01 0.29 0.5 0.2Verb 0.2 0.1 0.25 0.45Prep 0.5 0.05 0.25 0.2
Trognitz Der Viterbi Algorithmus
EinführungHidden Markov Models
Der Algorithmus
Vorgehensweise des Algorithmus
Der Algorithmus besteht aus drei TeilenInitialisierungInduktionmit den Funktionen δ und ψTerminierung und Pfadausgabe
und hat zwei wichtige Datenstrukturen, die Arrays derGröße K × N sind , wobei N die Anzahl der Wörter in derEingabe und K die Zahl der lexikalischen Kategorienrepräsentieren.
SEQSCORE(k,n), speichert die Wahrscheinlichkeiten fürdie beste Sequenz zur Position n, die mit einem Wort ausder lexikalischen Kategorie endet.BACKPTR, speichert für jede Kategorie an der Position ndie Kategorie der besten Sequenz an Position n − 1.
Trognitz Der Viterbi Algorithmus
EinführungHidden Markov Models
Der Algorithmus
Vorgehensweise des Algorithmus
Der Algorithmus besteht aus drei TeilenInitialisierungInduktionmit den Funktionen δ und ψTerminierung und Pfadausgabe
und hat zwei wichtige Datenstrukturen, die Arrays derGröße K × N sind , wobei N die Anzahl der Wörter in derEingabe und K die Zahl der lexikalischen Kategorienrepräsentieren.
SEQSCORE(k,n), speichert die Wahrscheinlichkeiten fürdie beste Sequenz zur Position n, die mit einem Wort ausder lexikalischen Kategorie endet.BACKPTR, speichert für jede Kategorie an der Position ndie Kategorie der besten Sequenz an Position n − 1.
Trognitz Der Viterbi Algorithmus
EinführungHidden Markov Models
Der Algorithmus
Vorgehensweise des Algorithmus
Der Algorithmus besteht aus drei TeilenInitialisierungInduktionmit den Funktionen δ und ψTerminierung und Pfadausgabe
und hat zwei wichtige Datenstrukturen, die Arrays derGröße K × N sind , wobei N die Anzahl der Wörter in derEingabe und K die Zahl der lexikalischen Kategorienrepräsentieren.
SEQSCORE(k,n), speichert die Wahrscheinlichkeiten fürdie beste Sequenz zur Position n, die mit einem Wort ausder lexikalischen Kategorie endet.BACKPTR, speichert für jede Kategorie an der Position ndie Kategorie der besten Sequenz an Position n − 1.
Trognitz Der Viterbi Algorithmus
EinführungHidden Markov Models
Der Algorithmus
Vorgehensweise des Algorithmus
Der Algorithmus besteht aus drei TeilenInitialisierungInduktionmit den Funktionen δ und ψTerminierung und Pfadausgabe
und hat zwei wichtige Datenstrukturen, die Arrays derGröße K × N sind , wobei N die Anzahl der Wörter in derEingabe und K die Zahl der lexikalischen Kategorienrepräsentieren.
SEQSCORE(k,n), speichert die Wahrscheinlichkeiten fürdie beste Sequenz zur Position n, die mit einem Wort ausder lexikalischen Kategorie endet.BACKPTR, speichert für jede Kategorie an der Position ndie Kategorie der besten Sequenz an Position n − 1.
Trognitz Der Viterbi Algorithmus
EinführungHidden Markov Models
Der Algorithmus
Vorgehensweise des Algorithmus
Der Algorithmus besteht aus drei TeilenInitialisierungInduktionmit den Funktionen δ und ψTerminierung und Pfadausgabe
und hat zwei wichtige Datenstrukturen, die Arrays derGröße K × N sind , wobei N die Anzahl der Wörter in derEingabe und K die Zahl der lexikalischen Kategorienrepräsentieren.
SEQSCORE(k,n), speichert die Wahrscheinlichkeiten fürdie beste Sequenz zur Position n, die mit einem Wort ausder lexikalischen Kategorie endet.BACKPTR, speichert für jede Kategorie an der Position ndie Kategorie der besten Sequenz an Position n − 1.
Trognitz Der Viterbi Algorithmus
EinführungHidden Markov Models
Der Algorithmus
Vorgehensweise des Algorithmus
Der Algorithmus besteht aus drei TeilenInitialisierungInduktionmit den Funktionen δ und ψTerminierung und Pfadausgabe
und hat zwei wichtige Datenstrukturen, die Arrays derGröße K × N sind , wobei N die Anzahl der Wörter in derEingabe und K die Zahl der lexikalischen Kategorienrepräsentieren.
SEQSCORE(k,n), speichert die Wahrscheinlichkeiten fürdie beste Sequenz zur Position n, die mit einem Wort ausder lexikalischen Kategorie endet.BACKPTR, speichert für jede Kategorie an der Position ndie Kategorie der besten Sequenz an Position n − 1.
Trognitz Der Viterbi Algorithmus
EinführungHidden Markov Models
Der Algorithmus
Vorgehensweise des Algorithmus
Der Algorithmus besteht aus drei TeilenInitialisierungInduktionmit den Funktionen δ und ψTerminierung und Pfadausgabe
und hat zwei wichtige Datenstrukturen, die Arrays derGröße K × N sind , wobei N die Anzahl der Wörter in derEingabe und K die Zahl der lexikalischen Kategorienrepräsentieren.
SEQSCORE(k,n), speichert die Wahrscheinlichkeiten fürdie beste Sequenz zur Position n, die mit einem Wort ausder lexikalischen Kategorie endet.BACKPTR, speichert für jede Kategorie an der Position ndie Kategorie der besten Sequenz an Position n − 1.
Trognitz Der Viterbi Algorithmus
EinführungHidden Markov Models
Der Algorithmus
Initialisierung
SEQSCORE(i,1) wird in unserem Beispiel mit demErgebnis folgender Formel gefüllt:P(Time|ki) ∗ P(ki |π)
Somit ergibt sich mit unserem Beispiel für SEQSCORE:1 (Nom) 2 (NomC) 3 (Verb) 4 (Prep)
1 0.14 0.06 0 02 0 0 0 03 0 0 0 04 0 0 0 0
Trognitz Der Viterbi Algorithmus
EinführungHidden Markov Models
Der Algorithmus
Initialisierung
SEQSCORE(i,1) wird in unserem Beispiel mit demErgebnis folgender Formel gefüllt:P(Time|ki) ∗ P(ki |π)
Somit ergibt sich mit unserem Beispiel für SEQSCORE:1 (Nom) 2 (NomC) 3 (Verb) 4 (Prep)
1 0.14 0.06 0 02 0 0 0 03 0 0 0 04 0 0 0 0
Trognitz Der Viterbi Algorithmus
EinführungHidden Markov Models
Der Algorithmus
Induktion
Mit δ wird die Wahrscheinlichkeit des wahrscheinlichstenPfades berechnetDie Ergebnisse von δ werden in SEQSCORE gespeichertMit ψ wird der Vorgänger auf dem wahrscheinlichsten PfadermitteltDie Ergebnisse von ψ werden in BACKPTR gespeichert
Trognitz Der Viterbi Algorithmus
EinführungHidden Markov Models
Der Algorithmus
Induktion
Mit δ wird die Wahrscheinlichkeit des wahrscheinlichstenPfades berechnetDie Ergebnisse von δ werden in SEQSCORE gespeichertMit ψ wird der Vorgänger auf dem wahrscheinlichsten PfadermitteltDie Ergebnisse von ψ werden in BACKPTR gespeichert
Trognitz Der Viterbi Algorithmus
EinführungHidden Markov Models
Der Algorithmus
Induktion
Mit δ wird die Wahrscheinlichkeit des wahrscheinlichstenPfades berechnetDie Ergebnisse von δ werden in SEQSCORE gespeichertMit ψ wird der Vorgänger auf dem wahrscheinlichsten PfadermitteltDie Ergebnisse von ψ werden in BACKPTR gespeichert
Trognitz Der Viterbi Algorithmus
EinführungHidden Markov Models
Der Algorithmus
Induktion
Mit δ wird die Wahrscheinlichkeit des wahrscheinlichstenPfades berechnetDie Ergebnisse von δ werden in SEQSCORE gespeichertMit ψ wird der Vorgänger auf dem wahrscheinlichsten PfadermitteltDie Ergebnisse von ψ werden in BACKPTR gespeichert
Trognitz Der Viterbi Algorithmus
EinführungHidden Markov Models
Der Algorithmus
Induktion δ
δi+1(nj) = max1≤k≤K [δi(nk )× P(wi+1|nj)× P(nj |nk )]
nj : j-tes Tag im Tagsetnk : Nachfolger von nj
wi+1: Wort an Position i+1Um die zweite Zeile in SEQSCORE zu berechnen, setztman in die Formel also folgendes ein:0.14×P(flies|Nom)×P(Nom|Nom) = 0.14× 0.25× 0.1 =3,5 ∗ 10−3
Damit erhält man den Wert für flies, wenn es sich dabei umein Nomen handelt.
Trognitz Der Viterbi Algorithmus
EinführungHidden Markov Models
Der Algorithmus
Induktion δ
δi+1(nj) = max1≤k≤K [δi(nk )× P(wi+1|nj)× P(nj |nk )]
nj : j-tes Tag im Tagsetnk : Nachfolger von nj
wi+1: Wort an Position i+1Um die zweite Zeile in SEQSCORE zu berechnen, setztman in die Formel also folgendes ein:0.14×P(flies|Nom)×P(Nom|Nom) = 0.14× 0.25× 0.1 =3,5 ∗ 10−3
Damit erhält man den Wert für flies, wenn es sich dabei umein Nomen handelt.
Trognitz Der Viterbi Algorithmus
EinführungHidden Markov Models
Der Algorithmus
Induktion δ
δi+1(nj) = max1≤k≤K [δi(nk )× P(wi+1|nj)× P(nj |nk )]
nj : j-tes Tag im Tagsetnk : Nachfolger von nj
wi+1: Wort an Position i+1Um die zweite Zeile in SEQSCORE zu berechnen, setztman in die Formel also folgendes ein:0.14×P(flies|Nom)×P(Nom|Nom) = 0.14× 0.25× 0.1 =3,5 ∗ 10−3
Damit erhält man den Wert für flies, wenn es sich dabei umein Nomen handelt.
Trognitz Der Viterbi Algorithmus
EinführungHidden Markov Models
Der Algorithmus
Induktion δ, SEQSCORE
SEQSCORE sieht dann so aus:1 (Nom) 2 (NomC) 3 (Verb) 4 (Prep)
1 (Time) 0.14 0.06 0 02 (flies) 3,5 ∗ 10−3 18.9 ∗ 10−3 47.88 ∗ 10−3 0
3 0 0 0 04 0 0 0 0
Trognitz Der Viterbi Algorithmus
EinführungHidden Markov Models
Der Algorithmus
Induktion ψ
Mit dieser Funktion wird der Vorgängerknoten gespeichertψi+1(nj) = argmax1≤k≤K [δi(nk )× P(wi+1|nj)× P(nj |nk )]
argmax speichert das Vorgängerelement, das dasMaximum in δ lieferteBACKPTR erhält diese Werte:
1 (Nom) 2 (NomC) 3 (Verb) 4 (Prep)1 (Time) 0 0 0 02 (flies) 1 1 1 0
3 0 0 0 04 0 0 0 0
Trognitz Der Viterbi Algorithmus
EinführungHidden Markov Models
Der Algorithmus
Induktion ψ
Mit dieser Funktion wird der Vorgängerknoten gespeichertψi+1(nj) = argmax1≤k≤K [δi(nk )× P(wi+1|nj)× P(nj |nk )]
argmax speichert das Vorgängerelement, das dasMaximum in δ lieferteBACKPTR erhält diese Werte:
1 (Nom) 2 (NomC) 3 (Verb) 4 (Prep)1 (Time) 0 0 0 02 (flies) 1 1 1 0
3 0 0 0 04 0 0 0 0
Trognitz Der Viterbi Algorithmus
EinführungHidden Markov Models
Der Algorithmus
Induktion ψ
Mit dieser Funktion wird der Vorgängerknoten gespeichertψi+1(nj) = argmax1≤k≤K [δi(nk )× P(wi+1|nj)× P(nj |nk )]
argmax speichert das Vorgängerelement, das dasMaximum in δ lieferteBACKPTR erhält diese Werte:
1 (Nom) 2 (NomC) 3 (Verb) 4 (Prep)1 (Time) 0 0 0 02 (flies) 1 1 1 0
3 0 0 0 04 0 0 0 0
Trognitz Der Viterbi Algorithmus
EinführungHidden Markov Models
Der Algorithmus
Induktion ψ
Mit dieser Funktion wird der Vorgängerknoten gespeichertψi+1(nj) = argmax1≤k≤K [δi(nk )× P(wi+1|nj)× P(nj |nk )]
argmax speichert das Vorgängerelement, das dasMaximum in δ lieferteBACKPTR erhält diese Werte:
1 (Nom) 2 (NomC) 3 (Verb) 4 (Prep)1 (Time) 0 0 0 02 (flies) 1 1 1 0
3 0 0 0 04 0 0 0 0
Trognitz Der Viterbi Algorithmus
EinführungHidden Markov Models
Der Algorithmus
Induktionsschleife
Diese Schritte werden wiederholt, bis die gesamte Eingabeanalysiert worden ist.
Trognitz Der Viterbi Algorithmus
EinführungHidden Markov Models
Der Algorithmus
Ende der Induktionsschleife I
SEQSCORE:1 (Nom) 2 (NomC) 3 (Verb) 4 (Prep)
1 (Time) 0.14 0.06 0 02 (flies) 3,5 ∗ 10−3 18.9 ∗ 10−3 47.88 ∗ 10−3 03 (like) 0 0 2.87 ∗ 10−3 21.55 ∗ 10−3
4 (arrows) 3.77 ∗ 10−3 0.27 ∗ 10−3 0 0
Trognitz Der Viterbi Algorithmus
EinführungHidden Markov Models
Der Algorithmus
Ende der Induktionsschleife II
BACKPTR:1 (Nom) 2 (NomC) 3 (Verb) 4 (Prep)
1 (Time) 0 0 0 02 (flies) 1.1 1.1 1.1 03 (like) 0 0 3.2 3.2
4 (arrows) 4.3 4.3 0 01.1 bedeutet: Nom gibt Time aus.
Trognitz Der Viterbi Algorithmus
EinführungHidden Markov Models
Der Algorithmus
Terminierung
Zuletzt wird mit Hilfe von BACKPTR der beste Pfadausgegeben.
In der letzen Zeile von SEQSCORE wird das höchsteErgebnis von δ gesucht. In unserem Beispiel: 3.77*10−3
Von hier aus kann der Algorithmus mit Hilfe von BACKPTRdie Analyse des Satzes zurückverfolgenIn unserem Beispiel: Time (Nom) flies (Verb) like (Prep)arrows (Nom).
Trognitz Der Viterbi Algorithmus
EinführungHidden Markov Models
Der Algorithmus
Terminierung
Zuletzt wird mit Hilfe von BACKPTR der beste Pfadausgegeben.
In der letzen Zeile von SEQSCORE wird das höchsteErgebnis von δ gesucht. In unserem Beispiel: 3.77*10−3
Von hier aus kann der Algorithmus mit Hilfe von BACKPTRdie Analyse des Satzes zurückverfolgenIn unserem Beispiel: Time (Nom) flies (Verb) like (Prep)arrows (Nom).
Trognitz Der Viterbi Algorithmus
EinführungHidden Markov Models
Der Algorithmus
Terminierung
Zuletzt wird mit Hilfe von BACKPTR der beste Pfadausgegeben.
In der letzen Zeile von SEQSCORE wird das höchsteErgebnis von δ gesucht. In unserem Beispiel: 3.77*10−3
Von hier aus kann der Algorithmus mit Hilfe von BACKPTRdie Analyse des Satzes zurückverfolgenIn unserem Beispiel: Time (Nom) flies (Verb) like (Prep)arrows (Nom).
Trognitz Der Viterbi Algorithmus
EinführungHidden Markov Models
Der Algorithmus
Terminierung
Zuletzt wird mit Hilfe von BACKPTR der beste Pfadausgegeben.
In der letzen Zeile von SEQSCORE wird das höchsteErgebnis von δ gesucht. In unserem Beispiel: 3.77*10−3
Von hier aus kann der Algorithmus mit Hilfe von BACKPTRdie Analyse des Satzes zurückverfolgenIn unserem Beispiel: Time (Nom) flies (Verb) like (Prep)arrows (Nom).
Trognitz Der Viterbi Algorithmus
EinführungHidden Markov Models
Der Algorithmus
Algorithmus
Datenstrukturen initialisieren
for i=1 to N:SEQSCORE(i,1)=P(Time|ki) ∗ P(ki |π)BACKPTR(i,1)=0
for i=1 to K:for j=1 to N:SEQSCORE(j,i+1)=max1≤k≤K [δi(nk )× P(wi+1|nj)× P(nj |nk )]BACKPTR(i,i+1)=argmax1≤k≤K [δi(nk )× P(wi+1|nj)× P(nj |nk )]
for j=K to 1:Suche in SEQSCORE das höchste Ergebnis und verfolgedieses mit BACKPTR zurück.
Ergebnis ausgeben
Trognitz Der Viterbi Algorithmus
EinführungHidden Markov Models
Der Algorithmus
Weiterführend
Allen, James (1995): Natural Language Unterstanding. 2nd edition.Addison-Wesley Publishing Co.
Haenelt, Karin: Der Viterbi-Algorithmus. Eine Erläuterung der formalenSpezifikationen am Beispiel des Part-of-Speech Tagging. Kursskript. 16.06.2007http://kontext.fraunhofer.de/haenelt/kurs/folien/Haenelt_Viterbi-Tutor.pdf
Haenelt,Karin: Der Viterbi-Algorithmus im Part-of-Speech Tagging. Kursfolien.16.06.2007.http://kontext.fraunhofer.de/haenelt/kurs/folien/Haenelt_Viterbi-Algorithmus.pdf
Manning, Christopher D. - Schütze, Hinrich (1999): Foundations of StatisticalNatural Language Processing. Cambridge, Mass., London: The MIT Press
Viterbi, Andrew J. (1967): Error bounds for convolutional codes and anasymptotically optimum decoding algorithm. In: IEEE Transactions onInformation Theory IT-13, S. 1260-1269.
Wikipedia
Trognitz Der Viterbi Algorithmus
EinführungHidden Markov Models
Der Algorithmus
Weiterführend
Allen, James (1995): Natural Language Unterstanding. 2nd edition.Addison-Wesley Publishing Co.
Haenelt, Karin: Der Viterbi-Algorithmus. Eine Erläuterung der formalenSpezifikationen am Beispiel des Part-of-Speech Tagging. Kursskript. 16.06.2007http://kontext.fraunhofer.de/haenelt/kurs/folien/Haenelt_Viterbi-Tutor.pdf
Haenelt,Karin: Der Viterbi-Algorithmus im Part-of-Speech Tagging. Kursfolien.16.06.2007.http://kontext.fraunhofer.de/haenelt/kurs/folien/Haenelt_Viterbi-Algorithmus.pdf
Manning, Christopher D. - Schütze, Hinrich (1999): Foundations of StatisticalNatural Language Processing. Cambridge, Mass., London: The MIT Press
Viterbi, Andrew J. (1967): Error bounds for convolutional codes and anasymptotically optimum decoding algorithm. In: IEEE Transactions onInformation Theory IT-13, S. 1260-1269.
Wikipedia
Trognitz Der Viterbi Algorithmus
EinführungHidden Markov Models
Der Algorithmus
Weiterführend
Allen, James (1995): Natural Language Unterstanding. 2nd edition.Addison-Wesley Publishing Co.
Haenelt, Karin: Der Viterbi-Algorithmus. Eine Erläuterung der formalenSpezifikationen am Beispiel des Part-of-Speech Tagging. Kursskript. 16.06.2007http://kontext.fraunhofer.de/haenelt/kurs/folien/Haenelt_Viterbi-Tutor.pdf
Haenelt,Karin: Der Viterbi-Algorithmus im Part-of-Speech Tagging. Kursfolien.16.06.2007.http://kontext.fraunhofer.de/haenelt/kurs/folien/Haenelt_Viterbi-Algorithmus.pdf
Manning, Christopher D. - Schütze, Hinrich (1999): Foundations of StatisticalNatural Language Processing. Cambridge, Mass., London: The MIT Press
Viterbi, Andrew J. (1967): Error bounds for convolutional codes and anasymptotically optimum decoding algorithm. In: IEEE Transactions onInformation Theory IT-13, S. 1260-1269.
Wikipedia
Trognitz Der Viterbi Algorithmus
EinführungHidden Markov Models
Der Algorithmus
Weiterführend
Allen, James (1995): Natural Language Unterstanding. 2nd edition.Addison-Wesley Publishing Co.
Haenelt, Karin: Der Viterbi-Algorithmus. Eine Erläuterung der formalenSpezifikationen am Beispiel des Part-of-Speech Tagging. Kursskript. 16.06.2007http://kontext.fraunhofer.de/haenelt/kurs/folien/Haenelt_Viterbi-Tutor.pdf
Haenelt,Karin: Der Viterbi-Algorithmus im Part-of-Speech Tagging. Kursfolien.16.06.2007.http://kontext.fraunhofer.de/haenelt/kurs/folien/Haenelt_Viterbi-Algorithmus.pdf
Manning, Christopher D. - Schütze, Hinrich (1999): Foundations of StatisticalNatural Language Processing. Cambridge, Mass., London: The MIT Press
Viterbi, Andrew J. (1967): Error bounds for convolutional codes and anasymptotically optimum decoding algorithm. In: IEEE Transactions onInformation Theory IT-13, S. 1260-1269.
Wikipedia
Trognitz Der Viterbi Algorithmus
EinführungHidden Markov Models
Der Algorithmus
Weiterführend
Allen, James (1995): Natural Language Unterstanding. 2nd edition.Addison-Wesley Publishing Co.
Haenelt, Karin: Der Viterbi-Algorithmus. Eine Erläuterung der formalenSpezifikationen am Beispiel des Part-of-Speech Tagging. Kursskript. 16.06.2007http://kontext.fraunhofer.de/haenelt/kurs/folien/Haenelt_Viterbi-Tutor.pdf
Haenelt,Karin: Der Viterbi-Algorithmus im Part-of-Speech Tagging. Kursfolien.16.06.2007.http://kontext.fraunhofer.de/haenelt/kurs/folien/Haenelt_Viterbi-Algorithmus.pdf
Manning, Christopher D. - Schütze, Hinrich (1999): Foundations of StatisticalNatural Language Processing. Cambridge, Mass., London: The MIT Press
Viterbi, Andrew J. (1967): Error bounds for convolutional codes and anasymptotically optimum decoding algorithm. In: IEEE Transactions onInformation Theory IT-13, S. 1260-1269.
Wikipedia
Trognitz Der Viterbi Algorithmus
EinführungHidden Markov Models
Der Algorithmus
Weiterführend
Allen, James (1995): Natural Language Unterstanding. 2nd edition.Addison-Wesley Publishing Co.
Haenelt, Karin: Der Viterbi-Algorithmus. Eine Erläuterung der formalenSpezifikationen am Beispiel des Part-of-Speech Tagging. Kursskript. 16.06.2007http://kontext.fraunhofer.de/haenelt/kurs/folien/Haenelt_Viterbi-Tutor.pdf
Haenelt,Karin: Der Viterbi-Algorithmus im Part-of-Speech Tagging. Kursfolien.16.06.2007.http://kontext.fraunhofer.de/haenelt/kurs/folien/Haenelt_Viterbi-Algorithmus.pdf
Manning, Christopher D. - Schütze, Hinrich (1999): Foundations of StatisticalNatural Language Processing. Cambridge, Mass., London: The MIT Press
Viterbi, Andrew J. (1967): Error bounds for convolutional codes and anasymptotically optimum decoding algorithm. In: IEEE Transactions onInformation Theory IT-13, S. 1260-1269.
Wikipedia
Trognitz Der Viterbi Algorithmus
