[TOC]

教科書

グラフィカルモデル 渡辺 有祐

1. 注意点

• 3章ベイジアンネットワークの証明の補足は終了 2019/2/14

ただし,定理3.5の証明が教科書だと載っていなくてネットで調べても出てこなかったので,載せていな.なお,定理3.5については以下のスライドの定理3.4で証明の概要が載っているんですが,確率分布の具体的な構成方法もしくは存在の証明が載っていないので納得していません.

事前知識

• 一般的なチェーンルール $P(A_1,\dots ,A_n)=P(A_n\mid A_1,\dots ,A_{n-1})P(A_{n-1}\mid A_1,\dots ,A_{n-2})\cdots P(A_2\mid A_1)P\left(A_1\right)$

証明の補足

2. 第3章 ベイジアンネットワーク

2.1. 定理3.2 (ベイジアンネットワークの因子分解)

Proofの補足

$P(X_i\mid X_{L\left(i\right)})=\frac{P(X_i,X_{L\left(i\right)})}{P\left(X_{pa\left(i\right)}\right)}\cdot \frac{P\left(X_{pa\left(i\right)}\right)}{P\left(X_{L\left(i\right)}\right)}=\frac{P\left(X_i\right)}{P\left(X_{pa\left(i\right)}\right)}\cdot \frac{P\left(X_{L\left(i\right)}\right)}{P\left(X_{pa\left(i\right)}\right)}\cdot \frac{P\left(X_{pa\left(i\right)}\right)}{P\left(X_{L\left(i\right)}\right)}=P(X_i\mid X_{pa\left(i\right)})$ 2つ目の不等式は条件付き独立性の性質の分離律から導かれる

Proof(3.2$\Rightarrow$3.1)

まず,教科書に載っている以下を示す

$$P(X_i,X_{\text{ndes}\left(i\right)})=P(X_i\mid X_{\text{pa}\left(i\right)})\cdot \prod _{j\in \text{ndes}\left(i\right)}P(X_j\mid X_{\text{pa}\left(j\right)})$$

Proof. $$\begin{array}{cc}P(X_i,X_{\text{ndes}\left(i\right)})& =\int P\left(X\right)d{X}_{\text{des}\left(i\right)}\\ & =\int \left(\prod _{j\in V}P\right(X_j\mid X_{\text{pa}\left(j\right)}\left)\right)\\ & =P(X_i\mid X_{\text{pa}\left(i\right)})\cdot \left(\prod _{j\in \text{ndes}\left(i\right)}P\right(X_j\mid X_{\text{pa}\left(j\right)}\left)\right)\cdot \\ & \int \left(\prod _{j\in \text{des}\left(i\right)}P\right(X_j\mid X_{\text{pa}\left(j\right)}\left)\right)d{X}_{\text{des}\left(i\right)}\\ & =P(X_i\mid X_{\text{pa}\left(i\right)})\cdot \left(\prod _{j\in \text{ndes}\left(i\right)}P\right(X_j\mid X_{\text{pa}\left(j\right)}\left)\right)\end{array}$$ ただし, 2つ目の等式は$j\notin \text{des}\left(i\right)\Rightarrow \text{pa}\left(j\right)\cap \text{des}\left(i\right)$から成り立つ.また3つ目の等式は終頂点に対応する$X$から始頂点に向かって順に積分していくと示される. その際に一般的に条件付き確率について$\int P(X\mid Y)dX=1$であることを用いる.

次に上記を用いて以下を示す.

$$P(X_i,X_{\text{ndes}\left(i\right)}\mid X_{\text{pa}\left(i\right)})=P(X_i\mid X_{\text{pa}\left(i\right)})\cdot P(X_{\text{ndes}\left(i\right)}\mid X_{\text{pa}\left(i\right)})$$

Proof. $$\begin{array}{cc}\text{(left)}& =\frac{P(X_i,X_{\text{ndes}\left(i\right)},X_{\text{pa}\left(i\right)})}{P\left(X_{\text{pa}\left(i\right)}\right)}\\ & =\frac{P(X_i,X_{\text{ndes}\left(i\right)})}{P\left(X_{\text{pa}\left(i\right)}\right)}\because \text{pa}\left(i\right)\subset \text{ndes}\left(i\right)\\ & =P(X_i\mid X_{\text{pa}\left(i\right)})\cdot \left(\prod _{j\in \text{ndes}\left(i\right)}P\right(X_j\mid X_{\text{pa}\left(j\right)}\left)\right)\cdot \frac{1}{P\left(X_{\text{pa}\left(i\right)}\right)}\end{array}$$ であるので, $$\prod _{j\in \text{ndes}\left(i\right)}P(X_j\mid X_{\text{pa}\left(j\right)})=P(X_{\text{ndes}\left(i\right)},X_{\text{pa}\left(i\right)})$$ であることを示せば十分. $$\begin{array}{cc}P(X_{\text{ndes}\left(i\right)},X_{\text{pa}\left(i\right)})& =P\left(X_{\text{ndes}\left(i\right)}\right)\because \text{pa}\left(i\right)\subset \text{ndes}\left(i\right)\\ & =\int P\left(X\right)d{X}_{\text{des}\left(i\right)}d{X}_i\\ & =\prod _{j\in \text{ndes}\left(i\right)}P(X_j\mid X_{\text{pa}\left(j\right)})\end{array}$$

2.2. 補題3.3 ベイジアンネットワークの構成の証明の補足

本文中に出てくる$q_i$は$q_i:X_i\times \{X_j{\}}_{j\in pa\left(i\right)}\to R_{\ge 0}$である

(定理3.2の証明と同様の手法を用いる)

帰納法より

$$\begin{array}{cc}\int P\left(X\right)dX& =\prod _{i\in V}{q}_i(X_i,X_{pa\left(i\right)})dX\\ & =\int (\int q_N(X_N,X_{pa\left(N\right)}d{X}_N\cdot \prod _{V\setminus \left\{N\right\}}{q}_i(X_i,X_{pa\left(i\right)})\left)\right)d{X}_{V\setminus \left\{N\right\}}\\ & \because N\text{is ending vertex}\\ & =\int \prod _{V\setminus \left\{N\right\}}{q}_i(X_i,X_{pa\left(i\right)})d{X}_{V\setminus \left\{N\right\}}\because \text{definition of}{q}_i\\ & =\int P\left(X_{V\setminus \left\{N\right\}}\right)d{X}_{V\setminus \left\{N\right\}}\\ & =1\because \text{assumption of induction}\end{array}$$ 次に式(3.4)を頂点数に関する帰納法を用いて示す. $$\begin{array}{c}P\left(X\right)=\left(\prod _{i\in V\setminus \left\{N\right\}}{q}_i\right(X_i,X_{pa\left(i\right)}\left)\right)\cdot q_N(X_N,X_{pa\left(N\right)})\end{array}$$ であり, $$\begin{array}{cc}P\left(X_{V\setminus \left\{N\right\}}\right)& =\int P\left(X\right)d{X}_N\\ & =\int \left(\prod _{i\in V}{q}_i\right(X_i,X_{pa\left(i\right)}\left)\right)d{X}_N\\ & =\prod _{i\in V\setminus \left\{N\right\}}{q}_i(X_i,X_{\text{pa}\left(i\right)})\cdot \int q_N(X_N,X_{\text{pa}\left(N\right)})d{X}_N\because \forall i\in V,N\notin \text{pa}\left(i\right)\\ & =\prod _{i\in V\setminus \left\{N\right\}}{q}_i(X_i,X_{\text{pa}\left(i\right)})\because \text{definition of}{q}_i\end{array}$$ であるので,$U:=V\setminus \left(\right\{N\}\cup \text{pa}(N\left)\right)$と定義すると, $$P\left(X\right)=P\left(X_{V\setminus \left\{N\right\}}\right)\cdot q_N(X_N,X_{pa\left(N\right)})=P(X_{\text{pa}\left(N\right)},X_U)\cdot q_N(X_N,X_{pa\left(N\right)})$$ であり,両辺を$X_U$で積分すると $$\begin{array}{cc}& P(X_N,X_{\text{pa}\left(N\right)})=q_N(X_N,X_{pa\left(N\right)})\cdot P\left(X_{\text{pa}\left(N\right)}\right)\\ \iff & P(X_N\mid X_{\text{pa}\left(N\right)})=q_N(X_N,X_{pa\left(N\right)})\end{array}$$ また,$P\left(X_{V\setminus \left\{N\right\}}\right)={\prod }_{i\in V\setminus \left\{N\right\}}{q}_i(X_i,X_{\text{pa}\left(i\right)})$であり,帰納法の仮定を用いると

$i\in V\setminus \left\{N\right\}$に対しても$P(X_i\mid X_{\text{pa}\left(i\right)})=q_i(X_i,X_{pa\left(i\right)})$が成立するので(3.4)は成立.

(これ以降は証明で使わなかったが,証明に挑戦する過程で示せた主張とその証明)

続いて以下を示す.

トポロジカルソートに対応する全単射を$n:V\to V$ (つまり, $(v_0,v_1)\in E\Rightarrow n\left(v_0\right)<n\left(v_1\right)$)とする.

また,任意の$j\in V$に対して$A_j:=\{i\in V\mid n(i)<n(j\left)\right\}$と定義する.

このとき,$\forall i\in A_j$に対して $j\notin pa\left(i\right)$

Proof.

$j\in \text{pa}\left(i\right)$を満たす$i\in A_j$が存在したとする. $j\in \text{pa}\left(i\right)$より$n\left(j\right)<n\left(i\right)$.一方で$i\in A_j$ より$n\left(i\right)<n\left(j\right)$より矛盾

$$\begin{array}{cc}P\left(X\right)& =\prod _{i\in V}{q}_i(X_i,X_{pa\left(i\right)})\\ & =q_N(X_N,X_{pa\left(N\right)})\prod _{i\in V\setminus \left\{N\right\}}{q}_i(X_i,X_{pa\left(i\right)})\end{array}$$

Nは終頂点より任意の$i\in V$に対して$pa\left(i\right)\cap \left\{N\right\}\ne mptyset$.また, $U$の定義より $U\bigsqcup pa\left(N\right)=V\setminus \left\{N\right\}$であるので,

関数$\varphi :X_U\times X_{pa\left(N\right)}\to R_{\ge 0}$が存在し $$\begin{array}{cc}{q}_N(X_N,X_{pa\left(N\right)})\prod _{i\in V\setminus \left\{N\right\}}{q}_i(X_i,X_{pa\left(i\right)})& =\varphi (X_U,X_{pa\left(N\right)})q_N(X_N,X_{pa\left(N\right)})\end{array}$$

次に$X_N⨿X_U\mid X_{\text{pa}\left(N\right)}$であるときに,次式の2つ目の等号が成立することを示す. $$\prod _{i\in V}{q}_i(X_i,X_{\text{pa}\left(i\right)})=P\left(X\right)=P(X_N\mid X_{\text{pa}\left(N\right)})\cdot P(X_{\text{pa}\left(N\right)},X_U)$$ Proof. $$\begin{array}{cc}P\left(X\right)& =P(X_N,X_{\text{pa}\left(N\right)},X_U)\\ & =P(X_N\mid X_{\text{pa}\left(N\right)})\cdot P(X_{\text{pa}\left(N\right)},X_U)\cdot \frac{P(X_N\mid X_{\text{pa}\left(N\right)},X_U)}{P(X_N\mid X_{\text{pa}\left(N\right)})}\end{array}$$ ゆえに, $P(X_N\mid X_{\text{pa}\left(N\right)},X_U)=P(X_N\mid X_{\text{pa}\left(N\right)})$であることが示せれば十分であるので,以下でそれを示す.

2.3. 定理3.4 (d分離の導く条件付き独立性)の証明

Step1(可能な限り周辺化したグラフに問題を落とし込む)

頂点集合$U,T,W$に含まれないものを終頂点の方から可能な限り周辺化したグラフ$(V^{\prime },\overrightarrow{E})$に対して定理が成立すれば元のグラフでも定理が成立する.

Proof.

グラフ構造$(V^{\prime },\overrightarrow{E})$をもつベイジアンネットワークの確率分布関数を$P^{\prime }$とすると,定理3.2より $$P^{\prime }\left(X\right)=\prod _{i\in V^{\prime }}P\left(i\right)=\int \prod _{i\in V}P\left(i\right)d{X}_{V\setminus V^{\prime }}=\int P\left(X\right)d{X}_{V\setminus V^{\prime }}$$ と表せる.ただし,$P\left(i\right):=P(X_i\mid X_{pa\left(i\right)})$とし2つ目の等号は終頂点から順に積分を行うことで得られる.

ゆえに $$\begin{array}{cc}{P}^{\prime }(X_U,X_T,X_W)& =\int P^{\prime }\left(X\right)d{X}_{V^{\prime }\setminus (U\cup T\cup W)}\\ & =\int (\int \prod _{i\in V}P(i\left)d{X}_{V\setminus V^{\prime }}\right)d{X}_{V^{\prime }\setminus (U\cup T\cup W)}\\ & =\int P\left(X\right)d{X}_{V\setminus (U\cup T\cup W)}\\ & =P(X_U,X_T,X_W)\end{array}$$ 以上より,グラフ構造$(V^{\prime },\overrightarrow{E^{\prime }})$をもつベイジアンネットワークで$X_U⨿X_T\mid X_W$が成立するとき$(V,E)$上のベイジアンネットワークでも成立. $\square$

以下では$(V^{\prime },\overrightarrow{E^{\prime }})$をもつベイジアンネットワークで定理が成立することを示す

Step2($U$と$T$を結ぶ無向路上で成立する性質)

$u\in U,t\in T$を結ぶ任意の無向路上で(ii)を満たす$r\in W$が存在する.

(ii) $r$はV構造ではなく$r\in W$が存在

Proof.

$U$,$T$が$W$のもとでd分離されているので$u,t$を結ぶ無向路は$W$のもとでアクティブではない.よって,無向路上に頂点$r$が存在して以下の(i)または(ii)が成立する.

(i) $r$がV構造であり,$\left\{r\right\}\cup \text{des}\left(r\right)\cap W=\varnothing$

(ii) $r$がV構造でなく$r\in W$

(i)が$r$で成立したとすると,$\left(\right\{r\}\cup \text{des}(r\left)\right)\cap (U\cup T)\ne \varnothing$である.もしそうでないなら$\left(\right\{r\}\cup \text{des}(r\left)\right)\cap (U\cup T\cup W)=\varnothing$となり,最初に可能な限り周辺化を行ったことに矛盾する.仮に$u^{\prime }\in \left(\right\{r\}\cup \text{des}(r\left)\right)\cap U$ がとれたとするとd分離より$u^{\prime }$と$t$を結ぶ無向路もアクティブでないはずである.頂点$v$から$u^{\prime }$まではV構造でなく$W$の元も存在しないことに注意すると$r$から$t$までの頂点$r^{\prime }(\ne r)$で(i)または(ii)が成立する.

$r$から$t$までの頂点$r^{\prime }$で(i)を満たしかつ$t^{\prime }\in \left(\right\{r^{\prime }\}\cup \text{des}(r^{\prime }\left)\right)\cap T$を満たすものが存在したとする.このとき$u^{\prime }\to r\to r^{\prime }\to t^{\prime }$の無向路はアクティブではなく,$u^{\prime }$から$r$,$r^{\prime }$から$t^{\prime }$はV構造でなく$W$の元も存在しないことから,$r$と$r^{\prime }$の間の頂点$r^{\prime \prime }(\ne r,r^{\prime })$で(i)または(ii)が成立する.上記の議論を繰り返すことで$u\in U$と$t\in T$を結ぶ任意の無向路上で(ii)を満たす$r\in W$が存在することがわかる.

Step3(同時確率分布の分解)

次に証明のために$U\subset \tilde{U},T\subset \tilde{T},S\subset V^{\prime }$を以下で定義する.

$\tilde{U}$は$V^{\prime }\setminus W$の部分集合であって,任意の$v\in \tilde{U}$に対して$u\in U$と$v$を結ぶ無向路(trail)が存在し,全ての頂点上で(ii)を満たさない.

英語の方が分かりやすいのでついでに書いとく $\tilde{U}$ is the set of node $v\in V^{\prime }\setminus W$ that $\exists u\in U$ and a trail connecting $u$ and $v$ such that every node of the path does not satisfy (ii)

$\tilde{T}$は$V^{\prime }\setminus W$の部分集合であって,任意の$v\in \tilde{T}$に対して$t\in T$と$v$を結ぶ無向路(trail)が存在し,全ての頂点上で(ii)を満たさない.

$S\equiv V^{\prime }\setminus (\tilde{U}\cup \tilde{T}\cup W)$

任意の$\tilde{u}\in \tilde{U}$に対して$\text{pa}\left(\tilde{u}\right)\cap \tilde{T}=\varnothing$

任意の$\tilde{t}\in \tilde{T}$に対して$\text{pa}\left(\tilde{t}\right)\cap \tilde{U}=\varnothing$

Proof.

対称性より任意の$\tilde{u}\in \tilde{U}$に対して$\text{pa}\left(\tilde{u}\right)\cap \tilde{T}=\varnothing$のみ示す.

$\tilde{t}\in \text{pa}\left(\tilde{u}\right)\cap \tilde{T}$が存在するとする.$\tilde{T}$の定義より$t\in T$が存在し,全ての頂点上で(ii)を満たさない$t$と$\tilde{t}$を結ぶ無向路が存在する.同様に.$\tilde{U}$の定義より$u\in U$が存在し,全ての頂点上で(ii)を満たさない$u$と$\tilde{u}$を結ぶ無向路が存在する.ゆえに任意の頂点において(ii)を満たさない$u$と$t$を結ぶ無向路が存在することになり矛盾.

任意の$\tilde{u}\in \tilde{U}$に対して$\text{pa}\left(\tilde{u}\right)\cap S=\varnothing$

任意の$\tilde{t}\in \tilde{T}$に対して$\text{pa}\left(\tilde{t}\right)\cap S=\varnothing$

Proof.

対称性より「任意の$\tilde{u}\in \tilde{U}$に対して$\text{pa}\left(\tilde{u}\right)\cap S=\varnothing$」のみを示せば十分.

$s\in \text{pa}\left(\tilde{u}\right)\cap S$が存在すると仮定する.$\tilde{U}$の定義より$u\in U$が存在し,全ての頂点上で(ii)を満たさない$u$と$\tilde{u}$を結ぶ無向路が存在する.よって,$u\to \tilde{u}\to s$の無向路を考えると$s\notin \tilde{U}$であることから,$\tilde{u},\tilde{s}$のいずれかが(ii)を満たすことになるが$\tilde{u},s\notin W$より(ii)を満たさない.ゆえに矛盾.

任意の$w\in W$に対して,

$$\text{pa}\left(w\right)\cap \tilde{U}\ne \varnothing \Rightarrow \text{pa}\left(w\right)\cap \tilde{T}=\varnothing ,\text{pa}\left(w\right)\cap S=\varnothing \text{pa}\left(w\right)\cap \tilde{T}\ne \varnothing \Rightarrow \text{pa}\left(w\right)\cap \tilde{U}=\varnothing ,\text{pa}\left(w\right)\cap S=\varnothing$$

のみ示す.

対称性より上のみ示す. $\tilde{u}\in \text{pa}\left(w\right)\cap \tilde{U}$とする.

Proof. $\text{pa}\left(w\right)\cap \tilde{T}=\varnothing$

$\tilde{t}\in \text{pa}\left(w\right)\cap \tilde{T}$が存在したとする.上記と同様の議論を行うことで$u\in U$, $t\in T$が存在し,全ての頂点において(ii)を満たさない$u\to \tilde{u}\to w\to \tilde{t}\to t$が存在するので矛盾

Proof. $\text{pa}\left(w\right)\cap S=\varnothing$

$s\in \text{pa}\left(w\right)\cap S$が存在したとする.$\tilde{U}$の定義より$u\in U$が存在し全ての頂点において(ii)を満たさない無向路$u\to \tilde{u}\to w\to s(\notin W)$が存在する.ゆえに$s\in \tilde{U}$となるがこれは$S$と$\tilde{U}$が共通部分を持たないことに矛盾.

任意の$s\in S$に対して

$\text{pa}\left(s\right)\cap \tilde{U}=\varnothing ,\text{pa}\left(s\right)\cap \tilde{T}=\varnothing$

Proof.

対称性より$\text{pa}\left(s\right)\cap \tilde{U}=\varnothing$のみ示す.$\tilde{u}\in \text{pa}\left(s\right)\cap \tilde{U}$が存在したとすると.$\tilde{U}$の定義より$u\in U$が存在し全ての頂点において(ii)を満たさない無向路$u\to \tilde{u}\to s(\notin W)$が存在する.ゆえに$s\in \tilde{U}$となるがこれは$S$と$\tilde{U}$が共通部分を持たないことに矛盾 $\square$

上記と同様の議論から$\tilde{U}\cap \tilde{T}=\varnothing$が示せるので$V^{\prime }=\tilde{U}\bigsqcup \tilde{T}\bigsqcup W\bigsqcup S$であり, $$P(X_{\tilde{U}},X_{\tilde{T}},X_W,X_S)=P\left(V^{\prime }\right)=\prod _{i\in V^{\prime }}P(X_i\mid X_{\text{pa}\left(i\right)})={\varphi }_1(X_{\tilde{U}},X_W){\varphi }_2(X_{\tilde{T}},X_W){\varphi }_3(X_S,X_W)$$ となる実数値関数${\varphi }_i(i=1,2,3)$が存在することが示される.なお最後の等式は確率の積を以下のルールに従って分解することで得られる.

任意の$i\in V^{\prime }$に対して$i\in \tilde{U}$ならば$P(X_i\mid X_{\text{pa}\left(i\right)})$を${\varphi }_1(X_{\tilde{U}},X_W)$の項に追加.$i\in S$ならば${\varphi }_3(X_S,X_W)$の項に追加, $i\in W$かつ$\text{pa}\left(i\right)\cap \tilde{U}\ne \varnothing$なら${\varphi }_1(X_{\tilde{U}},X_W)$の項に追加.

Step4(同時確率分布の積の分解と条件付き確率の対応)

最後に以下を示す.

$$\begin{array}{cc}& P(X_{\tilde{U}},X_{\tilde{T}},X_W,X_S)={\varphi }_1(X_{\tilde{U}},X_W){\varphi }_2(X_{\tilde{T}},X_W){\varphi }_3(X_S,X_W)\\ \Rightarrow & X_{\tilde{U}}⨿X_{\tilde{T}}\mid X_W\end{array}$$

Proof.

仮定の両辺を$X_S$で積分することで,実数値関数${\varphi }_4:X_W\to R_{\ge 0}$を用いて $$P(X_{\tilde{U}},X_{\tilde{T}},X_W)={\varphi }_1(X_{\tilde{U}},X_W){\varphi }_2(X_{\tilde{T}},X_W){\varphi }_4\left(X_W\right)$$ と表せる.この左辺を$X_{\tilde{T}}$と$X_{\tilde{U}}$でそれぞれ積分することで $$P(X_{\tilde{U}},X_W)={\varphi }_1(X_{\tilde{U}},X_W){\varphi }_5\left(X_W\right){\varphi }_4\left(X_W\right)P(X_{\tilde{T}},X_W)={\varphi }_6\left(X_W\right){\varphi }_2(X_{\tilde{T}},X_W){\varphi }_4\left(X_W\right)$$ が得られる.ゆえに $$\begin{array}{cc}P(X_{\tilde{U}},X_{\tilde{T}},X_W)& =P(X_{\tilde{U}},X_W)P(X_{\tilde{T}},X_W)\cdot \frac{1}{{\varphi }_4\left(X_W\right){\varphi }_5\left(X_W\right){\varphi }_6\left(X_W\right)}\\ & =P(X_{\tilde{U}},X_W)P(X_{\tilde{T}},X_W)\cdot \frac{1}{{\varphi }_7\left(X_W\right)}\end{array}$$ ここで両辺を$X_{\tilde{T}}$で積分すると $$P(X_{\tilde{U}},X_W)=P(X_{\tilde{U}},X_W)\cdot \frac{P\left(X_W\right)}{{\varphi }_7\left(X_W\right)}$$ より${\varphi }_7\left(X_W\right)=P\left(X_W\right)$,ゆえに$P(X_{\tilde{U}},X_{\tilde{T}},X_W)$の両辺を$P\left(X_W\right)$で割ることで所望の結果が得られる.

3. 4章 マルコフ確率場

3.1. 定理4.2 (マルコフ性条件の関係 2.)

任意のクリーク(clique)$C$は $C\subset \tilde{A}\cup S$または $C\subset \tilde{B}\cup S$である.

ここでのcliqueはmaximal cliqueのことを指す.

Proof.

${}^{\exists }\tilde{a}\in \tilde{A},\tilde{a}\in C\Rightarrow c\notin \tilde{B}{(}^{\forall }c\in C)$

${}^{\exists }\tilde{b}\in \tilde{B},\tilde{b}\in C\Rightarrow c\notin \tilde{A}{(}^{\forall }c\in C)$

を示せば十分.(${}^{\exists }\tilde{a}\in \tilde{A},\tilde{a}\in C$) $\wedge$ (${}^{\exists }c\in C,c\in \tilde{B}$)が成立すると仮定して矛盾を導く.

$\tilde{A}$の定義より$a\in A$が存在して$V\setminus S$に属する頂点のみを経由して$\tilde{a}$に達する路が存在する.一方$c\in \tilde{B}=V\setminus (\tilde{A}\cup S)\subset V$であり,クリークは完全グラフであるので$\tilde{a}c\in E$である.よって$a$から$V\setminus S$に属する頂点のみを経由して$\tilde{c}$に到達できるので$c\in \tilde{A}$になる.これは$c\in \tilde{B}=V\setminus (\tilde{A}\cup S)$に矛盾.ゆえに,${}^{\exists }\tilde{a}\in \tilde{A},\tilde{a}\in C\Rightarrow c\notin \tilde{B}{(}^{\forall }c\in C)$が成立.${}^{\exists }\tilde{b}\in \tilde{B},\tilde{b}\in C\Rightarrow c\notin \tilde{A}{(}^{\forall }c\in C)$も同様の議論によって示すことができる.

$X_{\tilde{A}}\perp \perp X_{\tilde{B}}\mid X_S$

Proof.

$\$P\left(X_V\right)=\frac{1}{Z}{\prod }_{C:\text{clique}}{\varphi }_C\left(X_C\right)=\frac{1}{Z}{\prod }_{C\subset \tilde{A}\cup S}{\varphi }_C\left(X_C\right){\prod }_{C\subset \tilde{B}\cup S}{\varphi }_C\left(X_C\right)={\varphi }_1(X_{\tilde{A}},X_S){\varphi }_2(X_{\tilde{B}},X_S)$$

と表せることに注意する.

$V=\tilde{A}\bigsqcup \tilde{B}\bigsqcup S$であることに留意して両辺を$\tilde{A},\tilde{B}$に対して周辺化すると $$P(X_{\tilde{B}},X_S)={\varphi }_3\left(X_S\right){\varphi }_2(X_{\tilde{B}},X_S)P(X_{\tilde{A}},X_S)={\varphi }_1(X_{\tilde{A}},X_S){\varphi }_4\left(X_S\right)$$ ゆえに, $$P\left(X_V\right){\varphi }_3\left(X_S\right){\varphi }_4\left(X_S\right)=P(X_{\tilde{A}},X_S)P(X_{\tilde{B}},X_S)$$ となり両辺を$\tilde{A},\tilde{B}$に対して順に周辺化すると, $$P\left(X_S\right){\varphi }_3\left(X_S\right){\varphi }_4\left(X_S\right)=P(X_S{)}^2$$ ゆえに,$P\left(X_S\right)>0$のとき$P\left(X_S\right)={\varphi }_3\left(X_S\right){\varphi }_4\left(X_S\right)$が成立する.よって $$P\left(X_V\right)P\left(X_S\right)=P(X_{\tilde{A}},X_S)P(X_{\tilde{B}},X_S)$$ より証明終了.

$B\subset \tilde{B}$

$b\in \tilde{A}$を満たす$b\in B$が存在したとする.この時$\tilde{A}$の定義より$A$から$b$への路で$S$に含まれない頂点のみを通るものが存在するが,これは$S$が$A$と$B$を分離することに矛盾する.よって$b\in B\Rightarrow b\notin \tilde{A}$であり,仮定より$b\in B\Rightarrow b\notin S$であるので$b\in B\Rightarrow b\in V\setminus (S\cup \tilde{A})=\tilde{B}$

3.2. 定理4.3(Hammersley-Cllifordの定理)

基本的な証明はこちらを参照

上記の補足

Lemma 2.1 (M$\ddot{o}$bius Inversion Lemma)

for any non empty set, there are the same number of even and odd subsets

Proof. $$\sum _k^n(-1{)}^k(\frac{n}{k})=\sum _k^n{1}^{n-k}(-1{)}^k(\frac{n}{k})=(1+(-1){)}^n$$

Theorem 2.2 (Hammersley and Clifford)

$\alpha ,\beta \in a,c=a\setminus \{\alpha ,\beta \},b:b\subseteq c$であるので,$|a\setminus b|\ge 2$であることに注意.

確率は全て正であるので,$f\left(x\right)=1$となる$x$は存在しない

Theorem 2.2 (Hammersley and Clifford)

(2.15) $\Rightarrow$ (2.16) $f(x_{\alpha }\mid x_{\beta },x_b,x_{d\setminus b}^{\ast })=f(x_{\alpha }\mid x_b,x_{d\setminus b}^{\ast })$

Proof.

$d=V\setminus \{a,b\}$であることに注意して,

$f(x_{\alpha }\mid x_{\beta },x_d)=f(x_{\alpha }\mid x_d)$であることを示せば十分.

$x_{\alpha }\perp \perp x_{\beta }\mid x_d$であることに注意すると, $$f(x_{\alpha }\mid x_{\beta },x_d)=\frac{f(x_{\alpha },x_{\beta },x_d)}{f(x_{\beta },x_d)}=\frac{f(x_{\alpha },x_{\beta },x_d)}{f\left(x_d\right)}\frac{f\left(x_d\right)}{f(x_{\beta },x_d)}=\frac{f(x_{\alpha },x_d)}{f\left(x_d\right)}\frac{f(x_{\beta },x_d)}{f\left(x_d\right)}\frac{f\left(x_d\right)}{f(x_{\beta },x_d)}=f(x_{\alpha }\mid x_d)$$

Theorem 2.2 (Hammersley and Clifford)

(2.17) $\Rightarrow$ (2.18)

$f(x_{\alpha }^{\ast }\mid x_b,x_{d\setminus b}^{\ast })f(x_{\beta },x_b,x_{d\setminus b}^{\ast })=f(x_b,x_{\beta },x_{\alpha },x_{d\setminus b}^{\ast })$

Proof. $$\begin{array}{cc}f(x_{\beta },x_{d\setminus b}^{\ast },x_b,x_{\alpha }^{\ast })& =f(x_{\alpha }^{\ast }\mid x_{\beta },x_{d\setminus b}^{\ast },x_b)f(x_b,x_{\beta },x_{d\setminus b}^{\ast })\\ & =f(x_{\alpha }^{\ast }\mid x_{d\setminus b}^{\ast },x_b)f(x_b,x_{\beta },x_{d\setminus b}^{\ast })\end{array}$$

3.3. 定理4.4(ベイジアンネットワークとマルコフ確率場) モラル化

確率変数族$X=\{X_v{\}}_{v\in V}$は有向非巡回グラフ$G=(V,\overrightarrow{E})$上のベイジアンネットワークであるとする.このとき,各頂点$v\in V$で$u,u^{\prime }\in \text{pa}\left(v\right)$同士を辺で結び有向枝を無向辺にしたグラフ$G^{\prime }=(V,E)$を考えると$\{X_v{\}}_{v\in V}$はグラフ$G^{\prime }$に関して因子分解する.この操作をモラル化(moralization)という.

$E$の構成方法により,任意の$v\in V$に対して$\left\{v\right\}\cup \text{pa}\left(v\right)$はグラフ$G^{\prime }$上で完全グラフである.よって,任意の$v\in V$に対して$\left\{v\right\}\cup \text{pa}\left(v\right)\subset C_v$となるようなクリーク$C_v$を1つ定めることができる.

ここで,グラフ$G^{\prime }$上の任意のクリーク$C$に対して${\varphi }_C\left(X_c\right):={\prod }_{v\in V,C_v=C}P(X_v\mid X_{\text{pa}\left(v\right)})$と定義すると, $$P\left(X\right)=\prod _{v\in V}P(X_v\mid X_{\text{pa}\left(v\right)})=\prod _{C:\text{clique}}{\varphi }_C\left(X_c\right)$$

3.4. 4.5 (例) ガウス型のマルコフ確率場

多変量正規分布について良さそうな教科書

確率変数ベクトル$x$が$n$次元多変量正規分布に従っているとする.つまり確率密度関数は正定値行列は正定値行列$\Sigma$とベクトル$\mu$を用いて以下のように表されるとする.

$$f\left(x\right)=\frac{1}{(\sqrt{2\pi }{)}^n\sqrt{|\Sigma |}}\exp (-\frac{1}{2}(x-\mu {)}^T{\Sigma }^{-1}(x-\mu ))$$

この時,確率ベクトルの添字を以下のようにして並び替えることができる.

$\tau$を任意の置換とする.$x_{\tau }:=(x_{\tau \left(1\right)},\cdots ,x_{\tau \left(n\right)})$,${\Sigma }_{\tau }^{-1}$を$({\Sigma }_{\tau }^{-1}{)}_{ij}=({\Sigma }^{-1}{)}_{\tau \left(i\right)\tau \left(j\right)}$と定義すると,