Hidden Markov Model

Dieser Artikel enthält mathematische Zeichen, die in der Tabelle mit mathematischen Symbolen erklärt werden.

---

Hidden Markov Models oder meist kurz HMMs sind stochastische Modelle, die auf Markow-Ketten beruhen. Die Symbole in der beobachteten Ausgabesequenz sind dabei von der Markow-Kette entkoppelt, indem zusätzlich zu den Übergangswahrscheinlichkeiten für die internen (versteckten, hidden) Zustände noch Emissionswahrscheinlichkeiten für die Ausgabesymbole in Abhängigkeit von dem internen Zustand in das Modell einfließen.

Veranschaulichung

Es bedeuten:

x - (versteckte) Zustände des Markow-Modells

a - Übergangswahrscheinlichkeiten

b - Emissionswahrscheinlichkeiten

y - (sichtbare) Ausgabesymbole

Beispiel

Ein Gefangener im Kerkerverlies möchte das Wetter kennen. Er weiss, dass auf einen sonnigen Tag zu 70% ein Regentag folgt und dass auf einen Regentag zu 50% ein Sonnentag folgt.

Weiss 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.

Formales Modell

Formal definiert man ein HMM üblicherweise in folgender Notation:

$S_{1}...S_{N}$, Vektor von $N$ Zuständen.

$\Sigma =\{v_{1}...v_{M}\}$, diskretes Emissionsalphabet über $M$ Symbole.

$\pi =(\pi _{1}...\pi _{N})$, Vektor mit Startwahrscheinlichkeiten. $\pi _{i}$ ist die Wahrscheinlichkeit im ersten Zeitschritt im Zustand $S_{i}$ zu sein.

$A=\{a_{ij}\}$, Matrix der Übergangswahrscheinlichkeiten wobei $a_{ij}$ die Wahrscheinlichkeit angibt von Zustand $S_{i}$ zu Zustand $S_{j}$ zu wechseln.

$B=\{b_{ij}\}$, Matrix der Emissionswahrscheinlichkeiten, $b_{ij}$ steht für die Wahrscheinlichkeit das Symbol $v_{j}$ in Zustand $S_{i}$ zu erzeugen.

$\lambda =(A,B,\pi )$, vollständiger Parameter Vektor.

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.

Weblinks

• http://www.ghmm.org eine HMM C-Bibliothek, die unter der LGPL frei verfügbar ist