Hidden Markov Model

Ein Hidden Markov Model (engl., kurz HMM, nach Andrei Andrejewitsch Markow) ist ein stochastisches Modell, das sich durch zwei Zufallsprozesse beschreiben lässt. In der Literatur findet sich auch die Bezeichnung Verborgenes Markow-Modell (VMM).

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, hidden). 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.

Definition

Formal definiert man ein Hidden-Markov-Modell als Fünftupel $λ = (S, A, B,π, V)$ mit

$S = {s 1,..., s n}$ - Menge aller Zustände
$A = {a i j}$ - Zustandsübergangsmatrix, wobei $a i j$ die Wahrscheinlichkeit angibt, dass nach Zustand $s i$ in Zustand $s j$ gewechselt wird.
$B = {b 1,..., b n}$ - Menge der Emissionswahrscheinlichkeitsverteilungen bzw. Dichten
$b i (x)$ - Wahrscheinlichkeit im Zustand $s i$ die Beobachtung $x$ zu machen
$π$ - Anfangswahrscheinlichkeitsverteilung mit $π(i)$ Wahrscheinlichkeit, dass $s i$ der Startzustand ist
$V$ - Merkmalsraum (oft als Ausgabealphabet bezeichnet), also der Definitionsbereich von $b i$ . Dieser kann diskret, oder kontinuierlich sein. Je nach dem ist $b i$ eine Wahrscheinlichkeit oder eine Dichte.

Veranschaulichung

Es bedeuten:

x - (verborgene) Zustände des Markow-Modells
a - Übergangswahrscheinlichkeiten
b - Emissionswahrscheinlichkeiten
y - (sichtbare) Ausgabesymbole

Problemstellungen

Im Zusammenhang mit den Hidden-Markov-Modellen existieren drei Problemstellungen.

Das Evaluierungsproblem

Gegeben ist ein Hidden-Markov-Modell $λ$ sowie eine Beobachtung $O$ . Gesucht ist die Wahrscheinlichkeit $P (O | λ)$ (auch Baum-Welch-Score genannt), d. h. die Wahrscheinlichkeit dass die Beobachtung $O$ unter gegebenem Hidden-Markov-Modell $λ$ gemacht wird. Dazu müssen alle Zustandsfolgen $Z$ ,

$\mathcal{Z}=\{(z_1,\ldots,z_T)\,|\,z_t\in S\}=S^T$

betrachtet werden, die $O$ produzieren können. Somit gilt:

$P(\mathcal{O}|\lambda)=\sum_{X \in\mathcal{Z}} P(\mathcal{O},X|\lambda)$

$=\sum_{X\in\mathcal{Z}} P(\mathcal{O}|X,\lambda)P(X|\lambda)$

Dies bedeutet, dass zur Berechnung $| S | T$ und somit exponentiell viele Operationen nötig sind. Ein effizientes Verfahren zur Lösung des Evaluierungsproblems ist der Forward-Algorithmus.

Dekodierungsproblem

Gegeben ist ein Hidden-Markov-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.

Lernproblem

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 aktuelle Wetter herausfinden. 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.

Zur Untersuchung von DNA-Sequenzen mit bioinformatischen Methoden kann das Hidden Markov Model verwendet werden. Beispielsweise lassen sich so CpG-Inseln in einer DNA-Sequenz aufspüren. Dabei stellt die DNA-Sequenz die sichtbaren Zustände (A,G,C,T), während CpG-Insel oder nicht-CpG-Insel die unsichtbaren Zustände darstellen.

Anwendungsgebiete

Mustererkennung, Gen-Vorhersage in der Bioinformatik, Computerlinguistik (insbes. Spracherkennung), Spamfilter (insbesondere Markow-Filter, Gestenerkennung in der Mensch-Maschine-Kommunikation (Robotik), Zeitreihenanalyse, Psychologie

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. Proceedings of the IEEE, Band 77, Nr. 2, S. 257–286, 1989 (PDF; 2,2 MB).
Rainer Merkl, Stephan Waack: Bioinformatik interaktiv. Wiley-VCH, 2002, ISBN 3527306625.
Gernot A. Fink: Mustererkennung mit Markov-Modellen: Theorie, Praxis, Anwendungsgebiete. Teubner, 2003, ISBN 3519004534

Weblinks

http://www.ghmm.org HMM C-Bibliothek, die unter der LGPL frei verfügbar ist
Hidden Markov Model Toolkit (HTK) (Toolkit zum Erstellen und Bearbeiten von Hidden-Markov-Modellen)

Quelle:

Artikel Hidden Markov Model aus der freien Enzyklopädie Wikipedia mit dieser Versionsgeschichte

Lizenz:

GFDL

Kategorien:

Lexikalischer Artikel

Ähnliche Einträge in anderen Lexika

Adelung-1793: Model, der

Brockhaus-1911: Model

Herder-1854: Model

Lueger-1904: Schrägmaß, -model · Reißhaken, -maß, -model, -nadel und -stock · Model

Meyers-1905: Model