Viterbiアルゴリズムは、与えられた一連の観測イベントを生成した可能性が最も高い隠れ状態の系列を特定する動的計画法アルゴリズムである。結果として得られる系列は、しばしばViterbi経路と呼ばれる。これは最も一般的には隠れマルコフモデル（HMM）に適用され、そこでは基礎となる状態が直接観測可能ではないが、観測に影響を与える。例えば、医師が数日間にわたって患者の症状を観察する場合、このアルゴリズムを用いて、それらの症状を引き起こした基礎となる健康状態の最も可能性の高い系列を推測できる。
このアルゴリズムは、CDMAおよびGSMデジタル携帯電話ネットワーク、ダイヤルアップモデム、衛星および深宇宙通信、802.11無線LANで使用される畳み込み符号の復号に広く応用されている。また、音声認識、音声合成、話者ダイアライゼーション、キーワードスポッティング、計算言語学、バイオインフォマティクスでも広く使用されている。音声からテキストへの変換システムでは、音響信号が観測系列として機能し、テキスト文字列が隠れた原因となる。Viterbiアルゴリズムは、音響信号が与えられた場合に最も可能性の高いテキストを見つける。
歴史
Viterbiアルゴリズムは、1967年にノイズの多いデジタル通信リンク上の畳み込み符号の復号アルゴリズムとして提案したAndrew Viterbiにちなんで名付けられた。これは複数回の発明の歴史を持ち、Viterbi、NeedlemanとWunsch、WagnerとFischerによるものを含む少なくとも7つの独立した発見がある。これは1987年には早くも品詞タグ付けの方法として自然言語処理に導入された。
「Viterbi経路」および「Viterbiアルゴリズム」という用語は、確率を含む最大化問題に対する動的計画法アプローチの標準となっている。統計的構文解析では、動的計画法アルゴリズムが文字列の最も可能性の高い単一の文脈自由導出（構文解析）を発見でき、これは一般に「Viterbi構文解析」と呼ばれる。もう一つの応用はターゲット追跡であり、そこではアルゴリズムが一連の観測に対して最大尤度を割り当てる軌跡を計算する。
アルゴリズム概要
隠れ状態の集合S、可能な放出（観測）の集合M、およびT個の観測の系列o0, o1, ..., oT-1を持つ隠れマルコフモデルが与えられた場合、Viterbiアルゴリズムはそれらの観測を生成した可能性が最も高い隠れ状態の系列を見つける。各時間ステップtで、アルゴリズムは観測がotまでのみ考慮される部分問題を解く。
サイズT × |S|の2つの行列が構築される。行列Pt,sは、観測tで状態sに到達する最大確率を含み、そこに至るすべての可能な状態系列のうちのものである。行列Qt,sは、この最大確率の状態系列においてsの前に使用された前の状態を追跡する。
πsとar,sをそれぞれ初期確率と遷移確率とし、bs,oを状態sでのoの観測確率とする。すると、Pの値は漸化式によって与えられる。時間t = 0では、Pt,sはπsにbs,o0を掛けたものに等しい。t > 0では、Pt,sはすべての前の状態rに対する(Pt-1,r × ar,s × bs,ot)の最大値に等しい。行列を埋めた後、アルゴリズムは最終時間ステップで最も高い確率を持つ状態からQ行列を使用して逆方向にトレースし、最も可能性の高い状態系列を再構築する。
通信における応用
このアルゴリズムは現代のデジタル通信の基礎である。これは、多くの無線および有線システムで使用される誤り訂正符号である畳み込み符号を復号する。CDMAおよびGSM携帯電話ネットワークでは、Viterbiアルゴリズムはノイズや干渉にもかかわらず送信データの回復を支援する。ダイヤルアップモデム、衛星リンク、および深宇宙通信システムもこれに依存している。802.11無線LAN標準は、信頼性の高いデータ伝送のためにViterbi復号を組み込んでいる。
このアルゴリズムの効率性はその動的計画法の性質に由来する。つまり、中間確率を保存し、最適性の原理を使用することで、すべての可能な状態系列の網羅的な列挙を回避する。これにより、リソースに制約のあるデバイスでも、長い系列をリアルタイムで復号することが可能になる。
音声および言語における応用
音声認識では、Viterbiアルゴリズムは音響特徴を音声または単語モデルと整列させる。音響信号が観測系列であり、テキスト文字列が隠れた原因である。このアルゴリズムは、音響信号が与えられた場合に最も可能性の高いテキスト文字列を見つけ、正確な書き起こしを可能にする。また、音声合成では最も自然な音声ユニットの系列を選択するために、話者ダイアライゼーションでは誰がいつ話したかを決定するために使用される。
計算言語学では、このアルゴリズムは品詞タグ付けに適用され、そこでは隠れ状態が文法カテゴリであり、観測が単語である。また、統計的構文解析もサポートし、文の最も可能性の高い構文解析ツリーを見つける。バイオインフォマティクスでは、生物学的系列の整列や遺伝子構造の予測を支援し、DNAまたはタンパク質配列を観測として、機能的要素を隠れ状態として扱う。
関連技術
Viterbiアルゴリズムは、他の動的計画法手法と密接に関連しており、例えば前向き後ろ向きアルゴリズムは、最も可能性の高いものだけでなく、すべての可能な状態系列にわたる確率を計算する。また、系列生成で使用されるヒューリスティック探索手法であるBeam Searchと概念的な基盤を共有している。現代のMachine learningおよびArtificial intelligenceシステム、特にSequence-to-Sequence (Seq2Seq)モデルやLarge language modelを含むものでは、関与する状態空間が大きいため、正確なViterbi復号よりもビーム探索が好まれることが多い。
Neural networkアプローチの台頭にもかかわらず、Viterbiアルゴリズムはハイブリッドシステムにおいて依然として関連性がある。例えば、音声認識におけるNeural network音響モデルからの出力を復号するため、またはNatural language processingタスクで構造的制約を強制するために使用できる。その数学的な明瞭さと効率性により、古典的および現代的な応用の両方で継続的な使用が保証されている。