Der Forward-Backward-Algorithmus ist eine grundlegende Technik der dynamischen Programmierung, die im Kontext von Hidden-Markov-Modellen (HMMs) und verwandten probabilistischen Sequenzmodellen verwendet wird. Er berechnet die posteriore Marginalverteilung jedes verborgenen Zustands gegeben eine Sequenz von Beobachtungen und ermöglicht so effiziente Inferenz und Parameterschätzung. Der Algorithmus ist ein Eckpfeiler des klassischen maschinellen Lernens und bleibt in modernen Anwendungen wie Spracherkennung, Bioinformatik und natürlicher Sprachverarbeitung relevant.
Entwickelt in den späten 1960er und frühen 1970er Jahren, wurde der Algorithmus von Leonard Baum und seinen Kollegen in einer Reihe von Arbeiten zur statistischen Schätzung für probabilistische Funktionen von Markov-Ketten formalisiert. Er wird oft zusammen mit dem Viterbi-Algorithmus präsentiert, der die wahrscheinlichste Sequenz verborgener Zustände findet, während der Forward-Backward-Algorithmus Wahrscheinlichkeiten für jeden einzelnen Zustand zu jedem Zeitpunkt berechnet. Der Algorithmus arbeitet in zwei Durchläufen: einem Vorwärtsdurchlauf, der die Wahrscheinlichkeit berechnet, die Sequenz bis zu einem bestimmten Zeitpunkt zu beobachten und in einem bestimmten Zustand zu enden, und einem Rückwärtsdurchlauf, der die Wahrscheinlichkeit berechnet, den Rest der Sequenz gegeben einen Startzustand zu beobachten. Die Kombination dieser beiden Wahrscheinlichkeitssätze ergibt die gewünschten posterioren Marginalen.
Mathematische Formulierung
Betrachten wir ein HMM mit verborgenen Zuständen \( S = \{s_1, s_2, \ldots, s_N\} \), Übergangswahrscheinlichkeiten \( a_{ij} = P(s_j | s_i) \), Emissionswahrscheinlichkeiten \( b_j(o_t) = P(o_t | s_j) \) und einer Anfangsverteilung \( \pi_i = P(s_i) \). Für eine Beobachtungssequenz \( O = (o_1, o_2, \ldots, o_T) \) ist die Vorwärtsvariable \( \alpha_t(i) \) definiert als die Wahrscheinlichkeit der partiellen Beobachtungssequenz bis zum Zeitpunkt \( t \) und des Aufenthalts im Zustand \( s_i \) zum Zeitpunkt \( t \): \( \alpha_t(i) = P(o_1, o_2, \ldots, o_t, q_t = s_i | \lambda) \), wobei \( \lambda \) die Modellparameter bezeichnet. Der Vorwärtsdurchlauf initialisiert \( \alpha_1(i) = \pi_i b_i(o_1) \) und berechnet rekursiv \( \alpha_{t+1}(j) = b_j(o_{t+1}) \sum_{i=1}^N \alpha_t(i) a_{ij} \).
Die Rückwärtsvariable \( \beta_t(i) \) ist definiert als die Wahrscheinlichkeit der Beobachtungssequenz von Zeitpunkt \( t+1 \) bis \( T \), gegeben dass der Zustand zum Zeitpunkt \( t \) \( s_i \) ist: \( \beta_t(i) = P(o_{t+1}, o_{t+2}, \ldots, o_T | q_t = s_i, \lambda) \). Der Rückwärtsdurchlauf initialisiert \( \beta_T(i) = 1 \) für alle \( i \) und berechnet rekursiv \( \beta_t(i) = \sum_{j=1}^N a_{ij} b_j(o_{t+1}) \beta_{t+1}(j) \). Die posteriore Wahrscheinlichkeit, sich zum Zeitpunkt \( t \) im Zustand \( s_i \) zu befinden, ist dann gegeben durch \( \gamma_t(i) = \frac{\alpha_t(i) \beta_t(i)}{\sum_{j=1}^N \alpha_t(j) \beta_t(j)} \).
Anwendungen in der Sequenzmodellierung
Der Algorithmus wird häufig zum Training von HMMs über den Baum-Welch-Algorithmus verwendet, einer Instanz der Erwartungsmaximierung. Im E-Schritt berechnet der Forward-Backward-Algorithmus erwartete hinreichende Statistiken, wie die erwartete Anzahl von Übergängen zwischen Zuständen und die erwartete Anzahl von Emissionen jedes Beobachtungssymbols. Diese Statistiken werden dann im M-Schritt verwendet, um die Modellparameter zu aktualisieren. Dieses iterative Verfahren konvergiert zu einem lokalen Maximum der Likelihood-Funktion.
In der Spracherkennung waren HMMs mit Forward-Backward-Training von den 1970er bis in die frühen 2000er Jahre der dominierende Ansatz für akustische Modellierung, bevor sie weitgehend durch Deep-Learning-Methoden ersetzt wurden. In der Bioinformatik wird der Algorithmus für die Genvorhersage und die Analyse von Proteinsequenzen verwendet, wobei HMMs konservierte Motive modellieren. In der natürlichen Sprachverarbeitung erscheint er bei der Part-of-Speech-Tagging und beim Training von Sequence-to-Sequence-Modellen, wenn diese mit strukturierten Ausgabeschichten verwendet werden.
Beziehung zum modernen maschinellen Lernen
Obwohl der Forward-Backward-Algorithmus eine klassische Technik ist, bleiben seine Prinzipien im modernen maschinellen Lernen bestehen. Der Vorwärtsdurchlauf ist analog zur Informationsausbreitung in rekurrenten neuronalen Netzen, und der Rückwärtsdurchlauf ähnelt der Rückpropagation von Fehlersignalen, obwohl sich die mathematischen Ziele unterscheiden. In neuronalen Netzen, die für Sequenzlabeling verwendet werden, wie bidirektionale LSTMs, werden die Vorwärts- und Rückwärts-Hidden-States kombiniert, um Kontext aus beiden Richtungen zu erfassen, was die Vorwärts- und Rückwärtsvariablen des Algorithmus widerspiegelt. Darüber hinaus hat die effiziente Nutzung der dynamischen Programmierung durch den Algorithmus ähnliche Techniken in Transformer-basierten Modellen inspiriert, wie den Forward-Backward-Algorithmus, der in einigen Formen der strukturierten Vorhersage und beim Training von großen Sprachmodellen für Aufgaben wie die Erkennung benannter Entitäten verwendet wird.
Der Algorithmus ist auch mit dem Konzept der Strahlensuche verwandt, da beide die Rechenkomplexität bei Sequenzproblemen verwalten, aber sie dienen unterschiedlichen Zwecken: Die Strahlensuche approximiert die wahrscheinlichste Sequenz, während Forward-Backward exakte Marginalwahrscheinlichkeiten berechnet. In probabilistischen grafischen Modellen ist der Forward-Backward-Algorithmus ein Spezialfall des Summen-Produkt-Algorithmus auf einem Ketten-Graphen und verallgemeinert sich auf baumstrukturierte Modelle über Belief Propagation.
Rechenkomplexität und Varianten
Der Forward-Backward-Algorithmus läuft in \( O(T N^2) \) Zeit und \( O(T N) \) Speicher, wobei \( T \) die Sequenzlänge und \( N \) die Anzahl der verborgenen Zustände ist. Diese Effizienz macht ihn für Sequenzen mit Tausenden von Zeitschritten und Hunderten von Zuständen machbar. Für große Zustandsräume werden Approximationen wie der Forward-Filtering-Backward-Sampling-Algorithmus in Partikelfiltern und Monte-Carlo-Methoden verwendet. In Online-Einstellungen kann allein der Vorwärtsalgorithmus für das Filtern verwendet werden, während der Rückwärtsdurchlauf die gesamte Sequenz erfordert, was ihn offline macht. Zu den Varianten gehört der skalierte Forward-Backward-Algorithmus, um numerischen Unterlauf zu vermeiden, der bei langen Sequenzen und kleinen Wahrscheinlichkeiten häufig auftritt.
Siehe auch
- hidden-markov-model
- Viterbi Algorithm
- Baum-Welch Algorithm
- dynamic-programming
- sequence-modeling