隠れマルコフモデル |

隠れマルコフモデル（HMM）は、有限状態オートマンに確率を付与したモデルである。アラインメントやモチーフ領域の予測などバイオインフォマティックスの分野で幅広く使われている。

隠れマルコフモデルは、次の四項で構築される。

Σ	配列を構成する文字列の集合を表す。例えば、核酸ならば Σ={A,C,G,T} となり、このとき集合の大きさ \|Σ\| = 4 である。
Q = {q₀, q₁, ..., q_m}	状態の集合を表す。
A = (a_kl)	状態遷移確率を表す (m+1)×(m+1) の行列。a_kl は、q_k から q_l への遷移確率を表す。また、Σ_la_kl = 1 が成り立つ。
E = (e_k(b))	文字の出力確率を表す (m+1)×\|Σ\| の行列。(e_k(b)) は状態q_k において、文字 b を出力する確率を表す。また、Σ_be(_k(b)) = 1 が成り立つ。

HMM では、開始状態から終了状態に到達するまでの道のりをパスといい、π で表す。例えば、q₁ → q₂ → q₃ → q₁ → q₄ のように、状態が遷移したとき、パス π は次のように書き表せる。

\[ \pi = \pi[1]\pi[2]\pi[3]\pi[4]\pi[5] \]

ただし、π₁=q₁、π₂=q₂、π₃=q₃、π₄=q₁、π₅=q₄ である。

ここで、もし状態遷移確率 A と文字出力確率 E が既知ならば、「パス π=π[1]π[2]...π[n] が生成され」かつ「配列 s=s[1]s[2]...s[n] が生成される」同時確率は次のように書ける。

\[ P(s, \pi | A, E) = a_{0\pi [1]}\prod_{i=1}^{n}\left( e_{\pi [i]}(s[i])\cdot a_{\pi [i]\pi [i+1]} \right) \]

このように構築された HMM に対して、配列 s を生成する確率を求めたり、逆に配列 s を入力して状態遷移確率 A や文字出力確率 E を求めたりすることができる。これらの問題を解決するために、様々なアルゴリズムが考え出されている。有名なものとしては、次に挙げたようなアルゴリズムがある。

アルゴリズム
Viterbi アルゴリズム	配列 s を生成するパス π を求めるアルゴリズム。
前向きアルゴリズム	配列 s を生成する確率を求めるアルゴリズム。
後向きアルゴリズム	配列 s を生成する確率を求めるアルゴリズム。
Baum-Welch アルゴリズム	入力配列を学習して、状態遷移確率 A や文字出力確率 E を推測するアルゴリズム。