Python でのビタビアルゴリズムの実装

Vaibhav Vaibhav 2021年12月4日

Python

ビタビアルゴリズムは、最大事後確率で最も可能性の高い状態シーケンスを見つけるために使用されます。これは、動的計画法ベースのアルゴリズムです。この記事では、Python を使用してビタビアルゴリズムを実装する方法について説明します。実装には NumPy を使用します。

ビタビアルゴリズムの Python 実装

次のコードは、Python でビタビアルゴリズムを実装しています。次の 4つのパラメータを受け入れる関数です-

y：これは観測状態のシーケンスです。
A：これは状態遷移行列です。
B：これは放出マトリックスです。
initial_probs：これらは初期状態の確率です。

そして、関数は次のように 3つの値を返します-

x：モデルパラメータ A、B、initial_probs の下での観測シーケンス y を条件として、隠れた状態の軌跡の最大事後確率推定。
T1：最も可能性の高いパスの確率。
T2：最も可能性の高いパスの確率。

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

著者： Vaibhav Vaibhav

Vaibhav is an artificial intelligence and cloud computing stan. He likes to build end-to-end full-stack web and mobile applications. Besides computer science and technology, he loves playing cricket and badminton, going on bike rides, and doodling.