ページ

2016年4月6日水曜日

【R】マルコフ解析の基礎(2)

前回は、マルコフ性とは何か、チャップマン・コルモゴロフの等式、等を説明した。今回は、マルコフ・チェーンの分類に焦点を当てる。最初に、状態の分類方法を説明、これに基づいて周期の概念などを説明して、最後にマルコフ・チェーンの分類を示す。

なお、今回以降、特に断らない限りは、斉時的マルコフ・チェーン(推移確率が定常)を対象とする。



状態の分類:到達可能・既約な集合・吸収状態

t次推移確率行列が決まっていることを前提に考える。次のときに、状態iから状態jに「到達可能」(i→j)と言う。
\[
\exists t > 0 \; \; \; p_{ij}^{(t)} > 0
\]

「i→j」かつ「j→i」のときに、iとjは「相互到達可能」または「連結」(i⇔j)と言う。

状態空間Sの部分集合Cについて、

1)Cの内部の任意の要素同士は「相互到達可能」
\[
\forall i,j \in C \; \; \; i \leftrightarrow j
\]

2)一度その中に入ると出て来れない(次に飛ばされるのは必ずCの内部)

\[
\forall i \in C \; \; \; \sum_{j \in C} p_{ij} = 1
\]

この二つの条件を満たすものを「既約な集合」と言う。一つの要素だけから成る既約な集合を「吸収状態」と言う。

状態の間を推移確率が0でないときにやじるしで結んだ有向グラフを状態遷移図とかシャノン線図というのだが、これを既約集合の考え方をつかって分解して理解することが出来る。任意の状態遷移図は、幾つかの既約集合(の内部)とその外側の部分に分解できる。

このことを理解するには、「相互到達可能」が同値関係であることを理解すれば良い(同値関係の規則のうち、反射律、対称律は自明。推移律はチャップマン・コルモゴロフの式より)。この同値関係によって状態空間Sを複数の同値類に分割する。たとえばこんな具合に。
\[
S = C_{1} \cup C_{2} \cup \cdots \cup C_{k} \cup C_{k+1} \cup \cdots \cup C_{m}
\]
ここで1~kまでは既約な集合、つまり内側に入る矢印はあっても外側に出る矢印はないもの、k+1~mは既約でない集合になる。これらの同値類の一つ一つを「クラス」と呼ぶ。

既約でない集合を束ねて、
\[
S = C_{1} \cup C_{2} \cup \cdots \cup C_{k} \cup T
\]
とする。このようにして、全体の挙動はTで理解して、一度Cに入った後はその範囲内だけで考えられるようになる。

初度到達確率:再帰状態・一時状態

状態iからスタートして、時刻tではじめて状態jになる確率(初度到達確率)を考える。
\[
\begin{eqnarray} f_{ij}^{(t)} & = & P(H_{t}(j) \cap H_{t-1}(\bar{j}) \cap \cdots \cap H_{1}(\bar{j}) | H_{0}(i) ) \\ & = & P(F_{t}(j) | H_{0}(i)) \end{eqnarray}
\]
Fで「初めて到達した」という事象を表現している。

初度到達確率と推移確率の関係は「初度到達の式」と呼ばれている。これの導出は、

\[
\begin{eqnarray} p_{ij}^{(t)} & = & P\left( H_{t}(j) | H_{0}(i)\right) \\ & = & \sum_{s \in [1:t] } P(H_{t}(j)|H_{s}(j)) \cdot P(F_{s}(j)|H_{0}(i)) \\ & = & \sum_{s \in [1:t]} p_{jj}^{(t-s)} f_{ij}^{(s)} \end{eqnarray}
\]
これは前回の状態確率の式を導出した場合と同じやり方。

順番を変えて、
\[
p_{ij}^{(t)} = \sum_{s \in [1:t]} f_{ij}^{(s)} p_{jj}^{(t-s)}
\]

トータルでのiからjへの到達確率は、初度到達確率から次のように計算。
\[
f_{ij} = \sum_{t \in [1:\infty] } f_{ij}^{(t)}
\]

同様に平均到達時刻。
\[
\mu_{ij} = \left\{ \begin{array}{l l} \displaystyle \sum_{t \in [1:\infty] } t \cdot f_{ij}^{(t)} & (f_{ij}=1) \\ \infty & (f_{ij}<1) \end{array} \right. \] 自分自身への到達確率を考える。これより、再帰状態と一時状態が定義される。 状態iが「一時的」であるとは、 \[ f_{ii} < 1 \] 状態iが「再帰的」であるとは、 \[ f_{ii} = 1 \] iが再帰状態であるとき、さらに平均到達時刻で「正再帰的」と「零再帰的」を区別する。 正再帰的とは、 \[ \mu_{ii} < \infty \] 零再帰的とは、 \[ \mu_{ii} = \infty \]

再帰状態とか一時状態は「クラス」の性質である。つまり、iとjが相互到達であるならば、iが再帰的であるか一時的であるかの別はjのそれと一致する。証明は母関数を使ったものが多いようである。


また、既約でない集合は一時的であることも知られている(逆は成り立たない。つまり、一時的であるからといって規約でない集合となるわけではない)。


周期

再帰的なクラスについて、「周期」の概念を導入する。この周期という性質も「クラス」の性質である。
\[
d_{i} = g.c.d. \{ t \geq 1 | p_{ii}^{(t)} > 0 \}
\]
g.c.d.は最大公約数。

まとめ

相互到達可能=連結の関係から「クラス」(同値類)と「既約な集合」(吸収状態)を説明した。クラスの性質として、「再帰的/一時的」、「周期」を説明した。状態の分類はできたが、今回はマルコフ・チェーンそのものの分類まで行かなかった。既約な集合の概念を基礎として、次回にマルコフ・チェーンを分類してみよう。

おまけ

そろそろ応用のことも考えて、Rでマルコフ連鎖を取り扱えるパッケージがないか探してみた。次のCRANから見つけた文献は参考になりそうだ。

The markovchain Package: A Package for Easily Handling Discrete Markov Chains in R

Package ‘markovchain’

最初の方にはマルコフ連鎖を前提とした分析パッケージの例が示されていて、それにも関わらず「マルコフ連鎖」そのものを扱うパッケージが無い、と指摘している。その次に「マルコフ連鎖」の理論が示されているけれども、本ブログのその1、その2の内容と被るところが多い。その後、Spedicatoさんが作成したパッケージによる実際の計算例がある。次回以降のいつか、内容を解説してみる。

Getting Started with Markov Chains

上はやはり同パッケージの使い方をJoseph Rickertさんが解説している。

Markov Chains Explained Visually

こちらはRとは関係ないが、マルコフ連鎖をVictor Powellさんがアニメで説明しているもの。

他にもググると、MCMC(googleのページランクに使われているとか、今はやりのやつ)、マルコフモデルによる自動テキスト生成など(一昔前の人工無脳が高度化したやつ、Siriとか)などもヒットするが、それらは当面は言及しない。