機械学習に詳しくなりたいブログ

機械学習や数学について勉強した内容を中心に書きます。100%趣味です。記事は数学的に厳密でなかったり誤りを含んでいるかもしれません。ご指摘頂ければ幸いです。

マルコフ過程

時刻1,\cdots,nにおける状態 x_nにより、 x_{n+1}の確率が決まるとしたとき、つまりx_{n+1}の確率がx_1,\cdots,x_nから決まるのではなく、1つ前の状態x_nのみによって定まるとき、マルコフ性といい、このような性質を持つ確率過程をマルコフ過程といいます。状態が離散的なとき、特にマルコフ連鎖と呼びます。

状態が3つあるとしたとき、例えば以下の図のようにマルコフ連鎖を表すことができます。

f:id:opabinia2:20180407005135p:plain

各状態をつなぐ矢印は、時刻が進んだときに遷移できる方向を表し、数字は遷移する確率を表します。

時刻nに状態iにいる確率を p_{i}^{(n)}とすれば、行列を用いて


  \displaystyle 
\left(
    \begin{array}{c}
      p_{1}^{(n+1)} \\
      p_{2}^{(n+1)} \\
      p_{3}^{(n+1)}
    \end{array}
  \right)
= \left(
    \begin{array}{ccc}
     0 & \frac{1}{4} & \frac{1}{2} \\
     \frac{1}{4}  & \frac{3}{4} & \frac{1}{2} \\
     \frac{3}{4}  & 0 & 0 \\
    \end{array}
  \right)
\left(
    \begin{array}{c}
      p_{1}^{(n)} \\
      p_{2}^{(n)} \\
      p_{3}^{(n)}
    \end{array}
  \right)
 \tag{1}

と表すことができます。この式における行列は推移行列と呼ばれます。

マルコフ連鎖において、

  • どの状態からスタートしても有限時間内に任意の状態に遷移可能(既約性)
  • 周期的でない

であることをエルゴード性といい、これを満たすとき、時刻 n \to \infty


\mathbf p = \mathbf P \mathbf p \tag{2}

を満たす分布\mathbf pに収束します。\mathbf Pは推移行列です。これを不変分布または定常分布と呼びます。既約性を満たさないマルコフ連鎖の例としては、上図の2の状態のように自分自身に推移する線があり、かつ他の状態へ推移できないときなどが考えられます。その場合だと永遠に同じ状態を繰り返してしまいます。

今回の例で示したマルコフ連鎖では、状態1~3がおよそ 0.235163 0.588277 0.17656 に収束することが確認できました。これは各状態がこのような確率で発生する乱数生成器であるとみなすことができるようです。(ただしサンプルの前後間には相関がある)

確率論の参考書は難しくてなかなか理解が進まず、、、。Amazonでわかりやすいと評価が高かったものを購入してみましたが、僕の頭ではとても独学で理解できる代物ではなく、今まで学んできた確率統計とは別の学問としか思えないような難解さ。とりあえずマルコフ過程については、このくらいの理解で先に進んでいこうと思います。

今回実験したコードです。状態遷移をシミュレーションしたものと、式(1)を繰り返し演算した結果がそれぞれ一致することが確認できました。コード内では初期状態を1としていますが、何を初期状態としても収束しました。

# マルコフ連鎖のテスト
import numpy as np


def markov(x):
    p = np.random.uniform()
    if x == 1:
        if p < 0.25:
            return 2
        else:
            return 3
    if x == 2:
        if p < 0.25:
            return 1
        else:
            return 2
    if x == 3:
        if p < 0.5:
            return 1
        else:
            return 2


# 初期値
x = 1

# サンプル数
N = 1000000

history = np.empty(N)

for i in range(N):
    x = markov(x)
    history[i] = x

print(np.count_nonzero(history == 1)/N)
print(np.count_nonzero(history == 2)/N)
print(np.count_nonzero(history == 3)/N)

s = np.array([[0,0.25,0.5],[0.25,0.75,0.5],[0.75,0,0]])
x = np.array([1,0,0]).reshape(3,1)

for i in range(N):
    x = np.dot(s, x)

print(x)