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
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 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] 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