Hidden Markov Model - LinkFang.de





Hidden Markov Model


Das Hidden Markov Model (englisch, HMM) ist ein stochastisches Modell, in dem ein System durch eine Markow-Kette – benannt nach dem russischen Mathematiker A. A. Markow – mit unbeobachteten Zuständen modelliert wird. Ein HMM kann dadurch als einfachster Spezialfall eines dynamischen bayesschen Netzes angesehen werden.

Die Modellierung als Markow-Kette bedeutet, dass das System auf zufällige Weise von einem Zustand in einen anderen übergeht, wobei die Übergangswahrscheinlichkeiten nur jeweils vom aktuellen Zustand abhängen, aber nicht von den davor eingenommenen Zuständen. Außerdem wird angenommen, dass die Übergangswahrscheinlichkeiten über die Zeit konstant sind. Bei einem HMM werden jedoch nicht diese Zustände selbst von außen beobachtet; sie sind verborgen (engl. hidden). Stattdessen sind jedem dieser inneren Zustände beobachtbare Ausgabesymbole, sogenannte Emissionen, zugeordnet, die je nach Zustand mit gewissen Wahrscheinlichkeiten auftreten. Die Aufgabe besteht meist darin, aus der beobachteten Sequenz der Emissionen zu wahrscheinlichkeitstheoretischen Aussagen über die verborgenen Zustände zu kommen.

Wichtige Anwendungsgebiete sind Spracherkennung, Computerlinguistik und die Bioinformatik, aber unter anderem auch Spamfilter, Gestenerkennung in der Mensch-Maschine-Kommunikation (Robotik), Schrifterkennung und Psychologie.

Markow-Ansatz

Gegeben seien zwei zeitdiskrete Zufallsprozesse [math]\{X_t\}_{t \in \N}[/math] und [math]\{Y_t\}_{t \in \N}[/math], von denen nur der letzte beobachtbar sei. Durch ihn sollen Rückschlüsse auf den Verlauf des ersten Prozesses gezogen werden; hierfür wird ein mathematisches Modell benötigt, das die beiden Prozesse miteinander in Beziehung setzt.

Der hier beschriebene Ansatz zeichnet sich durch die folgenden beiden Annahmen aus:

1. Markow-Eigenschaft

Der aktuelle Wert des ersten Prozesses hängt ausschließlich von seinem letzten Wert ab:

[math]\forall t \in \N \colon P(X_t = x_t | X_1 = x_1; \ldots; X_{t-1} = x_{t-1}; Y_1 = y_1; \ldots; Y_t = y_t ) = P(X_t = x_t | X_{t-1} = x_{t-1})[/math]
2. Markow-Eigenschaft

Der aktuelle Wert des zweiten Prozesses hängt ausschließlich vom aktuellen Wert des ersten ab:

[math]\forall t \in \N \colon P(Y_t = y_t | X_1 = x_1; \ldots; X_t = x_t; Y_1 = y_1; \ldots; Y_{t-1} = y_{t-1}) = P(Y_t = y_t | X_t = x_t)[/math]

Haben die beiden Prozesse nun noch jeweils einen endlichen Wertevorrat, so lässt sich das so gewonnene Modell als probabilistischer Automat auffassen, genauer als Markow-Kette. Man sagt auch [math]\{X_t\}[/math] ist ein Markow-Prozess. Angelehnt an den Sprachgebrauch in der theoretischen Informatik – insbesondere der Automatentheorie und der Theorie formaler Sprachen – heißen die Werte des ersten Prozesses Zustände und die des zweiten Emissionen bzw. Ausgaben.

Definition

Ein Hidden Markov Model ist ein 5-Tupel [math]\lambda = (S;V;A;B;\pi)[/math] mit:

  • [math]S = \{s_1; \dotsc; s_n \}[/math] der Menge aller Zustände, das sind die möglichen Werte der Zufallsvariablen [math]X_t[/math]
  • [math]V = \{v_1; \dotsc; v_m \}[/math] das Alphabet der möglichen Beobachtungen – die Emissionen der [math]Y_t[/math]
  • [math]A \in \R^{n \times n}[/math] die Übergangsmatrix zwischen den Zuständen, [math]a_{ij}[/math] gibt dabei jeweils die Wahrscheinlichkeit an, dass vom Zustand [math]s_i[/math] in den Zustand [math]s_j[/math] gewechselt wird
  • [math]B \in \R^{n \times m}[/math] die Beobachtungsmatrix, die [math]b_i(v_j)[/math] geben die Wahrscheinlichkeit an, im Zustand [math]s_i[/math] die Beobachtung [math]v_j[/math] zu machen
  • [math]\pi \in \R^n[/math] die Anfangsverteilung, [math]\pi_i = P(X_1 = s_i)[/math] ist die Wahrscheinlichkeit, dass [math]s_i[/math] der Startzustand ist

Ein HMM heiße stationär (oder auch zeitinvariant), wenn sich die Übergangs- und Emissionswahrscheinlichkeiten nicht mit der Zeit ändern. Diese Annahme ist oft sinnvoll, weil auch die modellierten Naturgesetze konstant sind.

Veranschaulichung

Das Bild zeigt die generelle Architektur eines instanziierten HMMs. Jedes Oval ist die Repräsentation einer zufälligen Variable [math]x(t)[/math] oder [math]y(t)[/math], welche beliebige Werte aus [math]S[/math] bzw. [math]V[/math] annehmen kann. Die erste Zufallsvariable ist dabei der versteckte Zustand des HMMs zum Zeitpunkt [math]t[/math], die zweite ist die Beobachtung zu diesem Zeitpunkt. Die Pfeile in dem Trellis-Diagramm bedeuten eine bedingte Abhängigkeit.

Im Diagramm sieht man, dass der Zustand der versteckten Variable [math]x(t)[/math] nur vom Zustand der Variable [math]x(t-1)[/math] abhängt, frühere Werte haben keinen weiteren Einfluss. Deshalb ist das Modell ein Markov-Modell 1. Ordnung. Sollten höhere Ordnungen benötigt werden, so können diese durch das Einfügen neuer versteckter Zustände stets auf die 1. Ordnung zurückgeführt werden. Der Wert von [math]y(t)[/math] hängt weiter ausschließlich von [math]x(t)[/math] ab.

Beispiel

Gefangener im Verlies

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 durch Beobachtung der Wärterschuhe Rückschlüsse über das Wetter ziehen (das heißt, er kann die Wahrscheinlichkeit für Regenwetter gegenüber sonnigem Wetter abschätzen).

DNA-Sequenz: CpG-Inseln aufspüren

Zur Untersuchung von DNA-Sequenzen mit bioinformatischen Methoden kann das HMM verwendet werden. Beispielsweise lassen sich so CpG-Inseln in einer DNA-Sequenz aufspüren. Dies sind Bereiche eines DNS-Einzelstrangs mit einem erhöhten Anteil von aufeinanderfolgenden Cytosin- und Guanin-Nukleinbasen. Dabei stellt die DNA-Sequenz die Beobachtung dar, deren Zeichen [math]V = \{A,C,G,T\}[/math] bilden das Ausgabealphabet. Im einfachsten Fall besitzt das HMM zwei verborgene Zustände, nämlich CpG-Insel und nicht-CpG-Insel. Diese beiden Zustände unterscheiden sich in ihrer Ausgabeverteilung, so dass zum Zustand CpG-Insel mit größerer Wahrscheinlichkeit Zeichen [math]C[/math] und [math]G[/math] ausgegeben werden.

Spracherkennung

In der automatischen Spracherkennung mit HMM werden die gesprochenen Laute als versteckte Zustände aufgefasst und die tatsächlich hörbaren Töne als Emission.

Problemstellungen

Im Zusammenhang mit HMMs existieren mehrere grundlegende Problemstellungen.[1][2]

Bestimmen der Modellgröße

Gegeben sind die beobachtbaren Emissionen [math]V[/math]. Es ist zu klären, welche Modelleigenschaften – insbesondere welche orthogonale Dimensionalität – den Schluss auf die nicht direkt beobachtbaren Zustände erlauben und gleichzeitig eine sinnvolle Berechenbarkeit zulassen. Insbesondere ist zu entscheiden, welche Laufzeit für die Modellrechnungen erforderlich werden darf, um die Verwendbarkeit der Schätzungen zu erhalten.

Implementierung

Die Berechnung der Schätzwerte der nicht beobachtbaren Zustände aus den beobachtbaren Ausgabesequenzen muss die erreichbaren numerischen Genauigkeiten beachten. Weiter müssen Kriterien zur Klassifizierung der statistischen Signifikanz implementiert werden. Bei Verwendung eines HMM für einen bestimmten Merkmalsvektor bestimmt die Signifikanz die Wahrscheinlichkeit einer zutreffenden oder falschen Modellhypothese sowie deren Informationsgehalt (Entropie, Bedingte Entropie) bzw. deren Informationsqualität.

Filtern

Gegeben sei ein HMM [math]\lambda[/math] sowie eine Beobachtungssequenz [math]\boldsymbol o \in V^*[/math] der Länge [math]T[/math]. Gesucht ist die Wahrscheinlichkeit [math]P(X_T = s_i|\boldsymbol o;\lambda)[/math], dass der momentane verborgene Zustand zum letzten Zeitpunkt [math]T[/math] gerade [math]s_i[/math] ist. Ein effizientes Verfahren zur Lösung des Filterungsproblems ist der Forward-Algorithmus.

Prädiktion/Vorhersage

Gegeben sei wieder ein HMM [math]\lambda[/math] und die Beobachtungssequenz [math]\boldsymbol o[/math] sowie ein [math]\delta \ge 1[/math]. Gesucht ist Wahrscheinlichkeit [math]P(X_{T+\delta} = s_i|\boldsymbol o;\lambda)[/math], also die Wahrscheinlichkeit, dass sich das HMM zum Zeitpunkt [math]T+\delta[/math] im Zustand [math]s_i[/math] befindet, falls die betreffende Ausgabe beobachtet wurde. Prädiktion ist dabei gewissermaßen wiederholtes Filtern ohne neue Beobachtungen und lässt sich auch einfach mit dem Forward-Algorithmus berechnen.

Glätten

Erneut seien [math]\lambda[/math], [math]\boldsymbol o[/math] und ein [math]\delta[/math] gegeben. Gesucht ist die Wahrscheinlichkeit [math]P(X_{T-\delta} = s_i|\boldsymbol o;\lambda)[/math], also die Wahrscheinlichkeit, dass sich das Modell zu einem früheren Zeitpunkt in einem bestimmten Zustand befand, unter der Bedingung, dass [math]\boldsymbol o[/math] beobachtet wurde. Mit Hilfe des Forward-Backward-Algorithmus kann diese Wahrscheinlichkeit effizient berechnet werden.

Dekodierung

Seien wieder [math]\lambda[/math] sowie [math]\boldsymbol o[/math] gegeben. Es soll die wahrscheinlichste Zustandsfolge aus [math]S^*[/math] bestimmt werden, die eine vorgegebene Ausgabesequenz erzeugt haben könnte. Dieses Problem lässt sich effizient mit dem Viterbi-Algorithmus lösen.

Lernproblem

Gegeben sei nur die Ausgabesequenz [math]\boldsymbol o[/math]. Es sollen die Parameter eines HMM bestimmt werden, die am wahrscheinlichsten die Ausgabesequenz erzeugen. Dies ist lösbar mit Hilfe des Baum-Welch-Algorithmus.

Interpretationsproblem

Gegeben seien nur die möglichen Ausgaben [math]V[/math]. Es sollen die Zustände im Modellsystem und die korrespondierenden Effekte im realen System identifiziert werden, die die Zustandsmenge [math]S[/math] des Modells beschreibt.[3] Dazu muss vorweg die Bedeutsamkeit der einzelnen Emissionen bestimmt werden.

Anwendungsgebiete

Anwendung finden HMMs häufig in der Mustererkennung bei der Verarbeitung von sequentiellen Daten, beispielsweise bei physikalischen Messreihen, aufgenommenen Sprachsignalen oder Proteinsequenzen. Dazu werden die Modelle so konstruiert, dass die verborgenen Zustände semantischen Einheiten entsprechen (z. B. Phoneme in der Spracherkennung), die es in den sequentiellen Daten (z. B. Kurzzeit-Spektren des Sprachsignals) zu erkennen gilt. Eine weitere Anwendung besteht darin, für ein gegebenes HMM durch eine Suche in einer Stichprobe von sequentiellen Daten solche Sequenzen zu finden, die sehr wahrscheinlich von diesem HMM erzeugt sein könnten. Beispielsweise kann ein HMM, das mit Vertretern einer Proteinfamilie trainiert wurde, eingesetzt werden, um weitere Vertreter dieser Familie in großen Proteindatenbanken zu finden.

Geschichte

Hidden-Markov-Modelle wurden erstmals von Leonard E. Baum und anderen Autoren in der zweiten Hälfte der 1960er Jahre publiziert. Eine der ersten Applikationen war ab Mitte der 1970er die Spracherkennung. Seit Mitte der 1980er wurden HMMs für die Analyse von Nukleotid- und Proteinsequenzen eingesetzt und sind seitdem fester Bestandteil der Bioinformatik.

Einzelnachweise

  1. L. R. Rabiner: A Tutorial on Hidden Markov Models and Selected Applications in Speech Recognition. (PDF, 2.2 MB) Proceedings of the IEEE, Band 77, Nr. 2, S. 257–286, 1989.
  2. P. Blunsom: Hidden Markov Models (PDF; 237 kB).
  3. S. P. Chatzis: A Variational Bayesian Methodology for Hidden Markov Models .

Literatur

  • R. Merkl, S. Waack: Bioinformatik interaktiv. Wiley-VCH, 2002, ISBN 3-527-30662-5.
  • G. A. Fink: Mustererkennung mit Markov-Modellen: Theorie, Praxis, Anwendungsgebiete. Teubner, 2003, ISBN 3-519-00453-4.
  • Kai-Fu Lee, Hsiao-Wuen Hon: Speaker-Independent Phone Recognition Using Hidden Markov Models. IEEE Transactions on accoustics, speech and signal processing, Nr. 37. IEEE, November 1989, S. 1641–1648 (englisch, IEEE Nr. 8930533, 0096-3518/89/1100-1641).

Weblinks


Kategorien: Computerlinguistik | Maschinelles Lernen | Stochastik

Quelle: Wikipedia - http://de.wikipedia.org/wiki/Hidden Markov Model (Vollständige Liste der Autoren des Textes [Versionsgeschichte])    Lizenz: CC-by-sa-3.0

Änderungen: Alle Bilder mit den meisten Bildunterschriften wurden entfernt. Ebenso alle zu nicht-existierenden Artikeln/Kategorien gehenden internen Wikipedia-Links (Bsp. Portal-Links, Redlinks, Bearbeiten-Links). Entfernung von Navigationsframes, Geo & Normdaten, Mediadateien, gesprochene Versionen, z.T. ID&Class-Namen, Style von Div-Containern, Metadaten, Vorlagen, wie lesenwerte Artikel. Ansonsten sind keine Inhaltsänderungen vorgenommen worden. Weiterhin kann es durch die maschinelle Bearbeitung des Inhalts zu Fehlern gerade in der Darstellung kommen. Darum würden wir jeden Besucher unserer Seite darum bitten uns diese Fehler über den Support mittels einer Nachricht mit Link zu melden. Vielen Dank!

Stand der Informationen: August 201& - Wichtiger Hinweis: Da die Inhalte maschinell von Wikipedia übernommen wurden, ist eine manuelle Überprüfung nicht möglich. Somit garantiert LinkFang.de nicht die Richtigkeit und Aktualität der übernommenen Inhalte. Sollten die Informationen mittlerweile fehlerhaft sein, bitten wir Sie darum uns per Support oder E-Mail zu kontaktieren. Wir werden uns dann innerhalb von spätestens 10 Tagen um Ihr Anliegen kümmern. Auch ohne Anliegen erfolgt mindestens alle drei Monate ein Update der gesamten Inhalte.