Inverted Index Compression and Query Processing

PRML読書会第10回
8.2 条件付き独立性
2010-01-09
SUHARA YOSHIHIKO
(id:sleepy_yoshi)
目次
• 8.2 条件付き独立性
– 8.2.1 3つのグラフの例
• 8.2.2 有向分離 (d分離)
1
8.2 条件付き独立性
2
条件付き独立性 (1)
• 変数a, b, cを考える．bとcが与えられたときに，aの
条件付き分布がbの値に依存しない
p(a | b, c)  p(a | c)
⇒ cが与えられた下で，aはbに対して条件付き独立
3
条件付き独立性 (2)
• cで条件付けられたaおよびbの同時分布を考える
p(a,b)=p(a|b)p(b)
p(a, b | c)  p(a | b, c) p(b | c)
 p(a | c) p(b | c)
⇒ cが与えられたとき，aおよびbが統計的に独立である
記法：
a b|c
cが与えられた際に，aがbに対して条件付き独立
4
演習8.8
•
a b, c | d
解)
ならば
a b|d
p(a, b, c | d )  p(a | d ) p(b, c | d )
cについて周辺化
p(a, b | d )  p(a | d ) p(b | d )
a b | d
5
8.2.1 3つのグラフの例
6
8.2.1 3ノードから成るグラフ
• ３つの構造
– (1) tail-to-tail
– (2) head-to-tail
– (3) head-to-head
• 「弁明」現象
7
(1) tail-to-tail
8
(1) tail-to-tail
c
tail-to-tail
tail
b
a
head
p(a, b, c)  p(a | c) p(b | c) p(c)
どの変数も観測されていない場合に
aとbの独立を確かめる (両辺をcに関して周辺化)
p(a, b)   p(a | c) p(b | c) p(c)
c
⇒ p(a)p(b)に分解不可能 (
a b |
)
9
tail-to-tail: 変数cの観測
• 前頁の例を変数cで条件付ける
p(a,b,c)
= p(a,b|c)p(c)
p(a, b, c)
p(a, b | c) 
p (c )
 p(a | c) p(b | c)
よって条件付き独立が導かれる
a b|c
10
tail-to-tail: 経路の遮断
• cを観測することにより，経路を遮断 (block) し，
aとbとを条件付き独立にする
c
a
b
p(a, b | c)  p(a | c) p(b | c)
ポイント１
tail-to-tailのノードを観測すれば，
ふたつのノードの経路を遮断できる
11
(2) head-to-tail
12
(2) head-to-tail
c
a
b
head-to-tail
p(a, b, c)  p(a)(c | a) p(b | c)
どの変数も観測されていない場合にaとbの独立を確かめる
p(a, b)  p(a) p(c | a) p(b | c)  p(a) p(b | a)
c
⇒ p(a)p(b)に分解不可能 (
a b |
)
13
head-to-tail: 変数cの観測
• 前頁の例を変数cで条件付ける
p
(
a
,
b
,
c
)
p(a, b | c) 
ベイズの定理
p (c )
p(a) p(c | a) p(b | c)

p (c )
 p(a | c) p(b | c)
よって条件付き独立が導かれる
a b|c
14
head-to-tail: 経路の遮断
• cを観測することにより，経路を遮断 (block) し，
aとbとを条件付き独立にする
a
c
b
p(a, b, c)  p(a | c)(b | c)
ポイント２
head-to-tailのノードを観測すれば，
ふたつのノードの経路を遮断できる
15
(3) head-to-head
16
(3) ead-to-head
b
a
c
head-tohead
p(a, b, c)  p(a) p(b) p(c | a, b)
どの変数も観測されていない場合にaとbの独立を確かめる
p(a, b)  p(a) p(b)
⇒ p(a)p(b)に分解可能 (
a b | )
17
head-to-head: 変数cの観測
• 前頁の例を変数cで条件付ける
p(a, b, c)
p(a, b | c) 
p (c )
p(a) p(b)(c | a, b)

p (c )
p(a|c)p(b|c)に因数分解できないため，
条件付き独立ではない
a b|c
18
head-to-head: 経路の遮断解除
b
a
c
p(a) p(b) p(c | a, b)
p ( a, b | c ) 
p (c )
ポイント３
head-to-headのノードを観測すると，
ふたつのノードの経路の遮断が解かれる
19
head-to-headの子孫の観測
依存関係の発生
b
a
c
ポイント４
d
head-to-headかその子孫のうちいずれか
を観測すると，経路の遮断が解かれる
(⇒ 演習8.10)
20
演習8.10 (1/2)
b
a
c
d
p(a, b, c, d )  p(a) p(b) p(c | a, b) p(d | c)
a
b |
の確認
変数c, dについて周辺化
p(a, b)  p(a) p(b) p(c | a, b) p(d | c)
d
c
 p(a) p(b) p(d | a, b)  p(a) p(b)
d
21
演習8.10 (2/2)
a b|d
の確認
dで条件づける
p(a, b, c, d ) p(a) p(b) p(c | a, b) p(d | c)
p(a, b, c | d ) 

p(d )
p(d )
変数cに関して周辺化
p ( a, b | d ) 
p(a) p(b) p(c | a, b) p(d | c)
c
p(d )
p(a) p(b) p(d | a, b)

 p(a | d ) p(b | d )
p(d )
22
演習8.10の考察
• head-to-headノードの子孫である変数zを観測しても，
変数の周辺化によって変数cの観測と同じ効果が発生
b
a
p(a, b, c,...| z )
p(a) p(b) p(c | a, b)...p( z | ...)

p( z )
c
周辺化
…
z
周辺化
p(a) p(b) p( z | a, b)
p ( a, b | z ) 
p( z )
23
「弁明」現象
24
車の燃料タンクモデル
• 車の燃料装置のモデル
– バッテリの状態 B {1, 0}
– 燃料タンクの状態 F {1, 0}
– 電動燃料計 G {1, 0}
バッテリと燃料タンクが
満タンである事前確率
p( B  1)  0.9
p( F  1)  0.9
B
F
G
燃料タンクとバッテリの状態が
与えられた際の燃料系が満タンを指す確率
p(G  1 | B  1, F  1)  0.8
p(G  1 | B  1, F  0)  0.2
p(G  1 | B  0, F  1)  0.2
p(G  1 | B  0, F  0)  0.1
何も観測していないとき，
燃料タンクが空である確率 p(F=0) = 0.1
25
燃料計観測による確率の変化
燃料計が空を指している事実を観測
B
F
ベイズの定理より
G
p(G  0) 
p(G  0 | F  0) p( F  0)
p( F  0 | G  0) 
p(G  0)
  p(G  0 | B, F ) p(B) p(F )  0.315
B{0,1} F{0,1}
p(G  0 | F  0) 
 p(G  0 | B, F  0) p(B)  0.81
B{0,1}
0.81  0.1

 0.257
0.315
p( F  0 | G  0)  p( F  0)
観測によってタンクが空である可能性が高くなる
26
「弁明」現象
つづいてバッテリが切れていること (B=0) を観測
B
p( F  0 | G  0, B  0)
F
G

P(G  0 | F  0, B  0) p( F  0)
 0.111
F{0,1} p(G  0 | B  0, F ) p(F )
バッテリの観測によってタンクが空である確率が
0.257から0.111に下がった
バッテリが切れているという事実が，
燃料計が空を指していることを「弁明」している
※1 燃料計Gの代わりにGの子孫を観測しても起こる
※2 バッテリが切れていても，燃料計が0を指しているという事実
が証拠となり，事前確率p(F=0)よりも大きい
27
補足:B, G観測後の事後確率計算
p( F , G, B)  p( F , G | B) p( B)  p( F | G, B) p(G | B) p( B)
 p(G, B | F ) p( F )  p(G | F , B) p( B | F ) p( F )
p(B)
p(G  0 | B  0, F  0) p( B  0) p( F  0)
p( F  0 | G  0, B  0) 
 p(G  0 | B  0, F ) p( B  0) p( F )
F{0,1}
Σの外に出て打ち消す
p(G  0 | F  0, B  0) p( F  0)

 0.111
F{0,1} p(G  0 | B  0, F ) p(F )
28
突然ですが
29
アンケート
• “explain away” あなたならどう訳す?
–
–
–
–
–
–
–
(1) 弁明 (現象) 1名
(2) 釈明 (現象) 1名
(3) 言い逃れ (現象) 1名
(4) 説明を加えて明らかにする現象 5名
(5) (他人がフォローするので) 弁護 (現象) 7名
(6) 真犯人が現れました現象
(その他自由回答)
PRML読書会的には「弁護」現象となりました
30
8.2.1のポイントまとめ
31
ポイント１
tail-to-tailのノードを観測すれば，
ふたつのノードの経路を遮断できる
ポイント２
head-to-tailのノードを観測すれば，
ふたつのノードの経路を遮断できる
ポイント３
head-to-headのノードを観測すると，
ふたつのノードの経路の遮断が解かれる
ポイント４
head-to-headかその子孫のうちいずれか
を観測すると，経路の遮断が解かれる
32
8.2.2 有向分離 (D分離)
今までの話を一般化
33
有向分離
• グラフの有向分離
– A, B, Cを重複のないノード集合とする
– 条件付き独立性 A B | C を調べたい
⇒ Aの任意のノードからBの任意のノードまで全ての経
路が遮断されていることを確認する
A
B
C
34
経路の遮断条件
• 以下の条件のいずれかを満たすノードを含む経
路は遮断されている
(a) 集合Cに含まれるノードであって，経路に含まれ
る矢印がそこでhead-to-tailあるいはtail-to-tailである
(b) 経路に含まれる矢印がそのノードでhead-to-headで
あり，自身あるいはそのすべての子孫いずれもが集
合Cに含まれない
• 全ての経路が遮断されていれば，AはCによって
Bから有向分離され，A B | C を満たす
35
例1)
• aからbの経路を調べる
有向分離
できないか?
a
f
e
b
c
1. fによって遮断されない
⇒ tail-to-tailかつ観測されていないため
2. eによって遮断されない
⇒ head-to-headだが，子孫のcが観測されているため
このグラフからでは条件付き独立性は導けない
36
例2)
• aからbの経路を調べる
a
f
e
b
c
1. fによって遮断される
⇒ tail-to-tailかつ観測されているため
2. eによっても遮断される
⇒ head-to-headかつ，いずれの子孫が観測されていないため
条件付き独立a b | f が成立する
37
独立同分布データの場合
1.2.4節の独立同分布 (i.i.d.) の例
• 1変量ガウス分布の平均事後分布を得る問題
– 下記のグラフより p(μ,x) = p(x|μ)p(μ)
μ
μ
x1
…
xN または
xn
N
μを条件付け変数と見なすと，任意のxiとxi≠jの経路がtail-to-tailの
観測済みノードμのため，すべての経路が遮断される
⇒ μが与えられた下で観測値D = {x1, ..., xN} は独立である
N
p ( D |  )   p ( xn |  )
n 1
38
図8.7の例
• \hat{t}からtnに対する任意の経路において，wはtailto-tailであるため，以下の条件付き独立性が成立する
tˆ tn | w
つまり多項式係数wで条件つけら
れた下で，\hat{t}の予測分布は
訓練データtnに対して独立
一旦訓練データを利用して係数w上の事後分布を決め
てしまえば，訓練データを捨ててしまってよい
39
ナイーブベイズモデル
• ナイーブベイズモデルのグラフ構造
– 観測変数x = (x1,...xD)T
– クラスベクトルz = (z1, ..., zK)
zを観測すると，xiとxj (j≠i)
との間の経路が遮断される
ナイーブベイズ仮説
クラスzで条件付けると
入力変数x1, ...xDが互いに独立
zを観測せずにzに関して周辺化すると，
xiとxj (j≠i) への経路の遮断は解かれる
p(x)を各成分x1,...,xDに関して
分解できないことを意味する
i.e.,
D
p(x)   p( xi )
i
40
ナイーブベイズモデルの特長
• 入力ベクトルxに離散変数と連続変数が混在するような
場合にも使える
⇒ 変数それぞれに対して適切なモデルを採用する
実数値には
ガウス分布
2値観測値には
ベルヌーイ分布
D
p( y | x)  arg max p( y) p( xi | y)
yY
i
様々な分布の組み合わせが可能
41
有向分離定理
42
有向分離定理
2つの方法によって得られる分布の集合は等価である
(1) 有向分解 (directed factorization)
– 同時分布の因数分解から得られる分布の集合
K
p(x)   p( xk | pak )
(8.5)
k 1
(2) 有向分離 (directed separation)
– グラフの経路遮断を調べて得られる分布の集合
43
マルコフブランケット
44
マルコフブランケット (1/2)
• D個のノードを持つグラフで表現される同時分布
p(x1, ..., xD) と，変数xiに対応するノード上の，他ノー
ドxj≠iで条件付けられた条件付き分布を考える
p(xi | x{ j i} ) 
p(a|b,c) =
p(a,b,c) / p(b,c)
p(x1 ,...,x D )
 p(x ,...,x )dx
 p(x | pa )

  p(x | pa )dx
1
D
i
k
x k i
xi  pak
k
k
k
k
i
xiに依存しないノードは積分の外
に出て分子と打ち消しあう
k
p(xi | pai )
xiの親ノードに依存
p(xk | pak )
xi (の子)と共同親に依存 (誤植? 下巻p.95, 原書p.382)
45
マルコフブランケット (2/2)
• xiをグラフから条件付き独立にするためのノード最小集合 (⇒ 演習8.9)
共同親
(co-parent)
• 共同親が必要な理由
⇒ 子の観測により遮断が解かれるため
共同親
xi
head-to-headノードが観測 (ポイント3)
46
演習8.9
• マルコフブランケットを条件付けることにより，xiが全
てのノードから条件付き独立
親ノード集合:
tail-to-tail or head-to-rail
かつ観測 ⇒ 遮断
子ノード集合:
(1) head-to-tail
かつ観測 ⇒ 遮断
(2) head-to-head
かつ観測 + 共同親も観測
⇒ 遮断
47
本節のまとめ
48
本節のまとめ
• 3ノードのグラフ
– tail-to-tail
– head-to-tail
– head-to-head
• 「弁明」現象
• 有向分離基準
– 3ノードグラフの性質を一般化
• 有向分離定理
– 有向分解 (8.5) と有向分離基準で得られる条件付き独立性は一緒
• マルコフブランケット
49
おしまい
50

Download Report