Implementación del algoritmo de Viterbi en Python

El algoritmo de Viterbi se utiliza para encontrar la secuencia de estados más probable con la máxima probabilidad a posteriori. Es un algoritmo basado en programación dinámica. Este artículo hablará sobre cómo podemos implementar el algoritmo de Viterbi usando Python. Usaremos NumPy para la implementación.

Implementación en Python del algoritmo de Viterbi

El siguiente código implementa el algoritmo de Viterbi en Python. Es una función que acepta 4 parámetros que son los siguientes:

• y: esta es la secuencia del estado de observación.
• A: Esta es el array de transición de estados.
• B: Esta es el array de emisión.
• initial_probs: son las probabilidades del estado inicial.

Y la función devuelve 3 valores de la siguiente manera:

• x: Estimación de probabilidad máxima a posteriori de la trayectoria del estado oculto, condicionada a la secuencia de observación y bajo los parámetros del modelo A, B, initial_probs.
• T1: la probabilidad del trayecto más probable.
• T2: la probabilidad del trayecto más probable.

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