Ein verborgenes Modell von Markov (HMM) ist ein statistisches Modell von Markov, in dem, wie man annimmt, das System, das wird modelliert, ein Prozess von Markov mit unbemerkten (verborgenen) Staaten ist. Ein HMM kann als das einfachste dynamische Netz von Bayesian betrachtet werden. Die Mathematik hinter dem HMM wurde von L. E. Baum und Mitarbeitern entwickelt. Es ist nah mit einer früheren Arbeit am optimalen nichtlinearen durchscheinenden Problem (stochastische Prozesse) durch Ruslan L. Stratonovich verbunden, der erst war, um das rückwärts gerichtete Verfahren zu beschreiben.

In einem regelmäßigen Modell von Markov ist der Staat dem Beobachter direkt sichtbar, und deshalb sind die Zustandübergangswahrscheinlichkeiten die einzigen Rahmen. In einem verborgenen Modell von Markov ist der Staat nicht direkt sichtbar, aber Produktion, Abhängiger auf dem Staat, ist sichtbar. Jeder Staat hat einen Wahrscheinlichkeitsvertrieb über die möglichen Produktionsjetons. Deshalb gibt die Folge von durch einen HMM erzeugten Jetons etwas Information über die Folge von Staaten. Bemerken Sie, dass sich das 'verborgene' Adjektiv auf die Zustandfolge bezieht, durch die das Modell geht, nicht zu den Rahmen des Modells; selbst wenn die Musterrahmen genau bekannt sind, wird das Modell noch 'verborgen'.

Verborgene Modelle von Markov sind besonders für ihre Anwendung in der zeitlichen Muster-Anerkennung wie Rede, Handschrift, Geste-Anerkennung, Wortart markierende, musikalische Kerbe im Anschluss an, teilweise Entladungen und bioinformatics bekannt.

Ein verborgenes Modell von Markov kann als eine Generalisation eines Mischungsmodells betrachtet werden, wo die verborgenen Variablen (oder latenten Variablen), die den für jede Beobachtung auszuwählenden Mischungsbestandteil kontrollieren, durch einen Prozess von Markov aber nicht unabhängig von einander verbunden sind.

Beschreibung in Bezug auf Urnen

Abbildung 1. Rahmen von Probabilistic eines verborgenen Modells von Markov (Beispiel)

x - Staaten

y - mögliche Beobachtungen

a - Zustandübergangswahrscheinlichkeiten

b - Produktionswahrscheinlichkeiten]]

In seiner getrennten Form kann ein verborgener Prozess von Markov als eine Generalisation des Urne-Problems vergegenwärtigt werden: Ein Dschinn ist in einem Zimmer, das einem Beobachter nicht sichtbar ist. In diesem verborgenen Zimmer gibt es Urnen X1, X2, X3... von denen jeder eine bekannte Mischung von Bällen enthält, jeder Ball hat y1, y2, y3 etikettiert.... Der Dschinn wählt eine Urne in diesem Zimmer und zieht zufällig einen Ball von dieser Urne. Es stellt dann den Ball auf ein Förderband, wo der Beobachter die Folge der Bälle, aber nicht die Folge von Urnen beobachten kann, von denen sie gezogen wurden. Der Dschinn hat ein Verfahren, um Urnen zu wählen; die Wahl der Urne für den n-ten Ball hängt nur auf eine Zufallszahl und die Wahl der Urne für ab (n − 1)-Th-Ball. Die Wahl der Urne hängt von den vor dieser einzelnen vorherigen Urne gewählten Urnen nicht direkt ab; deshalb wird das einen Prozess von Markov genannt. Es kann durch den oberen Teil der Abbildung 1 beschrieben werden.

Der Prozess von Markov selbst kann nicht beobachtet werden, und nur die Folge von etikettierten Bällen kann so beobachtet werden diese Einordnung wird einen "verborgenen Prozess von Markov" genannt. Das wird durch den niedrigeren Teil des in der Abbildung 1 gezeigten Diagramms illustriert, wo man sehen kann, dass Bälle y1, y2, y3, y4 an jedem Staat gezogen werden können. Selbst wenn der Beobachter die Zusammensetzung der Urnen weiß und gerade eine Folge von drei Bällen, z.B y1, y2 und y3 auf dem Förderband beobachtet hat, kann der Beobachter nicht noch überzeugt sein, von welcher Urne (d. h. an der Staat) der Dschinn den dritten Ball gezogen hat. Jedoch kann der Beobachter andere Details wie die Identität der Urne ausarbeiten, von der der Dschinn höchstwahrscheinlich den dritten Ball gezogen haben wird.

Architektur

Das Diagramm zeigt unten die allgemeine Architektur eines realisierten HMM. Jede ovale Gestalt vertritt eine zufällige Variable, die einigen mehrerer Werte annehmen kann. Die zufällige Variable x (t) ist der verborgene Staat in der Zeit t (mit dem Modell aus dem obengenannten Diagramm, x (t)  {x, x, x}). Die zufällige Variable y (t) ist die Beobachtung in der Zeit t (mit y (t)  {y, y, y, y}). Die Pfeile im Diagramm (hat häufig ein Gitterwerk-Diagramm genannt), zeigen bedingte Abhängigkeiten an.

Aus dem Diagramm ist es klar, dass der bedingte Wahrscheinlichkeitsvertrieb der verborgenen Variable x (t) in der Zeit t, in Anbetracht der Werte der verborgenen Variable x zu jeder Zeit, nur vom Wert der verborgenen Variable x abhängt (t − 1): die Werte in der Zeit t − 2 und haben vorher keinen Einfluss. Das wird das Eigentum von Markov genannt. Ähnlich hängt der Wert der beobachteten Variable y (t) nur vom Wert der verborgenen Variable x (t) (beide in der Zeit t) ab.

Im Standardtyp des verborgenen Modells von Markov betrachtet hier ist der Zustandraum der verborgenen Variablen getrennt, während die Beobachtungen selbst entweder (normalerweise erzeugt von einem kategorischen Vertrieb) getrennt oder (normalerweise von einem Vertrieb von Gaussian) dauernd sein können. Die Rahmen eines verborgenen Modells von Markov sind zwei Typen, Übergangswahrscheinlichkeiten und Emissionswahrscheinlichkeiten (auch bekannt als Produktionswahrscheinlichkeiten). Die Übergangswahrscheinlichkeiten kontrollieren die Weise, wie der verborgene Staat in der Zeit gegeben der verborgene Staat in der Zeit gewählt wird.

Wie man

annimmt, besteht der verborgene Zustandraum aus einem von möglichen Werten, modelliert als ein kategorischer Vertrieb. (Sieh die Abteilung unten auf Erweiterungen für andere Möglichkeiten.) Bedeutet das, dass für jeden der möglichen Staaten, in denen eine verborgene Variable in der Zeit sein kann, es eine Übergangswahrscheinlichkeit von diesem Staat bis jeden der möglichen Staaten der verborgenen Variable in der Zeit für insgesamt Übergangswahrscheinlichkeiten gibt. (Bemerken Sie jedoch, dass der Satz von Übergangswahrscheinlichkeiten für Übergänge von jedem gegebenen Staat zu 1 resümieren muss, bedeutend, dass irgendwelche Übergangswahrscheinlichkeit bestimmt werden kann, sobald andere bekannt sind, insgesamt Übergang-Rahmen verlassend.)

Außerdem, für jeden der möglichen Staaten, gibt es eine Reihe von Emissionswahrscheinlichkeiten, den Vertrieb der beobachteten Variable in einer bestimmten Zeit gegeben der Staat der verborgenen Variable damals regelnd. Die Größe dieses Satzes hängt von der Natur der beobachteten Variable ab. Zum Beispiel, wenn die beobachtete Variable mit möglichen Werten getrennt ist, die durch einen kategorischen Vertrieb geregelt sind, wird es getrennte Rahmen für insgesamt Emissionsrahmen über alle verborgenen Staaten geben. Andererseits, wenn die beobachtete Variable - dimensionaler gemäß einem willkürlichen multivariate Vertrieb von Gaussian verteilter Vektor ist, wird es Rahmen geben, die Mittel und Rahmen kontrollierend, die Kovarianz-Matrix für insgesamt Emissionsrahmen kontrollierend. (In solch einem Fall, wenn der Wert dessen nicht klein ist, kann es praktischer sein, um die Natur der Kovarianzen zwischen individuellen Elementen des Beobachtungsvektoren z.B einzuschränken. durch das Annehmen, dass die Elemente von einander, oder weniger einschränkend unabhängig sind, sind von allen außer einer festgelegten Zahl von angrenzenden Elementen unabhängig.)

Mathematische Beschreibung

Allgemeine Beschreibung

Ein grundlegender, non-Bayesian verborgenes Modell von Markov kann wie folgt beschrieben werden:

:

\begin {Reihe} {lcl }\

N &=& \text {Zahl von Staaten} \\

T &=& \text {Zahl von Beobachtungen} \\

\theta_ {i=1 \dots N} &=& \text {Emissionsparameter für eine Beobachtung hat mit dem Staat} ich \\verkehrt

\phi_ {i=1 \dots N, j=1 \dots N} &=& \text {Wahrscheinlichkeit des Übergangs vom Staat} ich \text {um} j \\festzusetzen

\boldsymbol\phi_ {i=1 \dots N} &=& N\text {-dimensionaler Vektor, der aus} \phi_ {ich, 1 \dots N} \text {zusammengesetzt ist; muss zu 1\\\resümieren

x_ {t=1 \dots T} &=& \text {Staat der Beobachtung in der Zeit} t \\

y_ {t=1 \dots T} &=& \text {Beobachtung in der Zeit} t \\

F (y |\theta) &=& \text {Wahrscheinlichkeitsvertrieb einer Beobachtung, die auf} \theta \\parametrisiert ist

x_ {t=2 \dots T} &\\sim& \operatorname {Kategorisch} (\boldsymbol\phi_ {x_ {t-1}}) \\

y_ {t=1 \dots T} &\\sim& F (\theta_ {x_t})

\end {ordnen }\

</Mathematik>

Bemerken Sie, dass, im obengenannten Modell (und auch dasjenige unten), der vorherige Vertrieb des anfänglichen Staates nicht angegeben wird. Typische Lernmodelle entsprechen dem Annehmen einer getrennten Rechteckverteilung über mögliche Staaten (d. h. kein besonderer vorheriger Vertrieb wird angenommen).

In einer Einstellung von Bayesian werden alle Rahmen mit zufälligen Variablen wie folgt vereinigt:

: \begin {Reihe} {lcl }\

N, T &=& \text {als oben} \\

\theta_ {i=1 \dots N}, \phi_ {i=1 \dots N, j=1 \dots N}, \boldsymbol\phi_ {i=1 \dots N} &=& \text {als oben} \\

x_ {t=1 \dots T}, y_ {t=1 \dots T}, F (y |\theta) &=& \text {als oben} \\

\alpha &=& \text {geteilter Hyperparameter für Emissionsrahmen} \\

\beta &=& \text {geteilter Hyperparameter für Übergang-Rahmen} \\

H (\theta |\alpha) &=& \text {vorheriger Wahrscheinlichkeitsvertrieb von Emissionsrahmen, die auf} \alpha \\parametrisiert sind

\theta_ {i=1 \dots N} &\\sim& H (\alpha) \\

\boldsymbol\phi_ {i=1 \dots N} &\\sim& \operatorname {Symmetrischer-Dirichlet} _N (\beta) \\

x_ {t=2 \dots T} &\\sim& \operatorname {Kategorisch} (\boldsymbol\phi_ {x_ {i-t}}) \\

y_ {t=1 \dots T} &\\sim& F (\theta_ {x_t})\end {ordnen }\</Mathematik>

Diese Charakterisierungen Gebrauch und willkürlichen Vertrieb über Beobachtungen und Rahmen beziehungsweise zu beschreiben. Normalerweise wird der verbundene vorherige davon sein. Die zwei allgemeinsten Wahlen dessen sind Gaussian und kategorisch; sieh unten.

Im Vergleich zu einem einfachen Mischungsmodell

Wie oben erwähnt ist der Vertrieb jeder Beobachtung in einem verborgenen Modell von Markov eine Mischungsdichte mit den Staaten des HMM entsprechend Mischungsbestandteilen. Es ist nützlich, die obengenannten Charakterisierungen für einen HMM mit den entsprechenden Charakterisierungen eines Mischungsmodells mit derselben Notation zu vergleichen.

Ein non-Bayesian Mischungsmodell:

: \begin {Reihe} {lcl }\

N &=& \text {Zahl von Mischungsbestandteilen} \\

T &=& \text {Zahl von Beobachtungen} \\

\theta_ {i=1 \dots N} &=& \text {Parameter des Vertriebs der Beobachtung hat mit dem Bestandteil} ich \\verkehrt

\phi_ {i=1 \dots N} &=& \text {Mischungsgewicht, d. h. vorherige Wahrscheinlichkeit eines besonderen Bestandteils} ich \\

\boldsymbol\phi &=& N\text {-dimensionaler Vektor hat von der ganzen Person} \phi_ {1 \dots N} \text {gedichtet; muss zu 1\\\resümieren

x_ {i=1 \dots T} &=& \text {Bestandteil der Beobachtung} ich \\

y_ {i=1 \dots T} &=& \text {Beobachtung} ich \\

F (y |\theta) &=& \text {Wahrscheinlichkeitsvertrieb einer Beobachtung, die auf} \theta \\parametrisiert ist

x_ {i=1 \dots T} &\\sim& \operatorname {Kategorisch} (\boldsymbol\phi) \\

y_ {i=1 \dots T} &\\sim& F (\theta_ {x_i})

\end {ordnen }\</Mathematik>

Ein Bayesian Mischungsmodell:

: \begin {Reihe} {lcl }\N, T &=& \text {als oben} \\

\theta_ {i=1 \dots N}, \phi_ {i=1 \dots N}, \boldsymbol\phi &=& \text {als oben} \\

x_ {i=1 \dots T}, y_ {i=1 \dots T}, F (y |\theta) &=& \text {als oben} \\

\alpha &=& \text {geteilter Hyperparameter für Teilrahmen} \\

\beta &=& \text {geteilter Hyperparameter für Mischungsgewichte} \\

H (\theta |\alpha) &=& \text {vorheriger Wahrscheinlichkeitsvertrieb von Teilrahmen, die auf} \alpha \\parametrisiert sind

\theta_ {i=1 \dots N} &\\sim& H (\alpha) \\

\boldsymbol\phi &\\sim& \operatorname {Symmetrischer-Dirichlet} _N (\beta) \\

x_ {i=1 \dots T} &\\sim& \operatorname {Kategorisch} (\boldsymbol\phi) \\y_ {i=1 \dots T} &\\sim& F (\theta_ {x_i})\end {ordnen }\</Mathematik>

Beispiele

Die folgenden mathematischen Beschreibungen werden völlig ausgeschrieben und für die Bequemlichkeit der Durchführung erklärt.

Ein typischer non-Bayesian HMM mit Beobachtungen von Gaussian sieht wie das aus:

: \begin {Reihe} {lcl }\N &=& \text {Zahl von Staaten} \\T &=& \text {Zahl von Beobachtungen} \\\phi_ {i=1 \dots N, j=1 \dots N} &=& \text {Wahrscheinlichkeit des Übergangs vom Staat} ich \text {um} j \\festzusetzen\boldsymbol\phi_ {i=1 \dots N} &=& N\text {-dimensionaler Vektor, der aus} \phi_ {ich, 1 \dots N} \text {zusammengesetzt ist; muss zu 1\\\resümieren

\mu_ {i=1 \dots N} &=& \text {bösartig von Beobachtungen hat mit dem Staat} ich \\verkehrt

\sigma^2_ {i=1 \dots N} &=& \text {Abweichung von Beobachtungen hat mit dem Staat} ich \\verkehrt

x_ {t=1 \dots T} &=& \text {Staat der Beobachtung in der Zeit} t \\y_ {t=1 \dots T} &=& \text {Beobachtung in der Zeit} t \\x_ {t=2 \dots T} &\\sim& \operatorname {Kategorisch} (\boldsymbol\phi_ {x_ {t-1}}) \\

y_ {t=1 \dots T} &\\sim& \mathcal {N} (\mu_ {x_t}, \sigma_ {x_t} ^2)

\end {ordnen }\</Mathematik>

Ein typischer Bayesian HMM mit Beobachtungen von Gaussian sieht wie das aus:

: \begin {Reihe} {lcl }\N &=& \text {Zahl von Staaten} \\T &=& \text {Zahl von Beobachtungen} \\\phi_ {i=1 \dots N, j=1 \dots N} &=& \text {Wahrscheinlichkeit des Übergangs vom Staat} ich \text {um} j \\festzusetzen\boldsymbol\phi_ {i=1 \dots N} &=& N\text {-dimensionaler Vektor, der aus} \phi_ {ich, 1 \dots N} \text {zusammengesetzt ist; muss zu 1\\\resümieren\mu_ {i=1 \dots N} &=& \text {bösartig von Beobachtungen hat mit dem Staat} ich \\verkehrt\sigma^2_ {i=1 \dots N} &=& \text {Abweichung von Beobachtungen hat mit dem Staat} ich \\verkehrtx_ {t=1 \dots T} &=& \text {Staat der Beobachtung in der Zeit} t \\y_ {t=1 \dots T} &=& \text {Beobachtung in der Zeit} t \\

\beta &=& \text {Konzentrationshyperparameter, die Dichte der Übergang-Matrix} \\kontrollierend

\mu_0, \lambda &=& \text {geteilte Hyperrahmen der Mittel für jeden Staat} \\

\nu, \sigma_0^2 &=& \text {geteilte Hyperrahmen der Abweichungen für jeden Staat} \\

\boldsymbol\phi_ {i=1 \dots N} &\\sim& \operatorname {Symmetrischer-Dirichlet} _N (\beta) \\x_ {t=2 \dots T} &\\sim& \operatorname {Kategorisch} (\boldsymbol\phi_ {x_ {t-1}}) \\

\mu_ {i=1 \dots N} &\\sim& \mathcal {N} (\mu_0, \lambda\sigma_i^2) \\

\sigma_ {i=1 \dots N} ^2 &\\sim& \operatorname {Umgekehrtes Gamma} (\nu, \sigma_0^2) \\

y_ {t=1 \dots T} &\\sim& \mathcal {N} (\mu_ {x_t}, \sigma_ {x_t} ^2)

\end {ordnen }\</Mathematik>

Ein typischer non-Bayesian HMM mit kategorischen Beobachtungen sieht wie das aus:

: \begin {Reihe} {lcl }\N &=& \text {Zahl von Staaten} \\T &=& \text {Zahl von Beobachtungen} \\\phi_ {i=1 \dots N, j=1 \dots N} &=& \text {Wahrscheinlichkeit des Übergangs vom Staat} ich \text {um} j \\festzusetzen\boldsymbol\phi_ {i=1 \dots N} &=& N\text {-dimensionaler Vektor, der aus} \phi_ {ich, 1 \dots N} \text {zusammengesetzt ist; muss zu 1\\\resümieren

V &=& \text {Dimension von kategorischen Beobachtungen, z.B Größe des Wortvokabulars} \\

\theta_ {i=1 \dots N, j=1 \dots V} &=& \text {Wahrscheinlichkeit für den Staat} ich \text {} j\text {th Artikel} \\zu beobachten

\boldsymbol\theta_ {i=1 \dots N} &=& V\text {-dimensionaler Vektor, der aus }\\theta_ {ich, 1 \dots V} \text {zusammengesetzt ist; muss zu 1\\\resümieren

x_ {t=1 \dots T} &=& \text {Staat der Beobachtung in der Zeit} t \\y_ {t=1 \dots T} &=& \text {Beobachtung in der Zeit} t \\x_ {t=2 \dots T} &\\sim& \operatorname {Kategorisch} (\boldsymbol\phi_ {x_ {t-1}}) \\

y_ {t=1 \dots T} &\\sim& \text {Kategorisch} (\boldsymbol\theta_ {x_t})

\end {ordnen }\</Mathematik>

Ein typischer Bayesian HMM mit kategorischen Beobachtungen sieht wie das aus:

: \begin {Reihe} {lcl }\N &=& \text {Zahl von Staaten} \\T &=& \text {Zahl von Beobachtungen} \\\phi_ {i=1 \dots N, j=1 \dots N} &=& \text {Wahrscheinlichkeit des Übergangs vom Staat} ich \text {um} j \\festzusetzen

\boldsymbol\phi_ {i=1 \dots N} &=& N\text {-dimensionaler Vektor, der aus} \phi_ {ich, 1 \dots N} \text {zusammengesetzt ist; muss zu 1\\\resümieren

V &=& \text {Dimension von kategorischen Beobachtungen, z.B Größe des Wortvokabulars} \\\theta_ {i=1 \dots N, j=1 \dots V} &=& \text {Wahrscheinlichkeit für den Staat} ich \text {} j\text {th Artikel} \\zu beobachten

\boldsymbol\theta_ {i=1 \dots N} &=& V\text {-dimensionaler Vektor, der aus }\\theta_ {ich, 1 \dots V} \text {zusammengesetzt ist; muss zu 1\\\resümieren

x_ {t=1 \dots T} &=& \text {Staat der Beobachtung in der Zeit} t \\y_ {t=1 \dots T} &=& \text {Beobachtung in der Zeit} t \\

\alpha &=& \text {geteilter Konzentrationshyperparameter} \boldsymbol\theta \text {für jeden Staat} \\

\beta &=& \text {Konzentrationshyperparameter, die Dichte der Übergang-Matrix} \\kontrollierend\boldsymbol\phi_ {i=1 \dots N} &\\sim& \operatorname {Symmetrischer-Dirichlet} _N (\beta) \\

\boldsymbol\theta_ {1 \dots V} &\\sim& \text {Symmetrischer-Dirichlet} _V (\alpha) \\

x_ {t=2 \dots T} &\\sim& \operatorname {Kategorisch} (\boldsymbol\phi_ {x_ {t-1}}) \\y_ {t=1 \dots T} &\\sim& \text {Kategorisch} (\boldsymbol\theta_ {x_t})\end {ordnen }\</Mathematik>

Bemerken Sie, dass in den obengenannten Charakterisierungen von Bayesian, (ein Konzentrationsparameter) die Dichte der Übergang-Matrix kontrolliert. D. h. mit einem hohen Wert (bedeutsam oben 1) werden die Wahrscheinlichkeiten, den Übergang aus einem besonderen Staat kontrollierend, alle ähnlich sein, bedeutend, dass es bedeutsam Wahrscheinlichkeit des Wechselns zu einigen der anderen Staaten geben wird. Mit anderen Worten wird der von der Kette von Markov von verborgenen Staaten gefolgte Pfad hoch zufällig sein. Mit einem niedrigen Wert (bedeutsam unten 1) wird nur eine kleine Zahl von den möglichen Übergängen aus einem gegebenen Staat bedeutende Wahrscheinlichkeit haben, bedeutend, dass der von den verborgenen Staaten gefolgte Pfad etwas voraussagbar sein wird.

Ein Zwei-Niveaus-Bayesian HMM

Eine Alternative für die obengenannten zwei Beispiele von Bayesian würde ein anderes Niveau von vorherigen Rahmen für die Übergang-Matrix hinzufügen sollen. D. h. ersetzen Sie die Linien

: \begin {Reihe} {lcl }\\beta &=& \text {Konzentrationshyperparameter, die Dichte der Übergang-Matrix} \\kontrollierend

\boldsymbol\phi_ {i=1 \dots N} &\\sim& \operatorname {Symmetrischer-Dirichlet} _N (\beta)

\end {ordnen }\</Mathematik>

mit dem folgenden:

: \begin {Reihe} {lcl }\

\gamma &=& \text {das Konzentrationshyperparameter-Steuern, wie viele Staaten} \\wirklich wahrscheinlich sind

\beta &=& \text {Konzentrationshyperparameter, die Dichte der Übergang-Matrix} \\kontrollierend

\boldsymbol\eta &=& N\text {-dimensionaler Vektor von Wahrscheinlichkeiten, die innere Wahrscheinlichkeit eines gegebenen Staates} \\angebend

\boldsymbol\eta &\\sim& \operatorname {Symmetrischer-Dirichlet} _N (\gamma) \\

\boldsymbol\phi_ {i=1 \dots N} &\\sim& \operatorname {Dirichlet} _N (\beta N \boldsymbol\eta)

\end {ordnen }\</Mathematik>

Was das bedeutet, ist der folgende:

1. ist ein Wahrscheinlichkeitsvertrieb über Staaten, angebend, welche Staaten von Natur aus wahrscheinlich sind. Je größer die Wahrscheinlichkeit eines gegebenen Staates in diesem Vektoren, desto wahrscheinlicher ein Übergang zu diesem Staat (unabhängig vom Startstaat) ist.

1. kontrolliert die Dichte dessen. Werte bedeutsam oben 1 verursachen einen dichten Vektoren, wo alle Staaten ähnliche vorherige Wahrscheinlichkeiten haben werden. Werte bedeutsam unten 1 verursachen einen spärlichen Vektoren, wo nur einige Staaten von Natur aus wahrscheinlich sind (haben Sie vorherige Wahrscheinlichkeiten bedeutsam oben 0).

1. kontrolliert die Dichte der Übergang-Matrix, oder mehr spezifisch, die Dichte der N verschiedenen Wahrscheinlichkeitsvektoren, die die Wahrscheinlichkeit von Übergängen aus dem Staat i zu jedem anderen Staat angeben.

Stellen Sie sich vor, dass der Wert dessen bedeutsam oben 1 ist. Dann werden die verschiedenen Vektoren dicht sein, d. h. die Wahrscheinlichkeitsmasse wird ziemlich gleichmäßig über alle Staaten ausgedehnt. Jedoch, im Ausmaß, dass diese Masse, Steuerungen uneben ausgebreitet wird, welche Staaten wahrscheinlich mehr Masse bekommen werden als andere.

Stellen Sie sich jetzt stattdessen vor, dass das bedeutsam unten 1 ist. Dieser willl macht die Vektoren spärlich, d. h. fast die ganze Wahrscheinlichkeitsmasse wird über eine kleine Anzahl von Zuständen, und für den Rest verteilt, ein Übergang zu diesem Staat wird sehr unwahrscheinlich sein. Bemerken Sie, dass es verschiedene Vektoren für jeden Startstaat, und so gibt, selbst wenn alle Vektoren spärlich sind, verschiedene Vektoren die Masse zu verschiedenen endenden Staaten verteilen können. Jedoch, für alle Vektoren, Steuerungen, welche endende Staaten wahrscheinlich Masse ihnen zuteilen lassen werden. Zum Beispiel, wenn 0.1 ist, dann wird jeder spärlich sein und, für jeden gegebenen Startstaat i wird der Satz von Staaten, zu denen Übergänge wahrscheinlich vorkommen werden, sehr klein sein, normalerweise nur ein oder zwei Mitglieder habend. Jetzt, wenn die Wahrscheinlichkeiten darin alle gleich sind (oder gleichwertig wird eines der obengenannten Modelle ohne verwendet), dann für den verschiedenen ich, es wird verschiedene Staaten im Entsprechen geben, so dass alle Staaten ebenso wahrscheinlich in irgendwelchem gegeben vorkommen werden. Andererseits, wenn die Werte darin unausgeglichen sind, so dass ein Staat eine viel höhere Wahrscheinlichkeit hat als andere, werden fast alle diesen Staat enthalten; folglich, unabhängig vom Startstaat, werden Übergänge fast immer zu diesem gegebenen Staat vorkommen.

Folglich erlaubt ein Zwei-Niveaus-Modell solcher, wie gerade beschrieben, unabhängige Kontrolle über (1) die gesamte Dichte der Übergang-Matrix, und (2) die Dichte von Staaten, zu denen Übergänge (d. h. die Dichte des vorherigen Vertriebs von Staaten in jeder besonderen verborgenen Variable) wahrscheinlich sind. In beiden Fällen wird das getan, während man noch Unerfahrenheit annimmt, über die besondere Staaten wahrscheinlicher sind als andere. Wenn es gewünscht wird, um diese Information ins Modell einzuspritzen, kann der Wahrscheinlichkeitsvektor direkt angegeben werden; oder wenn es weniger Gewissheit über diese Verhältniswahrscheinlichkeiten gibt, kann ein nichtsymmetrischer Vertrieb von Dirichlet als der vorherige Vertrieb verwendet werden. D. h. anstatt einen symmetrischen Vertrieb von Dirichlet mit einem einzelnen Parameter (oder gleichwertig, ein General Dirichlet mit einem Vektoren zu verwenden, alle sind dessen Werte dem gleich), verwenden Sie einen General Dirichlet mit Werten, die verschiedenartig größer sind oder weniger als, gemäß dem Staat mehr oder weniger bevorzugt wird.

Das Lernen

Die Parameter-Lernaufgabe in HMMs ist, in Anbetracht einer Produktionsfolge oder einer Reihe solcher Folgen, des besten Satzes des Zustandübergangs und der Produktionswahrscheinlichkeiten zu finden. Die Aufgabe ist gewöhnlich, die maximale Wahrscheinlichkeitsschätzung der Rahmen des HMM gegeben der Satz von Produktionsfolgen abzuleiten. Kein lenksamer Algorithmus ist bekannt, um dieses Problem genau zu beheben, aber eine lokale maximale Wahrscheinlichkeit kann effizient mit dem Baum-walisischen Algorithmus oder dem Algorithmus von Baldi-Chauvin abgeleitet werden. Der Baum-walisische Algorithmus ist ein Beispiel eines rückwärts gerichteten Algorithmus, und ist ein spezieller Fall des Erwartungsmaximierungsalgorithmus.

Schlussfolgerung

5 3 2 5 3 2 </br>

4 3 2 5 3 2 </br>

3 1 2 5 3 2 </br>

Wir können die wahrscheinlichste Folge finden, indem wir die gemeinsame Wahrscheinlichkeit sowohl der Zustandfolge als auch der Beobachtungen für jeden Fall bewerten (einfach durch das Multiplizieren der Wahrscheinlichkeitswerte, die hier der Undurchsichtigkeit der Pfeile beteiligt entsprechen). Im Allgemeinen kann dieser Typ des Problems (d. h. Entdeckung der wahrscheinlichsten Erklärung für eine Beobachtungsfolge) effizient mit dem Algorithmus von Viterbi gelöst werden.]]

Mehrere Interferenzprobleme werden mit verborgenen Modellen von Markov, wie entworfen, unten vereinigt.

Wahrscheinlichkeit einer beobachteten Folge

Die Aufgabe ist, in Anbetracht der Rahmen des Modells, der Wahrscheinlichkeit einer besonderen Produktionsfolge zu rechnen. Das verlangt Summierung über alle möglichen Zustandfolgen:

Die Wahrscheinlichkeit, eine Folge zu beobachten

:

der Länge wird L durch gegeben

:

wo die Summe alle möglichen Folgen des verborgenen Knotens durchgeht

:

Den Grundsatz der dynamischen Programmierung anwendend, kann dieses Problem auch effizient mit dem Vorwärtsalgorithmus behandelt werden.

Wahrscheinlichkeit der latenten Variablen

Mehrere zusammenhängende Aufgaben fragen nach der Wahrscheinlichkeit ein oder mehr von den latenten Variablen, in Anbetracht der Rahmen des Modells und einer Folge von Beobachtungen

Entstörung

Die Aufgabe ist, in Anbetracht der Rahmen des Modells und einer Folge von Beobachtungen, dem Vertrieb über verborgene Staaten der letzten latenten Variable am Ende der Folge zu rechnen, d. h. zu rechnen. Diese Aufgabe wird normalerweise verwendet, wenn von der Folge von latenten Variablen als die zu Grunde liegenden Staaten gedacht wird, die ein Prozess durch an einer Folge von Punkten der Zeit mit entsprechenden Beobachtungen an jedem Punkt rechtzeitig bewegt. Dann ist es natürlich, nach dem Staat des Prozesses am Ende zu fragen.

Dieses Problem kann effizient mit dem Vorwärtsalgorithmus behandelt werden.

Glanzschleifen

Das ist der Entstörung ähnlich, aber fragt nach dem Vertrieb einer latenten Variable irgendwo in der Mitte einer Folge, d. h. für einige zu rechnen

Der rückwärts gerichtete Algorithmus ist eine effiziente Methode, für die geglätteten Werte für alle verborgenen Zustandsgrößen zu schätzen.

Wahrscheinlichste Erklärung

Die Aufgabe, verschieden von den vorherigen zwei, fragt nach der gemeinsamen Wahrscheinlichkeit der kompletten Folge von verborgenen Staaten, die eine besondere Folge von Beobachtungen erzeugt haben (sieh Illustration rechts). Diese Aufgabe ist allgemein anwendbar, wenn HMM'S auf verschiedene Sorten von Problemen von denjenigen angewandt wird, für die die Aufgaben der Entstörung und des Glanzschleifens anwendbar sind. Ein Beispiel ist markierende Wortart, wo die verborgenen Staaten die zu Grunde liegenden Wortarten entsprechend einer beobachteten Folge von Wörtern vertreten. In diesem Fall, was von Interesse ist, ist die komplette Folge von Wortarten, aber nicht einfach der Wortart für ein einzelnes Wort, weil Entstörung oder Glanzschleifen rechnen würden.

Das beansprucht stark verlangt Entdeckung eines Maximums über alle möglichen Zustandfolgen, und kann effizient durch den Algorithmus von Viterbi gelöst werden.

Statistische Bedeutung

Für einige der obengenannten Probleme kann es auch interessant sein, nach der statistischen Bedeutung zu fragen. Wie ist die Wahrscheinlichkeit, dass eine von etwas ungültigem Vertrieb gezogene Folge eine HMM Wahrscheinlichkeit (im Fall vom Vorwärtsalgorithmus) oder eine maximale Zustandfolge-Wahrscheinlichkeit (im Fall vom Algorithmus von Viterbi) mindestens so groß haben wird wie diese einer besonderen Produktionsfolge? Wenn ein HMM verwendet wird, um die Relevanz einer Hypothese für eine besondere Produktionsfolge zu bewerten, zeigt die statistische Bedeutung die falsche positive Rate an, die mit dem Annehmen der Hypothese für die Produktionsfolge vereinigt ist.

Ein konkretes Beispiel

Dieses Beispiel wird weiter in der Algorithmus-Seite von Viterbi sorgfältig ausgearbeitet.

Anwendungen

HMMs kann in vielen Feldern angewandt werden, wo die Absicht ist, eine Datenfolge wieder zu erlangen, die nicht sofort erkennbar ist (aber andere Daten, der von der Folge abhängt, ist). Anwendungen schließen ein:

• Cryptanalysis
• Spracherkennung
• Rede-Synthese
• Wortart, die markiert
• Maschinelle Übersetzung
• Teilweise Entladung
• Genvorhersage
• Anordnung von Lebensfolgen
• Tätigkeitsanerkennung
• Protein, das sich faltet
• Metamorphe Virus-Entdeckung

Geschichte

Der nachschicken und rückwärts gerichteter recursions, der in HMM sowie Berechnung von Randglanzschleifen-Wahrscheinlichkeiten verwendet ist, wurden zuerst von Ruslan L. Stratonovich 1960 (Seiten 160 — 162) und gegen Ende der 1950er Jahre in seinen Zeitungen in Russisch beschrieben.

Die Verborgenen Modelle von Markov wurden später in einer Reihe von statistischen Vorträgen von Leonard E. Baum und anderen Autoren in der zweiten Hälfte der 1960er Jahre beschrieben. Eine der ersten Anwendungen von HMMs war Spracherkennung, Mitte der 1970er Jahre anfangend.

In der zweiten Hälfte der 1980er Jahre hat HMMs begonnen, auf die Analyse von biologischen Folgen in der besonderen DNA angewandt zu werden. Seitdem sind sie allgegenwärtig im Feld von bioinformatics geworden.

Typen

Verborgene Modelle von Markov können Komplex Prozesse von Markov modellieren, wo die Staaten die Beobachtungen gemäß etwas Wahrscheinlichkeitsvertrieb ausstrahlen. Ein solches Beispiel des Vertriebs ist Vertrieb von Gaussian, in solch einem Verborgenen Markov Modellieren die Zustandproduktion wird durch einen Vertrieb von Gaussian vertreten.

Außerdem konnte es noch komplizierteres Verhalten vertreten, wenn die Produktion der Staaten als Mischung von zwei oder mehr Gaussians vertreten wird, in welchem Fall die Wahrscheinlichkeit, eine Beobachtung zu erzeugen, das Produkt der Wahrscheinlichkeit ist, zuerst einen von Gaussians und die Wahrscheinlichkeit des Erzeugens dieser Beobachtung von diesem Gaussian auszuwählen.

Erweiterungen

In den verborgenen Modellen von Markov, die oben betrachtet sind, ist der Zustandraum der verborgenen Variablen getrennt, während die Beobachtungen selbst entweder (normalerweise erzeugt von einem kategorischen Vertrieb) getrennt oder (normalerweise von einem Vertrieb von Gaussian) dauernd sein können. Verborgene Modelle von Markov können auch verallgemeinert werden, um dauernde Zustandräume zu erlauben. Beispiele solcher Modelle sind diejenigen, wo der Prozess von Markov über verborgene Variablen ein geradliniges dynamisches System mit einer geradlinigen Beziehung unter zusammenhängenden Variablen ist, und wo alle verborgenen und beobachteten Variablen einem Vertrieb von Gaussian folgen. In einfachen Fällen wie das geradlinige dynamische System gerade ist erwähnte, genaue Schlussfolgerung (in diesem Fall, mit dem Filter von Kalman) lenksam; jedoch, im Allgemeinen, ist die genaue Schlussfolgerung in HMMs mit dauernden latenten Variablen unausführbar, und ungefähre Methoden, müssen wie der verlängerte Filter von Kalman oder der Partikel-Filter verwendet werden.

Verborgene Modelle von Markov sind generative Modelle, in denen der gemeinsame Vertrieb von Beobachtungen und verborgenen Staaten, oder gleichwertig beiden der vorherige Vertrieb von verborgenen Staaten (die Übergangswahrscheinlichkeiten) und bedingte Vertrieb von Beobachtungen gegeben Staaten (die Emissionswahrscheinlichkeiten), modelliert wird. Die obengenannten Algorithmen nehmen implizit einen gleichförmigen vorherigen Vertrieb über die Übergangswahrscheinlichkeiten an. Jedoch ist es auch möglich, verborgene Modelle von Markov mit anderen Typen des vorherigen Vertriebs zu schaffen. Ein offensichtlicher Kandidat, in Anbetracht des kategorischen Vertriebs der Übergangswahrscheinlichkeiten, ist der Vertrieb von Dirichlet, der der verbundene vorherige Vertrieb des kategorischen Vertriebs ist. Gewöhnlich wird ein symmetrischer Vertrieb von Dirichlet gewählt, Unerfahrenheit widerspiegelnd, über die Staaten von Natur aus wahrscheinlicher sind als andere. Der einzelne Parameter dieses Vertriebs (hat den Konzentrationsparameter genannt), kontrolliert die Verhältnisdichte oder Spärlichkeit der resultierenden Übergang-Matrix. Eine Wahl von 1 Erträgen eine Rechteckverteilung. Werte, die größer sind als 1, erzeugen eine dichte Matrix, in der die Übergangswahrscheinlichkeiten zwischen Paaren von Staaten wahrscheinlich fast gleich sein werden. Werte weniger als 1 läuft auf eine spärliche Matrix hinaus, in der, für jeden gegebenen Quellstaat, nur eine kleine Anzahl von Bestimmungsort-Zuständen nichtunwesentliche Übergangswahrscheinlichkeiten hat. Es ist auch möglich, einen vorherigen Zwei-Niveaus-Vertrieb von Dirichlet zu verwenden, in dem ein Vertrieb von Dirichlet (der obere Vertrieb) die Rahmen eines anderen Vertriebs von Dirichlet regelt (der niedrigere Vertrieb), der der Reihe nach die Übergangswahrscheinlichkeiten regelt. Der obere Vertrieb regelt den gesamten Vertrieb von Staaten, bestimmend, wie wahrscheinlich jeder Staat vorkommen soll; sein Konzentrationsparameter bestimmt die Dichte oder Spärlichkeit von Staaten. Solch ein vorheriger Zwei-Niveaus-Vertrieb, wo beide Konzentrationsparameter aufgestellt werden, um spärlichen Vertrieb zu erzeugen, könnte zum Beispiel in der unbeaufsichtigten markierenden Wortart nützlich sein, wo einige Wortarten viel allgemeiner vorkommen als andere; das Lernen von Algorithmen, die einen gleichförmigen vorherigen Vertrieb allgemein annehmen, leistet schlecht auf dieser Aufgabe. Die Rahmen von Modellen dieser Sorte, mit dem ungleichförmigen vorherigen Vertrieb, können mit Gibbs erfahren werden, der ausfällt oder verlängerte Versionen des Erwartungsmaximierungsalgorithmus.

Eine Erweiterung der vorher beschriebenen verborgenen Modelle von Markov mit Dirichlet priors verwendet einen Prozess von Dirichlet im Platz eines Vertriebs von Dirichlet. Dieser Typ des Modells berücksichtigt einen unbekannten und potenziell unendliche Zahl von Staaten. Es ist üblich, einen Zwei-Niveaus-Prozess von Dirichlet zu verwenden, der dem vorher beschriebenen Modell mit zwei Niveaus des Vertriebs von Dirichlet ähnlich ist. Solch ein Modell wird einen hierarchischen Prozess von Dirichlet verborgenes Modell von Markov oder HDP-HMM für den kurzen genannt.

Ein verschiedener Typ der Erweiterung verwendet ein unterscheidendes Modell im Platz des generativen Modells von normalem HMM'S. Dieser Typ des Modells modelliert direkt den bedingten Vertrieb der verborgenen Staaten gegeben die Beobachtungen, anstatt den gemeinsamen Vertrieb zu modellieren. Ein Beispiel dieses Modells ist das so genannte maximale Wärmegewicht Modell von Markov (MEMM), das den bedingten Vertrieb der Staaten mit dem logistischen rückwärts Gehen (auch bekannt als ein "maximales Wärmegewicht-Modell") modelliert. Der Vorteil dieses Typs des Modells besteht darin, dass willkürliche Eigenschaften (d. h. Funktionen) der Beobachtungen modelliert werden können, bereichsspezifische Kenntnisse des Problems in der Nähe erlaubend, ins Modell eingespritzt zu werden. Modelle dieser Sorte werden auf das Modellieren direkter Abhängigkeiten zwischen einem verborgenen Staat und seiner verbundenen Beobachtung nicht beschränkt; eher können Eigenschaften von nahe gelegenen Beobachtungen, Kombinationen der verbundenen Beobachtung und nahe gelegenen Beobachtungen, oder tatsächlich willkürlicher Beobachtungen in jeder Entfernung von einem gegebenen verborgenen Staat in den Prozess eingeschlossen werden, der verwendet ist, um den Wert eines verborgenen Staates zu bestimmen. Außerdem gibt es kein Bedürfnis nach diesen Eigenschaften, um von einander statistisch unabhängig zu sein, wie der Fall sein würde, wenn solche Eigenschaften in einem generativen Modell verwendet würden. Schließlich können willkürliche Eigenschaften über Paare von angrenzenden verborgenen Staaten aber nicht einfache Übergangswahrscheinlichkeiten verwendet werden. Die Nachteile solcher Modelle sind: (1) werden Die Typen des vorherigen Vertriebs, der auf verborgenen Staaten gelegt werden kann, streng beschränkt; (2) ist Es nicht möglich, die Wahrscheinlichkeit vorauszusagen, eine willkürliche Beobachtung zu sehen. Diese zweite Beschränkung ist häufig nicht ein Problem in der Praxis, da vieler allgemeiner Gebrauch von HMM'S solche prophetischen Wahrscheinlichkeiten nicht verlangt.

Eine Variante des vorher beschriebenen unterscheidenden Modells ist die geradlinige Kette bedingtes zufälliges Feld. Das verwendet ein ungeleitetes grafisches Modell (auch bekannt als Markov zufälliges Feld) aber nicht die geleiteten grafischen Modelle der und ähnlichen Modelle von MEMM. Der Vorteil dieses Typs des Modells besteht darin, dass es unter dem so genannten Etikett-Neigungsproblem von MEMM'S nicht leidet, und so genauere Vorhersagen machen kann. Der Nachteil ist, dass Ausbildung langsamer sein kann als für den MEMM'S.

Und doch ist eine andere Variante der factorial verborgenes Modell von Markov, das eine einzelne Beobachtung berücksichtigt, die auf den entsprechenden verborgenen Variablen von einer Reihe unabhängiger Ketten von Markov, aber nicht einer einzelnen Kette von Markov zu bedingen ist. Es ist zu einem einzelnen HMM mit Staaten gleichwertig (das Annehmen, dass es Staaten für jede Kette gibt), und deshalb, ist das Erfahren in solch einem Modell schwierig: Für eine Folge der Länge hat ein aufrichtiger Algorithmus von Viterbi Kompliziertheit. Um eine genaue Lösung zu finden, konnte ein Verbindungspunkt-Baumalgorithmus verwendet werden, aber er läuft auf eine Kompliziertheit hinaus. In der Praxis konnten ungefähre Techniken, wie abweichende Annäherungen, verwendet werden.

Alle obengenannten Modelle können erweitert werden, um entferntere Abhängigkeiten unter verborgenen Staaten zu berücksichtigen, z.B einen gegebenen Staat berücksichtigend, um von den vorherigen zwei oder drei Staaten aber nicht einem einzelnen vorherigen Staat abhängig zu sein; d. h. die Übergangswahrscheinlichkeiten werden erweitert, um Sätze von drei oder vier angrenzenden Staaten (oder in allgemeinen angrenzenden Staaten) zu umfassen. Der Nachteil solcher Modelle ist, dass dynamisch programmierende Algorithmen für die Ausbildung sie eine Laufzeit, für angrenzende Staaten und Gesamtbeobachtungen (d. h. eine Länge - Kette von Markov) haben.

Siehe auch

• Andrey Markov
• Schlussfolgerung von Bayesian
• Bewertungstheorie
• Hierarchisches verborgenes Modell von Markov
• Layered verborgenes Modell von Markov
• Verborgenes semi-Markov Modell
• Variable Ordnung Modell von Markov
• Folgendes dynamisches System
• Bedingtes zufälliges Feld
• Baum-walisischer Algorithmus
• Algorithmus von Viterbi
• Poisson verborgenes Modell von Markov
• Verborgenes Modell von Bernoulli
• HMMER, ein freies verborgenes Musterprogramm von Markov für die Protein-Folge-Analyse
• HHpred / HHsearch freier Server und Software für die Protein-Folge, die sucht
• Stochastische Grammatik ohne Zusammenhänge

Links

Konzepte

• Eine enthüllende Einführung in verborgene Modelle von Markov durch die Zeichen-Marke, San Jose staatliche Universität.
• Das Ausrüsten von HMM'S mit der Erwartungsmaximierung - vollendet Abstammung
• Die Schaltung autorückläufigen verborgenen Modells von Markov (SAR HMM)
• Ein schrittweiser Tutorenkurs auf HMMs (Universität von Leeds)
• Verborgene Modelle von Markov (eine Ausstellung mit der grundlegenden Mathematik)
• Verborgene Modelle von Markov (durch Narada Warakagoda)
• Verborgene Modelle von Markov: Grundlagen und Anwendungsteil 1, Teil 2 (durch V. Petrushin)

Software

• HMMdotEM HMM Allgemeiner Getrennt-Staatswerkzeugkasten (veröffentlicht laut der BSD ähnlichen 3-Klauseln-Lizenz, Zurzeit nur Matlab)
• Werkzeugkasten von Hidden Markov Model (HMM) für Matlab (durch Kevin Murphy)
• Verborgenes Musterwerkzeug von Markov (HTK) (ein tragbares Werkzeug, um verborgene Modelle von Markov zu bauen und zu manipulieren)

,

• Verborgenes MusterR-Paket von Markov, um sich niederzulassen, wenden Sie an und machen Sie Schlussfolgerung mit der diskreten Zeit und den getrennten Verborgenen Raummodellen von Markov
• GHMM Bibliothek (Hausseite des GHMM Bibliotheksprojektes)
• Bibliothek der KL-.-HMM (HMM Bibliothek für das allgemeine Lispeln)
• Jahmm javanische Bibliothek (javanische Mehrzweckbibliothek)
• HMM und andere statistische Programme (Durchführung in C durch Tapas Kanungo)
• Das hmm Paket Eine Bibliothek von Haskell, um mit Verborgenen Modellen von Markov zu arbeiten.
• GT2K Technologie-Geste-Werkzeug von Georgia (verwiesen auf als GT2K)
• Verborgene Modelle von Markov - Online-Rechenmaschine für HMM - Pfad von Viterbi und Wahrscheinlichkeiten. Beispiele mit dem perl Quellcode.