エージェントアプローチ 人工知能 B4　片渕　聡.

Presentation on theme: "エージェントアプローチ 人工知能 B4　片渕　聡."— Presentation transcript:

1 エージェントアプローチ 人工知能 B4　片渕　聡

2 目次 １５章　時間の伴う確率的推論 １６章　単純な意思決定

3 １５章　時間の伴う確率的推論 目次 時間の伴う確率推論 時制論理 　　－予測 　　－平滑化 　　－最尤の説明 代表的な時制モデル まとめ

4 １５章　時間の伴う確率的推論 目次 時間の伴う確率推論 時制論理 　　－予測 　　－平滑化 　　－最尤の説明 代表的な時制モデル まとめ

5 時間の伴う確率推論 １４章ではP(X|E)を導く推論を行った X:質問変数(観測不可能) E:証拠変数(観測可能)
　 －観測結果から観測できない事項の確率分布を導出 実際は時間tに伴い変化する場合が多い 　　－時制論理 　　１５章ではP(Xt|Et)を導く推論を行う

6 時間推移の伴うベイジアンネット （動的ベイジアンネット）
全ての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)

7 遷移モデルとセンサモデル 遷移モデル センサモデル Rt-1 P(rt) t f 0.7 0.3 Rt P(ut) t f 0.9 0.2
　　－状態が時間経過とともにどう変化するかを表現 センサモデル 　　－時間tにおける条件付き独立性を表現 Rt-1 P(rt) t f 0.7 0.3 例： Raint-1 Raint 一重マルコフ過程 Rt P(ut) t f 0.9 0.2 例： Raint Umbrellat

8 １５章　時間の伴う確率的推論 目次 時間の伴う確率推論 時制論理 　　－予測 　　－平滑化 　　－最尤の説明 代表的な時制モデル まとめ

9 予測、平滑化、最尤の説明 予測：現在(時間t)までの事実から未来の状態を推定 あるk>0に対するP(Xt+k|e1:t)
平滑化：現在までの事実から過去の状態を推定 　　　　　ある0≦k＜tに対するP(Xk|e1:t) 最尤の説明：現在までの観測結果(観測列)を生成する 　　　　　　　　　　確率の最も高い状態列を求める　 　　　　　 Maxx P(x1:t|e1:t) 時制論理において推定できること

10 時制論理の例題 日にちtにおいて雨が降っているかを知りたい －P(Rt|Ut)を知りたい 外の様子が見えないが傘を観測可能
P(Rt|Rt-1)=<0.7,0.3> P(Ut|Rt)=<0.9,0.2> 　　とする

11 １５章　時間の伴う確率的推論 目次 時間の伴う確率推論 時制論理 　　－予測 　　－平滑化 　　－最尤の説明 代表的な時制モデル まとめ

12 時間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のマルコフ性) ※マルコフ性 　　－未来の状態は過去の状態に依存せず 　　　　現在の状態のみに依存 フィルタリング

13 時間tからt+1の予測(2/2) P(Xt+1|e1:t+1)=αP(et+1|Xt+1)ΣP(Xt+1|xt)P(xt|e1:t)
　　　 －Xt+1をe1:ｔに条件付けられたxtから求める 　　　P(Xt+1|e1:t)=ΣP(Xt+1|xt)P(xt|e1:t) P(Xt+1|e1:t+1)=αP(et+1|Xt+1)ΣP(Xt+1|xt)P(xt|e1:t) xt 前向きメッセージ xt

14 予測(例題：傘問題)(1/2) t=0からt=1の予測は より、t=1で傘を目撃した(u1)場合
　　 P(R1)=ΣP(R1∧r0)=ΣP(R1|r0)P(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> r0 r0

15 予測(例題：傘問題)(2/2) また,t=1からt=2の予測は であり、t=2で傘を目撃した(u1)場合
　　 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>

16 １５章　時間の伴う確率的推論 目次 時間の伴う確率推論 時制論理 　　－予測 　　－平滑化 　　－最尤の説明 代表的な時制モデル まとめ

17 平滑化 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) ※P(ek+1:t|Xk,e1:k)=P(ek+1:t|Xk)P(ek+1:t|e1:k) 　　　　　　　　　　 =P(ek+1:t|Xk) (時間tまでの証拠は既知) Xk+1 後ろ向きメッセージ

18 平滑化（補足） 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) 再帰呼び出し

19 １５章　時間の伴う確率的推論 目次 時間の伴う確率推論 時制論理 　　－予測 　　－平滑化 　　－最尤の説明 代表的な時制モデル まとめ

20 最尤の説明 max P(x1,・・・,xt,Xt+1|e1:t+1) =αP(et+1|Xt+1)
　　　max{( P(Xt+1|Xt) max P(x1,・・・,xt-1|e1:t))} x1,・・・,xt 再帰呼び出し xt x1,・・・,xt-1 フィルタリングの式から「Σをmaxに変えた」＋「右端の部分を変えた」もの

21 この時,最尤列は[true,true,false,true,true]となる
最尤の説明（例題） 例：傘の問題で観測列が[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]となる

22 １５章　時間の伴う確率的推論 目次 時間の伴う確率推論 時制論理 　　－予測 　　－平滑化 　　－最尤の説明 代表的な時制モデル まとめ

23 代表的な時制モデル (研究対象) 隠れマルコフモデル(Hidden Marcov Model:HMM) －音声認識や自然言語処理に使用
　　－音声認識や自然言語処理に使用 カルマンフィルタ 　　－物体の位置などを動的に推定(トラッキング) 　　　　X(t+⊿)=X(t)+X⊿　（位置の更新） 動的ベイジアンネット ・

24 隠れマルコフモデルを用いた 音声認識 英単語「tomato」に対する隠れマルコフモデル t = 1 2 3 4 5 6
1.0 [ey] 0.5 1.0 1.0 1.0 [t] [ow] [t] [ow] [m] 0.5 [aa] 1.0 t = 発言者の発音の好みによって分岐

25 １５章　時間の伴う確率的推論 目次 時間の伴う確率推論 時制論理 　　－予測 　　－平滑化 　　－最尤の説明 代表的な時制モデル まとめ

26 まとめ 時間の伴う確率推論では遷移モデルが加わる 予測(未来)・平滑化(過去)・最尤の説明(原因)
現在では隠れマルコフモデルやカルマンフィルタなどの研究が進められている

27 ここまで１５章

28 １６章　単純な意思決定 目次 効用理論 効用理論の例題 多属性効用関数 情報の価値 まとめ

29 １６章　単純な意思決定 目次 効用理論 効用理論の例題 多属性効用関数 情報の価値 まとめ

30 効用理論 効用とは －例えば「少ない時間で目的地に着きたい」エージェントは 効用関数：効用の度合いを関数で表現したもの －U(A)で表現
　　エージェントが望む基準を満たす能力の度合い 　　－例えば「少ない時間で目的地に着きたい」エージェントは 　　　　　「２０分で着くルート」より「１０分で着くルート」を好む 効用関数：効用の度合いを関数で表現したもの 　　－U(A)で表現

31 期待効用 期待効用：効用関数の期待値を表現 －EU(A|E)=ΣP(Ri(A)|Do(A),E)U(Ri(A)) A:行為 E:証拠
　　　P(Ri(A)|Do(A),E)：Aを実行した時,結果iになる確率 最大期待効用の原理 　　－期待効用が最大になる動作を選ぶ i

32 効用理論の基礎 合理的なエージェントが持つ選好に対する制約 A ｝ B：エージェントはAをBより好む －U(A)＞U(B)
} ~ ※本当は「}」ではなくて左の記号です

33 効用理論の公理(1/3) 順序性：どちらの方が望ましいか決める必要がある (A } B)∨(A { B)∨(A~B)
推移律：AがBより好ましく、BがCより好ましい 　　　　　　とき、AはCより好ましくないといけない 　　 (A } B)∧(B } C)⇒(A } C)

34 効用理論の公理(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]

35 効用理論の公理(3/3) 単調性：同じ２つの結果AとBを持つ確率の違う２つの くじを考えたとき、
　　　　　　　くじを考えたとき、 　　　　　　　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]

36 １６章　単純な意思決定 目次 効用理論 効用理論の例題 多属性効用関数 情報の価値 まとめ

37 効用理論の例題（例：金銭の効用） 例：あるゲームに優勝して賞金を貰うとする あなたは100万円をそのまま受け取るか
　　　あなたは100万円をそのまま受け取るか 　　　ギャンブルにチャレンジすることができる 　　　コインを投げて表なら賞金が300万円になり 　　　裏なら賞金が０円になる 　この時、ギャンブルをすべきかどうかを考える

38 期待金銭価値 (Expected Monetary Value:EMV)
金銭に関する期待値 　　－EMV(Accept)=½×0+½× = 　　－EMV(Decline)= 　　　　EMV(Accept)＞EMV(Decline) よってギャンブルを受けたほうがいい？ 　　－所有財産にも依存する可能性がある 　　　　所有財産nの状態をSnとする

39 期待効用の計算 所有財産がkの時の期待効用は －EU(Accept)=½U(Sk)+½U(Sk+3000000)
　　－EU(Decline)= U(Sk ) ある人(所有財産k)にとっての効用関数(賞金の価値)が 　　U(Sk+n)=log(n)だと仮定する(人によって異なる)と 　　　－EU(Accept)≒ =3.74 　　　－EU(Decline)=6 　　とギャンブルを受けない方がいい場合もある

40 リスク U(Sk+n)は人によって異なる －借金が無い及び少ない人(-1000000≦k)は リスクを負いたくない リスク忌避的
　　　　リスクを負いたくない 　　　　リスク忌避的 　　－借金まみれで絶望的な人(k＜ )は 　　　　リスクを負ってでも大金を得たい 　　　　リスク指向

41 確実等価・保険料 確実等価：くじを引く代わりに得られる価値 －ほとんどの人は0円か100万円の半々の賭けより 確実に取れる40万円を選ぶ
　　－ほとんどの人は0円か100万円の半々の賭けより 　　　　確実に取れる40万円を選ぶ 　　　　・この場合の確実等価な額は４０万円である 保険料：期待金銭価値と確実等価の差 　　－保険業はリスク回避という考え方で成立 　　　　保険料-期待損害額=保険業の利益

42 １６章　単純な意思決定 目次 効用理論 効用理論の例題 多属性効用関数 情報の価値 まとめ

43 多属性効用関数 U(Noise,Cost,Death) 候補地S1,S2から効用の多い方を選好
決定するための要素（属性）が複数ある効用関数 　　－例：新たな空港建設地の決定 　　　　　　　・騒音(Noise) 　　　　　　　・費用(Cost) 　　　　　　　・安全性(Death) etc 　　　　　　　　U(Noise,Cost,Death) 候補地S1,S2から効用の多い方を選好

44 確率的な優位性 確率分布を用いることで選択肢を絞り込む S1はS2に 確率的に優位 S2を棄却 －例：候補地の費用(Cost)について

45 意思決定ネットワーク(影響図) 多属性効用における関係を表現 意思決定ノード 立地の選択 交通状況 Death 効用ノード U 訴訟
Noise 空港の建設 Cost 確率ノード (現在の状態) 確率ノード (将来の状態)

46 意思決定ネットワークでの評価 現在の状態に対する証拠変数の設定 意思決定ノードの可能な値それぞれに対して 最大効用をもつ行為を返す
　 －交通状況・訴訟・空港の建設に対する証拠 意思決定ノードの可能な値それぞれに対して 　　(a)その値を意思決定ノードに設定(noise=80 etc) 　　(b)P(x|e)を求める(確率推論アルゴリズム) 　　(c)その結果を用いて効用を計算(EU(noise)) 最大効用をもつ行為を返す

47 １６章　単純な意思決定 目次 効用理論 効用理論の例題 多属性効用関数 情報の価値 まとめ

48 情報の価値 可能な限りの情報を得ることが不可能なことがある －例：時間に猶予の無い患者etc エージェントが獲得すべき情報を選択
　　エージェントが獲得すべき情報を選択 　　　　　・情報の価値付け(情報への対価)

49 情報の価値（例題）(1/2) あなたはn個のくじから１つだけ引く(参加費C/n円) 当たりは１つでそれを引くと賞金C円貰える
あなたは主催者に 　　「くじ3は当たりなのか」を聞くとする あなたはその情報にいくら支払うべきかを考える

50 情報の価値（例題）(2/2) 1/n(※1)の確率で「くじ3は当たり」だとわかる －あなたの利益はC-C/n (※２)円となる
(n-1)/n (※３)の確率で「くじ３は外れ」だとわかる 　　－選択肢がn-1個に減ったので 　　　あなたの期待利益はC/(n-1)-C/n (※４)円となる よって、この質問結果が与えられた時の期待効用は 　　　(※１)×(※2)+(※3)×(※4)=C/n 情報の価値

51 １６章　単純な意思決定 目次 効用理論 効用理論の例題 多属性効用関数 情報の価値 まとめ

52 まとめ エージェントは効用が最も高い選択を取る 意思決定には期待値だけでなくリスクも影響する 選択基準(属性)が複数の場合でも推定可能
　　－確率的な優位(+厳密な優位性) 　　－意思決定ネットワーク 意思決定能力に「情報の価値」を付加することで柔軟性の高い(エキスパート)システムを実現