Backward phase

During the backward phase, we need to compute the probability of a sequence starting at time t+1: o_t+1, o_t+2, ..., o_{Sequence 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 x_Ending, which is not emitting, like the initial state; therefore we have:

We terminate the recursion with the initial state:

The steps are the following ones: 

1. Initialization of a vector Backward with shape (N + 2, Sequence Length).
2. Initialization of A (transition probability matrix) with shape (N, N). Each element is P(x_i|x_j).
3. Initialization of B with shape (Sequence Length, N). Each element is P(o_i|x_j).

1. For i=1 to N:
   1. Set Backward[x_Endind, Sequence Length] = A[i, x_Endind]
2. For t=Sequence Length-1 to 1:
   1. For i=1 to N:
      1. Set S = 0
      2. For j=1 to N
         1. Set S = S + Backward[j, t+1] · A[j, i] · B[t+1, i]
      3. Set Backward[i, t] = S
3. Set S = 0.
4. For i=1 to N:
   1. Set S = S + Backward[i, 1] · A[0, i] · B[1, i]
5. Set Backward[0, 1] = S.