Viterbi Algorithmus Vorwärts Algorithmus HMMs und der Viterbi-Algorithmus Christian Wurm July 8, 2015 Christian Wurm HMMs und der Viterbi-Algorithmus Viterbi Algorithmus Vorwärts Algorithmus Das Problem Wir haben gesehen: wir können P(~ w |~q )P(~q ) ohne große Probleme ausrechnen (~ w = b1 ...bi , ~q = q1 ...qi . P(~ w |~q )P(~q ) = π(q1 )τ (b1 , q1 )δ(q1 , q2 )τ (b2 , q2 )...δ(qi−1 , qi )τ (bi , qi ) = π(q1 ) i Y τ (bj , qj ) j=1 i−1 Y (1) δ(qj , qj+1 ) j=1 (δ-Terme sind für P(~q ), τ für P(~ w |~q )) Christian Wurm HMMs und der Viterbi-Algorithmus Viterbi Algorithmus Vorwärts Algorithmus Das Problem Was wir aber suchen ist argmax|~q|=|~w | P(~q |~ w ), also die Zustandsfolge, die gegeben unsere Beobachtung maximal wahrscheinlich ist. Natürlich haben wir: argmax|~q|=|~w | P(~q |~ w) P(~q ) P(~ w) = argmax|~q|=|~w | P(~ w |~q )P(~q ) = argmax|~q|=|~w | P(~ w |~q ) (~ w bleibt ja unverändert über Terme). Christian Wurm HMMs und der Viterbi-Algorithmus (2) Viterbi Algorithmus Vorwärts Algorithmus Der naive Ansatz Das Problem mit dem naiven Ansatz ist folgendes: I die Anzahl der möglichen Zustandsfolgen für eine ~ der Länge |~ Beobachtungsfolge w w | beträgt |Q||~w | I ~ aus 10 Beobachtungen also falls Q 10 Zustände enthält, w besteht, haben wir bereits 1010 Kandidaten! I Die Anzahl wächst also exponentiell in |~ w |, und ist damit praktisch nicht mehr handhabbar. Christian Wurm HMMs und der Viterbi-Algorithmus Viterbi Algorithmus Vorwärts Algorithmus Die Lösung Wir werden einen Algorithmus betrachten, der dieses Problem mittels dynamischer Programmierung löst, d.h. Teilergebnisse bisheriger Berechnungen werden immer weiter verwendet. Die Parameter des Algorithmus sind: 1. Ein HMM (B, Q, π, τ, δ) ~ über B 2. eine Eingabe w Die Ausgabe ist argmax|~q|=|~w | P(~ w |~q ) Christian Wurm HMMs und der Viterbi-Algorithmus Viterbi Algorithmus Vorwärts Algorithmus Der Viterbi-Algorithmus ~ = b1 , b2 , ...bj+1 , ~q = q1 , q2 , ..., qj+1 . Wir Wir nehmen wiederum w definieren nun αq (i) = maxq1 ,...,qi−1 ∈Q (P(q1 , ..., qi−1 , b1 , ..., bi−1 , qi = q)) (3) αq (i) gibt uns die maximale Wahrscheinlichkeit dafür, dass qi = q, wobei das Maximum bedeutet: maximal für alle Vorgängersequenzen von Zuständen. Christian Wurm HMMs und der Viterbi-Algorithmus Viterbi Algorithmus Vorwärts Algorithmus Der Viterbi Algorithmus 1. Initialisierung: αq (1) = π(q); 2. Induktionsschritt: αq0 (i + 1) = maxq∈Q αq (i)δ(q, q 0 )τ (q 0 , bi+1 ). Parallel werden die entsprechenden Zustände gespeichert: ψq0 (i + 1) = argmaxq∈Q αq (i)δ(q, q 0 )τ (q 0 , bi+1 ). 3. Terminierung: q̂j+1 = argmaxq∈Q αq (j + 1) q̂i = ψq̂i+1 (i + 1). (Wir berechnen jetzt also von hinten nach vorne die optimale Kette) Christian Wurm HMMs und der Viterbi-Algorithmus Viterbi Algorithmus Vorwärts Algorithmus P(~ w |~q ) berechnen q̂i bezeichnet den optimalen i-ten Zustand. Wir können nun sehr leicht P(~ w |~q ) berechnen: P(~ w |qˆ1 , ..., q̂i+1 ) = maxq∈Q αq (i + 1) (4) Was wir nicht haben ist die Wahrscheinlichkeit P(qˆ1 , ..., q̂i+1 |~ w )! Wir haben also nur die plausibelste Lösung gefunden (ähnlich der Maximum Likelihood Methode), ohne dass wir deren bedingte Wahrscheinlichkeit gegeben die Beobachtung kennen würden. Christian Wurm HMMs und der Viterbi-Algorithmus Viterbi Algorithmus Vorwärts Algorithmus Viterbi-Algorithmus: Komplexität I Der Viterbi Algorithmus muss die ganze Folge einmal vorwärts und einmal rückwarts durchlaufen. I Damit ist Anzahl der Rechenschritte damit linear in der Länge der Kette, I quadratisch in der Menge der Zustände. Das ist ein extrem gutes Ergebnis, denn die Zustandsmenge ist a priori begrenzt, es bleibt also effektiv ein lineares Problem Christian Wurm HMMs und der Viterbi-Algorithmus Viterbi Algorithmus Vorwärts Algorithmus Der Vorwärts-Algorithmus Wir werden nun ein etwas anderes Problem betrachten, das wir bereits für Markov Ketten behandelt haben: I Gegeben ein HMM M, eine Kette hb1 , b2 , ..., bi i, was ist die Wahrscheinlichkeit von hb1 , b2 , ..., bi i gegeben M? I Linguistisch gesehen wäre das die Frage: gegeben einen Satz S und ein HMM unserer Sprache, wie wahrscheinlich ist S? Christian Wurm HMMs und der Viterbi-Algorithmus Viterbi Algorithmus Vorwärts Algorithmus Der Vorwärts-Algorithmus Wir haben gesehen, wie wir P(~ w |~q ) ausrechnen. Wie kommen wir zu P(~ w )? Durch die übliche Methode des Marginalisierens: P(~ w) = X P(~ w |~q )P(~q ) (5) |~q |=|~ w| Hier haben wir aber dasselbe Problem wie vorher: die Menge der ~q wächst exponentiell in |~ w | – also ist der naive Ansatz nicht praktikabel. Christian Wurm HMMs und der Viterbi-Algorithmus Viterbi Algorithmus Vorwärts Algorithmus Der Vorwärts-Algorithmus Der Vorwärts-Algorithmus nimmt dieselben Parameter wie der Viterbi-Algorithmus. Wir definieren die Vorwärts-Variable wie folgt: αq (i) := P(hb1 , b2 , ..., bi i, qi = q) (6) αq (i) gibt uns also die Wahrscheinlichkeit, dass wir nach der i-ten ~ in Zustand q sind. Beobachtung in w Christian Wurm HMMs und der Viterbi-Algorithmus Viterbi Algorithmus Vorwärts Algorithmus Der Vorwärts-Algorithmus 1. Initialisierung: αq (1) = π(q). 2. Induktionsschritt: αq0 (i + 1) = 3. Ende: P(~ w) = P q∈Q P q∈Q αq (i)δ(q, q 0 )τ (q 0 , bi+1 ): i < j + 1 αq (j + 1). Christian Wurm HMMs und der Viterbi-Algorithmus Viterbi Algorithmus Vorwärts Algorithmus Der Vorwärts-Algorithmus: Komplexität Auch dieser Algorithmus ist sehr günstig was die nötigen Berechnungen angeht: I ~ mit Länge n zu berechnen, um die Wahrscheinlichkeit von w 2 2|Q| n Berechnungsschritte. I Da aber |Q|, die Anzahl der Zustände, a priori begrenzt ist, können wir sagen dass der Algorithmus linear ist. Christian Wurm HMMs und der Viterbi-Algorithmus
© Copyright 2024 ExpyDoc
