Algorithmen für Hidden-Markov-Models
Arbeitet man mit Hidden-Markov-Models, wird man mit einer Vielzahl von Algorithmen erschlagen, die häufig auch noch ähnliche Namen tragen. Ich will einen kurzen Überblick darüber geben, welche Algorithmen welches Informationsbedürfnis erfüllen und wann sie eingesetzt werden.
Generell kann man bei Hidden-Markov-Models von drei Grundproblemen sprechen:
- Evaluierungsproblem: Gegeben ein HMM und eine Beobachtung, was ist die Wahrscheinlichkeit \(P(O \vert \lambda)\)
- Dekodierungsproblem: Was ist die wahrscheinlichste Sequenz von versteckten Zuständen
- Lernproblem: Wie müssen wir die HMM-Parameter anpassen, um die Wahrscheinlichkeit \(P(O \vert \lambda)\) zu maximieren
Die verschiedenen Algorithmen bei der Arbeit mit Hidden-Markov-Models können nun diesen Problemen zugeordnet werden.
- Evaluierungsproblem: Forward-Algorithmus, Backward-Algorithmus
- Dekodierungsproblem: Viterbi-Algorithmus (=Viterbi-Decoding), Forward-Backward-Algorithmus
- Lernproblem: Baum-Welch-Algorithmus
Besonders interessant beim Dekodierungsproblem ist, dass die Wahl des Gütekriteriums “wahrscheinlichste Sequenz” nicht festgelegt ist. Vielmehr gibt es mehrere mögliche Kriterien, die man zur Wahl der besten Sequenz anlegen kann. Der Viterbi-Algorithmus bildet die maximale a-posteriori-Wahrscheinlichkeit über die gesamte Menge von möglichen Pfaden durch den Graphen.
Der Forward-Backward-Algorithmus hingegen maximiert die Wahrscheinlichkeit zu jedem einzelnen Zeitpunkt und fügt diese aneinander. Insbesondere könnten hierbei Zustandsequenzen entstehen, deren Übergänge laut Übergangswahrscheinlichkeitsmatrix gar nicht erlaubt sind (Rabiner, 1989).
I do not maintain a comments section. If you have any questions or comments regarding my posts, please do not hesitate to send me an e-mail to blog@stefan-koch.name.