# Backward algorithm Hidden Markov Model, 0th index (termination step) yields wrong result

I’m implementing a backwards HMM algorithm. I used this link as reference. This link contains the results of the numerical example used (I am attempting to implement that and compare my generated results to it). Page 3, section 2. Backward probability , there is a table containing the calculated results.

Here is my code:

``````# Initial Transition matrix as shown in page 2 of above link
A = np.array([[0.6, 0.4], [0.3, 0.7]])
A = torch.from_numpy(A)

# Initial State Probability (page 2)
pi = np.array([0.8, 0.2])
pi = torch.from_numpy(pi)

# Output probabilities (page 2)
emission_matrix = np.array([[0.3, 0.4, 0.3, 0.3], [0.4, 0.3, 0.3, 0.3]])
emission_matrix = torch.from_numpy(emission_matrix)

# Initialize empty 2x4 matrix (dimensions of emission matrix)
backward = torch.zeros(emission_matrix.shape, dtype=torch.float64)

# Backward algorithm
def _backward(emission_matrix):
# Initialization: A(i, j) * B(T, i) * B(Ot+1, j) , where B(Ot+1, j)  = 1
backward[:, -1] = torch.matmul(A, emission_matrix[:, -1])

# I reversed the emission matrix so as to start from the last column
rev_emission_mat = torch.flip(emission_matrix[:, :-1], [1])

# I transposed the reversed emission matrix such that each iterable in the for
# loop is the observation sequence probability
T_rev_emission_mat = torch.transpose(rev_emission_mat, 1, 0)

# This step is so that I assign a reverse index enumeration to each iterable in the
# emission matrix starts from time T to 0, rather than the opposite
zipped_cols = list(zip(range(len(T_rev_emission_mat)-1, -1, -1), T_rev_emission_mat))

for i, obs_prob in zipped_cols:
# Induction: Σ A(i, j) * B(j)(Ot+1) * β(t+1, j)
if i != 0:
backward[:, i] = torch.matmul(A * obs_prob, backward[:, i+1])

# Termination: Σ π(i) * bi * β(1, i)
backward[:, 0] = torch.matmul(pi * obs_prob, backward[:, 1])

# run backward algorithm
_backward(emission_matrix)

# check results, backward is an all zero matrix that was initialized above
print(backward)
>>> tensor([[0.0102, 0.0324, 0.0900, 0.3000],
[0.0102, 0.0297, 0.0900, 0.3000]], dtype=torch.float64)
``````

As you can see, the 0-th index does not match the result in page 3 of the previous link. What did I do wrong? If there is anything I can clarify, please let me know. Thanks in advance!

Leaving this for reference. Someone solved the question on stackoverflow with a simple one liner (https://stackoverflow.com/questions/57466547/backward-algorithm-hidden-markov-model-0th-index-termination-step-yields-wron/57482129#57482129)

``````backward[:, 0] = pi * obs_prob * backward[:, 1]
``````

I had the wrong matrix shape, in the termination step part of the code (the last line in the method). Cheers!