Viterbiアルゴリズムとは

動的計画法の一種である。

数式で表すと下記のような数式を再帰的に計算し、

$$ \delta_{t+1}(j)=max_{i}[\delta_i(i)a_{ij}]b_j(o_{t+1}) $$ $$ \psi_{i+1}(j)=argmax_{i}[\delta_i(i)a_{ij}] $$

時刻 $t=1,2,…,T-1$ として、状態 $q_j(j=1,…,N)$の最大の確率値 $\delta_{t+1}(j)$を再帰的に計算する。

そして、最大の確率値 $\delta_{t+1}(j)$ の直前の状態iを記録している $\psi$ も更新する

$ a_{ij} $ は、状態iから状態jに遷移する際の確率を表し $ b_j(o_{t+1}) $ は、時刻t+1における値 $ o_{t+1} $ を状態jで取りうる確率を表す

この再帰計算により、尤もらしい（最も確率の高い）状態のみを保存していくことで、全ての状態に対する組み合わせを考えなくて済む。

参考文献