ビタビアルゴリズム
ビタビアルゴリズム(英: Viterbi algorithm)は、観測された事象系列を結果として生じる隠された状態の最も尤もらしい並び(ビタビ経路と呼ぶ)を探す動的計画法アルゴリズムの一種であり、特に隠れマルコフモデルに基づいている。観測された事象系列の確率計算のアルゴリズムである 前向きアルゴリズム(forward algorithm)も密接に関連している。これらのアルゴリズムは情報理論の一部である。
このアルゴリズムには、いくつかの前提条件がある。まず、観測された事象と隠されている事象は1つの系列上に並んでいる。この系列は多くの場合時系列である。次に、これら2つの並びには一対一の対応があり、1つの観測された事象は正確に1つの隠されている事象に対応している。第三に、時点 t での最も尤もらしい隠されている事象の計算は、t での観測された事象と t − 1 での最も尤もらしい隠された事象の系列のみに依存している。これらの前提条件は、全て一次隠れマルコフモデルで満たされている。