エージェントアプローチ
人工知能
B4 片渕 聡
1
目次

15章 時間の伴う確率的推論

16章 単純な意思決定
2
15章 時間の伴う確率的推論
目次




時間の伴う確率推論
時制論理
-予測
-平滑化
-最尤の説明
代表的な時制モデル
まとめ
3
15章 時間の伴う確率的推論
目次




時間の伴う確率推論
時制論理
-予測
-平滑化
-最尤の説明
代表的な時制モデル
まとめ
4
時間の伴う確率推論

14章ではP(X|E)を導く推論を行った
X:質問変数(観測不可能) E:証拠変数(観測可能)
-観測結果から観測できない事項の確率分布を導出

実際は時間tに伴い変化する場合が多い
-時制論理
15章ではP(Xt|Et)を導く推論を行う
5
時間推移の伴うベイジアンネット
(動的ベイジアンネット)

全てのtに対してP(Rt|Rt-1),P(Ut|Rt)は一定
P(R0)
P(R1|R0)
P(R2|R1)
Rain0
Rain1
Rain2
Umbrella0
Umbrella1
Umbrella2
P(U0|R0)
P(U1|R1)
P(U2|R2)
6
遷移モデルとセンサモデル

遷移モデル
-状態が時間経過とともにどう変化するかを表現
例:
Raint-1
Raint
一重マルコフ過程

Rt-1
t
f
P(rt)
0.7
0.3
センサモデル
-時間tにおける条件付き独立性を表現
例:
Raint
Umbrellat
Rt
t
f
P(ut)
0.9
0.2
7
15章 時間の伴う確率的推論
目次




時間の伴う確率推論
時制論理
-予測
-平滑化
-最尤の説明
代表的な時制モデル
まとめ
8
予測、平滑化、最尤の説明

予測:現在(時間t)までの事実から未来の状態を推定
あるk>0に対するP(Xt+k|e1:t)

平滑化:現在までの事実から過去の状態を推定
ある0≦k<tに対するP(Xk|e1:t)

最尤の説明:現在までの観測結果(観測列)を生成する
確率の最も高い状態列を求める
Maxx P(x1:t|e1:t)
9
時制論理の例題





日にちtにおいて雨が降っているかを知りたい
-P(Rt|Ut)を知りたい
外の様子が見えないが傘を観測可能
事前確率P(R0)=<0.5,0.5>
P(Rt|Rt-1)=<0.7,0.3>
P(Ut|Rt)=<0.9,0.2>
とする
10
15章 時間の伴う確率的推論
目次




時間の伴う確率推論
時制論理
-予測
-平滑化
-最尤の説明
代表的な時制モデル
まとめ
11
時間tからt+1の予測(1/2)

P(Xt+1|e1:t+1)=P(Xt+1|e1:t,et+1) (証拠の分割)
=αP(et+1|Xt+1,et)P(Xt+1|e1:t) (ベイズ規則)
=αP(et+1|Xt+1)P(Xt+1|e1:t) (eのマルコフ性)
フィルタリング
※マルコフ性
-未来の状態は過去の状態に依存せず
現在の状態のみに依存
12
時間tからt+1の予測(2/2)
• Xt+1をe1:tから求める
-Xt+1をe1:tに条件付けられたxtから求める
P(Xt+1|e1:t)=ΣP(Xt+1|xt)P(xt|e1:t)
xt
前向きメッセージ
P(Xt+1|e1:t+1)=αP(et+1|Xt+1)ΣP(Xt+1|xt)P(xt|e1:t)
xt
13
予測(例題:傘問題)(1/2)

t=0からt=1の予測は
P(R1)=ΣP(R1∧r0)=ΣP(R1|r0)P(r0)
r0
r0
=P(R1|r0)P(r0)+P(R1|¬r0)P(¬r0)
=<0.5,0.5>
より、t=1で傘を目撃した(u1)場合
P(R1|u1)=αP(u1|R1)P(R1) (ベイズ規則)
=α<0.9,0.2><0.5,0.5>≒<0.818,0.182>
14
予測(例題:傘問題)(2/2)

また,t=1からt=2の予測は
P(R2|u1)=P(R2|r1)P(r1|u1)+P(R2|¬r1)P(¬r1|u1)
=<0.7,0.3>×0.818+<0.3,0.7>×0.182
≒<0.627,0.373>
であり、t=2で傘を目撃した(u1)場合
P(R2|u1,u2)=αP(u2|R2)P(R2|u1) (予測の公式)
=α<0.9,0.2><0.627,0.373>≒<0.883,0.117>
15
15章 時間の伴う確率的推論
目次




時間の伴う確率推論
時制論理
-予測
-平滑化
-最尤の説明
代表的な時制モデル
まとめ
16
平滑化

P(Xk|e1:t)=P(Xk|e1:k,ek+1:t) (証拠の分割)
=αP(ek+1:t|Xk,e1:k)P(Xk|e1:k) (ベイズ規則)
=αP(ek+1:t|Xk)P(Xk|e1:k) (条件付き独立性)
P(ek+1:t|Xk)=ΣP(ek+1|xk+1)P(ek+2:t|xk+1)P(xk+1|Xk)
Xk+1
後ろ向きメッセージ
※P(ek+1:t|Xk,e1:k)=P(ek+1:t|Xk)P(ek+1:t|e1:k)
=P(ek+1:t|Xk) (時間tまでの証拠は既知)
17
平滑化(補足)
P(ek+1:t|Xk)=ΣP(ek+1:t|xk+1,Xk)P(xk+1|Xk)
=ΣP(ek+1:t|xk+1)P(xk+1|Xk)
(条件付き独立性+マルコフ性)
=ΣP(ek+1:t|xk+1)P(xk+1|Xk) (eの分割)
=ΣP(ek+1|xk+1)P(ek+2:t|xk+1)P(xk+1|Xk)
再帰呼び出し
18
15章 時間の伴う確率的推論
目次




時間の伴う確率推論
時制論理
-予測
-平滑化
-最尤の説明
代表的な時制モデル
まとめ
19
最尤の説明

max P(x1,・・・,xt,Xt+1|e1:t+1)
x1,・・・,xt
再帰呼び出し
=αP(et+1|Xt+1)
max{( P(Xt+1|Xt) max P(x1,・・・,xt-1|e1:t))}
xt
x1,・・・,xt-1
20
最尤の説明(例題)

例:傘の問題で観測列が[T,T,F,T,T]の時
P(x1,・・・,xt-1,Xt|e1:t)は以下の通りになる。
T
0.818
0.515
0.036
0.033
0.021
F
0.181
0.049
0.123
0.017
0.002
m1:1
m1:2
m1:3
m1:4
m1:5
この時,最尤列は[true,true,false,true,true]となる
21
15章 時間の伴う確率的推論
目次




時間の伴う確率推論
時制論理
-予測
-平滑化
-最尤の説明
代表的な時制モデル
まとめ
22
代表的な時制モデル
(研究対象)

隠れマルコフモデル(Hidden Marcov Model:HMM)
-音声認識や自然言語処理に使用

カルマンフィルタ
-物体の位置などを動的に推定(トラッキング)
・
X(t+⊿)=X(t)+X⊿ (位置の更新)

動的ベイジアンネット
23
隠れマルコフモデルを用いた
音声認識

英単語「tomato」に対する隠れマルコフモデル
1.0
[t]
1.0
[ow]
0.5
2
3
1.0
[t]
[m]
0.5
t= 1
[ey]
1.0
[aa]
1.0
4
5
発言者の発音の好みによって分岐
[ow]
6
24
15章 時間の伴う確率的推論
目次




時間の伴う確率推論
時制論理
-予測
-平滑化
-最尤の説明
代表的な時制モデル
まとめ
25
まとめ

時間の伴う確率推論では遷移モデルが加わる

予測(未来)・平滑化(過去)・最尤の説明(原因)

現在では隠れマルコフモデルやカルマンフィルタ
などの研究が進められている
26
ここまで15章
27
16章 単純な意思決定
目次





効用理論
効用理論の例題
多属性効用関数
情報の価値
まとめ
28
16章 単純な意思決定
目次





効用理論
効用理論の例題
多属性効用関数
情報の価値
まとめ
29
効用理論

効用とは
エージェントが望む基準を満たす能力の度合い
-例えば「少ない時間で目的地に着きたい」エージェントは
「20分で着くルート」より「10分で着くルート」を好む

効用関数:効用の度合いを関数で表現したもの
-U(A)で表現
30
期待効用

期待効用:効用関数の期待値を表現
-EU(A|E)=ΣP(Ri(A)|Do(A),E)U(Ri(A))
i
A:行為 E:証拠
P(Ri(A)|Do(A),E):Aを実行した時,結果iになる確率

最大期待効用の原理
-期待効用が最大になる動作を選ぶ
31
効用理論の基礎

合理的なエージェントが持つ選好に対する制約
A } B:エージェントはAをBより好む
-U(A)>U(B)
A~B:エージェントはAとBを同等に好む
-U(A)=U(B)
}
A ~ B:エージェントはAをBより好む
-U(A)≧U(B)
※本当は「}」ではなくて左の記号です
32
効用理論の公理(1/3)

順序性:どちらの方が望ましいか決める必要が
ある
(A } B)∨(A { B)∨(A~B)

推移律:AがBより好ましく、BがCより好ましい
とき、AはCより好ましくないといけない
(A } B)∧(B } C)⇒(A } C)
33
効用理論の公理(2/3)

連続性:Bの好ましさがAとCの間にある時
「確実にBになること」と
「確率pでA,確率1-pでCになるくじを引くこと」を
同様に好むようなpが存在する
A } B } C ⇒ ∃p[p,A; 1-p,C] ~ B

置換可能性:AとBを同様に好むなら、あるAとCのくじに
おいて、AにBを代入しただけであれば
両者を同様に好む
A ~ B ⇒ [p,A; 1-p,C] ~ [p,B; 1-p,C]
34
効用理論の公理(3/3)

単調性:同じ2つの結果AとBを持つ確率の違う2つの
くじを考えたとき、
AをBより好む時Aになる確率の多いくじを好ま
なくてはならない
A } B ⇒ (p≧q ⇔ [p,A; 1-p,B] } [q,A; 1-q,B])

分解可能性:複合(二重)くじは確率の法則でより簡単な
くじに分解可能
[p,A; 1-p,[q,B;1-q,C] ] ~ [p,A; (1-p)q,B; (1-p)(1-q),C]
35
16章 単純な意思決定
目次





効用理論
効用理論の例題
多属性効用関数
情報の価値
まとめ
36
効用理論の例題(例:金銭の効用)

例:あるゲームに優勝して賞金を貰うとする
あなたは100万円をそのまま受け取るか
ギャンブルにチャレンジすることができる
コインを投げて表なら賞金が300万円になり
裏なら賞金が0円になる
この時、ギャンブルをすべきかどうかを考える
37
期待金銭価値
(Expected Monetary Value:EMV)

金銭に関する期待値
-EMV(Accept)=½×0+½×3000000=1500000
-EMV(Decline)=1000000
EMV(Accept)>EMV(Decline)

よってギャンブルを受けたほうがいい?
-所有財産にも依存する可能性がある
所有財産nの状態をSnとする
38
期待効用の計算

所有財産がkの時の期待効用は
-EU(Accept)=½U(Sk)+½U(Sk+3000000)
-EU(Decline)= U(Sk+1000000)

ある人(所有財産k)にとっての効用関数(賞金の価値)が
U(Sk+n)=log(n)だと仮定する(人によって異なる)と
-EU(Accept)≒0.5+3.24=3.74
-EU(Decline)=6
とギャンブルを受けない方がいい場合もある
39
リスク

U(Sk+n)は人によって異なる
-借金が無い及び少ない人(-1000000≦k)は
リスクを負いたくない
リスク忌避的
-借金まみれで絶望的な人(k<-1000000)は
リスクを負ってでも大金を得たい
リスク指向
40
確実等価・保険料

確実等価:くじを引く代わりに得られる価値
-ほとんどの人は0円か100万円の半々の賭けより
確実に取れる40万円を選ぶ
・この場合の確実等価な額は40万円である

保険料:期待金銭価値と確実等価の差
-保険業はリスク回避という考え方で成立
保険料-期待損害額=保険業の利益
41
16章 単純な意思決定
目次





効用理論
効用理論の例題
多属性効用関数
情報の価値
まとめ
42
多属性効用関数

決定するための要素(属性)が複数ある効用関数
-例:新たな空港建設地の決定
・騒音(Noise)
・費用(Cost)
・安全性(Death) etc
U(Noise,Cost,Death)

候補地S1,S2から効用の多い方を選好
43
確率的な優位性

確率分布を用いることで選択肢を絞り込む
-例:候補地の費用(Cost)について
・S1は28~48億円間の一様分布で決まる
・S2は30~52億円間の一様分布で決まる
S1はS2に
確率的に優位
S1
確
率
S2
Cost
S2を棄却
44
意思決定ネットワーク(影響図)

多属性効用における関係を表現
立地の選択
意思決定ノード
交通状況
Death
訴訟
Noise
空港の建設
Cost
確率ノード
(現在の状態)
確率ノード
(将来の状態)
効用ノード
U
45
意思決定ネットワークでの評価

現在の状態に対する証拠変数の設定
-交通状況・訴訟・空港の建設に対する証拠

意思決定ノードの可能な値それぞれに対して
(a)その値を意思決定ノードに設定(noise=80 etc)
(b)P(x|e)を求める(確率推論アルゴリズム)
(c)その結果を用いて効用を計算(EU(noise))

最大効用をもつ行為を返す
46
16章 単純な意思決定
目次





効用理論
効用理論の例題
多属性効用関数
情報の価値
まとめ
47
情報の価値

可能な限りの情報を得ることが不可能なことがある
-例:時間に猶予の無い患者etc
エージェントが獲得すべき情報を選択
・情報の価値付け(情報への対価)
48
情報の価値(例題)(1/2)




あなたはn個のくじから1つだけ引く(参加費C/n円)
当たりは1つでそれを引くと賞金C円貰える
あなたは主催者に
「くじ3は当たりなのか」を聞くとする
あなたはその情報にいくら支払うべきかを考える
49
情報の価値(例題)(2/2)

1/n(※1)の確率で「くじ3は当たり」だとわかる
-あなたの利益はC-C/n (※2)円となる

(n-1)/n (※3)の確率で「くじ3は外れ」だとわかる
-選択肢がn-1個に減ったので
あなたの期待利益はC/(n-1)-C/n (※4)円となる
よって、この質問結果が与えられた時の期待効用は
(※1)×(※2)+(※3)×(※4)=C/n 情報の価値
50
16章 単純な意思決定
目次





効用理論
効用理論の例題
多属性効用関数
情報の価値
まとめ
51
まとめ




エージェントは効用が最も高い選択を取る
意思決定には期待値だけでなくリスクも影響する
選択基準(属性)が複数の場合でも推定可能
-確率的な優位(+厳密な優位性)
-意思決定ネットワーク
意思決定能力に「情報の価値」を付加することで柔
軟性の高い(エキスパート)システムを実現
52
ダウンロード

15章&16章