隠れマルコフモデル

今週の自主セミナーのテーマは隠れマルコフモデル(HMM)。
Wikipedia先生による説明は以下の通り。

隠れマルコフモデル（かくれマルコフモデル, Hidden Markov Model）は確率モデルの一つである。 「システムがパラメータ未知のマルコフ過程である」と仮定し、 観測可能な情報からその未知のパラメータを推定する。 音声認識、ゲノミクス、形態素解析(自然言語処理)などに応用されている。 IBMの考案。連続的かつ伸縮しうる信号列のパターン抽出には適しているが、反面、 長い距離をはさんで呼応しているような信号列からのパターン認識には、間の距離の長さに応じて状態数を増やす必要があり、計算量の観点から実用的ではない。 また、局所最適に陥りやすいため、対象に応じて適切なパラメータの初期値を設定してやる(適切なモデルトポロジーを導入する)必要がある。

とはいってもたぶんわかりずらい(-"-)>
そこでカジノを例にして説明してみることにする。
まず以下のような簡単なゲームを考える。
「ディーラーがコインを投げ、参加者が裏か表かを当てる」
通常ならコインが表・裏を出す確率は同等（つまりどちらも0.5)
しかしディーラーはたまに表・裏の確率が同等でないイカサマコインを使う。

参加者はディーラーがいつコインを交換するかはわからない。

観測不可能
コイン：正正正正正正正正正正裏裏裏裏裏裏表

参加者が観測できるのは今までの表・裏の結果だけ。

観測可能
結果：表表裏裏表裏表裏裏表表表裏表表裏裏

これを確率モデルでモデル化したものがHMMだ。
例えば、ディーラーが1/4の確率でコインを交換し、
イカサマコインは表の確率が3/4である場合をモデル化すると以下のようになる。

ここでコインは状態、表・裏の結果を観測値という。
またコインを交換する確率はtransition probability、
各コインの表裏の確率はemission probabilityという。
ここで参加者は観測値のみしか情報として得ることができず、
状態の変化は隠れたままなため、隠れマルコフモデルという。
ちなみに観測値からtransition probabilityやemission probabilityを
推定するアルゴリズムにBaum-Welchアルゴリズムがあり、
推定した隠れマルコフモデルと観測値から最もらしい状態の変化を導く
Viterbiアルゴリズムがある。
つまりこのふたつのアルゴリズムを使えば、表裏の結果から
ディーラーがどこでコインを交換したのかを最もらしい答えを出すことができる。