マルコフ連鎖の数値解法とは何？わかりやすく解説 Weblio辞書

索引トップ用語の索引ランキングカテゴリー

マルコフ連鎖の数値解法

読み方：まるこふれんさのすうちかいほう
【英】：numerical method for Markov chain

概要

マルコフ連鎖の定常分布や過渡的分布を数値的に計算するための方法. 定常分布の計算は線形方程式系を解く問題に帰着され, 解法として消去法や状態縮約法などの直接法, ヤコビ法, ガウス・ザイデル法, 状態縮約/非縮約法などの反復法がある. また, 構造化されたマルコフ連鎖に対しては行列幾何形式解を利用する方法も有力である. 一方, 過渡的分布に対しては, 離散時間ではべき乗法, 連続時間ではランダム化を利用する方法などがある.

詳説

　マルコフ連鎖をマルコフ連鎖の数値的に解析する際の中心的な対象は定常分布である. 有限状態空間 ${\mathcal S}=\{ 1, 2, \ldots, N \}\,$ 上の既約で非周期的な (つまりエルゴード的) マルコフ連鎖を考え, その推移確率行列を $\boldsymbol{P}=(p_{ij})\,$ , 定常分布を $\boldsymbol{\pi}=(\pi_1, \pi_2,\ldots,\pi_N)\,$ とする. 一様化により, 連続時間マルコフ連鎖の定常分布は, 離散時間マルコフ連鎖の定常分布として計算できるので, 以下では離散時間マルコフ連鎖に限定して考える.

　エルゴード的なマルコフ連鎖では, 定常分布は

(平衡方程式)	$\pi_j = \sum_{i=1}^N \pi_i p_{ij}, \quad j=1, 2, \ldots,N, \qquad \,$	$(1)\,$
(正規化条件)	$\sum_{j=1}^N \pi_j = 1 \,$	$(2)\,$

を満たす一意の解として与えられる (式(1)) の解は定数倍に関して一意でないため, 式 (2) で正規化する). したがって, 定常分布の計算は, 原理的には線形方程式系を数値的に解く問題に帰着される. 状態数 $N\,$ が大きくなければ, 消去法や状態縮約法などの直接法 (反復計算を伴わない方法) でも解を求めることは可能だが, 一般にマルコフ連鎖によるモデル化はモデルが複雑になるに従って状態数が急激に増加する傾向があるため, そのような場合は計算精度などを考慮して反復法を用いることが多い.

ガウス・ザイデル法　反復法では, 反復回数 $k \to \infty\,$ のときに定常分布 $\boldsymbol{\pi}\,$ に収束するような近似値の列 $\boldsymbol{\pi}^{(k)} = (\pi_1^{(k)}, \pi_2^{(k)}, \ldots,\pi_N^{(k)})\,$ を構成する. 例えば, ヤコビ法 (Jacobi method) では, 適当な初期分布 $\boldsymbol{\pi}^{(0)}\,$ からスタートして

$\pi_j^{(k)} = \sum_{i=1}^N \pi_i^{(k-1)} p_{ij}, \quad j=1, 2, \ldots,N$

によって分布列 $\boldsymbol{\pi}^{(k)}\,$ を構成し, $\boldsymbol{\pi}^{(k-1)}\,$ と $\boldsymbol{\pi}^{(k)}\,$ が十分近くなった時点で収束したと判断する. エルゴード的なマルコフ連鎖に対しては, ヤコビ法は計算誤差を除けば必ず収束するが, 一般に大きな $N\,$ に対してはあまり収束は速くない. これに対して, ガウス・ザイデル法 (Gauss-Seidel method) では

$\pi_j^{(k)} = \frac{ \sum_{i=1}^{j-1} \pi_i^{(k)} p_{ij} + \sum_{i=j+1}^{N} \pi_i^{(k-1)} p_{ij} }{1-p_{jj}}, \quad j=1, 2, \ldots,N$

によって分布列を構成する. この方法では, $k\,$ 回目の反復で既に更新されている値を逐次利用するため, ヤコビ反復法に比べると一般に収束が速くなることが多い. また, 推移確率行列がブロック構造を持つ場合には, ブロックごとに更新された値を利用するブロックガウス・ザイデル法 (block Gauss-Seidel method) も有効である. さらに収束を加速する手段として過剰緩和法 (overrelaxation method) の利用がある. 過剰緩和法では, 緩和 (または加速) 係数を $\omega\,$ として

$\pi_j^{(k)} = \frac{ \omega \sum_{i=1}^{j-1} \pi_i^{(k)} p_{ij} + (1-\omega) \pi_j^{(k-1)} p_{jj} + \omega \sum_{i=j+1}^{N} \pi_i^{(k-1)} p_{ij} }{1-p_{jj}}, \quad j=1, 2, \ldots,N$

によって $\boldsymbol{\pi}^{(k)}\,$ を計算する. $\omega>1\,$ のときには, 外挿により $\boldsymbol{\pi}^{(k-1)}\,$ から $\boldsymbol{\pi}^{(k)}\,$ を計算しており, 適切な $\omega\,$ を選ぶことで収束を加速することが可能となる. なお, ガウス・ザイデル系の方法では, 初期分布 $\boldsymbol{\pi}^{(0)}\,$ が (2) を満たしていても, 途中の計算でこの制約が満たされなくなるため, 計算の最後に (2) が満たされるよう正規化することが必要である.

状態縮約/非縮約法　一方, 複数の状態をまとめて 1つの状態と見なした状態数の少ない確率過程に対して反復計算を行う方法に状態縮約/非縮約法 (aggregation/disaggregation method: AD法) がある. 例えば, 状態空間を $L\,$ 個の部分空間 ${\mathcal S}_1, \ldots, {\mathcal S}_L\,$ に分割し, ${\mathcal S}_{\alpha}\,$ には $d_\alpha\,$ 個の状態 $(\alpha,1), \ldots, (\alpha,d_\alpha)\,$ が含まれる場合を考え, 推移確率を $\boldsymbol{P}=( p_{(\alpha,i)(\beta,j)} )\,$ , 状態 $(\alpha,i)\,$ の定常確率を $\pi_{\alpha,i}\,$ , 部分空間 ${\mathcal S}_\alpha\,$ の定常確率を $\textstyle \tau_\alpha=\sum_{i=1}^{d_\alpha} \pi_{\alpha,i}\,$ とする. いま, $k-1\,$ 回の反復で近似値 $\pi_{\alpha,i}^{(k-1)}\,$ , $\tau_\alpha^{(k-1)}\,$ が求められているとしよう. $k\,$ 回目の反復計算のうち, まず縮約フェーズでは, 部分空間 ${\mathcal S}_\alpha,\; \alpha = 1,\ldots,L\,$ をそれぞれ 1つの状態 $s_\alpha\,$ に縮約した $L\,$ 状態の確率過程を考え, それをマルコフ連鎖と見なして (特殊なケースを除いて縮約した確率過程はマルコフ連鎖とならない) 推移確率, 例えば $s_\alpha\,$ から $s_\beta\,$ への推移確率を $\textstyle q_{\alpha,\beta}^{(k)}=\sum_{i=1}^{d_\alpha} \sum_{j=1}^{d_\beta}\pi_{\alpha,i}^{(k-1)} p_{(\alpha,i)(\beta,j)} / \tau_\alpha^{(k-1)}\,$ によって定める. このマルコフ連鎖 $\boldsymbol{Q}^{(k)}=(q_{\alpha,\beta}^{(k)})\,$ の平衡方程式を解いて, 更新された定常確率 $\tau_\alpha^{(k)},\; \alpha=1,\ldots,L\,$ を求める. 次に非縮約フェーズでは, 1つの着目した部分空間はそのままで他のすべての部分空間を1つの状態に縮約した確率過程を近似的にマルコフ連鎖と考える. 例えば, 部分空間 ${\mathcal S}_\alpha\,$ に注目した場合には, ${\mathcal S}_\alpha\,$ 内の推移確率は元のままで, ${\mathcal S}_\alpha\,$ 内の状態 $(\alpha,i)\,$ から縮約された状態への推移確率は $\textstyle \sum_{\beta \ne \alpha}\sum_{j=1}^{d_\beta} p_{(\alpha,i)(\beta,j)}\,$ , 逆に縮約された状態から $(\alpha,i)\,$ への推移確率は $\textstyle \sum_{\beta \ne \alpha} \sum_{j=1}^{d_\beta}\pi_{\beta,j}^{(k-1)} p_{(\beta,j)(\alpha,i)}/(1-\tau_{\alpha}^{(k)})\,$ で与えられるマルコフ連鎖を考え, その定常分布を計算し $\pi_{\alpha,i}^{(k)}, \; i=1,\cdots,d_\alpha\,$ を得る. この計算を, 注目する部分空間を ${\mathcal S}_1\,$ から ${\mathcal S}_L\,$ まで変えながら行えば, 更新された定常確率を求めることができる. この縮約/非縮約の手続きを, 値が収束するまで反復すればよい.