Verstecktes Markow-Modell

Ein Hidden-Markov-Modell (HMM) ist ein statistisches Modell, das zur Beschreibung von Beobachtungssequenzen verwendet wird, die von einem zugrunde liegenden, nicht beobachtbaren Prozess abhängen. In der Wahrscheinlichkeitstheorie ist ein HMM ein Markov-Modell, bei dem die Beobachtungen von einem latenten (oder verborgenen) Markov-Prozess abhängen, der oft als X bezeichnet wird. Das Modell erfordert einen beobachtbaren Prozess Y, dessen Ergebnisse in bekannter Weise von den Ergebnissen von X abhängen. Da X nicht direkt beobachtet werden kann, besteht das Ziel darin, etwas über den Zustand von X durch die Beobachtung von Y zu lernen. Aufgrund der Definition als Markov-Modell hat ein HMM die zusätzliche Anforderung, dass das Ergebnis von Y zum Zeitpunkt t0 ausschließlich durch das Ergebnis von X zum Zeitpunkt t0 beeinflusst werden muss und dass die Ergebnisse von X und Y vor dem Zeitpunkt t0 bedingt unabhängig von Y zum Zeitpunkt t0 gegeben X zum Zeitpunkt t0 sein müssen. Die Schätzung der Parameter in einem HMM kann mithilfe der Maximum-Likelihood-Schätzung erfolgen; für lineare Ketten-HMMs wird häufig der Baum-Welch-Algorithmus verwendet.

Hidden-Markov-Modelle sind für ihre Anwendungen in vielen Bereichen bekannt, darunter Thermodynamik, statistische Mechanik, Physik, Chemie, Wirtschaft, Finanzen, Signalverarbeitung, Informationstheorie und Mustererkennung. Zu den spezifischen Anwendungen gehören Spracherkennung, Handschrifterkennung, Gestenerkennung, Part-of-Speech-Tagging, Partiturverfolgung, Teilentladungen und Bioinformatik.

Formale Definition

Seien X_n und Y_n zeitdiskrete stochastische Prozesse mit n ≥ 1. Das Paar (X_n, Y_n) ist ein Hidden-Markov-Modell, wenn X_n ein Markov-Prozess ist, dessen Verhalten nicht direkt beobachtbar ist (daher „verborgen“), und die bedingte Wahrscheinlichkeit von Y_n gegeben die gesamte Historie von X erfüllt P(Y_n ∈ A | X_1 = x_1, ..., X_n = x_n) = P(Y_n ∈ A | X_n = x_n) für jedes n ≥ 1, jede Sequenz x_1, ..., x_n und jede Borel-Menge A. Diese Bedingung stellt sicher, dass die Beobachtung zum Zeitpunkt n nur vom verborgenen Zustand zum Zeitpunkt n abhängt, nicht von früheren verborgenen Zuständen.

Für zeitkontinuierliche Prozesse ist das Paar (X_t, Y_t) ein Hidden-Markov-Modell, wenn X_t ein Markov-Prozess ist, der nicht direkt beobachtbar ist, und die Wahrscheinlichkeit von Y zum Zeitpunkt t0 gegeben den gesamten Pfad von X bis t0 gleich der Wahrscheinlichkeit gegeben nur X zum Zeitpunkt t0 ist: P(Y_t0 ∈ A | {X_t ∈ B_t für t ≤ t0}) = P(Y_t0 ∈ A | X_t0). Dies verallgemeinert die zeitdiskrete Definition auf kontinuierliche Zeit.

Kernkomponenten

Ein HMM wird typischerweise durch drei Parametersätze charakterisiert. Erstens die Anfangsverteilung der Zustände, die die Wahrscheinlichkeiten angibt, mit denen der verborgene Prozess in jedem möglichen Zustand startet. Zweitens die Übergangswahrscheinlichkeiten, die beschreiben, wie sich der verborgene Zustand im Laufe der Zeit gemäß der Markov-Eigenschaft entwickelt. Drittens die Emissionswahrscheinlichkeiten, die die Wahrscheinlichkeit angeben, jeden möglichen Ausgang gegeben den aktuellen verborgenen Zustand zu beobachten. Diese Komponenten definieren zusammen die gemeinsame Verteilung der verborgenen und beobachtbaren Sequenzen.

Die verborgenen Zustände selbst bilden eine Markov-Kette, was bedeutet, dass die Wahrscheinlichkeit, in einen neuen Zustand zu wechseln, nur vom aktuellen Zustand abhängt, nicht von früheren Zuständen. Der beobachtbare Prozess ist bedingt unabhängig gegeben die verborgenen Zustände, was Inferenz und Lernen vereinfacht.

Inferenz und Lernen

Ein zentrales Problem bei HMMs ist die Inferenz: Gegeben eine Sequenz von Beobachtungen, bestimme die wahrscheinlichste Sequenz verborgener Zustände. Der Viterbi-Algorithmus ist eine Methode der dynamischen Programmierung, die für diesen Zweck verwendet wird und die beste einzelne Zustandssequenz findet. Eine weitere Inferenzaufgabe ist die Berechnung der Wahrscheinlichkeit einer Beobachtungssequenz gegeben das Modell, was mit dem Vorwärtsalgorithmus erfolgen kann. Der Vorwärts-Rückwärts-Algorithmus berechnet die A-posteriori-Wahrscheinlichkeiten, sich zu jedem Zeitpunkt in jedem Zustand zu befinden, was für Aufgaben wie Glättung nützlich ist.

Die Parameterschätzung erfolgt typischerweise über die Maximum-Likelihood-Schätzung. Für lineare Ketten-HMMs aktualisiert der Baum-Welch-Algorithmus, ein Spezialfall des Expectation-Maximization-Algorithmus (EM-Algorithmus), iterativ die Modellparameter, um die Likelihood der beobachteten Daten zu maximieren. Dieser Algorithmus wechselt zwischen der Berechnung erwarteter suffizienter Statistiken gegeben die aktuellen Parameter und der Neuschätzung der Parameter, um diese Erwartungen zu maximieren.

Historische Entwicklung

HMMs haben ihre Wurzeln in der Arbeit von Leonard Baum und Kollegen in den späten 1960er und frühen 1970er Jahren, die den Vorwärts-Rückwärts-Algorithmus und den Baum-Welch-Algorithmus entwickelten. Die theoretischen Grundlagen wurden von Forschern wie Lloyd Welch weiter verfeinert. In den 1980er Jahren gewannen HMMs an Bedeutung in der Spracherkennung, insbesondere durch Arbeiten an Institutionen wie Xerox PARC. Die Modelle wurden zu einem Standardwerkzeug im maschinellen Lernen für sequenzielle Daten, bevor Deep Learning und neuronale Netze aufkamen.

In den 1990er und 2000er Jahren wurden HMMs in der Bioinformatik häufig für Genfindung, Proteinstrukturvorhersage und Sequenzalignment eingesetzt. Sie wurden auch in der Verarbeitung natürlicher Sprache für Part-of-Speech-Tagging und Named-Entity-Erkennung wichtig. Die Modelle wurden später auf verschiedene Weise erweitert, wie hierarchische HMMs und gekoppelte HMMs, um komplexere Abhängigkeiten zu behandeln.

Anwendungen

HMMs wurden auf eine Vielzahl von Problemen angewendet. In der Spracherkennung modellieren sie die Sequenz akustischer Merkmale als von verborgenen phonetischen Zuständen erzeugt. In der Handschrift- und Gestenerkennung erfassen sie die zeitliche Dynamik von Strichen oder Bewegungen. In der Bioinformatik werden sie für die Genvorhersage und die Modellierung von Proteinfamilien verwendet. In der Finanzwirtschaft können sie Regime in wirtschaftlichen Zeitreihen modellieren, wie Bullen- und Bärenmärkte. In der Signalverarbeitung werden sie für Sprachverbesserung und Aktivitätserkennung eingesetzt.

Trotz der Dominanz von Transformer-basierten Modellen in der modernen künstlichen Intelligenz bleiben HMMs für Aufgaben relevant, bei denen Interpretierbarkeit und kleine Datenmengen wichtig sind. Sie werden auch als Komponenten in komplexeren Systemen verwendet, wie hybriden Modellen, die HMMs mit neuronalen Netzen kombinieren. Die Einfachheit und mathematische Handhabbarkeit von HMMs machen sie zu einem grundlegenden Werkzeug in der probabilistischen Modellierung.

Einschränkungen und Erweiterungen

HMMs nehmen an, dass der verborgene Prozess Markovsch ist und dass Beobachtungen bedingt unabhängig gegeben den verborgenen Zustand sind. Diese Annahmen können für komplexe reale Daten restriktiv sein. Erweiterungen umfassen HMMs höherer Ordnung, bei denen der verborgene Zustand von mehreren früheren Zuständen abhängt, sowie Eingabe-Ausgabe-HMMs, die exogene Variablen einbeziehen. Hidden-Semi-Markov-Modelle erlauben variable Dauern in jedem Zustand und adressieren eine häufige Einschränkung standardmäßiger HMMs.

Im Kontext des modernen maschinellen Lernens werden HMMs oft mit rekurrenten neuronalen Netzen und Transformer-Modellen verglichen, die längere Abhängigkeiten erfassen können. HMMs bieten jedoch Vorteile in Bezug auf Interpretierbarkeit und die Fähigkeit, mit kleinen Datensätzen zu arbeiten. Sie bleiben ein aktives Forschungsgebiet, insbesondere in Bereichen wie Computerbiologie und Sprachverarbeitung.