マルコフ連鎖(2章)

バイオインフォマティクス

• マルコフ性：未来は現在によってのみ特徴づけられる場合、この性質をマルコフ性を呼ぶ。
• 既約：すべての状態が他のすべての状態に到達可能であるという特性を状態遷移図が持つとき、かつそのときのみ、マルコフ連鎖は既約であるという。既約なマルコフ連鎖の遷移確率行列Pは、あるkに対してP^k＞0であるという特性をもつ。ここで、P^k＞0はすべての要素が厳密に正値を持つことを意味する。
• 永続的／一時的：もし状態iから出発したマルコフ連鎖が確率1でiに戻ってくるならば、状態iは永続的であるという。永続的でない場合を一時的という。
• エルゴード性：もし状態iが非周期的かつ永続的であれば、状態iはエルゴード的であるという。もしすべての状態がエルゴード的であるならば、そのマルコフ連鎖はエルゴード的であるという。有限個の状態を有するマルコフ連鎖に対して、エルゴード性は既約性および非周期性を伴う。
• 定常分布：状態遷移行列Pを乗じても、Πs(状態確率)が不変である場合、定常であるという。もし極限分布が存在するならば、それは定常分布である。もしマルコフ連鎖がエルゴード的(≒非周期的で既約的)なら極限が存在し、初期分布に依存しない。※考え中。
• 可逆マルコフ連鎖：pij(reversed) = pijが満たされる場合、マルコフ連鎖は可逆であるという。可逆性は、順方向と逆方向の両方の連鎖に対する定常性を意味する。ほとんどの応用においては、定常性の仮定の下で、逆マルコフ連鎖を解析することが重要となる。
• 連続時間マルコフ連鎖：離散的な時刻間の遷移を連続時間に拡張。連続時間マルコフ連鎖X(t)に強度行列Qを定義する。Qは確率遷移行列Pの微分。マルコフ過程X(t)の構築法は、塩基置換モデルのように強度行列Qを定義することから始まる。このような構築法が最も自然。
• マルコフ連鎖モンテカルロ(MCMC)法：代表例：メトロポリスーヘイスティングス法：直接サンプリングするのが難しい確率分布から統計標本の配分を生成するのに用いられる方法。この配列はマルコフ連鎖モンテカルロ法において、目標分布の近似として用いられたり、積分を計算するのに用いられる。状態1, 2, …, Nを有し、遷移確率がqijであるような既約かつ非周期的マルコフ連鎖を定義し、これらの確率に因子aijを掛け合わせる。pij = aij*qij. pijが局所釣合条件を満足する遷移確率となるように(可逆となるように)、因子aijを選ぶ。aijqijΠSi = ajiqjiΠSj*。aji, ajiのどちらかが1と仮定し、因子aijを求めると、aji = min(1, qjiΠSj/qijΠSi)。aijの表現はΠSiの絶対的な値には依存せず、その比のみに依存する。すなわちΠSの比例定数までを知る必要がないことを意味する。規格化定数を見出すことが難しい分布をシュミレートすることが可能となる。「ベクトルΠSによって与えられる定常分布を持ち、状態1, 2, …, Nを有するエルゴード的マルコフ連鎖を構築せよ」という類の問題で利用。
• 受容ー棄却法：既約かつ非周期的なマルコフ連鎖のシュミレーションする場合に利用。aji = min(1, qjiΠSj/qijΠSi)に基づいてaijを決定し、状態iからjへの移動を"受容"するか"棄却"するか決める。
• 隠れマルコフモデル：状態が観測可能ではないマルコフ連鎖。その状態から出力されたシンボル列のみが記録される。例：離散時間0, 1, 2, …, k, k+1, …, K上で、状態1, 2, …, Nを持つマルコフ連鎖を考える。加えて、出力と呼ばれるM個のシンボルo1, o2, …, om, om+1, … oMがあるとする。
• ヴィタビ・アルゴリズム：「シンボル列ojo, oj1, …, ojKが与えられたとき、最も確率が高い状態列i0, i1, …, iKを見つけよ」言い換えると条件付き確率 P[i0, i1, …, iK|oj0, oj1, …, ojk] ＝を最大化するような状態列を計算する問題で用いる。P[oj0, oj1, …, ojk]は状態に依存しない単なる尺度因子であるため、すべての状態列i0, i1, …, iKに対して、状態確率P[i0, oj0, i1, oj1, …, jK, ojK]を最大化することと等価。以下、対数尤度の最大化問題を動的計画法を使用して解く。(後述)
• バウムーウェルチ・アルゴリズム：