13章＆14章

エージェントアプローチ
人工知能
B4 片渕聡
1
目次

１３章不確実性

１４章確率推論
2
１３章不確実性
目次





エージェントの不確実性
確率論
完全結合確率分布を用いた推論
ベイズ規則
まとめ
3
１３章不確実性
目次





エージェントの不確実性
確率論
完全結合確率分布を用いた推論
ベイズ規則
まとめ
4
エージェントの不確実性

実環境では真偽が不確かである状況が多い
－条件の完全列挙の難しさ
・条件や結果の網羅に対する困難
－理論上の無知
・領域に関しての完全な理論が存在しない
－実際上の無知
・ある特定の状況でのテストの網羅に対する困難

信念の強さによってどの位文が真に近いかを判断
5
１３章不確実性
目次





エージェントの不確実性
確率論
完全結合確率分布を用いた推論
ベイズ規則
まとめ
6
確率論

文に対する信念の強さを扱う
－0～1の数値で表された確率(信念の強さ)を付与

実際は真か偽しかありえない
× その文が真である確率が80%
○ その文が真であることの信念の強さが80%
7
事前確率

何の情報も無い命題に関する信念の度合い
－例：今日の天気が晴れである確率は多分70%
 P(Weather=sunny) = 0.7

全ての確率をひとまとめにしたい場合はベクタを用いる
P(Weather=sunny) = 0.7
P(Weather=rain) = 0.2
P(Weather=cloudy) = 0.08
P(Weather=snow) = 0.02
P(Weather)= <0.7,0.2,0.08,0.02>
8
完全結合確率分布

問題領域に関する全ての組み合わせの確率を表現
－Toothache：歯が痛いかどうか
－Cavity：虫歯かどうか
P(Toothache,Cavity)
toothache
￢toothache
cavity
0.3
0.2
￢cavity
0.1
0.4
9
確率論の公理
(Kolmogorovの公理)
1.
0≦P(a) ≦1
2.
P(true)=1,P(false)=0
3.
P(a∨b)=P(a) + P(b) - P(a∧b)
※公理に反する事前確率を付与してはならない
（特に公理３）
10
条件付き確率（事後確率）

命題bが真である時に命題aが真になる確率
－P(a|b)

条件付確率は事前確率だけで表現可能
P(a∧b)
－P(a|b)= P(b)
P(a∧b)=P(b)P(a|b)
積の公式
11
積の公式のベクタへの適用

P(X=x1∧Y=y1) = P(X=x1∧Y=y1)P(Y=y1)
P(X=x2∧Y=y2) = P(X=x2∧Y=y2)P(Y=y2)
・・・
P(X,Y)=P(X|Y)P(Y)

P(Toothache,Cavity)=P(Toothache|Cavity)P(Cavity)
12
１３章不確実性
目次





エージェントの不確実性
確率論
完全結合確率分布を用いた推論
ベイズ規則
まとめ
13
完全結合確率分布を用いた推論(1/2)

知識ベース(完全結合確率分布)
cavity
￢cavity

toothache
0.3
0.1
￢toothache
0.2
0.4
周辺化：ある変数に対する分布を抜き出す
－例：P(toothache)=0.3+0.1=0.4 周辺確率
14
完全結合確率分布を用いた推論(2/2)

歯痛であることが判明した時の虫歯の確率を計算
P(cavity|toothache)= P(cavity∧toothache)
P(toothache)
=0.3/0.5=0.6
※独立した要素を含む場合、別問題として扱える
例：P(Toothache,Cavity,Weather)
＝P(Toothache,Cavity)P(Weather)
天気が歯痛や虫歯に影響を及ぼすとは考えにくい
15
１３章不確実性
目次





エージェントの不確実性
確率論
完全結合確率分布を用いた推論
ベイズ規則
まとめ
16
ベイズ規則

積の公式より２つの式が書ける
－P(a∧b)=P(a|b)P(b) (1)
－P(a∧b)=P(b|a)P(a) (2)

(1)(2)式より
P(a|b)P(b)
－P(b|a)=
P(a)
P(B|A)=αP(A|B)P(B)
α：P(B|A)の合計を１にする正規化定数
17
ベイズ規則の適用例






脳膜炎が50%で肩こりを生じさせる
患者が脳膜炎である事前確率は0.002%
患者が肩こりになっている事前確率は5%
S:患者が肩こりであるかどうか
s:S=true
M:患者が脳膜炎であるかどうか
m:M=true
P(s|m)=0.5 P(m)=0.00002 P(s)=0.05
よって肩こりの患者のどのくらいが脳膜炎であるかは
P(m|s)=0.5×0.00002/0.05=0.0002 (１人/5000人)
18
条件付き独立性


変数Zを介することでxとyを独立させることが可能
P(x∧y|Z)=P(x|Z)P(y|Z) 及び
P(X,Y|Z)=P(X|Z)P(Y|Z)
これにより３変数以上のベクタも分解可能
－P(X,Y,Z)=P(X,Y|Z)P(Z)
=P(X|Z)P(Y|Z)P(Z)
Z
T
F
P(x)
0.6
0.2
Z
T
F
P(y)
0.5
0.4
P(z)
0.2
19
証拠の組み合わせ

P(Z|x∧y)：証拠x,yから結果Zを求める
(1)P(Z|x∧y)=αP(x∧y|Z)P(Z) (ベイズ規則)
(2)P(x∧y|Z)=P(x|Z)P(y|Z) (条件付き独立性)

(1)(2)より
P(Z|x∧y)=αP(x|Z)P(y|Z)P(Z)
20
１３章不確実性
目次





エージェントの不確実性
確率論
完全結合確率分布を用いた推論
ベイズ規則
まとめ
21
まとめ






確実な決定ができない場合は信念の強さで判断
エージェントの信念は確率によって付与される
確率論の統語論：事前確率と条件付き確率
確率論の意味論：完全結合確率分布
ベイズ規則を用いることにより推論の幅が広がる
条件付き独立性で完全結合確率分布を分解可能
22
ここまで１３章

ここから１４章
23
１４章：確率推論
目次




ベイジアンネット
ベイジアンネットの厳密推論
ベイジアンネットの近似推論
－ダイレクトサンプリング
－棄却サンプリング
－尤度重み付け法
－マルコフ連鎖モンテカルロ
まとめ
24
ベイジアンネット

確率変数の関係を表現したグラフ
－例：P(Toothache|Cavity)P(Cavity)P(Weather)
親ノード
P(Cavity)
P(Weather)
Cavity
Weather
P(Toothache|Cavity)
Toothache
25
条件付き確率表
(Conditional Probability Table:CPT)
P(S|C)
C
t
f
S R
t t
t f
f t
f f
P(s)
0.1
0.5
P(t)
0.99
0.90
0.90
0.00
P(c)=0.5
Cloudy
Sprinkler
Rain
C
P(r)
t
0.8
f
0.2
Wet Grass
26
１４章：確率推論
目次




ベイジアンネット
ベイジアンネットの厳密推論
ベイジアンネットの近似推論
－ダイレクトサンプリング
－棄却サンプリング
－尤度重み付け法
－マルコフ連鎖モンテカルロ
まとめ
27
ベイジアンネットの厳密推論

観測事象(証拠変数)から求める変数(質問変数)の確率
分布を求める
－例：P(Cavity|toothache)=α<0.6,0.4>=<0.6,0.4>
※１３章参照

ではP(Cloudy|WetGrass=true)は？
－上記の式の中にはSprinklerとRainが隠れている
隠れ変数
28
厳密推論の公式

P(X|e)=αΣP(X,e,y)
y
－X:質問変数 e：証拠変数 y:隠れ変数

例：スプリンクラーの問題
－P(C|w)=αΣΣP(C,S,R,W)
s
r
⇒P(c|w)=αΣΣP(c)P(s|c)P(r|c)P(w|s,r)
s
r
= αP(c)ΣP(s|c)ΣP(r|c)P(w|s,r)
s
r
29
クラスタリングアルゴリズム(1/2)

S CR ,SWRのような複結合が存在するとき
SとRを一つにまとめることでネットワークを単純化
P(C)=0.5
S R
P(T)
t t
t f
0.99
0.90
0.90
0.00
f t
f f
Cloudy
Spr+Rain
C
P(S+R=x)
tt tf ft ff
t
.08 .02 .72 .18
f
.10 .40 .10 .40
Wet Grass
30
クラスタリングアルゴリズム(2/2)

クラスタ化したことにより計算時間を短縮
P(C|w)=αΣP(C,X,W)
x
⇒P(c|w)=αP(c)ΣP(x|c)P(w|x)
x
31
１４章：確率推論
目次




ベイジアンネット
ベイジアンネットの厳密推論
ベイジアンネットの近似推論
－ダイレクトサンプリング
－棄却サンプリング
－尤度重み付け法
－マルコフ連鎖モンテカルロ
まとめ
32
ベイジアンネットの近似推論

大規模なネットワークでの厳密推論は計算が困難
－サンプルを用いて近似解を求める
・コインを投げる＝
<0.5,0.5>の確率分布から１つサンプルを得る
33
１４章：確率推論
目次




ベイジアンネット
ベイジアンネットの厳密推論
ベイジアンネットの近似推論
－ダイレクトサンプリング
－棄却サンプリング
－尤度重み付け法
－マルコフ連鎖モンテカルロ
まとめ
34
ダイレクトサンプリング法

全変数において確率分布からサンプルを取得
例：１．P(C)=<0.5,0.5>からサンプル[true]を取得
２．P(S|c)=<0.1,0.9>からサンプル[false]を取得
３．P(R|c)=<0.8,0.2>からサンプル[true]を取得
４．P(W|￢s,r)=<0.9,0.1>からサンプル[true]を取得
サンプル結果は事象[true,false,true,true]を返す

サンプリング確率は0.5×0.9×0.8×0.9=32.4%
サンプルの32.4%はこの結果になることが期待できる
※サンプル数が限りなく多い場合に限る
35
ダイレクトサンプリングからの推論

例：質問P(C|￢s,r,w)を求める
P(C|￢s,r,w)=
α<事象[T,F,T,T]の確率,事象[F,F,T,T]の確率>
≒α<32.4,0.045>

例：質問P(Rain|s,w)を求める
P(R|s,w)=
α<事象[T,T,T,T]の確率+事象[F,T,T,T]の確率,
事象[T,T,F,T]の確率+事象[F,T,F,T]の確率>
36
１４章：確率推論
目次




ベイジアンネット
ベイジアンネットの厳密推論
ベイジアンネットの近似推論
－ダイレクトサンプリング
－棄却サンプリング
－尤度重み付け法
－マルコフ連鎖モンテカルロ
まとめ
37
棄却サンプリング

証拠に適合しないサンプルを棄却
例：[true,false,true,false]は証拠に不適合なので棄却

長所
ダイレクトサンプリングと比べて計算量が少ない

欠点
大量のサンプルを棄却してしまう場合がある
－証拠がtrueになる確率が極端に少ないとき
38
１４章：確率推論
目次




ベイジアンネット
ベイジアンネットの厳密推論
ベイジアンネットの近似推論
－ダイレクトサンプリング
－棄却サンプリング
－尤度重み付け法
－マルコフ連鎖モンテカルロ
まとめ
39
尤度重み付け法（1/2）

証拠と適合するサンプルだけを生成
－棄却サンプリングの非効率性を解消

各事象は証拠の尤度によって重み付けられる
－尤度：証拠(≠証拠変数)がtrueになる確率
・尤度が低い事象には重みを小さくすべきである

尤度重み付け法では重みω(初期値1.0)を適用
40
尤度重み付け法(2/2)

例：質問P(Rain|S=true,W=true)を求める
１．P(C)=<0.5,0.5>からサンプル[true]を取得
２．Sは証拠変数(true)なのでωを以下の値に設定
ωω×P(s|c) = 0.1
３．P(R|c)=<0.8,0.2>からサンプル[true]を取得
４．Wは証拠変数(true)なのでωを以下の値に設定
ωω×P(w|s,r) = 0.099

サンプル結果は重み0.099を持つ事象[t,t,t,t]を生成
サンプルの重み付き確率は0.5×0.8×0.099=0.0396
41
１４章：確率推論
目次




ベイジアンネット
ベイジアンネットの厳密推論
ベイジアンネットの近似推論
－ダイレクトサンプリング
－棄却サンプリング
－尤度重み付け法
－マルコフ連鎖モンテカルロ
まとめ
42
マルコフ連鎖モンテカルロ
(Marcov chain Monte Carlo:MCMC)

事象[A,・・・]の状態を確率によって状態遷移させる
事象[A,B,C]におけるMCMC(Cは証拠)
0.6
0.1
[a,b,c]
[a,￢b,c]
0.1
0.3
0.2
0.2
0.1
0.5
[￢a,b,c]
[￢a,￢b,c]
0.6
43
マルコフ連鎖モンテカルロ
(Marcov chain Monte Carlo:MCMC)

例：質問P(Rain|S=true,W=true)を求める
１．ランダムに初期化([true,true,false,true]とする)
２．現在の状態を基にCloudyをサンプル
この場合P(C|s,r)からサンプルを取得
その結果falseを返したら状態は[false,t,f,t]となる
３．現在の状態を基にRainをサンプル
この場合P(R|￢c,s,w)からサンプルを取得
その結果trueを返したら状態は[f,t,true,t]となる
サンプル

2,3を繰り返し行い、得たサンプルを基に確率を求める
44
マルコフ連鎖モンテカルロ
(Marcov chain Monte Carlo:MCMC)

前スライドを図で表現
事象[C,S,R,W]におけるMCMC(S,Wは証拠)
αP(c|s,￢r)
[c,s,r,w]
[c,s,￢r,w]
αP(￢c|s,￢r)
αP(r|￢c,s,w)
[￢c,s,￢r,w]
αP(￢r|￢c,s,w)
[￢c,s,r,w]
サンプルの一つ
45
１４章：確率推論
目次




ベイジアンネット
ベイジアンネットの厳密推論
ベイジアンネットの近似推論
－ダイレクトサンプリング
－棄却サンプリング
－尤度重み付け法
－マルコフ連鎖モンテカルロ
まとめ
46
まとめ


ベイジアンネットで条件付き独立を簡潔に表現
ベイジアンネットにおける推論
－P(X|e)=αΣP(X,e,y)
y

近似推論により精度を保ちつつ計算量を抑える
－尤度重み付け法、MCMC
47
補足

尤度重み付け法とMCMCの性質の違いについ
ては特に触れられていませんでした。
－精度、計算量？

一階述語論理の表現をベイジアンネットに適用
することで強力なシステムが作られる。（RPM）
48
１５章：時間を伴う確率的推論
導入

時間推移の伴うベイジアンネット
P(C0)
P(C1|C0)
P(C2|C1)
Cavity0
Cavity1
Cavity2
Toothache0
Toothache1
Toothache2
P(T0|C0)
P(T1|C1)
P(T2|C2)
49

Download Report