Implementation of the Viterbi Algorithm in Python

Viterbi Algorithm is used for finding the most likely state sequence with the maximum a posteriori probability. It is a dynamic programming-based algorithm. This article will talk about how we can implement the Viterbi Algorithm using Python. We will use numpy for the implementation.

Python implementation of the Viterbi Algorithm

The following code implements the Viterbi Algorithm in Python. It is a function that accepts 4 parameters which are as follows -

  • y: This is the observation state sequence.
  • A: This is the state transition matrix.
  • B: This is the emission matrix.
  • initial_probs: These are the initial state probabilities.

And the function returns 3 values as follows -

  • x: Maximum a posteriori probability estimate of hidden state trajectory, conditioned on observation sequence y under the model parameters A, B, initial_probs.
  • T1: The probability of the most likely path.
  • T2: The probability of the most likely path.
import numpy as np

def viterbi(y, A, B, initial_probs = None):
    K = A.shape[0]
    initial_probs = initial_probs if initial_probs is not None else np.full(K, 1 / K)
    T = len(y)
    T1 = np.empty((K, T), 'd')
    T2 = np.empty((K, T), 'B')
    T1[:, 0] = initial_probs * B[:, y[0]]
    T2[:, 0] = 0
    
    for i in range(1, T):
        T1[:, i] = np.max(T1[:, i - 1] * A.T * B[np.newaxis, :, y[i]].T, 1)
        T2[:, i] = np.argmax(T1[:, i - 1] * A.T, 1)

    x = np.empty(T, 'B')
    x[-1] = np.argmax(T1[:, T - 1])
    
    for i in reversed(range(1, T)):
        x[i - 1] = T2[x[i], i]

    return x, T1, T2
Contribute
DelftStack is a collective effort contributed by software geeks like you. If you like the article and would like to contribute to DelftStack by writing paid articles, you can check the write for us page.