# Forward–backward algorithm

The forward-backward algorithm is a dynamic programming method for computing posterior probabilities of hidden states in a hidden Markov model, given an observation sequence. It is essential for training and inference in sequence models.

The forward-backward algorithm is a fundamental dynamic programming technique used in the context of hidden Markov models (HMMs) and related probabilistic sequence models. It computes the posterior marginal distribution of each hidden state given a sequence of observations, enabling efficient inference and parameter estimation. The algorithm is a cornerstone of classical machine learning and remains relevant in modern applications such as speech recognition, bioinformatics, and natural language processing.

Developed in the late 1960s and early 1970s, the algorithm was formalized by Leonard Baum and his colleagues in a series of papers on statistical estimation for probabilistic functions of Markov chains. It is often presented alongside the Viterbi algorithm, which finds the most likely sequence of hidden states, whereas the forward-backward algorithm computes probabilities for each individual state at each time step. The algorithm operates in two passes: a forward pass that computes the probability of observing the sequence up to a given time point and ending in a particular state, and a backward pass that computes the probability of observing the remainder of the sequence given a starting state. Combining these two sets of probabilities yields the desired posterior marginals.

## Mathematical Formulation

Consider an HMM with hidden states \( S = \{s_1, s_2, \ldots, s_N\} \), transition probabilities \( a_{ij} = P(s_j | s_i) \), emission probabilities \( b_j(o_t) = P(o_t | s_j) \), and initial state distribution \( \pi_i = P(s_i) \). For an observation sequence \( O = (o_1, o_2, \ldots, o_T) \), the forward variable \( \alpha_t(i) \) is defined as the probability of the partial observation sequence up to time \( t \) and being in state \( s_i \) at time \( t \): \( \alpha_t(i) = P(o_1, o_2, \ldots, o_t, q_t = s_i | \lambda) \), where \( \lambda \) denotes the model parameters. The forward pass initializes \( \alpha_1(i) = \pi_i b_i(o_1) \) and recursively computes \( \alpha_{t+1}(j) = b_j(o_{t+1}) \sum_{i=1}^N \alpha_t(i) a_{ij} \).

The backward variable \( \beta_t(i) \) is defined as the probability of the observation sequence from time \( t+1 \) to \( T \) given that the state at time \( t \) is \( s_i \): \( \beta_t(i) = P(o_{t+1}, o_{t+2}, \ldots, o_T | q_t = s_i, \lambda) \). The backward pass initializes \( \beta_T(i) = 1 \) for all \( i \) and recursively computes \( \beta_t(i) = \sum_{j=1}^N a_{ij} b_j(o_{t+1}) \beta_{t+1}(j) \). The posterior probability of being in state \( s_i \) at time \( t \) is then given by \( \gamma_t(i) = \frac{\alpha_t(i) \beta_t(i)}{\sum_{j=1}^N \alpha_t(j) \beta_t(j)} \).

## Applications in Sequence Modeling

The algorithm is widely used for training HMMs via the Baum-Welch algorithm, an instance of expectation-maximization. In the E-step, the forward-backward algorithm computes expected sufficient statistics, such as the expected number of transitions between states and the expected number of emissions of each observation symbol. These statistics are then used in the M-step to update the model parameters. This iterative procedure converges to a local maximum of the likelihood function.

In speech recognition, HMMs with forward-backward training were the dominant approach for acoustic modeling from the 1970s through the early 2000s, before being largely superseded by [deep learning](https://www.wikiprompt.org/wiki/deep-learning) methods. In bioinformatics, the algorithm is used for gene prediction and for analyzing protein sequences, where HMMs model conserved motifs. In natural language processing, it appears in part-of-speech tagging and in the training of [sequence-to-sequence](https://www.wikiprompt.org/wiki/sequence-to-sequence) models when used with structured output layers.

## Relationship to Modern Machine Learning

Although the forward-backward algorithm is a classical technique, its principles persist in modern [machine learning](https://www.wikiprompt.org/wiki/machine-learning). The forward pass is analogous to the propagation of information in [recurrent neural networks](https://www.wikiprompt.org/wiki/recurrent-neural-network), and the backward pass resembles the backpropagation of error signals, though the mathematical objectives differ. In [neural networks](https://www.wikiprompt.org/wiki/neural-network) used for sequence labeling, such as bidirectional LSTMs, the forward and backward hidden states are combined to capture context from both directions, mirroring the forward and backward variables of the algorithm. Furthermore, the algorithm's efficient use of dynamic programming has inspired similar techniques in [transformer](https://www.wikiprompt.org/wiki/transformer)-based models, such as the forward-backward algorithm used in some forms of structured prediction and in the training of [large language models](https://www.wikiprompt.org/wiki/large-language-model) for tasks like named entity recognition.

The algorithm is also related to the concept of [beam search](https://www.wikiprompt.org/wiki/beam-search) in that both manage computational complexity in sequence problems, but they serve different purposes: beam search approximates the most likely sequence, while forward-backward computes exact marginal probabilities. In probabilistic graphical models, the forward-backward algorithm is a special case of the sum-product algorithm on a chain graph, and it generalizes to tree-structured models via belief propagation.

## Computational Complexity and Variants

The forward-backward algorithm runs in \( O(T N^2) \) time and \( O(T N) \) space, where \( T \) is the sequence length and \( N \) is the number of hidden states. This efficiency makes it feasible for sequences of thousands of time steps with hundreds of states. For large state spaces, approximations such as the forward-filtering backward-sampling algorithm are used in particle filtering and Monte Carlo methods. In online settings, the forward algorithm alone can be used for filtering, while the backward pass requires the entire sequence, making it offline. Variants include the scaled forward-backward algorithm to avoid numerical underflow, which is common when dealing with long sequences and small probabilities.

## See Also

- hidden-markov-model
- [viterbi-algorithm](https://www.wikiprompt.org/wiki/viterbi-algorithm)
- [baum-welch-algorithm](https://www.wikiprompt.org/wiki/baum-welch-algorithm)
- dynamic-programming
- sequence-modeling

---
Source: https://www.wikiprompt.org/wiki/forward-backward-algorithm
License: CC BY-SA 4.0 (https://creativecommons.org/licenses/by-sa/4.0/)
Last updated: 2026-09-14T06:29:45.218011+00:00