グラフォイドとは、「 Z が分かっているという条件の下で、 Xは Y とは無関係である」という形式の命題の集合であり、 X 、Y 、Z は変数の集合である。「無関係」と「分かっているという条件の下で」という概念は、適用に応じて、確率的 、関係的 、相関的など、さまざまな解釈が可能となる。これらの解釈は、グラフ内のパスによって捉えることができる共通の特性を共有している（そのため「グラフォイド」という名前が付けられている）。グラフォイド理論は、情報的無関係とそのグラフ表現に共通する有限個の公理 によって、これらの特性を特徴づける。
意味 依存モデルM は、述語I ( X , Z , Y ): Xは Z が与えられたときY とは独立である、が真となるトリプレット ( X , Z , Y )の部分集合である。グラフイドは、次の 5 つの公理の下で閉じている依存モデルとして定義される。
対称： 私 （ X 、 Z 、 Y ） ⇔ 私 （ Y 、 Z 、 X ） {\displaystyle I(X,Z,Y)\Leftrightarrow I(Y,Z,X)} 分解：私 （ X 、 Z 、 Y ∪ W ） ⇒ 私 （ X 、 Z 、 Y ） ＆ 私 （ X 、 Z 、 W ） {\displaystyle I(X,Z,Y\cup W)\Rightarrow I(X,Z,Y)~\&~I(X,Z,W)} 弱い組合：私 （ X 、 Z 、 Y ∪ W ） ⇒ 私 （ X 、 Z ∪ W 、 Y ） ＆ 私 （ X 、 Z ∪ Y 、 W ） {\displaystyle I(X,Z,Y\cup W)\Rightarrow I(X,Z\cup W,Y)~\&~I(X,Z\cup Y,W)} 収縮：私 （ X 、 Z 、 Y ） ＆ 私 （ X 、 Z ∪ Y 、 W ） ⇒ 私 （ X 、 Z 、 Y ∪ W ） {\displaystyle I(X,Z,Y)~\&~I(X,Z\cup Y,W)\Rightarrow I(X,Z,Y\cup W)} 交差点：私 （ X 、 Z ∪ W 、 Y ） ＆ 私 （ X 、 Z ∪ Y 、 W ） ⇒ 私 （ X 、 Z 、 Y ∪ W ） {\displaystyle I(X,Z\cup W,Y)~\&~I(X,Z\cup Y,W)\Rightarrow I(X,Z,Y\cup W)} 半グラフイドは、1～4 の下で閉じている依存モデルです。これら 5 つの公理はまとめてグラフイド公理として知られています。[ 8 ] [ 8 ]
グラフの種類
確率的グラフ 条件付き独立性とは、次のように定義される。
私 （ X 、 Z 、 Y ） ⇔ P （ X ∣ Y 、 Z ） = P （ X ∣ Z ） {\displaystyle I(X,Z,Y)\Leftrightarrow P(X\mid Y,Z)=P(X\mid Z)} これは半グラフイドであり、P が厳密に正の場合に完全なグラフイドになります。[ 1 ] [ 7 ]
相関グラフ 依存関係モデルは、ある確率関数において、以下の条件を満たす場合、相関グラフである。
私 c （ X 、 Y 、 Z ） ⇔ ρ x y 。 z = 0 すべての x ∈ X そして y ∈ Y \displaystyle I_{c}(X,Y,Z)\Leftrightarrow \rho _{xy.z}=0 \text{ は、すべての }}x\in X および }}y\in Y に対して成り立つ} どこρ x y 。 z {\displaystyle \rho _{xy.z}} Zが与えられたときの x とy の間の偏相関 です。
言い換えれば、Z の測定値を使用したXの変数の線形推定誤差は、 Y の変数の測定値を追加しても減少しないため、Y は X の推定とは無関係に なります。相関依存モデルと確率依存モデルは、正規分布では一致します。[ 1 ] [ 7 ]
関係グラフ 依存関係モデルは、以下の条件を満たす場合、関係グラフである。
P （ X 、 Z ） > 0 ＆ P （ Y 、 Z ） > 0 ⟹ P （ X 、 Y 、 Z ） > 0. {\displaystyle P(X,Z)>0~\&~P(Y,Z)>0\暗黙的に P(X,Y,Z)>0.} つまり、Z が固定されると、Xに許容される値の範囲は Y の選択によって制限されない。このモデルに属する独立性ステートメントは、データベースの埋め込み多値依存性（EMVD） に似ている。[ 1 ] [ 7 ]
グラフ誘導型グラフォイド 次のような無向グラフG が存在する場合、
私 （ X 、 Z 、 Y ） ⇔ ⟨ X 、 Z 、 Y ⟩ G 、 {\displaystyle I(X,Z,Y)\Leftrightarrow \langle X,Z,Y\rangle _{G},} この場合、グラフイドはグラフ誘導型と呼ばれます。言い換えれば、M のすべての独立性ステートメントがG の頂点分離として反映され、またその逆も成り立つような無向グラフG が存在します。依存モデルがグラフ誘導型グラフイドであるための必要十分条件は、対称性、分解性、交差性、強和性、推移性という以下の公理を満たすことです。
強力な労働組合は、
私 （ X 、 Z 、 Y ） ⟹ 私 （ X 、 Z ∪ W 、 Y ） {\displaystyle I(X,Z,Y)\implies I(X,Z\cup W,Y)} 推移律は次のように述べている。
私 （ X 、 Z 、 Y ） ⟹ （ ∀ γ ∉ X ∪ Y ∪ Z 、 私 （ X 、 Z 、 γ ） または 私 （ γ 、 Z 、 Y ） ） {\displaystyle I(X,Z,Y)\implies \left(\forall ~\gamma \notin X\cup Y\cup Z,~~I(X,Z,\gamma ){\text{ or }}I(\gamma ,Z,Y)\right)} 対称性、分解性、交差性、強和性、推移性の公理は、無向グラフの完全な特徴付けを構成する。[ 9 ]
DAG誘導グラフォイド グラフイドは、次のような有向非巡回グラフD が存在する場合に DAG 誘導であると呼ばれる。 私 （ X 、 Z 、 Y ） ⇔ ⟨ X 、 Z 、 Y ⟩ D {\displaystyle I(X,Z,Y)\Leftrightarrow \langle X,Z,Y\rangle _{D}} ⟨ X 、 Z 、 Y ⟩ D {\displaystyle \langle X,Z,Y\rangle _{D}} D におけるd 分離d は「方向性」を意味する) は、無向グラフの頂点分離の概念を、有向非巡回グラフに拡張する。これにより、 ベイジアンネットワーク の構造から条件付き独立性を読み取ることができる。ただし、DAG における条件付き独立性は、有限個の公理によって完全に特徴付けることはできない。[ 10 ]
インクルージョンと構築 グラフ誘導グラフォイドとDAG誘導グラフォイドはどちらも確率的グラフォイドに含まれます。[ 11 ] Gに対して、 P のすべての条件付き独立性がG で表現されるような確率分布Pが 存在し、その逆もまた同様であることを意味します。DAGについても同様です。ただし、グラフォイドではない確率分布も存在し、さらに、確率的条件付き依存性に対する有限の公理化はありません。 [ 12 ]
Thomas Verma は、すべての半グラフイドには、すべてのd 分離が有効となるDAG を再帰的に構築する方法があることを示した。[ 13 ] この構築方法はベイズネットワーク で使用されるものと似ており、次のようになる。
変数を任意の順序 1, 2,...,i,..., N に並べ、i = 1 から始めます。 各ノードiに対して、 PA i を条件としてi が そのすべての先行ノード 1, 2,..., i − 1から独立しているようなノードの集合PA i PA i からi へ矢印を描き、続けてください。この構成によって作成されるDAGは、構成で使用された条件付き独立性から導かれるすべての条件付き独立性を表します。さらに、DAGに示されるすべてのd 分離は、構成で使用されたグラフにおいて有効な条件付き独立性となります。
参考文献 1 2 3 4 5 Pearl, Judea; Paz, Azaria (1985). "Graphoids: A Graph-Based Logic for Reasoning About Relevance Relations" (PDF) . ↑ Dawid, A. Philip (1979). "統計理論における条件付き独立性". Journal of the Royal Statistical Society, Series B : 1– 31. ↑ Spohn, Wolfgang (1980). "確率的独立性、因果的独立性、および遮蔽可能性" . Journal of Philosophical Logic . 9 : 73–99 . doi : 10.1007/bf00258078 . ↑ Pearl, Judea (1986). "信念ネットワークにおける融合、伝播、構造化". 人工知能 . 29 (3): 241– 288. doi : 10.1016/0004-3702(86)90072-x . ↑ Verma, Thomas; Pearl, Judea (1988). "因果ネットワーク: 意味論と表現力". Proceedings of the 4th Workshop on Uncertainty in Artificial Intelligence : 352–359 . ↑ Lauritzen, SL (1996). Graphical Models . Oxford: Clarendon Press. 1 2 3 4 Geiger, Dan (1990). "Graphoids: A Qualitative Framework for Probabilistic Inference" (PhD Dissertation, Technical Report R-142, Computer Science Department, University of California, Los Angeles) . 1 2 パール、ジュデア (1988). 知能システムにおける確率的推論: もっともらしい推論のネットワーク . モーガン・カウフマン. ↑ A. Paz、J. Pearl、S. Ur、「インターセプション関係に基づくグラフの新しい特徴付け」Journal of Graph Theory、Vol. 22、No. 2、125-136、1996年。 ↑ Geiger, D. (1987). "有向非巡回グラフにおける依存関係の非公理化可能性" (PDF) . UCLA コンピュータサイエンス技術レポート R-83 . ↑ Geiger, D.; Pearl, J. (1993). "条件付き独立性とグラフィカルモデルの論理的およびアルゴリズム的特性". The Annals of Statistics . 21 (4): 2001–2021 . CiteSeerX 10.1.1.295.2043 . doi : 10.1214/aos/1176349407 . ↑ Studeny, M. (1992). Kubik, S.; Visek, JA (eds.). "条件付き独立関係には有限の完全な特徴付けはありません". 情報理論、統計的決定関数、およびランダムプロセス。第 11 回プラハ会議の論文集 。B . ドルドレヒト: Kluwer: 377–396 . ↑ Verma, T.; Pearl, J. (1990). Shachter, R.; Levitt, TS; Kanal, LN (編). "Causal Networks: Semantics and Expressiveness". Uncertainty in AI 4. Elsevier Science Publishers: 69–76 . 
