Implementação do Algoritmo de Viterbi em Python

O Algoritmo de Viterbi é usado para encontrar a sequência de estados mais provável com a probabilidade máxima a posteriori. É um algoritmo baseado em programação dinâmica. Este artigo irá falar sobre como podemos implementar o Algoritmo de Viterbi usando Python. Usaremos NumPy para a implementação.

Implementação Python do Algoritmo de Viterbi

O código a seguir implementa o Algoritmo de Viterbi em Python. É uma função que aceita 4 parâmetros que são os seguintes -

• y: Esta é a sequência do estado de observação.
• A: Esta é a matriz de transição de estado.
• B: Esta é a matriz de emissão.
• initial_probs: Estas são as probabilidades de estado inicial.

E a função retorna 3 valores da seguinte forma -

• x: Estimativa de probabilidade máxima a posteriori da trajetória do estado oculto, condicionada na sequência de observação y sob os parâmetros do modelo A, B, inicial_probs.
• T1: A probabilidade do caminho mais provável.
• T2: A probabilidade do caminho mais provável.

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