Viterbi アルゴリズム

Viterbi アルゴリズムはモデル$\lambda$において 最適な状態系列（最適経路） $S=s_1,s_2,...,s_T$と、この経路上での確率を求 めるアルゴリズムである。

モデル$\lambda$において観測系列 $O=o_1,o_2,...,o_T$に対する最 適な状態系列 $s=s_1,s_2,...,s_T$ を求めるために、時刻$t$で状 態$i$に至るまでの最適状態確率$\delta_t (i)$ を定義する。

$$\delta_t (i) = \max_{s_1,s_2,...,s_{t-1}} p(s_1,s_2,...,s_t=i,o_1,o_2,...,o_t \mid \lambda)$$ (2.15)

時刻$t+1$における最適状態の確率は次のように導出できる。

$$\delta_{t+1} (j) = [ \max_i \delta_t(i)a_{ij} ]\cdot b_{ij}(o_{t+1})$$ (2.16)

時刻$t$状態$i$において生成確率を最大にする経路（状態遷移）を $\psi_t(j)$ 、最適経路の生成確率を$P^*$ 、最適経路上の最終状態を $s_T^*$ とすると最適経路、およびその生成確率は以下の手順で求まる。

4.で求めた $s_0^*,s_1^*,...,s_T^*$が最適経路となる。 前出の$aab$を出力するモデルに Viterbi アルゴリズム を用いた簡単な 例を図 2.3 に示す。

図 2.3: Viterbi アルゴリズムの適用例