スパース推定の命題17の証明

条件付き独立性などの関係が、以下の条件を満足するときに、無向グラフの分離性によってすべて表現できることが知られている(J. Pearl, “Probabilistic Reasoning in Intelligent Systems”, 1988)。$$X_A\perp X_B\mid X_C \Longleftrightarrow X_B\perp X_A|X_C\tag{1}$$$$X_A\perp (X_B\cup X_D)\mid X_C \Longrightarrow X_A\perp X_B|X_C, X_A\perp X_D\mid X_C\tag{2}$$ $$X_A\perp (X_C\cup X_D)\mid X_B, X_A\perp_E X_D\mid (X_B\cup X_C) \Longrightarrow X_A\perp (X_B\cup X_D)\mid X_C\tag{3}$$ $$X_A\perp X_B\mid X_C \Longrightarrow X_A\perp X_B\mid (X_C\cup X_D)\tag{4}$$ $$X_A\perp X_B\mid X_C \Longrightarrow X_A\perp X_k \mid X_C\ {\rm or}\ X_k \perp X_B|X_C\tag{5}\ ,\ k\not \in C$$ ただし、各方程式で$A,B,C,D$は、排他的な$V$の部分集合であるとする。このうち、条件付き独立性に関しては(4)(5)以外は、満足されることがわかる。たえとえば(3)は、仮定$$f(x_A,x_B,x_C,x_D)f(x_C,x_D)=f(x_A,x_C,x_D)f(x_B,x_C,x_D) \tag{6}$$ $$f(x_A,x_B,x_C,x_D)f(x_B,x_C)=f(x_A,x_B,x_C)f(x_B,y_C,x_D)\ ,$$から、$f(x_B,x_C)f(x_A,x_C,x_D)=f(x_A,x_B,x_C)f(x_C,x_D)$が得られ、これを周辺化して、$$f(x_C)f(x_A,x_C,x_D)=f(x_A,x_C)f(x_C,x_D)\tag{7}$$が得られる。そして、(6)(7)は$$f(x_A,x_B,x_c,x_D)f(x_C)=f(x_A,x_c)f(x_B,x_C,x_D)$$を意味し、さらに(3)を意味する。また、(4)は命題16より成立する。したがって、(5)が成立することを言えば十分である。まず、$k\in A$または$k\in B$であれば、自明に成立する。そして、正規分布であるので、$k\not\in A\cup B\cup C$のもとで、$X_A\perp X_k \mid X_C$と $X_k \perp X_B|X_C$の両方が成立しないのは、 $X_A\perp X_B|X_C$と矛盾する。したがって、(5)が成立する。

以上より、正規分布の場合、無向グラフの分離性によって、条件付き独立性のすべてが無向グラフで表現できる。