修士論文 要旨

グラフィカルモデルへの imset を用いた代数的アプローチ
数理情報学専攻 48-096209
指導教員

柏村拓哉
竹村彰通教授における条件付き独立性 A ⊥⊥ B | C [P] の定義

1 導入
条件付き独立性は, 確率変数間の相関関係や絡みなど

PABC (xA , xB , xC )·PC (xC ) = PAC (xA , xC )·PBC (xB , xC )の質的関係を与えるものであり, 統計学や人工知能の分において, 両辺の対数を取ったものに対応している.

野で非常によく用いられている概念である.

特に, A = {a}, B = {b} のとき, u⟨{a},{b} | C⟩ を ele-条件付き独立性の構造は, 伝統的にグラフや特別なリmentary imset と呼ぶ. さらに, elementary imset のストで表せされるが, これらでは完全に構造を表すこと

張る凸錐内の格子点を structural imset と呼び, そのはできない. そこで, imset と呼ばれる整数ベクトルを集合を S(N ) で表す. 定義より, structural imset は,用いた手法が, M. Studený [4] により提案された. この

elementary imset の非負有理数結合で表せることがわ

手法を用いることにより, 離散確率測度による条件付きかる.

Structural imset u ∈ S(N ) と 3 つ組 ⟨A, B | C⟩ ∈独立性の構造を完全に記述することができる.
この imset を用いた手法では, 複数の imset が同じ条T (N ) に対して, A ⊥⊥ B | C [u] を, ∃k ∈ N, k · u −件付き独立性の構造を記述することがある. したがっu⟨A,B | C⟩ ∈ S(N ) が成り立つときと定義する. また,て, この imset の同値類の中で適切な代表元を求めるこMu = {⟨A, B | C⟩ ∈ T (N ) : A ⊥⊥ B | C [u]} とする.とが問題となる. Studený は, その問題の一つとして,任意の離散確率測度 P に対して, ある structural imset

古典的なグラフィカルモデルに対する imset を求める

u ∈ S(N ) が存在し,ことを考えた. 特に, 非巡回的有向グラフや分解可能グラフに対し, standard imset と呼ばれる imset を用いた表現法を与えている [4]. 連鎖グラフに対しても, 特別な場合においては imset による表現法を導いている [5].
本論文では, これらの先行研究の結果を拡張し, 無向グラフおよび一般の連鎖グラフに対する imset による表現法を導出した. ここで得られた imset は, 先行研究

A⊥
⊥ B | C [u] ⇐⇒ A ⊥⊥ B | C [P],∀⟨A, B | C⟩ ∈ T (N )が成り立つことが知られている [4].

3 分解可能グラフに対する imset (先行研究)
分解可能グラフに対する imset は Studený [4] により導出されている.
単純な無向グラフ G に対し, C ⊂ N を取り除いたグの一般化となっている.

ラフ GN \C において, 排反な部分集合 A, B ⊆ N \ C が2 Imset

連結でないとき, A ⊥⊥ B | C [G] と表す. また, MG =有限な変数集合を N とする. 条件付き独立性を考え{⟨A, B | C⟩ ∈ T (N ) : A ⊥⊥ B | C [G]} とする. G の極る際には, 通常 3 つの互いに排反な部分集合 A, B, C ⊆大クリークの集合を K(G) としたとき, あるこの要素のN を考える. ここでは, これらの 3 つ組を ⟨A, B | C⟩ と

順序 K1 , . . . , Km が存在し, RIP書く. この 3 つ組すべてからなる集合を T (N ) で表す.

Imset は Z2N上のベクトルである. 集合 A ⊆ N に対し,{1δA (B) =02 ≤ ∀i ≤ m, 1 ≤ ∃k < i, Si ≡ Ki ∩∪Kj ⊆ Kkj<iを満たすとき, G は分解可能であるという [2]. また,S(G) = {S2 , . . . , Sm } とする. 分解可能グラフ G の(B = A),(B ̸= A, B ⊆ N )を basic imset と呼ぶ. この basic imset は R2

standard imset は, 次のように定義される [4]:Nの標準基底をなす. また, 特別な imset として,u⟨A,B | C⟩ = δABC +δC −δAC −δBC , ⟨A, B | C⟩ ∈ T (N )を semi-elementary imset という. これは, 離散測度 PuG = δN −∑K∈K(G)δK +∑νG (S) · δS .

(1)S∈S(G)

この imset は, グラフ G が規定する条件付き独立性を完全に表している. つまり, MuG = MG が成り立つ.

グラフィカルモデルへの imset を用いた代数的アプローチ (柏村拓哉)

で定義する. ただし, C(G) は, グラフ G の連結成分の集4 無向グラフに対する imset の導出合であり, 任意の C ∈ C(G) について, uG(C) は閉包グラ

前節の分解可能の場合の結果を利用するために, グラフと呼ばれる無向グラフ G(C) に対する standard imset

フに辺を付け加えて分解可能にすることを考える. この(式 (2)) である. 連鎖グラフのうち, ある非巡回的有向操作でできたグラフを三角化 (triangulation [1]) と呼グラフと同じ条件付き独立を規定する場合には, 式 (3)ぶ. このうち, 辺の包含関係に対し極小なものを極小三で uG(C) を分解可能グラフに対する imset (式 (1)) とし角化と呼ぶ.

たもので与えられている [5]. よって, 式 (3) は先行研究

一般の無向グラフ G に対しては, すべての極小三角化 MT (G) を考えることにより, この無向グラフを表わす imset を構成することができる.
定理 4.1. 無向グラフ G に対し, vG =∑の一般化となっている. この imset は, 連鎖グラフに対する imset となっている.
定理 5.1. 連鎖グラフ G に対し, uG を式 (3) で定義す

G′ ∈MT (G) uG′(ただし, uG′ は式 (1) で与えられる) とする. このとき,MG = MvG が成り立つ.

る. このとき, MuG = MG が成り立つ.
これは, 無向グラフと同様の議論を行うことにより得られる. そのために, 本論文では連鎖グラフに対し, 三誘導部分グラフ GV , V ⊂ N がクリークセパレータを持たない部分グラフの中で極大であるとき, これをmp-subgraph であるという [3]. グラフの極小三角化は角化を一般化した概念を定義した.

6 まとめと今後の課題

mp-subgraph と呼ばれる誘導部分グラフに分解して,本論文では, 無向グラフと連鎖グラフに対して imset各グラフごとで極小三角化を考えれば十分であることの導出を行った. この過程で重要な概念は極小三角化でがわかる. よって, 無向グラフに対する imset を次で定ある. また他の成果として, 同じ条件付き独立性を表す

義する:

連鎖グラフに対し, 与えた imset が一意に定まることを

u G = δN −∑δV +V ∈V(G)∑+∑示した. これは, [5] の結果の一般化となっている.

νG (S) · δS

今後の課題としては, imset を elementary imset のS∈S(G)

∑uH .

(2)

和で表したとき, その足されている elemenrary imsetの個数 (次数) が少ないものを求めることが考えられる.

V ∈V(G) H∈MT (GV )ただし, V(G) を G の mp-subgraph の頂点集合の族でこれは, [4] で代表元の基準として考えられているものあり, 各 H ∈ MT (GV ) (V ∈ V(G)) 対し, uH は式 (1)の一つである. また, 本論文では, 無向グラフに対するで定義される standard imset である. この imset も Gimset を, 性質の良いグラフ (分解可能グラフ) の場合にの表す条件付き独立性を完全に記述している.

帰着することにより求めた. よって, 一般の条件付き独立モデルについて, 何らかの意味で三角化の概念を一般定理 4.2. 無向グラフ G に対し, uG を式 (2) で定義する. このとき, MuG = MG が成り立つ.

らの imset を求めることができると考えられる.

参考文献

5 連鎖グラフに対する imset の導出
連鎖グラフは, 有向辺と無向辺を持ち, 有向サイクルを持たないグラフとして定義される. これは, 非巡回的有向グラフや無向グラフの一般化となっている. 連鎖グラフ G には, moralization と呼ばれる分離基準があり [2], ここから規定される条件付き独立性の集合をMG で表す. 連鎖グラフ G に対しては, その standard
imset をu G = δN − δ∅ +化し, グラフィカルモデルの場合に帰着できれば, これ}∑ {δpaG (C) − δC∪paG (C) + uG(C)C∈C(G)(3)[1] P. Heggernes: Minimal triangulations of graphs: Asurvey. Discrete Mathematics, 306, pp. 297–317,
2006.
[2] S. L. Lauritzen: Graphical Models. Oxford University
Press, Oxford, 1996.
[3] H. G. Leimer: Optimal decomposition by cliqueseparators. Discrete Mathematics, 113, pp. 99–123,
1993.
[4] M. Studený: Probabilistic Conditional Independence
Structures. Springer-Verlag, London, 2005.
[5] M. Studený, A. Roverato, and Š. Štepànovà: Two
operations of merging and splitting components ina chain graph. Kybernetika, 45, no. 2, pp. 208–248,2009.