Hidden Markov Model
aus Freepedia, der freien Wissensdatenbank
Ein Hidden Markov Model (englisch, nach Andrei Andrejewitsch Markow, zu deutsch etwa Verborgenes Markow-Modell, kurz HMM) ist ein stochastisches Modell, das sich durch zwei Zufallsprozesse beschreiben läßt.
Der erste Zufallsprozess entspricht dabei einer Markow-Kette, die durch Zustände und Übergangswahrscheinlichkeiten gekennzeichnet ist. Die Zustände der Kette sind von außen jedoch nicht direkt sichtbar (sie sind verborgen). Stattdessen erzeugt ein zweiter Zufallsprozess zu jedem Zeitpunkt beobachtbare Ausgangssymbole gemäß einer zustandsabhängigen Wahrscheinlichkeitsverteilung. Die Aufgabe besteht häufig darin, aus der Sequenz der Ausgabesymbole auf die Sequenz der verborgenen Zustände zu schließen.
Inhaltsverzeichnis |
Formales Modell
Formal definiert man ein verborgenes Markow-Modell üblicherweise in folgender Notation:
- <math> S_{1} ... S_{N}</math>, Vektor von <math>N</math> Zuständen.
- <math>\Sigma = \{ v_{1} ... v_{M}\}</math>, diskretes Emissionsalphabet über <math>M</math> Symbole.
- <math>\pi = (\pi_{1}...\pi_{N})</math>, Vektor mit Startwahrscheinlichkeiten.
- <math>\pi_{i}</math> ist die Wahrscheinlichkeit im ersten Zeitschritt im Zustand <math>S_{i}</math> zu sein.
- <math>A=\{a_{ij}\} </math>, Matrix der Übergangswahrscheinlichkeiten wobei <math>a_{ij}</math> die Wahrscheinlichkeit angibt von Zustand <math>S_{i}</math> zu Zustand <math>S_{j}</math> zu wechseln.
- <math>B=\{b_{ij}\}</math>, Matrix der Emissionswahrscheinlichkeiten,
- <math>b_{ij}</math> steht für die Wahrscheinlichkeit das Symbol <math>v_{j}</math> in Zustand <math>S_{i}</math> zu erzeugen.
- <math>\lambda = (A,B,\pi)</math>, vollständiger Parameter Vektor.
Veranschaulichung
Es bedeuten:
- x - (verborgene) Zustände des Markow-Modells
- a - Übergangswahrscheinlichkeiten
- b - Emissionswahrscheinlichkeiten
- y - (sichtbare) Ausgabesymbole
Problemstellungen
Im Zusammenhang mit den verborgenen Markow-Modellen existieren folgende Problemstellungen:
- Gegeben ist ein verborgenes Markow-Modell. Es soll die Wahrscheinlichkeit einer speziellen Ausgabesequenz bestimmt werden. Lösbar mit Hilfe des Forward-Algorithmus.
- Gegeben ist ein verborgenes Markow-Modell. Es soll die wahrscheinlichste Sequenz der (versteckten, hidden) Zustände bestimmt werden, die eine vorgegebene Ausgabesequenz erzeugt hat. Lösbar mit Hilfe des Viterbi-Algorithmus.
- Gegeben ist nur die Ausgabesequenz. Es sollen die Parameter des HMM bestimmt werden, die am wahrscheinlichsten die Ausgabesequenz erzeugen. Lösbar mit Hilfe des Baum-Welch-Algorithmus.
Beispiel
Ein Gefangener im Kerkerverlies möchte das Wetter kennen. Er weiß, dass auf einen sonnigen Tag zu 70 % ein Regentag folgt und dass auf einen Regentag zu 50 % ein Sonnentag folgt.
Weiß er zusätzlich, dass die Schuhe der Wärter bei Regen zu 90 % dreckig, bei sonnigem Wetter aber nur zu 60 % dreckig sind, so kann er aus Beobachtung der Wärterschuhe Rückschlüsse über das Wetter ziehen.
Anwendungsgebiete
Mustererkennung, Gen-Vorhersage in der Bioinformatik, Computerlinguistik (insbes. Spracherkennung), Zeitreihenanalyse
Zum Beispiel kann beim computergestützten Lesen von Handschriften mit dieser Methode das Wort in seiner Gesamtheit erfasst werden und nicht Buchstabe für Buchstabe. Die Buchstaben sind bei Schreibschrift oft schwer trennbar.
Literatur
- Lawrence R. Rabiner: A Tutorial on Hidden Markov Models and Selected Applications in Speech Recognition. 1989
- Rainer Merkl, Stephan Waack: Bioinformatik interaktiv. Wiley-VCH, 2002, ISBN 3527306625
Weblinks
- http://www.ghmm.org HMM C-Bibliothek, die unter der LGPL frei verfügbar ist
