Perturbation method for determining the group of invariance of hierarchical models

(1)

.

.. .

.

Perturbation method for determining the group of

invariance of hierarchical models

清智也1 青木敏2 竹村彰通1

1_東京大学 2_{鹿児島大学}

(2)

概要

例：2× 3分割表 p11 p12 p13 p21 p22 p23 (pij ≥ 0, ∑ i;jpij = 1).

独立性：pij = aibj ⇔ log pij = αi+ βj.

(log pij) (αi) (βj)

行を入れ替えても，独立という構造は不変．（置換(1, j)↔ (2, j)）

(3)

概要

構造が不変に保たれない置換の例：

行の構造だけは保たれている．独立モデル以外の場合も考えてみる．

(4)

概要

m元分割表：(pi1´´ím)∈ R I1ˆ´´´Îm_. 対数線形モデル：(log pi1´´ím)∈ L, ここでLは線形部分空間．例：独立モデルではL ={(αi+ βj)}. 置換群 SI1_ˆ´´´Îm. .

Problem (Aoki & Takemura 2008, J. Symbolic Comput.)

. . . .. . . . 部分空間Lを不変に保つような部分群G⊂ SI1ˆ´´´ˆImを決定せよ．マルコフ基底を調べる上でも重要．本講演では，階層モデルに対する結果を示す．

詳細は→Sei, T., Aoki, S. and Takemura, A. (2009). Perturbation method for determining the group of invariance of hierarchical models, Advances in Applied Mathematics, 43 (4), 375–389.

(5)

マルコフ基底

対数線形モデルのマルコフ基底について簡単に復習する．セル集合 I =∏m_j=1Ij, Ij = {1, . . . , Ij}. (pi)i2I：I上の確率分布．対数線形モデルpi = ∏K k=1q Ak(i) k (⇔ (log pi)∈ span(Ak)) ファイバーF(t) = {x | ∑_iAk(i)xi = tk} を連結にするのがマルコフ基底． Remark: 対数線形モデルは多項式環の準同型と見なせる： K[p] 3 ∏ i pxi i 7→ ∏ k ( q P iAk(i)xi k ) ∈ K[q]. この準同型の核（トーリックイデアル）がマルコフ基底に対応する．グレブナー基底計算に帰着(Diaconis & Strumfels 1998).

(7)

マルコフ基底（例）

2元分割表の独立モデルのマルコフ基底を確認しておく．ファイバー=十分統計量が与えられた下での可能な分割表の集合独立モデルの十分統計量はxi+とx+jだったので， F({ri}, {cj}) = {{xij} | xi+ = ri, x+j= cj}. move: 十分統計量が等しい2つの分割表の差． F({ri}, {cj})は，次のmove だけで動き回ることができる： M(i, i0, j, j0) = j j0 i +1 −1 i0 −1 +1 つまり，集合{M(i, i0, j, j0)} がマルコフ基底（の1つ）．行・列の入れ替えを考えると，本質的にはM(1, 2, 1, 2)のみ．

(8)

階層モデルのマルコフ基底

階層モデルは対数線形モデルの特殊ケース（後で定義）．例：条件付独立モデル {{1, 2}, {2, 3}} log pijk = αij+ βjk マルコフ基底M = (zijk)は，あるj0について (zijk)j=j0 = → k ↓ i 1 −1 −1 1 , （その他のセルは零）というものだけ考えればOK. 分解可能モデルなら同様に求まる(Dobra 2003他)．

分解可能でないモデルはとても難しい(Aoki & Takemura 2003 他)

(9)

階層モデルのマルコフ基底

例：無3因子交互作用モデルlog pijk = αij + βjk+ γik.

Table: 3× 3 × K 分割表に対する一意最小マルコフ基底と簡約グレブナー

基底の個数 (Aoki & Takemura 2003)

K 3 4 5 6 7 # unique minimal MB 81 450 2670 10665 31815 # reduced GB 110 622 3240 12085 34790 # orbits in the MB 4 5 6 6 6 → 水準を並べ替えても異なるマルコフ基底は6個だけ．記憶領域の軽減．

(10)

不変群 (setwise stabilizer)

不変群

セル集合 I =∏m_j=1Ij, Ij = {1, . . . , Ij}. 対数線形モデル(log pi)i2I ∈ L. セルの置換全体を S_I と書く．S_I ={g : I → I | one to one}. g ∈ S_I は自然にRI へ作用する： (gx)i = xg`1₍_i). 左からの作用である：g(hx) = (gh)x. 線形部分空間 Lにも g は作用する： gL := {gx | x ∈ L}. Lの不変群(setwise stabilizer) GL := {g ∈ S_I | gL = L}. 清智也 (情報理工) 計算代数統計学の展開 2009/11/27 10 / 31

(11)

不変群

不変群 GL ={g ∈ S_I | gL = L} は，Lの構造を不変に保つ．マルコフ基底の記憶領域軽減に有用．

.

Problem (Aoki & Takemura 2008再掲)

. . . .. . . . いろいろなモデル Lに対し，GLを決定せよ． Remark GL = GL?．ここでL? ={x | ∑ ixiyi = 0, y ∈ L}（双対空間）．対数線形モデルの場合 L? = ker A． モデル Lのmove（特にマルコフ基底）は ker A の元であるから， GL は不変なマルコフ基底を定める．

(12)

既存の結果

完全独立モデルの場合（F = {{1}, . . . , {m}}），不変群は直積群と因子の入れ替えから生成される(Aoki & Takemura, JSC2008)：

GL = ( S_I1 × · · · × SIm, (τjj0)Ij=I0_j ) ただしτjj0 : (· · · , i_j,· · · , i_j0,· · · ) 7→ (· · · , i_j0,· · · , i_j,· · · )は因子の入れ替えである．また同論文では， .

.

. 1 _{無 3 因子交互作用モデル（}F = {{1, 2}, {1, 3}, {2, 3}}） .

.

. 2 _{Hardy-Weinberg}_{モデル（ /}∈ 階層モデル） についても不変群を求めている．清智也 (情報理工) 計算代数統計学の展開 2009/11/27 12 / 31

(13)

例

2元独立モデル log pij = αi+ βj. |I1| 6= |I2|の場合，不変群はGr(∆) = SI1× SI2,つまり行置換，列置換の直積となる．行置換：

(14)

階層モデル

階層モデルの定義

例えば Lauritzen (1996). m: 分割表の因子数．m元分割表． Ij ={1, . . . , Ij}: 第j因子の水準集合 (j = 1, . . . , m)． I =∏m j=1Ij: セルの集合． ∆: [m] = {1, . . . , m}の単体的複体．交互作用全体． F := red(∆): ∆のファセット．生成集合． ——————————————————— 例えば，m = 3, ∆ ={∅, {1}, {2}, {3}, {1, 2}, {2, 3}}のとき， F = {{1, 2}, {2, 3}}. 1 2 3 清智也 (情報理工) 計算代数統計学の展開 2009/11/27 14 / 31

(15)

階層モデル

階層モデルの定義

. Deﬁnition . . . .. . . . 生成集合 F で指定される階層モデルとは，次の対数線形モデルである： (log pi)∈ LF := ∑ D_2F LD, LD :={iDのみに依存するベクトル} .

例えばm = 3, F = {{1, 2}, {2, 3}}のとき log pijk= αij+ βjk.

1

2

3

(16)

主定理と例

定理のための準備

1 ：

wreath product

不変群 G_F の具体系を主定理として述べる．まず準備をする. (S_I₁)I2 ₌{g : I 2→ SI1} =「I2に応じてI1を置換」代数学では(S_I₁)I2 × S I2をwreath product（環積）と呼ぶ．より一般に，半順序集合Pに対して，∏__2P(S_I) A() _を

generalized wreath productという．ただしA(ρ)はρの先祖集合．例：P = {1, 2, 3}, 1 < 2, 3 < 2のとき，(S_I1)I2× SI2× (SI3)I2. 条件付き独立モデルlog pi1i2i3 = αi1i2+ βi2i3 を不変に保つ．

(17)

主定理と例

準備

2 ：

pseudofactor poset

生成集合族F に付随した半順序集合Pを定義する.

1

2

3

4

5

6

{1} {2} {5,6} {3} {4} 同値関係 i∼ jdef⇔ (∀D ∈ F (i ∈ D ⇔ j ∈ D)). P := [m]/ ∼．擬因子, pseudofactor． ρ, ρ0 ∈ P に対してρ≤ ρ0 def⇔ (∀D ∈ F (ρ ⊂ D ⇒ ρ0 ⊂ D)).

(18)

主定理と例

準備

2 ：

pseudofactor poset

Remark.

.

1 pseudofactor poset P はintersection poset Q より情報が粗い：

F P Q 1 2 3 {1} {2} {3} {1,2} {1,3} {2,3} 1 2 3 φ 一般には単射準同型P → Q が存在する． .

.

2 _{pseudofactor poset} _{にならない}_poset_{が存在する：}

. Problem (数学的興味) . . . .. . . .

posetが pseudofactor posetとなるための条件は？

(19)

主定理と例

主定理

すぐ例を出します． . Theorem (主定理) . . . .. . . . F を生成集合の族とするとき，下記正則条件の下で，不変群G_F はリース積で表わされる. G_F = ∏ _2P (S_I)IA().

ρ はpseudofactor poset, A(ρ)はρの先祖集合．

正則条件１：ID := ∏_j_2DIj (D∈ F) は互いに異なる. 正則条件２：高々一つのjを除いてIj ≥ 3.

(20)

主定理と例

例

1

m = 3, F = {{1, 2}, {2, 3}}. （条件付き独立モデル） 1 2 3 {1} {2} {3} 主定理より，不変群は G_F = (S_I₁)I2 × S I2× (SI3)I 2_. 清智也 (情報理工) 計算代数統計学の展開 2009/11/27 20 / 31

(21)

主定理と例

例

2

同一視できるマルコフ基底が増える例. m = 5, F = {{1, 3}, {2, 4}, {3, 4, 5}}とする．

1

2

3

4

5

{1} {2} {5} {3} {4} これは分解可能モデル．不変群は G_F = (S_I₁)I3× (S I2)I 4 × S I3× SI4× (SI5)If3;4g

(22)

主定理と例

例

2 (

つづき

)

m = 5, F = {{1, 3}, {2, 4}, {3, 4, 5}}. G_F = (S_I1)If3g× (SI2)If4g× SI3 × SI4 × (SI5)I3;4. 次の2つのmoveはマルコフ基底に必ず含まれる (indispensable) M1 = (11111)(12211)− (12111)(11211), M2 = (11112)(12211)− (12112)(11211). M1とM2は，直積群の下では同一視できないが,不変群の下では同一視できる．「(i3i4) = (11)のときに限りi5 = 1, 2を置換する」 M1 = (11111)(12211)− (12111)(11211), M2 = (11112)(12211)− (12112)(11211). 清智也 (情報理工) 計算代数統計学の展開 2009/11/27 22 / 31

(23)

主定理と例

例

3

主定理は,グラフィカルでなくても成り立つ. m = 6, F = {{1, 4, 5}, {2, 5, 6}, {3, 4, 6}}. ({4, 5, 6} /∈ F). 1 2 3 4 5 6 {1} {2} {3} {4} {5} {6} G_F = (S_I₁)If4;5g × (S I2)If5;6g × (SI3)If4;6g × SI4 × SI5 × SI6

(24)

数独分割表

数独は9× 9分割表上のパズル．各行，各列，各3× 3ブロックは1∼ 9の数字を唯一持つ． 1 2 3 4 5 6 7 8 9 4 5 6 7 8 9 1 2 3 7 8 9 1 2 3 4 5 6 2 3 1 5 6 4 8 9 7 5 6 4 8 9 7 2 3 1 8 9 7 2 3 1 5 6 4 3 1 2 6 4 5 9 7 8 6 4 5 9 7 8 3 1 2 9 7 8 3 1 2 6 4 5

数独不変群(Russell & Jarvis 2006)

大きい 3 行の並べ替え. 小さい 3 行の並べ替え. 大きい 3 列の並べ替え. 小さい 3 列の並べ替え. 転置.

(25)

数独分割表

数独の解は34× 9分割表(xijklc)で定義できる (Lawrence lifting). 「ファイバー」xij++c = xi+k+c= x++klc= xijkl+ = 1.

階層モデルに対応. F = {{1, 2, 5}, {1, 3, 5}, {3, 4, 5}, {1, 2, 3, 4}}. 1 2 3 4 5 主定理の正則条件は満たさないが,不変群の部分集合は求まる： S_I₁× (S_I₂)I1 × S I3× (SI4)I 3 × S I5. 転置以外の並べ替えは自動的に求まった.

(26)

数独分割表

証明の概略

. Theorem (再掲) . . . .. . . . 正則条件の下で，G_F =∏__2P(S_I_)IA()_. _{（包含関係}⊃_{は常に成立．}_）証明の道筋 .

.

. 1 一般に次の等式が成り立つ(Bailey et al. 1983 からの帰結) ： ∩ D_2F G_fDg = ∏ 2P (S_I)IA() .

.

. 2 _{よって，G} F ⊂ ∩ D2FGfDgを示せば十分． .

.

. 3 _D0 _{= argmin} D2F|ID| とし，G_F ⊂ ∩ D2FnfD0gGfDg を示す． .

.

. 4 またG F ⊂ GfD0gを示す．帰納法により証明完了．ステップ3, 4 でperturbation methodを用いる．例で説明する．清智也 (情報理工) 計算代数統計学の展開 2009/11/27 26 / 31

(27)

数独分割表

証明の概略

(

簡単ケース

1/3)

例として，I1× I2分割表の独立モデルF = {{1}, {2}} の不変群が G_F = S_I₁ × S_I₂（直積群）で与えられることを証明してみる． I1 < I2とする．（例えばI1= 2, I2= 4） 次の分割表を考える（perturbation） x = 1 0 0 0 1 0 0 0 このとき，任意のg∈ G_F に対して gx = 1 0 0 0 1 0 0 0 , 0 1 0 0 0 1 0 0 , · · · , 0 0 0 1 0 0 0 1 のいずれかであることが示せる．これを確認してみよう．

(28)

数独分割表

証明の概略

(

簡単ケース

2/3)

分割表gxの中の「1」が縦に並んでいることを示す．もし，1が縦に並んでいなければ，一般性を失わずに gx = 1 ∗ ∗ ∗ 0 ∗ ∗ ∗ . (1) 一方，gx ∈ L = {(αi+ βj)}だから gx = α1+ β1 α1+ β2 α1+ β3 α1+ β4 α2+ β1 α2+ β2 α2+ β3 α2+ β4 1行目と2行目の差を取ると (gx)1_·− (gx)2_· = α1− α2 α1− α2 α1− α2 α1− α2 (2) (1), (2)よりgxの1行目が全部1となり，矛盾．清智也 (情報理工) 計算代数統計学の展開 2009/11/27 28 / 31

(29)

数独分割表

証明の概略

(

簡単ケース

3/3)

ここまでで示したこと：g ∈ G_F ならば g : 1 0 0 0 1 0 0 0 7→ 1 0 0 0 1 0 0 0 ,· · · , 0 0 0 1 0 0 0 1 これは g∈ G_f2g を意味する．あとは g∈ G_f1g が言えればよい． gは，部分空間N := L_F ∩ L>_f2g を不変に保つ．特に g _{−1 −1 −1 −1}1 1 1 1 ∈ N である（perturbation）．これはg ∈ G_f1gを意味する．（証明終）

(30)

まとめ

まとめと課題

まとめ階層モデルの不変群を,正則条件のもとで決定した. 今後の課題は定理の条件を緩めること．

階層モデル以外の場合．e.g. structural zero, HSM,... pseudofactor poset の特徴づけ．

ありがとうございました.

(31)

まとめ

Bibliography

S. Aoki & A. Takemura (2003). Minimal basis for a connected Markov chain over 3_{ˆ 3 ˆ K contingency tables with ﬁxed two-dimensional marginals. Aust. N. Z. J.} Stardust., 45 (2), 229–249.

S. Aoki & A. Takemura (2008). The largest group of invariance for Markov bases and toric ideals. J. Symbolic Com-put., 43 (5), 342–358.

R. A. Bailey, C. E. Praeger, C. A. Rowley & T. P. Speed (1983). Generalized wreath products of permutation groups. Proc. London Math. Soc., 47 (3), 69–82. D. A. Cox. (2007). Gr¨obner basis tutorial. Part II. A sampler from recent

developments. (available from Cox’s homepage).

A. Dobra (2003). Markov bases for decomposable graphical models, Bernoulli, 9 (6), 1093–1108.

R. Fontana & M.-P. Rogantin (2008). Indicator function and sudoku designs, in press.

E. Russel & F. Jarvis (2006), Mathematics of Sudoku II, Preprint.

T. Sei, S. Aoki & A. Takemura (2008). Perturbation method for determining the group of invariance of hierarchical models, Advances in Applied Mathematics, 43 (4), 375–389. (arXiv:0808.2725v2)

Perturbation method for determining the group of invariance of hierarchical models

Perturbation method for determining the group of

invariance of hierarchical models

概要

概要

概要

目次

マルコフ基底

マルコフ基底（例）

階層モデルのマルコフ基底

階層モデルのマルコフ基底

不変群

不変群

既存の結果

.

.

例

階層モデルの定義

階層モデルの定義

定理のための準備

1

：

wreath product

準備

2

：

pseudofactor poset

1

2

3

4

5

6

準備

2

：

pseudofactor poset

.

.

主定理

例

1

例

2

1

2

3

4

5

例

2 (

つづき

)

例

3

数独分割表

数独分割表

証明の概略

.

.

.

.

証明の概略

(

簡単ケース

1/3)

証明の概略

(

簡単ケース

2/3)

証明の概略

(

簡単ケース

3/3)

まとめと課題

Bibliography