隠れマルコフモデル
ビタビアルゴリズム(Viterbi algorithm)は、モデルパラメータが既知のとき、与えられた配列を出力した可能性(尤度)が最も高い状態列(最尤状態列)を計算するアルゴリズムで、動的計画法の一種である。ある時点 t での最尤状態遷移列はtまでに観測された情報と、t-1 までで最も確からしい(=尤もらしい)最尤状態遷移列だけに依存すると仮定する。
例えば、出力 'A' と 'B' を確率0.5ずつで出力し、他の状態にまれにしか遷移しない状態 A と、出力 'A' と 'C' を確率0.5ずつで出力し、他の状態にまれにしか遷移しない状態Bがあった場合、時点 t で 'A' が出力され、時点 t-1 で最尤だと推定された状態遷移列からの遷移確率が状態 A の方が高いならば、時点 t では状態 A にいたと推定される。しかし、t+1 以降で 'C' の出力が続いた場合、全体としての尤度は状態 B に遷移していたほうが高くなる。
ビタビアルゴリズムを使用するには、観測可能なイベントは観測不可能な状態遷移と1対1対応していることが求められる。
隠れマルコフモデル(かくれマルコフモデル、英: hidden Markov model; HMM)は、確率モデルのひとつであり、観測されない(隠れた)状態をもつマルコフ過程である。
アリスは、ボブのいる地域の一般的な天候の変化(遷移確率)については知っている。また、どの天気のときにボブがどの行動をするか(出力確率)を知っている。つまり隠れマルコフモデルのパラメータが既知である。これは、Pythonで次のように表される。
このコードでstart_probability は、ボブが最初に電話する前の時点で、隠れマルコフモデルがどちらの状態にあるかというアリスの考えである(彼女は平均的には雨の方がやや多いと知っている)。この確率分布は平衡なものではない(遷移確率によれば平衡は {'Rainy': 0.57, 'Sunny': 0.43})。遷移確率 transition_probability はマルコフ連鎖での天気の変化を表す。この例では、今日が雨であれば、明日晴れる確率は30%である。出力確率 emission_probability は、その日にボブが行う行動の確率である。もし雨であれば掃除をする確率は50%で、晴れていれば散歩に行く確率は60%である。