Forward-Backward Algorithm

Forward-backward computes exact state posteriors in a hidden Markov model by two passes of dynamic programming.

Marginals over hidden states

Given an observation sequence, we often want the posterior probability of each hidden state at each time step, p(z_t | x_1..x_T). The forward-backward algorithm computes all of these exactly in a single sweep forward and a single sweep backward, reusing shared sub-computations.

The forward pass

Define alpha_t(i) = p(x_1..x_t, z_t = i), the joint probability of the observations up to time t and being in state i. It recurses as alpha_t(j) = [ sum_i alpha_{t-1}(i) A_ij ] B_j(x_t), starting from the initial distribution. Summing alpha_T over all states gives the total sequence likelihood.

The backward pass

Define beta_t(i) = p(x_{t+1}..x_T | z_t = i), the probability of the remaining observations given state i now. It recurses backward as beta_t(i) = sum_j A_ij B_j(x_{t+1}) beta_{t+1}(j), starting from beta_T = 1. The state posterior is then proportional to alpha_t(i) beta_t(i).

# Forward recursion (log-space is safer in practice)
alpha[0] = pi * B[:, x[0]]
for t in range(1, T):
    alpha[t] = (alpha[t-1] @ A) * B[:, x[t]]
likelihood = alpha[T-1].sum()

Numerical care and cost

Naive products underflow for long sequences, so implementations either rescale alpha and beta at each step or work entirely in log-space with the log-sum-exp trick. The algorithm runs in O(T K^2) time and O(T K) memory. Its outputs are the E-step responsibilities used by Baum-Welch to re-estimate transition and emission parameters.

Forward-backward gives smoothed estimates because each state benefits from evidence both before and after it; using only the forward pass gives filtered estimates that condition on the past alone.