ビタビアルゴリズムは、観測された系列データから、最も確からしい隠れた状態の系列を効率的に見つけ出す動的計画法に基づくアルゴリズムです。隠れマルコフモデルなどの確率モデルにおいて、音声認識や形態素解析などに広く利用されています。
ビタビアルゴリズムとは
ビタビアルゴリズムとは、隠れマルコフモデルなどの確率的生成モデルにおいて、観測された出力から最も確率の高い隠れ状態の道筋を効率的に計算するための動적計画法（アルゴリズム）です。
詳しく解説
ビタビアルゴリズムは1967年にアンドリュー・ビタビによって提案されました。本来、すべての可能な状態の組み合わせを総当たりで計算すると、系列の長さに応じて計算量が指数関数的に爆発します。しかし、このアルゴリズムは動的計画法を用いることで、各ステップにおいて最適な部分経路だけを保持し、不要な経路を枝刈りしながら計算を進めます。これにより、計算量を劇的に削減することが可能となります。音声認識のデコードや自然言語処理の形態素解析、さらには通信分野のエラー訂正などにおいて極めて重要な役割を果たしています。
具体例・使われ方
具体的な利用例として、音声認識システムにおいて「spoken」という音声波形から、最も確率の高い単語の並び（テキスト）を復元する際に使用されます。また、自然言語処理の分野では、分かち書きされていない文に対して、各単語の品詞タグの最も確からしい並びを推定する品詞タギングにも適用されます。
似た用語との違い
全探索やフォワード・バックワードアルゴリズムなどの他の確率計算手法と混同されやすいです。全探索がすべての経路をしらみつぶしに計算するのに対し、ビタビアルゴリズムは「最尤（さいゆう）推定」として最も確率の高い単語列や状態の並びを効率的に特定することに特化しています。
注意点
ビタビアルゴリズムの適用には、モデルが隠れマルコフモデルのようにマルコフ性を満たしている必要があります。また、観測データや遷移確率が正確でない場合、得られる推定結果の精度も大きく低下するという限界があります。