マルコフ確率場 - 機械学習基礎理論独習

マルコフ確率場(マルコフネットワークまたは無向グラフィカルモデル)は、
変数に対応するノード集合とノード対を接続する無向リンク集合からなります。

条件付き独立性

無向グラフは有向グラフのようなhead-to-headのような分かりにくい現象は発生しません。
無向グラフにおいて $3$ つのノード集合 $A,B,C$ で次の条件付き独立性が成り立つか考えます。

$\begin{eqnarray} A\mathop{\perp\!\!\!\!\perp}B|C\tag{1} \end{eqnarray}$

集合 $A$ に含まれるノードと集合 $B$ に含まれるノードとを結ぶ全ての可能な経路が
集合 $C$ に含まれるノードの少なくとも $1$ つを通るなら、式 $(1)$ が成り立ちます。

以下の図1は式 $(1)$ が成り立つ例です。

図1
f:id:olj611:20211003101343p:plain:w300

無向グラフにおけるマルコフブランケットは、以下の図 $2$ のようになります。

図2
f:id:olj611:20211003101358p:plain:w150

分解特性

$1$ つのリンクによって接続されない $2$ つのノード $x_i,x_j$ の同時分布は、以下の式で表せます。

$\begin{eqnarray} p(x_i,x_j|{\bf x}_{\backslash\{i,j\}})=p(x_i|{\bf x}_{\backslash\{i,j\}})p(x_j|{\bf x}_{\backslash\{i,j\}})\tag{1} \end{eqnarray}$

式 $(1)$ が成り立つためには、 $x_i,x_j$ が同じ因子ならないように因数分解される必要があります。

クリークという概念を導入します。
クリークの定義は、すべてのノードの組にリンクが存在するようなグラフの部分集合です。
すなわち、クリークの全ノードは全結合です。
極大クリークは、もう $1$ つのノードを加えるとクリークでなくなってしまうようなクリークのことです。

以下の図 $3$ を用いて、クリークについて具体的に説明します。

図3
f:id:olj611:20211003105142p:plain:w250

このグラフは
$2$ ノードから成る $5$ つのクリーク $\{x_1,x_2\},\{x_2,x_3\},\{x_3,x_4\},\{x_4,x_2\},\{x_1,x_3\}$
および、 $3$ ノードから成る $2$ つ極大クリーク $\{x_1,x_2,x_3\},\{x_2,x_3,x_4\}$
を持ちます。

クリークを $C$ と書き、クリーク内の変数集合を ${\bf x}_C$ と書きます。
このとき、同時分布はグラフの極大クリーク上のポテンシャル関数 $\psi({\bf x}_C)$ の積で、次のように書けます。

$\begin{eqnarray} p({\bf x})=\frac{1}{Z}\prod_C\psi_C({\bf x}_C)\tag{2} \end{eqnarray}$

ここで、 $Z$ は規格化定数(分散関数と呼ぶこともあります)で、以下の式で与えられます。

$\begin{eqnarray} Z=\sum_{\bf x}\prod_C\psi_C({\bf x}_C)\tag{3} \end{eqnarray}$

ここでポテンシャル関数 $\psi({\bf x}_C)$ は $\psi({\bf x}_C)\geqslant 0$ さえ満たせばよいことに注意が必要です。

ポテンシャル関数は、指数関数で表現すると便利です。

$\begin{eqnarray} \psi_C({\bf x}_C)=\exp(-E({\bf x}_C))\tag{4} \end{eqnarray}$

ここで、 $E({\bf x}_C)$ はエネルギー関数と呼ばれ、この指数関数表現はボルツマン分布と呼ばれます。

有向グラフとの関係

図4
f:id:olj611:20211003112612p:plain:h120

図 $4$ の(a)の有向グラフの同時分布は、以下のように表されます。

$\begin{eqnarray} p({\bf x})=p(x_1)p(x_2|x_1)p(x_3|x_2)\cdots p(x_N|x_{N-1})\tag{5} \end{eqnarray}$

図 $4$ の(b)の無向グラフの同時分布は、極大クリークは単なる隣接ノード対であるので、以下のように表されます。

$\begin{eqnarray} p({\bf x})=\frac{1}{Z}\psi_{1,2}(x_1,x_2)\psi_{2,3}(x_2,x_3)\cdots\psi_{N-1,N}(x_{N-1},x_N)\tag{6} \end{eqnarray}$

式 $(5),(6)$ より、以下のような対応付けができます。

$\begin{eqnarray} &&\psi_{1,2}(x_1,x_2)=p(x_1)p(x_2|x_1)\\ &&\psi_{2,3}(x_2,x_3)=p(x_3|x_2)\\ &&\vdots\\ &&\psi_{N-1,N}(x_{N-1},x_N)=p(x_N|x_{N-1})\tag{7} \end{eqnarray}$

なお、このときポテンシャル関数が全て確率関数に対応しているので $Z=1$ であることに注意が必要です。

図5
f:id:olj611:20211003113301p:plain:h250

図5の(a)の有向グラフの同時分布は、以下のように書けます。

$\begin{eqnarray} p({\bf x})=p(x_1)p(x_2)p(x_3)p(x_4|x_1,x_2,x_3)\tag{7} \end{eqnarray}$

因子 $p(x_4|x_1,x_2,x_3)$ は $4$ つの変数 $x_1,x_2,x_3,x_4$ を持つので、
この条件付き分布を $1$ つのクリークポテンシャル関数に吸収させるためには
これらの変数が $1$ つのクリークに属していなければなりません。
つまりノード $x_4$ の親同士をリンクで接続すればよいです。(図5の(b))
この「親同士を結婚させる」ことをモラル化といい、結果として得られる無向グラフをモラルグラフといいます。

以上をまとめると、一般に有向グラフを無向グラフに変換するには以下のようにすればよいです。
まず、グラフの各ノードに対してそのすべての親同士の対に無向リンクを付加し、
さらにもともとのリンクから矢印の方向性を取り除いてモラルグラフを作ります。
次に、モラルグラフのすべてのクリークポテンシャル関数を $1$ に初期化します。
そして、もともとの有向グラフの条件付き分布因子を $1$ つずつ取ってきて、それぞれ対応するクリークポテンシャルの $1$ つに掛けます。

有向グラフから無向グラフへの変換では、有向グラフの持つ条件付き独立性の一部が捨てられます。
モラル化とは、リンクの追加を最小限に抑えることによって条件付き独立性をできる限り残す方法です。

偉人の名言

f:id:olj611:20211003101823p:plain:h300
自分にはできると信じれば、あなたはもう道半ばまで来ている
セオドア・ルーズベルト

参考文献

パターン認識と機械学習下巻 p96-p107

動画

なし