Forward Algorithm

The forward algorithm computes the probability of an observed sequence in a hidden Markov model by summing over all possible hidden state paths, rather than finding the single most probable path as the Viterbi algorithm does. It uses dynamic programming to fill a matrix of forward probabilities, where each entry α_t(i) represents the probability of emitting the observed sequence up to time t and ending in hidden state i.

The forward algorithm is the evaluation problem of HMMs: given a model and an observation sequence, what is P(observations | model)? It is the basis for the Baum-Welch algorithm, which uses forward and backward probabilities to iteratively estimate HMM parameters.

The forward algorithm is less glamorous than the Viterbi algorithm because it does not produce a single path. It produces a probability. But that probability is the fundamental quantity for learning and model comparison. Without the forward algorithm, the Viterbi path would be a mere assertion, not a measured inference.