Viterbiアルゴリズム

Viterbiアルゴリズムは、シンボル系列 $O$ を生成するモデル $M$に対する 最適な状態遷移系列（最適経路）と、その経路上での確率を求めるためのアルゴ リズムである。シンボル系列 $o^{T}_{1} = o_{1} … o_{T}$ に対する最適経 路は、状態遷移確率 $P(o^{T}_{1}, q^{T}_{1}｜M)$ を最大にするような経路 $q^{T}_{1} = q_{1} … q_{T}$ であり、Viterbiアルゴリズムでは、この最適 経路を求める。Viterbiアルゴリズムの詳細について、参考文献[4]より引用し、 以下に説明する。

　
時刻 $t$ において、状態 $q_{i} (1≦i≦N)$ がシンボル系列 $o^{t}_{1} = o_{1} … o_{t}$ を生成する確率の最大値 $\delta_{t}(i)$ を求める。

$$\delta_{t}(i) = \max_{q^{t}_{1}}P(q^{t-1}_{1},X_{t} = q_{i},o^{t}_{1}｜M)$$

$\delta_{t}(i)$ は、以下のように再帰的に計算できる。

$$\delta_{t+1}(i) = \max_{i}[\delta_{t}a_{ij}]b_{j}(o_{t+1})$$

ここで、$a_{ij}$ は状態 $q_{i}$ から $q_{j}$ に遷移する確率、 $b_{i}(o_{t})$ は状態 $q_{i}$ でシンボル $o_{t}$ を出力する確率で ある。
また、状態遷移系列を復元するために、 $\delta_{t+1}(i)$ を与える直前の状 態 $i$ を $\psi(・)$ に記憶しておく。

$$\psi_{t+1}(j) = \arg\max_{i}[\delta_{t}(i)a_{ij}]$$

再帰計算が終了したら、時刻 $t = T$ における最適経路を、 $t = T - 1, ... , 1$ において、

$$\hat{q}_{t} = \psi_{t+1}(\hat{q}_{t+1})$$

により復元する。ただし、 $\hat{q}_{T} = \arg\max_{i} \delta_{T}(i)$ で ある。

以上の操作により、最適経路 $q^{T}_{1} = \hat{q}_{1} … \hat{q}_{T}$ が 求められる。