During the backward phase, we need to compute the probability of a sequence starting at time t+1: ot+1, ot+2, ..., oSequence Length, given that the state at time t is i. Just like we have done before, we define the following probability:
The backward algorithm is very similar to the forward one, but in this case, we need to move in the opposite direction, assuming we know that the state at time t is i. The first state to consider is the last one xEnding, which is not emitting, like the initial state; therefore we have:
We terminate ...
