Quelltext der Seite Hidden Markov Model

Das '''Hidden Markov Model''', kurz '''HMM''' ({{deS}} ''verdecktes Markowmodell'', oder ''verborgenes Markowmodell'') ist ein [[Stochastik|stochastisches]] [[Mathematisches Modell|Modell]], in dem ein System durch eine [[Markowkette]] – benannt nach dem russischen Mathematiker [[Andrei Andrejewitsch Markow (Mathematiker, 1856)|A. A. Markow]] – mit unbeobachteten Zuständen modelliert wird.
Ein HMM kann dadurch als einfachster Spezialfall eines [[Bayessches Netz|dynamischen bayesschen Netzes]] angesehen werden.

Die Modellierung als Markowkette bedeutet, dass das System auf zufällige Weise von einem Zustand in einen anderen übergeht, wobei die [[Übergangswahrscheinlichkeit]]en 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 die Zustände selbst von außen beobachtet; sie sind ''verborgen'' (engl. ''hidden'', siehe auch [[Latentes Variablenmodell]]). 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 [[Wahrscheinlichkeitstheorie|wahrscheinlichkeitstheoretischen]] Aussagen über die verborgenen Zustände zu kommen.

Da die Markowmodelle eng verwandt mit den in der [[Regelungstechnik]] verwendeten Zustandsraummodellen sind, ist darauf zu achten, dass der Begriff „beobachten“ nicht mit dem regelungstechnischen Begriff der „[[Beobachter (Regelungstechnik)|Beobachtbarkeit]]“, der von [[Rudolf Kálmán]] 1960 eingeführt wurde und eine eigenständige Systemeigenschaft beschreibt, verwechselt wird. „Beobachten“ im Sinn der Markowmodelle wird in der Regelungstechnik mit „messen“ bezeichnet. Die im Sinn der Markowtheorie „unbeobachteten“ oder „hidden“ Zustände können sehr wohl im Sinne der Regelungstechnik beobachtbar sein, müssen es aber nicht.

Wichtige Anwendungsgebiete sind [[Spracherkennung|Sprach-]] und [[Schrifterkennung]], [[Computerlinguistik]] und [[Bioinformatik]], [[Spamfilter]], [[Gestenerkennung]] in der [[Mensch-Maschine-Kommunikation]], [[physikalische Chemie]]<ref>S. Schmid, Dissertation, Technische Universität München, München, 2017. [https://mediatum.ub.tum.de/?id=1339594 ''Single Protein Dynamics at Steady State Quantified from FRET Time Traces'']</ref> und [[Psychologie]].

== Markowansatz ==
Gegeben seien zwei [[Zufallsprozess#Einteilung|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. Markoweigenschaft
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-1} = y_{t-1} ) = P(X_t = x_t | X_{t-1} = x_{t-1})</math>.

; 2. Markoweigenschaft
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 [[Wahrscheinlichkeitstheorie|probabilistischer]] [[Automat (Informatik)|Automat]] auffassen, genauer als ''Markow-Kette''.
Man sagt auch <math>\{X_t\}</math> ist ein ''[[Markow-Prozess#Diskrete Zeit und endliche Zustandsmenge|Markow-Prozess]]''.
Angelehnt an den Sprachgebrauch in der [[Theoretische Informatik|theoretischen Informatik]] – insbesondere der [[Automatentheorie]] und der [[Formale Sprache|Theorie formaler Sprachen]] – heißen die Werte des ersten Prozesses ''Zustände'' und die des zweiten ''Emissionen'' bzw. ''Ausgaben''.

== Definition ==
[[Datei:HiddenMarkovModel.svg|mini|Parameter eines Hidden Markov Model (Beispiel)<br />
''x'' – (verborgene) Zustände<br />
''y'' – mögliche Beobachtungen (Emissionen)<br />
''a'' – Übergangswahrscheinlichkeiten<br />
''b'' – Emissionswahrscheinlichkeiten]]

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 [[Zufallsvariable]]n <math>X_t</math>,
* <math>V = \{v_1; \dotsc; v_m \}</math> das [[Alphabet (Mathematik)|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} = P(X_t = s_j | X_{t-1} = s_i)</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_{ij}  = P( Y_t=v_j | X_t = s_i)</math> geben die Wahrscheinlichkeit an, im Zustand <math>s_i</math> die Beobachtung <math>v_j</math> zu machen, sowie
* <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 ==
[[Datei:hmm temporal bayesian net.svg|mini|hochkant=2|Zeitliche Entwicklung eines HMM]]
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 [[Relative Häufigkeit|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.&nbsp;Ordnung. Sollten höhere Ordnungen benötigt werden, so können diese durch das Einfügen neuer versteckter Zustände stets auf die 1.&nbsp;Ordnung zurückgeführt werden. Der Wert von <math>y(t)</math> hängt weiter ausschließlich von <math>x(t)</math> ab.

{{Absatz}}

== Beispiel ==
=== Gefangener im Verlies ===
[[Datei:Hidden markov model.svg|mini]]
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). Hier bildet das tatsächlich vorhandene, aber nicht sichtbare Wetter den zu ermittelnden versteckten Zustand, die Prozentwerte 70 % und 50 % sind (über längere Zeiten hinweg ermittelte) Trainingsdaten des Modells, und die tatsächlich beobachtbaren Zustände liegen im jeweiligen Aussehen der Schuhe.

Aus den Übergangswahrscheinlichkeiten <math>a_{ij}</math> ergibt sich (langfristig, also ohne den Anfangszustand eingehen zu lassen) die Wahrscheinlichkeit für Sonne von <math>p_\mathrm{S} = 50\%/(50\%+70\%) \approx 41{,}7 \%</math> und für Regen von <math>p_\mathrm{R} = 1 - p_\mathrm{S} \approx 58{,}3\%</math>. Damit ergeben sich die Kombinationen von Zuständen mit den Wahrscheinlichkeiten:
{| class="wikitable"
!  
! Sonne
! Regen
|-
! Saubere Schuhe
| <math>0{,}4 \cdot p_\mathrm{S} \approx 16{,}7\%</math>
| <math>0{,}1 \cdot p_\mathrm{R} \approx  5{,}8\%</math>
|-
! Dreckige Schuhe
| <math>0{,}6 \cdot p_\mathrm{S} \approx 25{,}0\%</math>
| <math>0{,}9 \cdot p_\mathrm{R} \approx 52{,}5\%</math>
|-
|}
Wenn ein Wärter saubere Schuhe hat, ist die Wahrscheinlichkeit von sonnigem Wetter damit <math>0{,}4 \cdot p_\mathrm{S} / (0{,}4 \cdot p_\mathrm{S} + 0{,}1 \cdot p_\mathrm{R}) \approx 74{,}1\%</math> und entsprechend ist bei dreckigen Schuhen die Regenwahrscheinlichkeit etwa 67,9 %. Außerdem müssten die Wärter im Mittel zu <math>0{,}4 \cdot p_\mathrm{S} + 0{,}1 \cdot p_\mathrm{R} = 22{,}5\%</math> der Tage saubere Schuhe haben, andernfalls kann sich der Gefangene überlegen, welche Parameter angepasst werden sollten, damit sein Modell stimmt.

So weit kann der Gefangene aus der Beobachtung an einem einzelnen Tag schließen. Dabei berücksichtigt er nicht die konkreten Wahrscheinlichkeiten des Wechsels von sonnigen und verregneten Tagen. Bezieht er diese mit ein, so kommt er mit dem [[Viterbi-Algorithmus]] zu einem etwas genaueren Ergebnis.

=== DNA-Sequenz: CpG-Inseln aufspüren ===
Zur Untersuchung von DNA-Sequenzen mit bioinformatischen Methoden kann das HMM verwendet werden. Beispielsweise lassen sich so [[CpG-Insel]]n in einer DNA-Sequenz aufspüren. Dies sind Bereiche eines [[Desoxyribonukleinsäure|DNS]]-Einzelstrangs mit einem erhöhten Anteil von aufeinanderfolgenden [[Cytosin]]- und [[Guanin]]-[[Nukleinbase]]n. Dabei stellt die DNS-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'' [[Laut]]e als versteckte Zustände aufgefasst und die tatsächlich ''hörbaren'' [[Tongemisch|Töne]] als Emission.

== Problemstellungen ==
Im Zusammenhang mit HMMs existieren mehrere grundlegende Problemstellungen.<ref>L. R. Rabiner: [http://www.cs.ubc.ca/~murphyk/Bayes/rabiner.pdf ''A Tutorial on Hidden Markov Models and Selected Applications in Speech Recognition.''] (PDF; 2,2&nbsp;MB; 30 Seiten) Proceedings of the IEEE, Band 77, Nr. 2, 1989, S. 257–286.</ref><ref>P. Blunsom, 19. August 2004: [https://web.archive.org/web/20111125100934/http://digital.cs.usu.edu/~cyan/CS7960/hmm-tutorial.pdf Hidden Markov Models] (PDF; 237&nbsp;kB; 7 Seiten), archive.org, abgerufen am 21. Februar 2019.</ref>

=== Bestimmen der Modellgröße ===
Gegeben sind die beobachtbaren Emissionen <math>V</math>.
Es ist zu klären, welche Modelleigenschaften – insbesondere welche [[Orthogonalität|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 [[Statistische Signifikanz|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 (Informationstheorie)|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 [[Wort (Theoretische Informatik)#Definition|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.
Mithilfe 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 [[Konnektionismus|Modellsystem]] und die korrespondierenden Effekte im realen System identifiziert werden, die die Zustandsmenge <math>S</math> des Modells beschreibt.<ref>S. P. Chatzis: [http://www.academia.edu/389168/A_Variational_Bayesian_Methodology_for_Hidden_Markov_Models_Utilizing_Students-t_Mixtures ''A Variational Bayesian Methodology for Hidden Markov Models''].</ref>
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 [[Messreihe]]n, aufgenommenen Sprachsignalen oder [[Proteinsequenz]]en. Dazu werden die Modelle so konstruiert, dass die verborgenen Zustände semantischen Einheiten entsprechen (z.&nbsp;B. [[Phonem]]e in der [[Spracherkennung]]), die es in den sequentiellen Daten (z.&nbsp;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 [[Nukleotidsequenz|Nukleotid-]] und Proteinsequenzen eingesetzt und sind seitdem fester Bestandteil der [[Bioinformatik]].

== 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.
* {{Literatur |Autor=Kai-Fu Lee, Hsiao-Wuen Hon |Titel=Speaker-Independent Phone Recognition Using Hidden Markov Models |Band=IEEE Transactions on accoustics, speech and signal processing |Nummer=37 |Verlag=IEEE |Datum=1989-11 |Seiten=1641-1648 |Sprache=en |Kommentar=IEEE Nr. 8930533, 0096-3518/89/1100-1641}}

== Weblinks ==
* R.v. Handel, 28. Juli 2008: [https://web.math.princeton.edu/~rvan/orf557/hmm080728.pdf ''Hidden Markov Models''] (PDF; 900&nbsp;kB; 123 Seiten) Lecture Notes Princeton University Juli 2008, abgerufen am 24. Februar 2019.
* E.G. Schukat-Talamazzini, 7. Dezember 2018: [https://www.minet.uni-jena.de/fakultaet/schukat/MAS/Scriptum/lect05-HMM.pdf ''Spezielle Musteranalysesysteme''] (PDF; 1,3&nbsp;MB; 17 Seiten) Vorlesung im WS 2018 an der Universität Jena. Kap. 5, abgerufen am 24. Februar 2019.
* [http://cran.r-project.org/web/packages/HMM/index.html HMM R-Package] zum Modellieren und Analysieren von Hidden-Markov-Modellen, das unter GPL2 frei verfügbar ist
* [http://code.google.com/p/jahmm/ HMM Java-Bibliothek, die unter der neuen BSD-Lizenz verfügbar ist] Internal Server Error
* [http://www.ghmm.org/ HMM C-Bibliothek, die unter der LGPL frei verfügbar ist]

== Einzelnachweise ==
<references />

[[Kategorie:Stochastik]]
[[Kategorie:Computerlinguistik]]
[[Kategorie:Maschinelles Lernen]]
[[Kategorie:Andrei Andrejewitsch Markow (Mathematiker, 1856) als Namensgeber]]