Der Baum-Welch-Algorithmus ist ein Spezialfall des Erwartungs-Maximierungs-Algorithmus (EM-Algorithmus), der verwendet wird, um die unbekannten Parameter eines Hidden-Markov-Modells (HMM) zu finden. Er ist die primäre Methode zur Inferenz in HMMs und nutzt den Vorwärts-Rückwärts-Algorithmus, um die Statistiken für den Erwartungsschritt zu berechnen. Der Algorithmus ist nach Leonard E. Baum und Lloyd R. Welch benannt, die ihn mit Kollegen am IDA Center for Communications Research in Princeton in den späten 1960er- und frühen 1970er-Jahren entwickelten.
Ein Hidden-Markov-Modell beschreibt die gemeinsame Wahrscheinlichkeit einer Sammlung von verborgenen und beobachteten diskreten Zufallsvariablen. Es beruht auf der Annahme, dass die i-te verborgene Variable bei gegebener (i-1)-ter verborgener Variable unabhängig von früheren verborgenen Variablen ist und die aktuellen Beobachtungsvariablen nur vom aktuellen verborgenen Zustand abhängen. Der Baum-Welch-Algorithmus verwendet den EM-Algorithmus, um die Maximum-Likelihood-Schätzung der Parameter eines HMM bei einer gegebenen Menge beobachteter Merkmalsvektoren zu finden.
Formale Beschreibung
Sei \(X_t\) eine diskrete verborgene Zufallsvariable mit \(N\) möglichen Werten, die insgesamt \(N\) Zustände repräsentiert. Die Übergangswahrscheinlichkeiten werden als zeitunabhängig angenommen, was zur Definition der stochastischen Übergangsmatrix \(A = \{a_{ij}\} = P(X_t = j \mid X_{t-1} = i)\) führt. Die Anfangsverteilung der Zustände ist durch \(\pi_i = P(X_1 = i)\) gegeben.
Die Beobachtungsvariablen \(Y_t\) können einen von \(K\) möglichen Werten annehmen. Die Wahrscheinlichkeit einer bestimmten Beobachtung \(y_i\) zum Zeitpunkt \(t\) für den Zustand \(X_t = j\) ist durch \(b_j(y_i) = P(Y_t = y_i \mid X_t = j)\) gegeben. Dies ergibt die \(N \times K\)-Matrix \(B = \{b_j(y_i)\}\). Eine Beobachtungssequenz ist durch \(Y = (Y_1 = y_1, Y_2 = y_2, \ldots, Y_T = y_T)\) gegeben. Somit kann eine verborgene Markov-Kette durch \(\theta = (A, B, \pi)\) beschrieben werden. Der Baum-Welch-Algorithmus findet ein lokales Maximum für \(\theta^* = \arg\max_\theta P(Y \mid \theta)\).
Algorithmusschritte
Der Algorithmus verfeinert iterativ die Parameterschätzungen. Im Erwartungsschritt berechnet er die Vorwärtswahrscheinlichkeiten \(\alpha_t(i) = P(Y_1, \ldots, Y_t, X_t = i \mid \theta)\) und Rückwärtswahrscheinlichkeiten \(\beta_t(i) = P(Y_{t+1}, \ldots, Y_T \mid X_t = i, \theta)\) mithilfe des Vorwärts-Rückwärts-Algorithmus. Diese werden verwendet, um die erwarteten hinreichenden Statistiken zu berechnen, wie die Wahrscheinlichkeit, sich zum Zeitpunkt \(t\) im Zustand \(i\) zu befinden, und die Wahrscheinlichkeit, zwischen den Zeitpunkten \(t\) und \(t+1\) vom Zustand \(i\) zum Zustand \(j\) zu wechseln.
Im Maximierungsschritt aktualisiert der Algorithmus die Parameter \(A\), \(B\) und \(\pi\), um die erwartete Log-Likelihood zu maximieren. Die aktualisierten Übergangswahrscheinlichkeiten werden als Verhältnis der erwarteten Anzahl von Übergängen vom Zustand \(i\) zum Zustand \(j\) zur erwarteten Anzahl von Aufenthalten im Zustand \(i\) berechnet. Ebenso werden Emissionswahrscheinlichkeiten basierend auf den erwarteten Anzahl von Beobachtungen in jedem Zustand aktualisiert. Die Anfangsverteilung der Zustände wird basierend auf der erwarteten Wahrscheinlichkeit, sich zum Zeitpunkt 1 in jedem Zustand zu befinden, aktualisiert.
Der Algorithmus iteriert weiter, bis Konvergenz erreicht ist, typischerweise wenn die Änderung der Log-Likelihood unter einen Schwellenwert fällt. Es ist garantiert, dass er zu einem lokalen Maximum der Likelihood-Funktion konvergiert, jedoch nicht notwendigerweise zum globalen Maximum.
Numerische Stabilität
Der Baum-Welch-Algorithmus ist numerisch instabil aufgrund seiner rekursiven Berechnung gemeinsamer Wahrscheinlichkeiten. Mit wachsender Anzahl von Variablen werden diese gemeinsamen Wahrscheinlichkeiten zunehmend kleiner, was dazu führt, dass die Vorwärtsrekursionen schnell Werte unterhalb der Maschinengenauigkeit erreichen. Dies kann in praktischen Implementierungen zu Unterlauf führen, insbesondere bei langen Beobachtungssequenzen. Um dies zu mildern, verwenden Implementierungen oft Skalierungstechniken, wie die Normalisierung der Vorwärts- und Rückwärtsvariablen bei jedem Zeitschritt, oder arbeiten im Log-Bereich.
Anwendungen
Eine der ersten großen Anwendungen von HMMs war im Bereich der Sprachverarbeitung. In den 1980er-Jahren etablierten sich HMMs als nützliches Werkzeug in der Analyse biologischer Systeme und Informationen, insbesondere genetischer Informationen. Sie sind seitdem ein wichtiges Werkzeug in der probabilistischen Modellierung genomischer Sequenzen geworden. Der Baum-Welch-Algorithmus wird auch in der natürlichen Sprachverarbeitung verwendet, wie bei der Wortartenmarkierung und der Erkennung benannter Entitäten, sowie in der Bioinformatik für die Genfindung und die Vorhersage von Proteinstrukturen.
Verwandte Konzepte
Der Baum-Welch-Algorithmus ist eng mit anderen Parameterschätzungstechniken im maschinellen Lernen verwandt. Er ist eine spezifische Instanz des Erwartungs-Maximierungs-Algorithmus, der häufig für Modelle mit latenten Variablen verwendet wird. Der Vorwärts-Rückwärts-Algorithmus, der eine Schlüsselkomponente darstellt, wird auch in anderen HMM-Inferenzaufgaben wie dem Viterbi-Algorithmus zur Dekodierung verwendet. In der modernen Tiefenlernung erscheinen ähnliche Prinzipien beim Training von Modellen mit latenten Variablen, obwohl neuronale Netze oft gradientenbasierte Methoden wie Adam-Optimierer und SGD-Varianten anstelle von EM verwenden. Die Verbindung des Algorithmus zu maschinellem Lernen und künstlicher Intelligenz ist grundlegend, da er einen frühen Rahmen für das Lernen aus sequenziellen Daten bot.