Main Content

マルコフ連鎖

マルコフ モデルは、確率過程 (ランダムな連続的な出力または"状態"をある確率に従い生成する過程) の例です。マルコフ過程は、無記憶性によって区別されます。マルコフ過程での現在の状態に続く次の状態は、現在の状態にのみ依存し、その状態に至った履歴には依存しません。マルコフ過程のモデルは、毎日の株価や染色体における遺伝子の位置など、広範囲に利用されます。

マルコフ モデルは、下記のような、state diagramをもつ可視化表現で与えられます。

マルコフ モデルに対する状態図

上図の四角形は、モデル化しようとしている過程が取り得る状態を表し、矢印は、状態間の遷移を表します。各矢印上のラベルは、遷移確率を表します。過程の各ステップにおいて、このモデルは、現在の状態に依存して、出力(emission)を生成してから他の状態に遷移します。マルコフ モデルの重要な特性は、次の状態が現在の状態のみに依存し、現在の状態に至った遷移の履歴には依存しないことです。

たとえば、一連のコイン投げの場合、表と裏の 2 つの状態があります。最後のコイン投げが、モデルの現在の状態を決定します。また、その後、投げるごとに、次の状態への遷移が決定されます。コインが公正であれば、遷移確率はすべて 1/2 です。出力は単に現状であるかもしれません。より複雑なモデルでは、各状態でのランダムな過程が出力を生成します。たとえば、サイコロを転がし、任意のステップでの出力を決めることができます。

マルコフ連鎖は、離散的な状態の集合をもつマルコフ モデルの数学的な記述です。マルコフ連鎖は、以下によって特徴付けられます。

  • 状態の集合 {1、2、...、M}

  • M行M列の"遷移行列"T。この行列の i、j 要素は、状態 i から状態 j への遷移確率です。Tの各行の要素の和は 1 でなければなりません。なぜなら、これは、与えられた状態から他の各状態に遷移する確率の和であるためです。

  • 可能な出力または"出力シンボル"、{s1、s2、...,sN}.既定の設定では、出力シンボルの集合は、{1、2、...,N} です。ここで、Nは可能な出力シンボルの数ですが、数やシンボルの集合を選択できます。

  • M行N列の"出力行列"E。この行列の i,k 要素は、モデルが状態 i にある場合に、出力シンボルskを出力する確率を与えます。

マルコフ連鎖は、ステップ 0 において"初期状態"i0で始まります。連鎖はその後、 T 1 i 1 という確率で状態i1に遷移し、 E i 1 k 1 という確率で s k 1 を出力します。したがって、 i 1 i 2 ... i r という状態のシーケンスと s k 1 s k 2 ... s k r という出力のシーケンスをはじめのrステップで観測する確率は、次のようになります。

T 1 i 1 E i 1 k 1 T i 1 i 2 E i 2 k 2 ... T i r − 1 i r E i r k

関連するトピック