Zurück: Standardmethoden von HMMs II
Inhalt
Weiter: Exkurs: Gaussian Mixtures
Index
Leitfragen
- Wie kriegt man die wahrscheinlichste Zustandsfolge mit erträglichem Rechenaufwand raus?
Warum braucht man dazu zwei Trellise?
Der Viterbi-Algorithmus findet zu jeder Beobachtung O die wahrscheinlichste Zustandsfolge X, die ein HMM bei der Ausgabe von Ogenommen hat.
Wir definieren uns ein Trellis
φj (t) enthält also an jeder Stelle die Wahrscheinlichkeit des wahrscheinlichsten Weges, der unter Emission von o1
ot-1 zumZustand j zur Zeit t führt. Wir brauchen aber noch zusätzlich die Information, welcher Weg das war. Diese Information wird uns dasunten definierte zweite Trellis ψ liefern.
Die Initialisierung ist wie gewohnt: φi(t) = δij mit dem Startzustand j.
Wir arbeiten uns nach vorne durch,
undmerken uns, woher wir jeweils gekommen sind:
Der Operator argmax bestimmt das Argument des Maximalwerts, wobei das Argument das ist, worüber die Maximierungsoperationläuft. Im Fall oben ist das das i, so dass wir in ψ gerade speichern, woher unser φ kam. Wir werden das brauchen, um uns wiederzurückzuhangeln.
Wenn unsere beiden Trellises gefüllt sind, suchen wir von hinten startend die wahrscheinlichste Sequenz 
:
Trelliseim Viterbi-Algorithmus für die Eingabe 01011100 und unser Schwarzweiß-HMM:
| oj | φ | ψ | ||||
| W | B | E | W | B | E | |
| 0 | 0.0 | - | - | - | - | - |
| 1 | 0.40 | 1.3 | - | W | W | - |
| 0 | 1.4 | 0.74 | 2.6 | W | W | B |
| 1 | 1.8 | 2.0 | 1.1 | W | B | B |
| 1 | 2.8 | 2.1 | 1.8 | W | W | E |
| 1 | 3.8 | 2.5 | 2.5 | W | B | E |
| 0 | 4.8 | 2.8 | 3.2 | W | B | E |
| 0 | 5.2 | 4.1 | 3.2 | W | B | B |
| - | 5.6 | 5.4 | 3.3 | W | B | E |
Die Wahrscheinlichkeiten sind als negative dekadische Logarithmen gegeben, 4.61 bedeutet etwa 10-4.61 ≈2.45 ×10-5. Für sokleine Zahlen ist das bequemer, und in der Tat lohnt es sich, den Viterbi-Algorithmus komplett in Logarithmen zuimplementieren.
Ein - als Quellzustand bedeutet, dass es keinen Weg zum entsprechenden Zustand gibt. Da unsere HMMs beim Übergangemittieren, durchlaufen sie für n Eingabezeichen n+ 1 Zustände, weshalb beim letzten Eingabezeichen nur ein Strichsteht.
Readout (von hinten): E, E, B, B, B, W, W, W mit Wahrscheinlichkeit 10-3.3. Der schwarze Strich geht wahrscheinlich von Spalte 4bis Spalte 6.
Dabei interessiert uns jeweils der Zustand, in den das System auf dem wahrscheinlichsten Pfad bei ” Emission“ des jeweiligen Zeichensgegangen ist. Ganz am Schluss war das ein E. Dessen Quelle war laut ψ wieder ein E (in der Zeile darüber), dessen Quelle wiederum einB und so weiter. Für die erste Zeile schreiben wir gar keinen Zustand auf, da ja das System hier noch gar kein Zeichen gelesen hatte,um in den Zustand zu kommen.
Übungen zu diesem Abschnitt
Ihr solltet euch wenigstens an den rötlich unterlegten Aufgaben versuchen
(1)
Besorgt euch das Programm hmm.py von der Vorlesungsseite. Das Programm benötigt das markovmodel-Modul von der Folie”Markov-Ketten“.
Seht euch darin die HMM-Klasse an. Sie macht zunächst für die Ausgabesymbole, was die MarkovModel-Klasse schon für die Zuständegemacht hat: Die Ausgabesymbole werden aufgezählt, so dass wir intern nur noch Zahlen zwischen 0 und n-1 verwenden( computeEmissionMapping).
Das ist für ein nacktes Markov-Modell kein großer Vorteil, hilft aber, wenn wir nachher unsere ” Standardfragen“ beantworten wollen.Ebenfalls analog zu MarkovModel berechnen wir sowohl eine Übergangsverteilung (_computeEmissionMatrix) als auchVerteilungsfunktionen für die Ausgaben der Übergänge, die wir wieder beim Generieren brauchen (_computeOutputDfs) und dienach Notwendigkeit von driveOn aufgerufen wird. driveOn wiederum greift auf das driveOn des MarkovModels zu undberechnet zusätzlich die Ausgaben.
(2)
Probiert die HiddenMarkovModel-Klasse aus. Folgende Beschreibung baut einen HMM ähnlich dem in der Vorlesung besprochenen füreinen schwarzen Streifen:
{"whitebefore":{"blackstrip":0.1,"whitebefore":0.9},"blackstrip":{"whiteafter":0.1,"blackstrip":0.9},"whiteafter":{"whiteafter":1},}---{"whitebefore":1}---+whitebefore-whitebefore+{'0':0.8,'1':0.2}+-++whitebefore-blackstrip+{'1':0.9,'0':0.1}+-++blackstrip-blackstrip+{'1':0.9,'0':0.1}+-++blackstrip-whiteafter+{'1':0.1,'0':0.9}+-++whiteafter-whiteafter+{'0':0.8,'1':0.2}+-+Schreibt das in eine Datei, deren Inhalt ihr dem HMM-Konstruktor übergebt, ruft dessen setUpInitDf-Methode auf undlasst euch das Resultat der getAnOutput-Methode für, sagen wir, 30Schritte ausgeben. Erklärt, was ihr seht.
(3)
Bei den meisten nützlichen Anwendungen von HMMs hat man als Trainingsdaten die versteckten Variablen zusammen mit derAusgabe (z.B.handgetaggte Korpora). Unter diesen Umständen braucht man kein EM-Training, sondern kann einfach die relevantenParameter des HMM (Übergangs- und Emissionswahrscheinlichkeiten) schätzen. Wir wollen das hier schlicht mit ML machen (warumwäre für das Pixelstreifen-Modell SGT nicht gut?).
Seht euch die Funktion estimateModelParameters an – sie will eine Liste von Listen der Art, wie sie HMM.getAnOutputzurückgibt. Erzeugt euch also einen Schwung Ausgaben, übergebt sie an estimateModelParameters und seht, wie gut dieSchätzung so wird.
estimateModelParameters tut so, als würde es eine Eingabe für den Konstruktor von HMM ausgeben. Dabei fehlt allerdings dieAnfangsverteilung. Vielleicht wollt ihr das ja noch nachrüsten?
(4)
Um zu sehen, wie viel man von Viterbi erwarten kann, wollen wir jetzt die tatsächlich von einem gegebenen HMM durchlaufenenZustandsfolgen mit dem vergleichen, was Viterbi ausgibt. Das wird von probD gemacht. Versucht, zu verstehen, was diese Funktion tutund probiert sie dann aus. Damit die Ausgabe etwas übersichtlicher wird, ist es klug, die versteckten Zustände oben umzubenennen,etwa so:
{"(":{"_":0.1,"(":0.9},"_":{")":0.1,"_":0.9},")":{")":1},}---{"(":1}---+(-(+{'0':0.8,'1':0.2}+-++(-_+{'1':0.9,'0':0.1}+-++_-_+{'1':0.9,'0':0.1}+-++_-)+{'1':0.1,'0':0.9}+-++)-)+{'0':0.8,'1':0.2}+-+Überlegt euch, warum es gar nicht zu erwarten ist, dass der Viterbi die tatsächliche Zustandsfolge immer findet. Versucht, die Irrtümerzu erklären.
Dateien zu diesem Abschnitt
- hmm.py -- Eine Implementation von HMMs inklusive Forward und Viterbi
Zurück: Standardmethoden von HMMs II
Inhalt
Weiter: Exkurs: Gaussian Mixtures
Index
Markus Demleitner
Copyright Notice
