Implementierung des Viterbi-Algorithmus in Python

Der Viterbi-Algorithmus wird verwendet, um die wahrscheinlichste Zustandsfolge mit der maximalen a posteriori-Wahrscheinlichkeit zu finden. Es ist ein dynamischer programmbasierter Algorithmus. In diesem Artikel wird erläutert, wie wir den Viterbi-Algorithmus mit Python implementieren können. Für die Implementierung verwenden wir NumPy.

Python-Implementierung des Viterbi-Algorithmus

Der folgende Code implementiert den Viterbi-Algorithmus in Python. Es ist eine Funktion, die 4 Parameter akzeptiert, die wie folgt lauten:

• y: Dies ist die Beobachtungszustandssequenz.
• A: Dies ist die Zustandsübergangsmatrix.
• B: Dies ist die Emissionsmatrix.
• initial_probs: Dies sind die Anfangszustandswahrscheinlichkeiten.

Und die Funktion gibt 3 Werte wie folgt zurück -

• x: Maximale a-posteriori-Wahrscheinlichkeitsschätzung der Trajektorie des versteckten Zustands, konditioniert auf die Beobachtungssequenz y unter den Modellparametern A, B, initial_probs.
• T1: Die Wahrscheinlichkeit des wahrscheinlichsten Pfads.
• T2: Die Wahrscheinlichkeit des wahrscheinlichsten Pfads.

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