ベイジアンネット

認知システム論 知識と推論(3)
知識を表現し,それを用いて推論する
不確実な知識の表現と確率推論
事後確率と信念改訂
同時分布からの事後確率計算
ベイズの規則
ベイジアンネット
1.事後確率と信念改訂(1/4)
事前確率
Prior
probability
P(A) = 何の情報もない場合に,
エージェントが「Aである」と信じる信念の強さ
証拠
Evidence
B である事実を知る
信 念 の改 訂
Belief revision
事後確率
Posterior
probability
AとBの時間的な前後関係はどうでもよい
条件付き確率
P(A|B) = 知っていることがBのみであるときに,
エージェントが「Aである」と信じる信念の強さ
1.事後確率と信念改訂(2/4)
例
A=「2個のさいころの目がどちらも6」
P(A) = 1/36
一方の目は6
P(A | 一方の目は6) = 1/6
1.事後確率と信念改訂(3/4)
故障診断の例
a,b,c,d,e∈{0,1}
g1,g2,g3 ∈{normal,abnormal}
a
事後確率
d
AND
b
a=1,b=1のとき,e=1 だった.
e
OR
c
g1
NOT
g3
g2
ゲートg2が故障である確率 P(g2=abnormal | a=1,b=1,e=1)は?
質問変数
a
P(a)
P(b)
b
P(d|a,c,g2)
c
g1
事前確率
ベイジアンネット
P(g1)
証拠変数
P(e|d,g3)
d
P(c|a,b,g1)
g2
P(g2)
P(g3)
e
g3
条件付き確率
1.事後確率と信念改訂(4/4)
医療診断の例題
1
P ( A  1) 
10
9
P ( A  0) 
10
カゼ
カゼ(A=1)
カゼでない(A=0)
ノド
60%
B=1
20%
カゼのときには,60%の確率でノドがいたい.
カゼでないときには,20%の確率でノドがいたい.
10人に1人はカゼをひいている.
ノドがいたいとき,カゼである確率はどの程度か.
同時分布から計算する方法と
ベイズの規則を使う方法がある.
いずれも,カゼである確率は,P(A=1|B=1)=25%
2.同時分布からの事後確率の計算(1/7)
同時分布
X
確率変数 (random variable)
授業では「命題」を表わすのに限定.
値は 0 または 1
P( X  0)  P( X  1)  1
P( X )  ( p0 , p1 )
P ( X  x, Y  y )
P( X , Y )
確率分布 (probability distribution)
Xについての関数.表で与えられる.
結合確率 (joint probability)
同時確率 (simultaneous probability)
同時分布
(simultaneous probability distribution)
すべての変数の取り得る値の
すべての組合せに対する確率の表
2.同時分布からの事後確率の計算(2/7)
周辺分布
P( X )   P( X , Y )
Y
周辺分布
(marginal distribution)
同時分布
P(X,Y)
Y=0
Y=1
P(X)
X=0
0.1
0.2
0.3
X=1
0.3
0.4
0.7
P(Y)
0.4
0.6
P ( X )   P( X , Y , Z )
Y ,Z
2.同時分布からの事後確率の計算(3/7)
条件付き確率
条件付き確率 (conditional probability)
P( X  x | Y  y ) 
P ( X  x, Y  y )
P (Y  y )
条件付き確率分布
P( X | Y ) 
P( X , Y )
P (Y )
同時分布
P(X,Y)
X=0
周辺分布
Y=0
0.1
Y=1
0.2
X=1
0.3
0.4
P(Y)
0.4
0.6
P ( X  0 | Y  1) 
P ( X 0,Y 1)
P (Y 1)
0.2
1


0.6
3
2.同時分布からの事後確率の計算(4/7)
連鎖公式
条件付き確率
P( X | Y ) 
P( X , Y )
P (Y )
連鎖公式 (chain rule)
P( X , Y )  P( X | Y ) P(Y )
P( X , Y , Z )  P( X | Y , Z ) P(Y | Z ) P(Z )
2.同時分布からの事後確率の計算(5/7)
例題の解(1)
P ( B  1| A  1) 
1
P ( A  1) 
10
9
P ( A  0) 
10
カゼ
3
2
P ( B  0 | A  1) 
5
5
60%
カゼ(A=1)
ノド
B=1
カゼでない(A=0)
20%
1
4
P ( B  1| A  0)  P( B  0 | A  0) 
5
5
連鎖公式を使って,同時分布を計算する.
P( A  1, B  1) 
1 3 3
 
10 5 50
9 1 9
P( A  0, B  1)   
10 5 50
P( A  1, B  0) 
1 2 2
 
10 5 50
9 4 36
P( A  0, B  0)   
10 5 50
2.同時分布からの事後確率の計算(6/7)
例題の解(2)
1
P ( A  1) 
10
9
P ( A  0) 
10
カゼ
カゼ(A=1)
B=1
カゼでない(A=0)
20%
同時分布
単位:1/50
P(A,B)
B=1
B=0
P(A)
A=1
3
2
5
A=0
9
36
45
P(B)
ノド
60%
12
38
50
条件付き確率を計算する.
P ( A  1 | B  1) 

3
12

1
4
P ( A  1, B  1)
P ( B  1)
25%
2.同時分布からの事後確率の計算(7/7)
この方法の問題点
同時分布
X1 X2
…
Xn
0
0
…
0
0
0
…
1
… …
…
…
1
1
…
0
1
1
…
1
確率
記憶領域の問題
同時分布表のサイズが指数的
n
O(2 )
…
計算時間の問題
周辺分布の計算時間が指数的
n
O(2 )
3.ベイズの規則(1/3)
P( X , Y )  P( X | Y ) P(Y )
P( X , Y )  P(Y | X ) P( X )
P( X | Y ) P (Y )
ベイズの規則
(Bayes' rule)

P(Y | X ) P( X )
P(Y | X ) P( X )
P( X | Y
) 
P(Y )
結果から原因を推測できる
原因
X
因果関係
(causality)
結果
Y
3.ベイズの規則(2/3) 正規化
P(Y | X ) P( X )
P( X | Y ) 
P(Y )
質問変数X の値には無関係
正規化定数
証拠変数Y を固定
  1 P(Y )
P( X | Y )   P(Y | X ) P( X )
分子だけ計算
P( X  0 | Y )   P(Y | X  0) P( X  0)
P( X  1 | Y )   P(Y | X  1) P( X  1)
P( X  0 | Y )  P( X  1 | Y )  1
となるように,定数倍
(正規化)
3.ベイズの規則(3/3) 例題の解
P( A  1)  1
10
P( A  0)  9
P( B  1| A  1)  3
カゼ
60%
カゼ(A=1)
B=1
カゼでない(A=0)
10
5 ノド
20%
P( B  1| A  0)  1
5
ベイズの規則を使って,事後確率を計算する.
3/(3+9)
P ( A  1 | B  1)   P ( B  1 | A  1) P ( A  1)

3
5

1 
10

3
50

正規化
25%
P ( A  0 | B  1)   P ( B  1 | A  0) P ( A  0)

1
5

9
10
  9
50

75%
4.ベイジアンネット(1/5) 導入
(Bayesian network)
ベイジアンネット
=
有向非循環グラフ
P(B)
P(E)
B
E
+
条件付き確率表
P(D|E)
P(A|B,E)
有向非循環グラフ
(directed acyclic graph: DAG)
A
D
P(C|A) C
条件付き確率表
(conditional probability table: CPT)
4.ベイジアンネット(2/5) 条件付き確率表
parents(Y )  {}
Y
Z
X
Xの親ノードの集合
parents( X )  {Y , Z}
各ノード X ごとに
その親ノードの集合を条件とする
条件付き確率表をつくる
P( X | parents( X ))
P( X | Y , Z )
Y
1
Z
1
X=1
0.95
X=0
0.05
1
0
0.9
0.1
0
1
0.3
0.7
0
0
0.01
0.99
4.ベイジアンネット(3/5) 連鎖公式
ベイジアンネットの連鎖公式
P( A, B, C, D, E )  P(C | A)  P( A | B, E )  P( B)  P( D | E )  P( E )
P(B)
P(E)
B
E
P(D|E)
ベイジアンネットでの約束
P(A|B,E)
A
同時分布は条件付き確率表の積になる
記憶領域の問題は解決!
P(C|A) C
D
4.ベイジアンネット(4/5) 例題
ベイジアンネットの連鎖公式
P( A, B, C, D, E )  P(C | A)  P( A | B, E )  P( B)  P( D | E )  P( E )
【例題】B=1,C=0,E=1のとき,A=1である確率の
求め方を説明せよ.
P(A,1,0,D,1)=P(C=0|A) P(A|B=1,E=1)
P(B=1) P(D|E=1) P(E=1)
P(B)
P(E)
B
E
P(D|E)
P(A|B,E)
A
=α P(C=0|A) P(A|B=1,E=1) P(D|E=1)
を用いて,
P(1,1,0,1,1),P(1,1,0,0,1),P(0,1,0,1,1),P(0,1,0,0,1) P(C|A) C
を計算する.
最初の2項の和がP(A=1, B=1,C=0,E=1).
4項の和が
P(B=1,C=0,E=1).
その比がP(A=1 | B=1,C=0,E=1).
周辺分布
D
4.ベイジアンネット(5/5) 多重結合と単結合
多重結合ネットワーク: 無向グラフが閉路を持つ
(multiply-connected network)
事後確率の計算はNP困難
→指数時間のアルゴリズムしかなさそう
A
B
C
D
単結合ネットワーク: 無向グラフが閉路を持たない
(singly-connected network)
ネットワークの規模に対して
線形時間のアルゴリズムがある
B
E
A
C
D