Forward Algorithm

Notice that we have an expression to calculate at time t+1 using only the partial probabilities at time t.

We can now calculate the probability of an observation sequence given a HMM recursively - i.e. we use 's at t=1 to calculate 's at t=2; 's at t=2 to calculate 's at t=3; and so on until t = T. The probability of the sequence given the HMM is then the sum of the partial probabilities at time t = T

2d. Reduction of computational complexity

We can compare the computational complexity of calculating the probability of an observation sequence by exhaustive evaluation and by the recursive forward algorithm.

We have a sequence of T observations, O. We also have a Hidden Markov Model, l=(,A,B), with n hidden states.