2013 年度統計関連学会連合大会チュート リアルセミナー
統計的グラフィカルモデルの展開
∼ その他の話題 ∼
原 尚幸
.
.
新潟大学・経済学部
2013 年 9 月 8 日
原尚幸 (新潟大・経済)
統計的グラフィカルモデル
2013 年 9 月 8 日
1 / 43
2 元分割表
3 × 3 の 2 元分割表
50 人のクラスの統計と解析の期末試験の成績
統計 \ 解析
優
良
可
列和
原尚幸 (新潟大・経済)
優
7
10
2
14
良
5
5
6
21
統計的グラフィカルモデル
可
1
6
8
15
行和
13
21
16
50
2013 年 9 月 8 日
2 / 43
2 元分割表
I1 × I2 の 2 元分割表 x = {xi1 i2 }
要因 1 \ 要因 2
1
..
.
I1
列和
1
x11
···
···
I2
x1I2
xI1 1
x+1
···
···
···
xI1 I2
x+I2
行和
x1+
..
.
xI1 +
x++
xi1 + : 行和, x+i2 : 列和, x++ : 総頻度
pi1 i2 : セル確率
原尚幸 (新潟大・経済)
統計的グラフィカルモデル
2013 年 9 月 8 日
2 / 43
χ2 適合度検定
通常の関心：2 変数の独立性
統計と解析の成績は独立か？
H0 : pi1 i2 = pi1 + · p+i2
セル確率 pi1 i2 が周辺確率 pi1 + , p+i2 の積で表される
このモデルが 2 元完全独立モデルである
pi1 i2 = pi1 + · p+i2
⇔ log pi1 i2 = log pi1 + + log p+i2
1
原尚幸 (新潟大・経済)
2
統計的グラフィカルモデル
2013 年 9 月 8 日
3 / 43
χ2 適合度検定
pi1 + , p+i2 の MLE は
pˆi1 + =
xi1 +
,
x++
pˆ+i2 =
x+i2
x++
pi1 i2 = pi1 + p+i2 の MLE pˆi1 i2 は
pˆi1 i2 =
xi1 + x+i2
x2++
期待頻度 ei1 i2
ei1 i2 = x++ · pˆi1 i2 =
原尚幸 (新潟大・経済)
統計的グラフィカルモデル
xi1 + x+i2
x++
2013 年 9 月 8 日
4 / 43
χ2 適合度検定
H0 : pi1 i2 = pi1 + · p+i2 の検定
Pearson の χ2 統計量
χ2 =
∑ (xi i − ei i )2
1 2
1 2
,
ei1 i2
ei1 i2 :=
i1 ,i2
xi1 + x+i2
x++
漸近的に自由度 (I1 − 1)(I2 − 1) の χ2 分布に従う
⇒ これに基づいて検定
現実の問題ではこの近似を正当化するほどの標本数が
得られないことも多い
標本数が少ないときは漸近近似の精度が落ちる
原尚幸 (新潟大・経済)
統計的グラフィカルモデル
2013 年 9 月 8 日
5 / 43
分割表の条件付分布
十分統計量
b = {x1+ , . . . , xI1 + , x+1 , . . . , x+I2 }
b を与えたときの分割表 x の条件付き分布は ,
以下の超幾何分布で明示的に与えられる
)
∏(
x+i2
x1i2 · · · xI1 i2
i
)
Pr(x | b) = 2(
x++
x+1 · · · x+I2
原尚幸 (新潟大・経済)
統計的グラフィカルモデル
2013 年 9 月 8 日
6 / 43
条件付正確検定
Pearson の χ2 統計量は分割表 x の関数 χ2 (x)
x の正確分布 Pr(x | b) がわかれば , χ2 (x) の正確分布に
基づく評価も可能
∑
P (χ20 | b) =
P (x | b)
x:χ2 (x)=χ20
このような χ2 (x) の条件付正確分布に基づく検定を
Fisher の正確検定と言う
標本数に依存しないので , 特に標本数が小さい場合に有用
十分統計量の条件付検定は , 未知パラメータによらないので
ロバスト (相似検定)
原尚幸 (新潟大・経済)
統計的グラフィカルモデル
2013 年 9 月 8 日
7 / 43
正確検定の実装
ファイバー Fb
十分統計量 b を共有する分割表の集合
ファイバーのすべての要素の数え上げができれば ,
検定統計量の正確分布による評価が可能
P (x) が分かれば P (χ2 (x)) も得られる
→ χ2 の正確分布が得られる
ファイバーの要素数は一般には非常に大きいため,
列挙による検定統計量の評価は困難
✓⇓
ファイバー内の状態遷移を用いて, MCMC 法により
分割表をサンプリングし , それに用いて検定統計量を
評価する
✒
原尚幸 (新潟大・経済)
統計的グラフィカルモデル
✏
✑
2013 年 9 月 8 日
8 / 43
分割表の move
2 元分割表を 1 次元ベクト ルと考える
1 I2
x := (x11 , . . . , xI1 I2 )t ∈ ZI≥0
十分統計量 b：周辺和 (行和・列和) の集合
配置 A : 分割表 x から十分統計量 b への線形写像
Ax = b
原尚幸 (新潟大・経済)
統計的グラフィカルモデル
2013 年 9 月 8 日
9 / 43
分割表の move
move z
行和・列和がすべて 0 の整数配列 ⇔ A の整数核
Az = 0
move の例
1
-1
0
0
-1
1
0
0
0
0
0
0
0
0
0
0
分割表に move を足し 引きしても行和・列和の値は変わらない
ファイバーの要素間は move の足し 引きで移動できる
⇒ ファイバー内の状態遷移
5
4
1
10
3
2
5
10
2
4
4
10
原尚幸 (新潟大・経済)
10
10
10
30
+
1
-1
0
0
-1
1
0
0
0
0
0
0
0
0
0
0
=
統計的グラフィカルモデル
6
3
1
10
2
3
5
10
2
4
4
10
10
10
10
30
2013 年 9 月 8 日
10 / 43
Markov 基底
Markov 基底 M
.
要素数が 2 以上のすべてのファイバーの要素を連結に結ぶ move
の集合
マルコフ基底の move の足し 引きによって
ファイバー内をくまなく行き来できる
.
x, y : 同一ファイバーに属する任意の 2 表
move の足し 引きで x から y に辿り着ける
∃z1 , . . . , zK ∈ M s.t.
y =x+
K
∑
k=1
原尚幸 (新潟大・経済)
zk ,
x+
K
∑
zk ≥ 0, K ≤ K.
k=1
統計的グラフィカルモデル
2013 年 9 月 8 日
11 / 43
Markov 基底
Markov 基底 M
.
要素数が 2 以上のすべてのファイバーの要素を連結に結ぶ move
の集合
マルコフ基底の move の足し 引きによって
ファイバー内をくまなく行き来できる
.
x, y : 同一ファイバーに属する任意の 2 表
move の足し 引きで x から y に辿り着ける
∃z1 , . . . , zK ∈ M s.t.
y =x+
K
∑
k=1
原尚幸 (新潟大・経済)
zk ,
x+
K
∑
zk ≥ 0, K ≤ K.
k=1
統計的グラフィカルモデル
2013 年 9 月 8 日
11 / 43
Markov 基底
Markov 基底 M
.
要素数が 2 以上のすべてのファイバーの要素を連結に結ぶ move
の集合
.
マルコフ基底の move の足し 引きによって
ファイバー内をくまなく行き来できる
x
x, y : 同一ファイバーに属する任意の 2 表
y
move の足し 引きで x から y に辿り着ける
∃z1 , . . . , zK ∈ M s.t.
y =x+
K
∑
k=1
原尚幸 (新潟大・経済)
zk ,
x+
K
∑
zk ≥ 0, K ≤ K.
k=1
統計的グラフィカルモデル
2013 年 9 月 8 日
11 / 43
Markov 基底
Markov 基底 M
.
要素数が 2 以上のすべてのファイバーの要素を連結に結ぶ move
の集合
.
マルコフ基底の move の足し 引きによって
ファイバー内をくまなく行き来できる
x
x, y : 同一ファイバーに属する任意の 2 表
y
move の足し 引きで x から y に辿り着ける
∃z1 , . . . , zK ∈ M s.t.
y =x+
K
∑
k=1
原尚幸 (新潟大・経済)
zk ,
x+
K
∑
zk ≥ 0, K ≤ K.
k=1
統計的グラフィカルモデル
2013 年 9 月 8 日
11 / 43
Markov 基底
命題
i2 i2
i1
1 −1
i1 −1
1
というタイプの move の集合は 2 元完全独立モデルのマルコフ基底を
なす
.
原尚幸 (新潟大・経済)
統計的グラフィカルモデル
2013 年 9 月 8 日
12 / 43
正確検定の実装
[超幾何分布を定常分布に持つ分割表の発生]
Step 0. x(0) : データセット , Pr(x | b) : 超幾何分布
M : マルコフ基底, t ← 0
Step 1. z ∈ M をランダムに抽出
Step 2. if x(t) + z ≥ 0
x(t+1)
x(t+1)
)
Pr(x + z | b)
,1
←
+ z with prob min
( Pr(x | b)
)
Pr(x + z | b)
(t)
←x
with prob 1 − min
,1
Pr(x | b)
(
x(t)
else
x(t+1) ← x(t)
Step 1 に戻る
原尚幸 (新潟大・経済)
統計的グラフィカルモデル
2013 年 9 月 8 日
13 / 43
正確検定の実装
x(t) , t → ∞ の定常分布は超幾何分布
t が十分大きいところサンプリングした x(t) から計算した
χ2 (x(t) ) の標本分布は , χ2 (x(t) ) の正確分布の近似となる
この標本分布で Pearson χ2 統計量 χ2 (x) を評価すれば ,
χ2 (x) の正確分布に基づく検定の近似とみなせる
原尚幸 (新潟大・経済)
統計的グラフィカルモデル
2013 年 9 月 8 日
14 / 43
階層モデルの適合度検定
これまでは 2 元完全独立モデルの条件付正確検定を議論してきた
一般の階層モデルでも同じような議論に基づき条件付正確検定を
構成することができる
分解可能モデルのマルコフ基底の構造は完全に解明されている
(Dobra (2003), Hara et al.(2010))
マルコフ基底を求める代数的アルゴリズムが知られている
4ti2 などのソフト ウエアで実装されている
表が大きくなると実時間内での計算が困難
可約のモデルの場合は , 以下に述べるような局所計算アルゴリズムが
知られている
原尚幸 (新潟大・経済)
統計的グラフィカルモデル
2013 年 9 月 8 日
15 / 43
マルコフ基底の局所計算
Dobra and Sullivant (2004)
グラフィカルモデルの場合, 極大な既約部分グラフに対応する周辺モ
デルのマルコフ基底から , 全体のモデルのマルコフ基底が計算可能
既約グラフに対するグラフィカルモデルのマルコフ基底が与えられ
れば , すべてのグラフィカルモデルのマルコフ基底が計算可能
原尚幸 (新潟大・経済)
統計的グラフィカルモデル
2013 年 9 月 8 日
16 / 43
マルコフ基底の局所計算
Dobra and Sullivant (2004)
グラフィカルモデルの場合, 極大な既約部分グラフに対応する周辺モ
デルのマルコフ基底から , 全体のモデルのマルコフ基底が計算可能
既約グラフに対するグラフィカルモデルのマルコフ基底が与えられ
れば , すべてのグラフィカルモデルのマルコフ基底が計算可能
原尚幸 (新潟大・経済)
統計的グラフィカルモデル
2013 年 9 月 8 日
16 / 43
マルコフ基底の局所計算
Dobra and Sullivant (2004)
グラフィカルモデルの場合, 極大な既約部分グラフに対応する周辺モ
デルのマルコフ基底から , 全体のモデルのマルコフ基底が計算可能
既約グラフに対するグラフィカルモデルのマルコフ基底が与えられ
れば , すべてのグラフィカルモデルのマルコフ基底が計算可能
原尚幸 (新潟大・経済)
統計的グラフィカルモデル
2013 年 9 月 8 日
16 / 43
マルコフ基底の局所計算
Dobra and Sullivant (2004)
グラフィカルモデルの場合, 極大な既約部分グラフに対応する周辺モ
デルのマルコフ基底から , 全体のモデルのマルコフ基底が計算可能
既約グラフに対するグラフィカルモデルのマルコフ基底が与えられ
れば , すべてのグラフィカルモデルのマルコフ基底が計算可能
原尚幸 (新潟大・経済)
統計的グラフィカルモデル
2013 年 9 月 8 日
16 / 43
マルコフ基底の局所計算
Dobra and Sullivant (2004)
グラフィカルモデルの場合, 極大な既約部分グラフに対応する周辺モ
デルのマルコフ基底から , 全体のモデルのマルコフ基底が計算可能
既約グラフに対するグラフィカルモデルのマルコフ基底が与えられ
れば , すべてのグラフィカルモデルのマルコフ基底が計算可能
原尚幸 (新潟大・経済)
統計的グラフィカルモデル
2013 年 9 月 8 日
16 / 43
マルコフ基底の局所計算
Dobra and Sullivant (2004)
グラフィカルモデルの場合, 極大な既約部分グラフに対応する周辺モ
デルのマルコフ基底から , 全体のモデルのマルコフ基底が計算可能
既約グラフに対するグラフィカルモデルのマルコフ基底が与えられ
れば , すべてのグラフィカルモデルのマルコフ基底が計算可能
原尚幸 (新潟大・経済)
統計的グラフィカルモデル
2013 年 9 月 8 日
16 / 43
マルコフ基底の局所計算
Dobra and Sullivant (2004)
グラフィカルモデルの場合, 極大な既約部分グラフに対応する周辺モ
デルのマルコフ基底から , 全体のモデルのマルコフ基底が計算可能
既約グラフに対するグラフィカルモデルのマルコフ基底が与えられ
れば , すべてのグラフィカルモデルのマルコフ基底が計算可能
原尚幸 (新潟大・経済)
統計的グラフィカルモデル
2013 年 9 月 8 日
16 / 43
マルコフ基底の局所計算
Dobra and Sullivant (2004)
グラフィカルモデルの場合, 極大な既約部分グラフに対応する周辺モ
デルのマルコフ基底から , 全体のモデルのマルコフ基底が計算可能
既約グラフに対するグラフィカルモデルのマルコフ基底が与えられ
れば , すべてのグラフィカルモデルのマルコフ基底が計算可能
原尚幸 (新潟大・経済)
統計的グラフィカルモデル
2013 年 9 月 8 日
16 / 43
マルコフ基底の局所計算
Dobra and Sullivant (2004)
グラフィカルモデルの場合, 極大な既約部分グラフに対応する周辺モ
デルのマルコフ基底から , 全体のモデルのマルコフ基底が計算可能
既約グラフに対するグラフィカルモデルのマルコフ基底が与えられ
れば , すべてのグラフィカルモデルのマルコフ基底が計算可能
原尚幸 (新潟大・経済)
統計的グラフィカルモデル
2013 年 9 月 8 日
16 / 43
マルコフ基底の局所計算
Dobra and Sullivant (2004)
グラフィカルモデルの場合, 極大な既約部分グラフに対応する周辺モ
デルのマルコフ基底から , 全体のモデルのマルコフ基底が計算可能
既約グラフに対するグラフィカルモデルのマルコフ基底が与えられ
れば , すべてのグラフィカルモデルのマルコフ基底が計算可能
原尚幸 (新潟大・経済)
統計的グラフィカルモデル
2013 年 9 月 8 日
16 / 43
Dobra-Sullivant の主張
可約モデルのマルコフ基底は極大既約分解後の部分モデルの
マルコフ基底から再帰的に計算が可能
1
3
5
2
4
6
M1 : L({1, 2, 3, 4}) のマルコフ基底
M2 : L({3, 4, 5, 6}) のマルコフ基底
L のマルコフ基底は M1 , M2 から move の拡大を用いて計算が可能
可約な階層モデルのマルコフ基底の計算には極大既約成分のマルコ
フ基底が与えられれば十分
原尚幸 (新潟大・経済)
統計的グラフィカルモデル
2013 年 9 月 8 日
17 / 43
Dobra-Sullivant の主張
可約モデルのマルコフ基底は極大既約分解後の部分モデルの
マルコフ基底から再帰的に計算が可能
1
3
5
2
4
6
M1 : L({1, 2, 3, 4}) のマルコフ基底
M2 : L({3, 4, 5, 6}) のマルコフ基底
L のマルコフ基底は M1 , M2 から move の拡大を用いて計算が可能
可約な階層モデルのマルコフ基底の計算には極大既約成分のマルコ
フ基底が与えられれば十分
原尚幸 (新潟大・経済)
統計的グラフィカルモデル
2013 年 9 月 8 日
17 / 43
Dobra-Sullivant の主張
可約モデルのマルコフ基底は極大既約分解後の部分モデルの
マルコフ基底から再帰的に計算が可能
1
3
5
2
4
6
M1 : L({1, 2, 3, 4}) のマルコフ基底
M2 : L({3, 4, 5, 6}) のマルコフ基底
L のマルコフ基底は M1 , M2 から move の拡大を用いて計算が可能
可約な階層モデルのマルコフ基底の計算には極大既約成分のマルコ
フ基底が与えられれば十分
原尚幸 (新潟大・経済)
統計的グラフィカルモデル
2013 年 9 月 8 日
17 / 43
Dobra-Sullivant の主張
可約モデルのマルコフ基底は極大既約分解後の部分モデルの
マルコフ基底から再帰的に計算が可能
1
3
5
2
4
6
1
3
3
5
2
4
4
6
M1 : L({1, 2, 3, 4}) のマルコフ基底
M2 : L({3, 4, 5, 6}) のマルコフ基底
L のマルコフ基底は M1 , M2 から move の拡大を用いて計算が可能
可約な階層モデルのマルコフ基底の計算には極大既約成分のマルコ
フ基底が与えられれば十分
原尚幸 (新潟大・経済)
統計的グラフィカルモデル
2013 年 9 月 8 日
17 / 43
Dobra-Sullivant の主張
可約モデルのマルコフ基底は極大既約分解後の部分モデルの
マルコフ基底から再帰的に計算が可能
M
1
1
3
5
2
4
6
3
3
5
M1
M2
2
4
4
6
M1 : L({1, 2, 3, 4}) のマルコフ基底
M2 : L({3, 4, 5, 6}) のマルコフ基底
L のマルコフ基底は M1 , M2 から move の拡大を用いて計算が可能
可約な階層モデルのマルコフ基底の計算には極大既約成分のマルコ
フ基底が与えられれば十分
原尚幸 (新潟大・経済)
統計的グラフィカルモデル
2013 年 9 月 8 日
17 / 43
有向グラフ
有向グラフ
頂点集合 V = { v1 , v2 , . . .} と有向辺の集合
E = { (vi , vj ), (vk , vl ), . . .} の組
G = (V, E)
を無向グラフという.
.
(vi , vj ) と (vj , vi ) を区別する
vi → vj = vi ← vj
.
原尚幸 (新潟大・経済)
統計的グラフィカルモデル
2013 年 9 月 8 日
18 / 43
非巡回有向グラフ (DAG)
非巡回有向グラフ (DAG)
有向巡回閉路が存在しない有向グラフを非巡回有向グラフ (DAG) と
いう.
.
.
DAG が定義するマルコフ性を定義したい .
原尚幸 (新潟大・経済)
統計的グラフィカルモデル
2013 年 9 月 8 日
19 / 43
非巡回有向グラフ (DAG)
非巡回有向グラフ (DAG)
有向巡回閉路が存在しない有向グラフを非巡回有向グラフ (DAG) と
いう.
.
.
DAG が定義するマルコフ性を定義したい .
原尚幸 (新潟大・経済)
統計的グラフィカルモデル
2013 年 9 月 8 日
19 / 43
非巡回有向グラフ (DAG)
非巡回有向グラフ (DAG)
有向巡回閉路が存在しない有向グラフを非巡回有向グラフ (DAG) と
いう.
.
.
DAG が定義するマルコフ性を定義したい .
原尚幸 (新潟大・経済)
統計的グラフィカルモデル
2013 年 9 月 8 日
19 / 43
非巡回有向グラフ (DAG)
α→β
α は β の親
β は α の子
pa(β) : β の親の集合
γ から β に有向パスがあ
るとき
δ
γ は β の先祖
β は γ の子孫
β から δ に有向パスがな
いとき
γ
α
β
δ は β の非子孫
nd(β) : β の非子孫の集合
原尚幸 (新潟大・経済)
統計的グラフィカルモデル
2013 年 9 月 8 日
20 / 43
非巡回有向グラフ (DAG)
α→β
α は β の親
β は α の子
pa(β) : β の親の集合
γ から β に有向パスがあ
るとき
δ
γ は β の先祖
β は γ の子孫
β から δ に有向パスがな
いとき
γ
α
β
δ は β の非子孫
nd(β) : β の非子孫の集合
原尚幸 (新潟大・経済)
統計的グラフィカルモデル
2013 年 9 月 8 日
20 / 43
非巡回有向グラフ (DAG)
α→β
α は β の親
β は α の子
pa(β) : β の親の集合
γ から β に有向パスがあ
るとき
δ
γ は β の先祖
β は γ の子孫
β から δ に有向パスがな
いとき
γ
α
β
δ は β の非子孫
nd(β) : β の非子孫の集合
原尚幸 (新潟大・経済)
統計的グラフィカルモデル
2013 年 9 月 8 日
20 / 43
非巡回有向グラフ (DAG)
α→β
α は β の親
β は α の子
pa(β) : β の親の集合
γ から β に有向パスがあ
るとき
δ
γ は β の先祖
β は γ の子孫
β から δ に有向パスがな
いとき
γ
α
β
δ は β の非子孫
nd(β) : β の非子孫の集合
原尚幸 (新潟大・経済)
統計的グラフィカルモデル
2013 年 9 月 8 日
20 / 43
非巡回有向グラフ (DAG)
α→β
α は β の親
β は α の子
pa(β) : β の親の集合
γ から β に有向パスがあ
るとき
δ
γ は β の先祖
β は γ の子孫
β から δ に有向パスがな
いとき
γ
α
β
δ は β の非子孫
nd(β) : β の非子孫の集合
原尚幸 (新潟大・経済)
統計的グラフィカルモデル
2013 年 9 月 8 日
20 / 43
非巡回有向グラフ (DAG)
α→β
α は β の親
β は α の子
pa(β) : β の親の集合
γ から β に有向パスがあ
るとき
δ
γ は β の先祖
β は γ の子孫
β から δ に有向パスがな
いとき
γ
α
β
δ は β の非子孫
nd(β) : β の非子孫の集合
原尚幸 (新潟大・経済)
統計的グラフィカルモデル
2013 年 9 月 8 日
20 / 43
Block recursive Markov property
Block recursive Markov property
Xβ ⊥⊥ Xnd(β)\pa(β) | Xpa(β) for all β ∈ V
であるとき, XV は G 上の Block recursive Markov property を持つと
.
いう.
δ
.
γ
原尚幸 (新潟大・経済)
α
統計的グラフィカルモデル
β
2013 年 9 月 8 日
21 / 43
モラルグラフ
モラルグラフ
DAG G = (V, E) に対し , 次をみたすグラフ G = (V, E ) を G のモラル
グラフという.
頂点集合は V
α → β ∈ E ⇒ (α, β) ∈ E
.
α → β ∈ E かつ γ → β ∈ E ⇒ (α, γ) ∈ E
δ
.
γ
原尚幸 (新潟大・経済)
α
統計的グラフィカルモデル
β
2013 年 9 月 8 日
22 / 43
モラルグラフ
モラルグラフ
DAG G = (V, E) に対し , 次をみたすグラフ G = (V, E ) を G のモラル
グラフという.
頂点集合は V
α → β ∈ E ⇒ (α, β) ∈ E
.
α → β ∈ E かつ γ → β ∈ E ⇒ (α, γ) ∈ E
δ
.
γ
原尚幸 (新潟大・経済)
α
統計的グラフィカルモデル
β
2013 年 9 月 8 日
22 / 43
モラルグラフ
モラルグラフ
DAG G = (V, E) に対し , 次をみたすグラフ G = (V, E ) を G のモラル
グラフという.
頂点集合は V
α → β ∈ E ⇒ (α, β) ∈ E
.
α → β ∈ E かつ γ → β ∈ E ⇒ (α, γ) ∈ E
δ
.
γ
原尚幸 (新潟大・経済)
α
統計的グラフィカルモデル
β
2013 年 9 月 8 日
22 / 43
Block recursive Markov property
定理 (e.g. Lauritzen(1996))
XV が G 上の Block recursive Markov property を持つとき,. XV はモラ
ルグラフ G 上の大域的マルコフ場である.
一般には曲指数型分布族
.
Xγ ⊥⊥ X
δ
γ
原尚幸 (新潟大・経済)
α
統計的グラフィカルモデル
β
2013 年 9 月 8 日
23 / 43
Block recursive Markov property
定理 (e.g. Lauritzen(1996))
XV が G 上の Block recursive Markov property を持つとき,. XV はモラ
ルグラフ G 上の大域的マルコフ場である.
一般には曲指数型分布族
.
Xγ ⊥⊥ X
δ
γ
原尚幸 (新潟大・経済)
α
統計的グラフィカルモデル
β
2013 年 9 月 8 日
23 / 43
Block recursive Markov property
定理 (e.g. Lauritzen(1996))
XV が G 上の Block recursive Markov property を持つとき,. XV はモラ
ルグラフ G 上の大域的マルコフ場である.
一般には曲指数型分布族
.
Xγ ⊥⊥ X
γ
原尚幸 (新潟大・経済)
ǫ
δ
α
β
統計的グラフィカルモデル
2013 年 9 月 8 日
23 / 43
Block recursive Markov property
定理 (e.g. Lauritzen(1996))
XV が G 上の Block recursive Markov property を持つとき,. XV はモラ
ルグラフ G 上の大域的マルコフ場である.
一般には曲指数型分布族
.
Xγ ⊥⊥ X
γ
原尚幸 (新潟大・経済)
ǫ
δ
α
β
統計的グラフィカルモデル
2013 年 9 月 8 日
23 / 43
MLE
定理 (e.g. Lauritzen(1996))
離散の block recursive モデルのセル確率 p(i) は
p(i) =
∏
p(iβ | ipa(β) )
β∈V
と分解される. そのとき MLE は
pˆ(i) =
∏ x(iβ∪pa(β) )
.
x(ipa(β) )
β∈V
原尚幸 (新潟大・経済)
統計的グラフィカルモデル
.
2013 年 9 月 8 日
24 / 43
Chain グラフ
Chain グラフ
V1 , . . . , VK を頂点集合 V の互いに排反な部分集合とする. 今, あるグラフ
G が以下をみたすとする.
頂点集合は V
(v, v ) ∈ E なら
∃k, v, v ∈ Vk で (v, v ) は無向辺
もし くは
∃k < k , v ∈ Vk , v ∈ Vk で (v, v ) は v → v という有向辺.
各 Vk に対する誘導部分グラフの連結成分の数は 1
そのとき G を V1 , . . . , VK を chain component とする chain. グラフ と
いう.
有向辺, 無向辺が混在するグラフ
原尚幸 (新潟大・経済)
統計的グラフィカルモデル
2013 年 9 月 8 日
25 / 43
Chain グラフ
chain グラフの例
V1 = {1}, V2 = {2}, V3 = {3, 4}, V4 = {5, 6, 7, 8}
1
3
5
7
2
4
6
8
chain グラフでないグラフの例
原尚幸 (新潟大・経済)
1
3
2
4
統計的グラフィカルモデル
2013 年 9 月 8 日
26 / 43
Chain グラフと DAG
chain グラフの chain component 上の DAG を定義することがで
きる.
1
3
5
7
2
4
6
8
⇓
1
3, 4
5, 6, 7, 8
2
原尚幸 (新潟大・経済)
統計的グラフィカルモデル
2013 年 9 月 8 日
27 / 43
Chain グラフの用語
V ⊂ V に対し
V の親集合 pa(V )
(
pa(V ) =
∪
)
pa(v)
\V
v∈V
V の近傍 adj(V )
(
adj(V ) =
∪
)
adj(v)
\V
v∈V
原尚幸 (新潟大・経済)
統計的グラフィカルモデル
2013 年 9 月 8 日
28 / 43
Chain グラフ上のマルコフ性
Chain グラフ上のマルコフ性を定義したい .
定義：Markov property 1
V : chain component の集合
XU ⊥⊥ Xnd(U )\pa(U ) | Xpa(U ) for all U ∈ V
.
DAG の Block recursive Markov property に対応
1
.
3, 4
5, 6, 7, 8
2
原尚幸 (新潟大・経済)
統計的グラフィカルモデル
2013 年 9 月 8 日
29 / 43
Chain グラフ上のマルコフ性
定義：Markov property 2
V : chain component の集合
2a. XW ⊥⊥ XU \(W ∪nb(W )) | Xpa(U )∪nb(W ) ,
2b. XW ⊥⊥ XU \(W ∪nb(W )) | Xpa(U ) ,
∀U ∈ V,.∀W ⊂ U.
∀U ∈ V, ∀W ⊂ U.
2a. {5, 7} ⊥⊥ {8} | {3, 4, 6}
2b. {5, 7} ⊥⊥ {8} | {3, 4}
原尚幸 (新潟大・経済)
.
1
3
5
7
2
4
6
8
統計的グラフィカルモデル
2013 年 9 月 8 日
30 / 43
Chain グラフ上のマルコフ性
定義：Markov property 3
V : chain component の集合
3a. XW ⊥⊥ Xpa(U )\pa(W ) | Xpa(W )∪nb(W ) ,
3b. XW ⊥⊥ Xpa(U )\pa(W ) | Xpa(W ) ,
∀U ∈ V, .∀W ⊂ U.
∀U ∈ V, ∀W ⊂ U.
3a. {5, 7} ⊥⊥ {4} | {3, 6}
3b. {5, 7} ⊥⊥ {8} | {3}
原尚幸 (新潟大・経済)
.
1
3
5
7
2
4
6
8
統計的グラフィカルモデル
2013 年 9 月 8 日
31 / 43
Chain グラフモデルの Markov property
Block recursive Markov property
2a
2a
XV が 1,
,
2b
2b
3a
3b
3a
3b
I
II
をみたすとき, それぞれ type
の
III
. IV
Block recursive Markov property を持つという.
ガウスのモデルの場合はすべてのタイプが滑らかな曲指数型分布族.
type I は最も自然な DAG のモデルの拡張.
type I, IV は離散のモデルでも滑らかな曲指数型分布族になる.
.
type II, III は離散のモデルの場合に特異なモデルが含まれることが知
られている.
解明されていない部分が多い
原尚幸 (新潟大・経済)
統計的グラフィカルモデル
2013 年 9 月 8 日
32 / 43
Type I モデルの MLE
ここでも離散のモデルを考える.
Type I モデルの場合
p(i) =
∏ p(iU ∪pa(U ) )
.
p(ipa(U ) )
U ∈V
したがって MLE は
pˆ(i) =
∏ pˆ(iU ∪pa(U ) )
.
pˆ(ipa(U ) )
U ∈V
pˆ(iU ∪pa(U ) ) は G のモラルグラフ G の U ∪ pa(U ) に対する誘導部分
グラフによって定義されるグラフィカル (階層) モデル .
前出の局所化アルゴリズムによる計算効率化が可能.
その他の type は推定アルゴリズムなども未知な点が多い .
原尚幸 (新潟大・経済)
統計的グラフィカルモデル
2013 年 9 月 8 日
33 / 43
高次元グラフィカルモデルのモデル同定
m 次元ガウスグラフィカルモデルのモデル数は 2m C2 個
モデルの数は指数的に増大
m が大きい状況では AIC などによる客観的なモデル選択が困難
しかし 高次元ではモデルが疎であることが仮定できる場合が多い
高次元線形回帰の lasso の考え方をグラフィカルモデルに適用した
L1 正則化法に基づく分散行列の推定法を紹介する
原尚幸 (新潟大・経済)
統計的グラフィカルモデル
2013 年 9 月 8 日
34 / 43
最尤推定
未知パラメータ : µ, Σ (K)
¯ := n−1 ∑n X t ⇒ µ の MLE は X
¯
X
∑n t=1t
t − X)
¯
¯
W := t=1 (X − X)(X
K(=Σ−1 ) に関する尤度
L(K) ∝ (detK)
n/2
{
}
1
exp − trKW .
2
対数尤度
1
log L(K) ∝ log(detK) − trK(W/n)
2
原尚幸 (新潟大・経済)
統計的グラフィカルモデル
2013 年 9 月 8 日
35 / 43
sparse graphical model
疎なモデル：グラフの辺が少ないモデル
K の多くの非対角要素が 0 のモデルを推定したい
そこで
1
log L(K) ∝ log(detK) − trK(W/n)
2
∑
subject to
|kij | ≤ l
i,j
の最大化を考える
原尚幸 (新潟大・経済)
統計的グラフィカルモデル
2013 年 9 月 8 日
36 / 43
sparse graphical model
この最大化は
∑
1
− log(detK) + trK(W/n) + λ
|kij |
2
i,j
の最小化と等価
∑
λ i,j |kij | : L1 正則化項
この項があるため kij は 0 を取りやすくなる
σi2′ j ′
ˆ
K
2
σij
x
原尚幸 (新潟大・経済)
統計的グラフィカルモデル
2013 年 9 月 8 日
37 / 43
sparse graphical model
この最大化アルゴリズムはさまざまな文献で提案されている
Meinshausen and Buhlmann
(2006)
¨
Barnergee et al. (2007)
Yuan and Lin (2007)
Friedman et al. (2008)
その他いろいろ
R には glasso という Friedman et al. (2008) に基づくアルゴリズム
のパッケージがある
理論的には K が疎であるという条件下での一致性も示されている
Meinshausen and Buhlmann
(2006)
¨
Ravikumar et al.(2011)
原尚幸 (新潟大・経済)
統計的グラフィカルモデル
2013 年 9 月 8 日
38 / 43
sparse graphical model
ガウスの有向グラフのモデルについても
1
2
モラルグラフの推定
モラルグラフに矛盾しない DAG の探索
.
という形のスパース推定が提案されている.
.
離散のモデルのスパース推定は限られたモデルでしか実用化されて
いない .
また chain グラフモデルのスパース推定は離散・連続ともにほとん
ど成果がない .
原尚幸 (新潟大・経済)
統計的グラフィカルモデル
2013 年 9 月 8 日
39 / 43
References
Diaconis, P. and Sturmfels, B.(1998).
Algebraic algorithms for sampling from conditional distributions.
Ann. Statist., 26, 363-397.
Hara, H., Aoki, S. and Takemura, A.(2010).
Minimal and minimal invariant Markov bases of decomposable
models for contingency tables.
Bernoulli, 16, 208-233.
Dobra, A. and Sullivant, S.(2004).
A divide-and-conquer algorithm for generating Markov bases of
multi-way tables.
Comput. Statist., 19, 347–366.
Dobra, A. (2003).
Markov bases for decomposable graphical models.
Bernoulli, 9, 1093-1108.
原尚幸 (新潟大・経済)
統計的グラフィカルモデル
2013 年 9 月 8 日
40 / 43
References
Lauritzen, S. L. (1996).
Graphical Models,
Oxford University Press, Oxford
Frydenberg, M. (1990). The chain graph Markov property.
Scand. J. Statist., 17, 333-353.
Andersson, S. A., Madigan, D. and Perlman, M.D. (2001).
Alternative Markov properties for chain graphs.
Scand. J. Statist., 28, 33-85.
Drton, M. (2008).
Discrete chain graph models.
Bernoulli, 15, 736-753.
原尚幸 (新潟大・経済)
統計的グラフィカルモデル
2013 年 9 月 8 日
41 / 43
References
Meinshausen, N. and Buhlmann,
P. (2006).
¨
High-dimensional graphs and variable selection with the lasso
Ann. Statist., 34, 1436-1462.
Benerjee, O., Ghaoui, L. E. and D’Aspremont, A. (2007).
Model selection through sparse maximum likelihood estimation.
J. Machine Learning Research, 101, 485-516.
Yuan, M. and Lin, Y. (2007)
Model Selection and estimation in the Gaussian graphicsl model.
Biometrika, 94, 19-35.
Friedman, J, Hastie, T. and Tibshirani, R. (2008).
Sparse inverse covariance estimation with the graphical lasso.
Biostatistics, 9, 432-441.
原尚幸 (新潟大・経済)
統計的グラフィカルモデル
2013 年 9 月 8 日
42 / 43
References
Ravikumar, P, Wainwright, M. J., Raskutti, G. and Yu, B. (2011).
High-dimensional covariance estimation by minimizing
l1 -penalized log-determinant divergence.
Electronic Journal of Statistics, 5, 935-980.
原尚幸 (新潟大・経済)
統計的グラフィカルモデル
2013 年 9 月 8 日
43 / 43
© Copyright 2024 ExpyDoc
