Viterbi Algorithm
ビタビアルゴリズムは、動的計画法を使ってHMMの最も尤もらしい隠れ状態列を求める手法で、すべてのパスの列挙を避ける。
目的
HMMの最適な隠れ状態パスを効率的に復号する。音声認識やNLPで使われる。
メカニズム
前向き再帰 δ_t(j)=max_i[δ_{t-1}(i)*a_{ij}]*b_j(o_t) で計算し、最良の前置状態ψ_t(j)を記録する。時点Tで最大のδ_Tからバックトラッキングを開始し、ψを辿って最適パスを復元する。計算量はO(TN^2)である。
ユースケース
- スピーチ認識
- 品詞タグ付け
- バイオ配列解析