マルコフモデルと状態空間モデル - 機械学習基礎理論独習

マルコフモデル

系列データ ${\bf x}_1,\ldots,{\bf x}_N$ が与えられているとします。
このような系列データを扱う確率モデルとして、マルコフモデルを考えます。
マルコフモデルは以下の式で表せます。

$\begin{eqnarray} p({\bf x}_1,\ldots,{\bf x}_N)=p({\bf x}_1)\prod_{n=2}^Np({\bf x}_n|{\bf x}_1,\ldots,{\bf x}_{n-1})\tag{1} \end{eqnarray}$

一次マルコフ連鎖

式 $(1)$ の右辺の条件付分布のもの者が最も近い観測値以外の全ての過去の観測値から独立であると仮定すると、
一次マルコフ連鎖を得ます。
この一次マルコフ連鎖は次のグラフィックモデルで表せます。
図1
f:id:olj611:20210920113958p:plain
一次マルコフ連鎖の下で $N$ 個の観測系列の同時分布は以下のようになります。

$\begin{eqnarray} p({\bf x}_1,\ldots,{\bf x}_N)=p({\bf x}_1)\prod_{n=2}^Np({\bf x}_n|{\bf x}_{n-1})\tag{2} \end{eqnarray}$

図1において、 ${\bf x}_m(m < n-1)$ から ${\bf x}_n$ への経路は、 ${\bf x}_{n-1}$ を通り、そこでhead-to-tailであるため、
${\bf x}_n\mathop{\perp\!\!\!\!\perp} {\bf x}_m|{\bf x}_{n-1}$ であり、以下の式が成り立ちます。

$\begin{eqnarray} p({\bf x}_n|{\bf x}_1,\ldots,{\bf x}_{n-1})=p({\bf x}_n|{\bf x}_{n-1})\tag{3} \end{eqnarray}$

また、式 $(3)$ は次のように示すこともできます。
まず、 ${\bf x}_{n+1},\ldots,{\bf x}_N$ で周辺化した同時分布 $p({\bf x}_1,\ldots,{\bf x}_n)$ を計算します。

$\begin{eqnarray} p({\bf x}_1,\ldots,{\bf x}_n)&=&\sum_{{\bf x}_{n+1}}\cdots\sum_{{\bf x}_N}p({\bf x}_1,\ldots,{\bf x}_N)\\ &=&\sum_{{\bf x}_{n+1}}\cdots\sum_{{\bf x}_N}p({\bf x}_1)\prod_{m=2}^Np({\bf x}_m|{\bf x}_{m-1})\\ &=&p({\bf x}_1)\prod_{m=2}^np({\bf x}_m|{\bf x}_{m-1})\tag{4} \end{eqnarray}$

条件付き分布 $p({\bf x}_n|{\bf x}_1,\ldots,{\bf x}_{n-1})$ を計算します。

$\begin{eqnarray} p({\bf x}_n|{\bf x}_1,\ldots,{\bf x}_{n-1})&=&\frac{p({\bf x}_1,\ldots,{\bf x}_n)}{\sum_{{\bf x}_n}p({\bf x}_1,\ldots,{\bf x}_n)}\\ &=&\frac{p({\bf x}_1)\prod_{m=2}^np({\bf x}_m|{\bf x}_{m-1})}{\sum_{{\bf x}_n}p({\bf x}_1)\prod_{m=2}^np({\bf x}_m|{\bf x}_{m-1})}\\ &=&\frac{p({\bf x}_1)(\prod_{m=2}^{n-1}p({\bf x}_m|{\bf x}_{m-1}))p({\bf x}_n|{\bf x}_{n-1})}{p({\bf x}_1)(\prod_{m=2}^{n-1}p({\bf x}_m|{\bf x}_{m-1}))\sum_{{\bf x}_n}p({\bf x}_n|{\bf x}_{n-1})}\\ &=&\frac{p({\bf x}_n|{\bf x}_{n-1})}{\sum_{{\bf x}_n}p({\bf x}_n|{\bf x}_{n-1})}\\ &=&p({\bf x}_n|{\bf x}_{n-1})\tag{5} \end{eqnarray}$

式 $(5)$ より、式 $(3)$ が示せました。

高次のマルコフ連鎖

予測値が直前のさらに一つ前の値にも依存することを許すと、以下のグラフで表現される二次マルコフ連鎖を得ます。
図2
f:id:olj611:20210920114019p:plain
二次マルコフ連鎖の同時分布は以下の式で表せます。

$\begin{eqnarray} p({\bf x}_1,\ldots,{\bf x}_N)=p({\bf x}_1)p({\bf x}_2|{\bf x}_1)\prod_{n=3}^Np({\bf x}_n|{\bf x}_{n-1},{\bf x}_{n-2})\tag{6} \end{eqnarray}$

図2において、 ${\bf x}_m(m < n-2)$ から ${\bf x}_n$ への経路は、 ${\bf x}_{n-1}$ または ${\bf x}_{n-2}$ を通り、そこでhead-to-tailであるため、
${\bf x}_n\mathop{\perp\!\!\!\!\perp}{\bf x}_m|{\bf x}_{n-1},{\bf x}_{n-2}$ であり、以下の式が成り立ちます。

$\begin{eqnarray} p({\bf x}_n|{\bf x}_1,\ldots,{\bf x}_{n-1})=p({\bf x}_n|{\bf x}_{n-1},{\bf x}_{n-2})\tag{7} \end{eqnarray}$

また、式 $(7)$ は次のように示すこともできます。
まず、 ${\bf x}_{n+1},\ldots,{\bf x}_N$ で周辺化した同時分布 $p({\bf x}_1,\ldots,{\bf x}_n)$ を計算します。

$\begin{eqnarray} p({\bf x}_1,\ldots,{\bf x}_n)&=&\sum_{{\bf x}_{n+1}}\cdots\sum_{{\bf x}_N}p({\bf x}_1,\ldots,{\bf x}_N)\\ &=&\sum_{{\bf x}_{n+1}}\cdots\sum_{{\bf x}_N}p({\bf x}_1)p({\bf x}_2|{\bf x}_1)\prod_{m=3}^Np({\bf x}_m|{\bf x}_{m-1},{\bf x}_{m-2})\\ &=&p({\bf x}_1)p({\bf x}_2|{\bf x}_1)\prod_{m=3}^np({\bf x}_m|{\bf x}_{m-1},{\bf x}_{m-2})\tag{8} \end{eqnarray}$

条件付き分布 $p({\bf x}_n|{\bf x}_1,\ldots,{\bf x}_{n-1})$ を計算します。

$\begin{eqnarray} p({\bf x}_n|{\bf x}_1,\ldots,{\bf x}_{n-1})&=&\frac{p({\bf x}_1,\ldots,{\bf x}_n)}{\sum_{{\bf x}_n}p({\bf x}_1,\ldots,{\bf x}_n)}\\ &=&\frac{p({\bf x}_1)p({\bf x}_2|{\bf x}_1)\prod_{m=3}^np({\bf x}_m|{\bf x}_{m-1},{\bf x}_{m-2})}{\sum_{{\bf x}_n}p({\bf x}_1)p({\bf x}_2|{\bf x}_1)\prod_{m=3}^np({\bf x}_m|{\bf x}_{m-1},{\bf x}_{m-2})}\\ &=&\frac{p({\bf x}_1)p({\bf x}_2|{\bf x}_1)(\prod_{m=3}^{n-1}p({\bf x}_m|{\bf x}_{m-1},{\bf x}_{m-2}))p({\bf x}_n|{\bf x}_{n-1},{\bf x}_{n-2})}{p({\bf x}_1)p({\bf x}_2|{\bf x}_1)(\prod_{m=3}^{n-1}p({\bf x}_m|{\bf x}_{m-1},{\bf x}_{m-2}))\sum_{{\bf x}_n}p({\bf x}_n|{\bf x}_{n-1},{\bf x}_{n-2})}\\ &=&\frac{p({\bf x}_n|{\bf x}_{n-1},{\bf x}_{n-2})}{\sum_{{\bf x}_n}p({\bf x}_n|{\bf x}_{n-1},{\bf x}_{n-2})}\\ &=&p({\bf x}_n|{\bf x}_{n-1},{\bf x}_{n-2})\tag{9} \end{eqnarray}$

式 $(9)$ より、式 $(7)$ が示せました。

同様に、 $M$ 次マルコフ連鎖を考えることができます。
$M$ 次マルコフ連鎖の条件付確率は以下の式で表せます。

$\begin{eqnarray} p({\bf x}_n|{\bf x}_1,\ldots,{\bf x}_{n-1})=p({\bf x}_n|{\bf x}_{n-1},\ldots,{\bf x}_{n-M})\tag{10} \end{eqnarray}$

観測変数が $K$ 個の状態を持っているとします。
このとき、一次マルコフ連鎖の条件付き分布 ${\bf x}_{n-1}$ の $K$ 個の状態の各々に対する $K-1$ 個のパラメータをもち、
全体のパラメータ数は $K(K-1)$ となります。
同様に、 $M$ 次マルコフ連鎖の条件付き分布 $p({\bf x}_n|{\bf x}_{n-1},\ldots,{\bf x}_{n-M})$ の全体のパラメータ数は $K^M(K-1)$ となります。
この値は、 $M$ が大きくなるにつれて指数的に増大し、そのために、 $M$ の値が大きくなると、このアプローチは実用にならなくなることが多いです。

状態空間モデル

系列データに対し、次数をもつマルコフ性の仮定に制限されず、なおかつ自由パラメータの数が制限されたモデルを作ることを考えます。
マルコフ連鎖を構成する潜在変数であると仮定することにより、以下の図に示すような状態空間モデルと呼ばれるグラフ構造を得ることができます。

図3
f:id:olj611:20210921165135p:plain:w500

これは ${\bf z}_n$ を与えたとき ${\bf z}_{n-1}$ と ${\bf z}_{n+1}$ が独立であるという、重要な条件付き独立性を満たします。
この独立性は有向分離( ${\bf z}_n$ でhead-to-tail で観測済み)より確認できます。

$\begin{eqnarray} {\bf z}_{n+1}\mathop{\perp\!\!\!\!\perp}{\bf z}_{n-1}|{\bf z}_n\tag{11} \end{eqnarray}$

このモデルの同時分布は以下で与えられます。(単純に図3のグラフから式を起こしただけです)

$\begin{eqnarray} p({\bf x}_1,\ldots,{\bf x}_N,{\bf z}_1,\ldots,{\bf z}_N)=p({\bf z}_1)\left(\prod_{n=2}^Np({\bf z}_n|{\bf z}_{n-1})\right)\prod_{n=1}^Np({\bf x}_n|{\bf z}_n)\tag{12} \end{eqnarray}$

潜在変数を経由して $2$ つの観測変数 ${\bf x}_n$ と ${\bf x}_m$ をつなぐ経路は存在し、
有向分離の基準を用いることにより、この経路は決して遮断されないことが分かります。
したがって、過去の観測値をすべて与えたときの、観測 ${\bf x}_{n+1}$ の予測分布 $p({\bf x}_{n+1}|{\bf x}_1,\ldots,{\bf x}_n)$ は、
条件付き独立の性質を何ももたず、したがって、 ${\bf x}_{x+1}$ の予測はすべての過去の観測値に依存します。

このグラフによって表現される系列データのモデルとして、以下の $2$ つのモデルが重要です。
もし、潜在変数が離散変数である場合、隠れマルコフモデルを得ます。
ここで、HMMの観測変数は、離散変数でも連続変数でもよいことに注意が必要です。
もし、潜在変数と観測変数の両方がガウス分布に従う場合、線形動径システムが得られます。

偉人の名言

f:id:olj611:20210921174251p:plain:h300
「どんな人だって成功できる」自分にそう何度も言い聞かせ続けていれば、絶対に成功できるのです。
ジョン・レノン

参考文献

パターン認識と機械学習下巻 p324-p328

動画

なし