Der Viterbi Algorithmus -...

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