Home Statistical Dictionary Forward-Backward Algorithm

Forward-Backward Algorithm

A dynamic programming procedure that computes the probability of a hidden Markov model being in each possible state at every time point, using the entire observed sequence, both what came before and what came after.

Stochastic ProcessesAdvancedFree

In Plain English

If you only look at observations up to the present, you can make a reasonable guess about a hidden Markov model's current hidden state, that's filtering. But the forward-backward algorithm does better: it uses the entire sequence, including observations that haven't happened yet relative to a given time point, to compute the best possible estimate of the hidden state at every point in the sequence, a step called smoothing. It works by combining two efficient sweeps through the data, a forward pass accumulating evidence from the past, and a backward pass accumulating evidence from the future, then combining the two at each time point.

Definition

The forward-backward algorithm computes the smoothed posterior distribution $P (Z_{t} = i ∣ X_{1}, \dots, X_{T})$ for a hidden Markov model, using the entire observed sequence of length $T$ . The forward pass recursively computes $α_{t} (i) = P (X_{1}, \dots, X_{t}, Z_{t} = i)$ , the joint probability of the observations up to time $t$ and being in state $i$ at time $t$ , building up from $t = 1$ to $t = T$ . The backward pass recursively computes $β_{t} (i) = P (X_{t + 1}, \dots, X_{T} ∣ Z_{t} = i)$ , the probability of the remaining future observations given state $i$ at time $t$ , building up from $t = T$ back to $t = 1$ . Combining both, $P (Z_{t} = i ∣ X_{1}, \dots, X_{T}) \propto α_{t} (i) β_{t} (i)$ , gives the exact smoothed state probability using all available information. Both the forward and backward recursions run in $O (T \cdot N^{2})$ time (for $N$ hidden states and sequence length $T$ ), a dramatic improvement over the naive $O (N^{T})$ cost of summing over every possible hidden state sequence directly, and the forward pass alone also gives the total sequence likelihood $P (X_{1}, \dots, X_{T}) = \sum_{i} α_{T} (i)$ , needed for the E-step of the Baum-Welch algorithm.

Formula

P (Z_{t} = i ∣ X_{1}, \dots, X_{T}) \propto α_{t} (i) β_{t} (i)

Notation

α_{t} (i)

—Forward probability: joint probability of observations up to $t$ and state $i$ at time $t$

β_{t} (i)

—Backward probability: probability of future observations given state $i$ at time $t$

Properties

The dynamic programming trick underlying both passes, reusing partial computations rather than recomputing sums from scratch, is exactly what turns an intractable exponential-time problem (summing over every possible length- $T$ hidden state sequence) into a polynomial-time one, the same core idea that makes the Viterbi algorithm efficient too.
Forward probabilities alone answer the filtering question (state given only past and present observations) and the total-likelihood question, needed on their own in real-time applications, while the full forward-backward combination is needed specifically for smoothing and for the E-step of Baum-Welch parameter learning.
This algorithm has close cousins across the broader state-space model family: the Kalman filter's forward pass (filtering) and the associated Kalman smoother (using a backward pass analogous to $β_{t}$ ) solve the exact same forward/backward estimation problem for linear-Gaussian, continuous-state models instead of discrete HMMs.

At a Glance

Computessmoothed hidden-state probabilities using the full observed sequence

Two passesforward (

α_{t}

, past evidence) and backward (

β_{t}

, future evidence)

Combined result

P (Z_{t} = i ∣ all data) \propto α_{t} (i) β_{t} (i)

Efficiency

O (T N^{2})

via dynamic programming, vs.

O (N^{T})

for brute-force enumeration

Last updated September 8, 2026← Back to the Dictionary