How to Implement 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