マルコフ連鎖と定常分布(Stationary distribution)について

マルコフ連鎖(Markov Chain)は時系列の取り扱いなどで主に用いられる手法で、言語・音声処理や強化学習においても用いられることがある。また、乱数を用いて近似解を求める手法であるMCMC(Markov Chain Monte Carlo)や、将棋・囲碁の学習に用いられるMCTS(Monte Carlo Tree Search)などもマルコフ連鎖を元に手法が構築されている。当稿ではマルコフ連鎖の基本トピックについてまとめるにあたって、漸化式の確認から定常分布(Stationary distribution)などの取りまとめを行なった。
内容の作成にあたっては「統計学実践ワークブック」などを元に作成を行なった。

基本事項の確認

数列と漸化式

マルコフ連鎖の定義

$$
\large
\begin{align}
P(X_{n+1}|X_{n}, X_{n-1}, … , X_{1}, X_{0}) = P(X_{n+1}|X_{n})
\end{align}
$$
確率変数の列$\{X_n\}$に関して上記が成立するとき、これを確率変数列$\{X_n\}$のマルコフ性(Markov property)といい、このような性質を持つ$\{X_n\}$をマルコフ連鎖(Markov chain)という。

マルコフ連鎖を直感的に理解するにあたっては、「将来の予測にあたって現在の状態のみを参照する」と考えればよい。

状態確率ベクトルと推移確率行列

前項のマルコフ連鎖の表記は抽象的な表記であったが、ここで状態確率ベクトル(state probability vector)と推移行列(transition matrix)を導入することによってより具体的な考察が可能となる。
このとき確率変数$X_n$が状態$1$〜$N$の値を取るとした際に、下記のように$N$次元の状態確率ベクトル$\mathbf{\pi}_n$を定義する。
$$
\large
\begin{align}
\mathbf{\pi}_n = \left(\begin{array}{ccc} P(X_n=1) & … & P(X_n=N) \end{array} \right)
\end{align}
$$
状態確率ベクトル$\mathbf{\pi}_n$のうち、$n=0$となる$\mathbf{\pi}_0$を初期分布(initial distribution)ということも抑えておくとよい。

状態確率ベクトルについて確認したので次に推移行列$Q(m)$について確認する。状態$i$から状態$j$に$m$ステップで推移する確率を$p_m(i,j)=P(X_{n+m}=j|X_n=i)$と表現するとき、推移行列$Q(m)$は下記のように定義できる。
$$
\large
\begin{align}
Q(m) = \left(\begin{array}{ccc} p_m(1,1) & … & p_m(1,N) \\ … & … & … \\ p_m(N,1) & … & p_m(N,N) \end{array} \right)
\end{align}
$$
また、下記では簡易化にあたって$Q=Q(1)$を確率行列(probability matrix)と考えることとする。

状態確率ベクトル$\mathbf{\pi}_n$、確率行列$Q$を上記のように定義したと考えると、状態確率ベクトル$\mathbf{\pi}_n$と初期分布$\mathbf{\pi}_0$間で下記のような式が成立する。
$$
\large
\begin{align}
\mathbf{\pi}_n = \mathbf{\pi}_0 Q^n
\end{align}
$$

定常分布

定常分布の数式表記

状態確率ベクトル$\mathbf{\pi}_n$において、$n \to \infty$の極限が成立するときに、それを$\mathbf{\pi}$と定義すると、$\mathbf{\pi}$は下記のように表すことができる。
$$
\large \begin{align} \mathbf{\pi} = \lim_{n \to \infty} \mathbf{\pi}_n
\end{align}
$$
また、上記より下記が成立すると考えることができる。
$$
\large
\begin{align}
\mathbf{\pi} = \mathbf{\pi} Q
\end{align}
$$
これは、$Q$の固有値$1$の固有ベクトルに一致することを意味している。

ここで考えた$\mathbf{\pi}$を定常分布(stationary distribution)といい、初期分布が定常分布であるようなマルコフ連鎖を定常マルコフ連鎖という。

パラメータ推定

推移確率行列$Q$が未知のパラメータ$\theta$によって決定されることを下記のように表すとする。
$$
\large
\begin{align}
Q_{\theta} = \left(\begin{array}{ccc} p_{\theta}(1,1) & … & p_{\theta}(1,N) \\ … & … & … \\ p_{\theta}(N,1) & … & p_{\theta}(N,N) \end{array} \right)
\end{align}
$$

このとき確率変数列${X_i}$に対して、観測列${x_i}$が与えられたとする。この同時確率はマルコフ性が成立することなどを利用して下記のように計算することができる。
$$
\begin{align}
P(X_0=x_0, X_1=x_1, …, X_n=x_n) &= P(X_n=x_n|X_0=x_0, …, X_{n-1}=x_{n-1}) P(X_n=x_{n-1}|X_0=x_0, …, X_{n-2}=x_{n-2}) … P(X_1=x_1|X_0=x_0)P(X_0=x_0) \\
&= P(X_n=x_n|X_{n-1}=x_{n-1}) P(X_n=x_{n-1}|X_{n-2}=x_{n-2}) … P(X_1=x_1|X_0=x_0)P(X_0=x_0) \\
&= p_{0}(x_0) \prod_{j=1}^{n} p_{\theta}(x_{j-1}, x_{j})
\end{align}
$$
上記において初期確率$p_{0}$はパラメータ$\theta$によらないと考えるものとする。

最尤法的な考え方に基づくと、尤度$L(\theta)$は同時確率$P(X_0=x_0, X_1=x_1, …, X_n=x_n)$に一致するため、下記が成立する。
$$
\large
\begin{align}
L(\theta) &= P(X_0=x_0, X_1=x_1, …, X_n=x_n) \\
&= p_{0}(x_0) \prod_{j=1}^{n} p_{\theta}(x_{j-1}, x_{j})
\end{align}
$$
このとき両辺の対数を取ることで対数尤度$l_n(\theta)$を考え、$\theta$が関係ない項を無視することで対数尤度関数は下記のように表せる。
$$
\large
\begin{align}
l_{n}(\theta) = \sum_{j=1}^{n} \log{p_{\theta}(x_{j-1}, x_{j})}
\end{align}
$$

よって、$\theta$の最尤推定値の$\hat{\theta}$は以下の微分方程式の解を求めることで得られる。
$$
\large
\begin{align}
\frac{\partial}{\partial \theta}l_{n}(\theta) = 0
\end{align}
$$

ここでは推移行列を未知のパラメータとし、$Q_{\theta}$を定義したが、Deep Learningを用いるときなども同様の式設定を行い、そこから誤差関数(loss function)を導出することが多いことは抑えておくとよい。

天気を例に定常分布を具体的に確認する