ビタビアルゴリズム
transition_probability は、このマルコフ連鎖での天気の変化を表している。この例では、今日が雨だった場合に翌日が晴れとなる可能性は 30% しかない。emission_probability は、友人がある活動を行う確率を示している。雨だった場合、50% の確率で部屋を掃除する。晴れだった場合、60% の確率で外を散歩する。
友人と三日間続けて話をしたところ、初日は散歩、二日目は買い物、三日目は掃除をしたという。ここで2つの疑問が生じる。この観測されたシーケンスの全体としての確率はどうなるか? そして、この観測結果を説明する最も尤もらしい天気のシーケンスはどうなるか? 第一の疑問には前向きアルゴリズムで答えられる。第二の疑問にはビタビアルゴリズムで答えられる。これら2つのアルゴリズムは構造的に非常に近いので(実際、これらは同じ抽象アルゴリズムのインスタンスである)、1つの関数として次のように実装できる。
関数 forward_viterbi は、次のような引数をとる。y は観測シーケンスであり、例では ('walk', 'shop', 'clean') となる。X は隠された状態の集合である(例では states)。sp は初期の確率である(例では start_probability)。tp は遷移確率である(例では transition_probability)。ep は隠された状態から観測された状態への対応確率である(例では emission_probability)。
このアルゴリズムは、T と U というマッピングを使う。
遠く離れた地に友人がいて、毎日その友人と電話をして彼がその日何をしたかを聞くものとする。その友人は、公園を散歩すること、買い物をすること、部屋を掃除することという3つのことにしか興味が無い。ある日にどれをするかは、その日の天気だけに依存する。その友人が住んでいる地の天気に関する具体的情報は、別経路では全く得られないが、一般的傾向はわかっている。彼が電話で話した毎日の行動に基づいて、その場所の天気を推測してみよう。 天気の変動は離散マルコフ連鎖になっているものとする。状態としては「雨; Rainy」と「晴れ; Sunny」の2つだけだが、直接観測することはできないので、我々にとってはそれが「隠された」状態である。毎日、友人は「散歩; walk」、「買い物; shop」、「掃除; clean」のいずれかを行う可能性がある。彼は何をしたかを電話連絡してくるので、それが「観測された」状態となる。システム全体としては、隠れマルコフモデル (HMM) となる。
その地域の天気の傾向はわかっていて、平均的にその友人が何をする傾向があるかもわかっている。言い換えれば、HMM のパラメータは既知である。これを Python で書くと次のようになる。
このコードにおいて、start_probability は最初に友人が電話してきたときに HMM がどの状態にあるかを表している(つまり、雨の可能性がやや高いということしか知らない)。ここで使われている確率分布は定常時のものではない(定常時の確率分布はだいたい {'Rainy': 0.571, 'Sunny': 0.429} である)。