エージェントアプローチ 人工知能 B4 片渕 聡 1 目次 １７章 複雑な意思決定 １８章 経験からの学習 2 １７章 時間の伴う確率的推論 目次 逐次意思決定問題 マルコフ意思決定過程 価値反復 方策反復 部分マルコフ意思決定過程 ゲーム理論 まとめ 3 １７章 時間の伴う確率的推論 目次 逐次意思決定問題 マルコフ意思決定過程 価値反復 方策反復 部分マルコフ意思決定過程 ゲーム理論 まとめ 4 逐次意思決定問題 １６章では１回限りの意思決定について扱った －効用理論 １７章では逐次意思決定問題を扱う －効用を用いて一連の動作を決定 5 逐次意思決定問題 （例題：４×３問題） -0.04 (報酬) -0.04 S -0.04 -0.04 -0.04 -0.04 -0.04 -0.04 G +1 G -1 -0.04 意図した方向 0.8 0.1 0.1 環境：完全観測可能 環境全体及び自分の位置を知ることができる 6 １７章 時間の伴う確率的推論 目次 逐次意思決定問題 マルコフ意思決定過程 価値反復 方策反復 部分マルコフ意思決定過程 ゲーム理論 まとめ 7 マルコフ意思決定過程 完全観測可能な環境での逐次意思決定問題 －初期状態：S0 －遷移モデル：T(s,a,s’) 状態sから行動aが行われた時,状態s’に遷移する確率 －報酬関数(各状態での報酬を規定)：R(s) 状態sにおける報酬 8 方策 エージェントが何をすべきなのかを示す π(s):状態sにおいて方策πが推奨する行動 最適方策 －環境の履歴に対する期待効用が最大となる方策 現在の知覚を元に行動π*(s)を実行 9 リスクと報酬のバランス 現在のR(s)の範囲によって最適方策が異なる －動き続けるのがつらい時(R(s)≦-1.63) 「-1」のゴールであろうと出口に向かう －あまり動きたくない時(-0.43≦R(s)≦-0.09) リスクを冒してでも「+1」のゴールに向かう(リスク指向) －動いても問題がない時(R(s)>-0.02) 「-1」のゴールだけは避けたい(リスク忌避的) 10 逐次意思決定問題の効用 報酬関数から効用関数を求める２つの方法がある －加法的報酬：報酬関数の単純な加算 Uh([s0,s1,…])=R(s0)+R(s1)+R(s２)+… －割引報酬：割引率γ(0~1)の採用 Uh([s0,s1,…])=R(s0)+γR(s1)+γ²R(s２)… 割引報酬は選好に良い結果を齎すことが多い 11 １７章 時間の伴う確率的推論 目次 逐次意思決定問題 マルコフ意思決定過程 価値反復 方策反復 部分マルコフ意思決定過程 ゲーム理論 まとめ 12 価値反復 各状態の効用を計算して最適方策を導出 －最大期待効用の原理を利用 次状態の期待効用の最大化 EUπ*(s’)=maxΣT(s,a,s’)U(s’) a s’ (状態sにおける効用値) = (状態sの報酬) + (次の状態の割引期待効用) U(s)=R(s)+γEUπ*(s’) Bellman方程式 13 価値反復アルゴリズム 状態ｓにおける効用値の更新 Ui+1(s)R(s)+γmaxΣT(s,a,s’)Ui(s’) a s’ Bellman更新 14 １７章 時間の伴う確率的推論 目次 逐次意思決定問題 マルコフ意思決定過程 価値反復 方策反復 部分マルコフ意思決定過程 ゲーム理論 まとめ 15 方策反復 次の２つのステップを反復して実行 －方策評価 ・方策πiを行ったと仮定した時の効用Ui=Uπiを計算 －方策改善 ・ 効用Uiを用いて新しい方策πi+1を計算 s’ Ui(s)=R(s)+γΣT(s, πi ,s’)Ui(s’) 16 価値反復と方策反復の相違 最適方策の導出法 価値反復：全ての効用値からMaxを導出 方策反復：ある方策から徐々に改善 性能差 計算量の少なさ 価値反復＜方策反復 17 １７章 時間の伴う確率的推論 目次 逐次意思決定問題 マルコフ意思決定過程 価値反復 方策反復 部分マルコフ意思決定過程 ゲーム理論 まとめ 18 部分マルコフ意思決定過程 （Partically Obsevable MDP;POMDP） 部分観測可能な環境での逐次意思決定問題 －自分の現在の状態を把握できないetc 遷移モデル：T(s,a,s’) 報酬関数：R(s) 観測モデル：O(s,o) －状態sにおける観測結果oを知覚する確率 信念状態：b －全ての可能な状態における確率分布 例：b(s0)=<1/9,1/9,1/9,1/9,1/9,1/9,1/9,1/9,1/9,0,0> 19 POMDPの意思決定プロセス 行動aを起こすと信念状態は変化 新しい信念状態b’(s’)の導出 b’(s’)=αO(s’,o)ΣT(s,a,s’)b(s) s POMDPの意思決定サイクル １．現在の信念状態bからa=π*(b)を導出 ２．観測結果oを受け取る ３．上記の式より新たな信念状態b’を導出 ４．１～３を繰り返す 20 １７章 時間の伴う確率的推論 目次 逐次意思決定問題 マルコフ意思決定過程 価値反復 方策反復 部分マルコフ意思決定過程 ゲーム理論 まとめ 21 ゲーム理論 複数のエージェントが相互作用する環境での意思決定 －競売、国防etc エージェント設計 －エージェントの決定を解析し最適方策を導出 機構設計 －複数のエージェント間の相互作用のルールを定義 ・マルチエージェントシステムの構築に利用可能 22 １７章 時間の伴う確率的推論 目次 逐次意思決定問題 マルコフ意思決定過程 価値反復 方策反復 部分マルコフ意思決定過程 ゲーム理論 まとめ 23 まとめ 逐次意思決定問題：一連の動作の決定 マルコフ意思決定過程 －完全観測可能な環境における逐次意思決定問題 価値反復 方策反復 部分マルコフ意思決定過程 －自分の状態を把握できない中での意思決定 24 ここまで１７章 25 １８章 経験からの学習 目次 学習とは 帰納学習 決定木の学習 アンサンブル学習 計算論的学習理論 まとめ 26 １８章 経験からの学習 目次 学習とは 帰納学習 決定木の学習 アンサンブル学習 計算論的学習理論 まとめ 27 機械学習とは 人間と同様な学習能力を機械で実現する技術 －行動結果及びサンプルデータを解析 －有用な規則を導く －エージェントの行動を改善 28 学習の形式 教師あり学習 －入出力事例から「関数」を導き出す 例：IF-THENルール 教師なし学習 －入出力事例の無い状態から入力パターンを解析 強化学習(２１章) －行動結果(報酬)から効用関数の要素を導き出す 29 １８章 経験からの学習 目次 学習とは 帰納学習 決定木の学習 アンサンブル学習 計算論的学習理論 まとめ 30 帰納学習 教師あり学習では特定の入出力例から関数を導く －対(x,f(x)) (x:入力 f:関数) 帰納学習 －fの例集合に対して近似する関数h(仮説)を求める よい近似かを判断するのは困難 同じ入出力例から複数の関数を得てしまう 31 オッカムの剃刀 入出力例に無矛盾な仮説のうち 最も簡潔な仮説が好ましいという考え方 ・同じ例に対して複数の仮説が存在する時は 最も単純な仮説を選ぶ ※選んだ仮説が正しいとは限らない 32 １８章 経験からの学習 目次 学習とは 帰納学習 決定木の学習 アンサンブル学習 計算論的学習理論 まとめ 33 決定木 入出力事例をグラフで表現 －例：レストランで待つかどうかの決定木 客の入り 皆無 No 属性 入力値 満員 そこそこ 待ち時間 Yes ２０分以上 腹具合 Yes No ２０分以内 Yes 出力値 No Yes 34 決定木の学習 入出力例から決定木を生成 レストラン問題の 入出力例 例 X1 X2 X3 X4 X5 X6 X7 客 None Full None Some Full Full Some 待 20↓ 20↓ 20↓ 20↓ 20↑ 20↑ 20↓ 腹 No No Yes Yes Yes No No 出力 No Yes No Yes No Yes Yes 35 決定木の生成(1/2) 根ノード属性の選択 －最も分類を促進するノード（深さの最小化を目指す） 悪いノード 良いノード 腹具合 Yes 客の入り No No Yes X3, X4 X5 X1, X2 X6, X7 出力がばらばら No X1, X3 Yes 属性2 X4, X7 X2,X6, X5 出力がある程度まとまってる 36 決定木の生成(1/2) 入出力例から生成された決定木 客の入り No X1, X3 腹具合 Yes X4, X7 実際の決定木と異なる No Yes X5 X2,X6 37 属性選択 属性選択に用いるノード=情報量の最小となるノード n －情報量：I(P(v1,…,vn))=Σ(-P(vi)log2P(vi)) i=1 表裏が公平なコインの場合情報量 －I(½,½)=-½log2½-½log2½=1(bit) 38 アルゴリズムの性能評価 １．例をたくさん集める ２．それを訓練集合とテスト集合の２つの排反集合に分別 －訓練集合：仮説Hを生成に用いる －テスト集合：Hが正しいか検査するテストに用いる ３．学習アルゴリズムを訓練集合に適用して仮説Hを生成 ４．Hによって正しく分類されたテスト集合の百分率をとる ５．訓練集合の大きさ及び例を変えて2~4を繰り返す。 テスト 成功率 訓練集合のサイズ 39 １８章 経験からの学習 目次 学習とは 帰納学習 決定木の学習 アンサンブル学習 計算論的学習理論 まとめ 40 アンサンブル学習 複数の予測結果から多数決で最良の予測値を決める －例：同一の訓練集合から百個の異なる決定木を生成 新しい例がきた時、 Yesを返す決定木が60個 Noを返す決定木が40個の場合 この例の予測値はYesとする 仮説が１つの時と比べ誤分類する確率は大幅に減少 41 ブースティング法 アンサンブル法の代表的な手法 －ある訓練集合を元に仮説H1を生成 －その訓練集合でH1の検査を行う ・正しく分類された例には重みwを少なくする ・誤分類された例には重みwを多くする －分類成功率から仮説H1じたいにも重みzをつける －重み付けされた訓練集合からH2を作成 －同様の操作を行い仮説をN個作成 －重みzの最も高い仮説を返す 42 １８章 経験からの学習 目次 学習とは 帰納学習 決定木の学習 アンサンブル学習 計算論的学習理論 まとめ 43 計算論的学習理論 学習における計算量や仮説モデルの表現力を研究 一般的に 仮説モデルの表現力（精度・誤分類率の低さ） トレードオフ サンプル計算量(例の個数)・時間計算量 44 １８章 経験からの学習 目次 学習とは 帰納学習 決定木の学習 アンサンブル学習 計算論的学習理論 まとめ 45 まとめ 学習の形式は教師あり、教師なし、強化学習 帰納学習は例に無矛盾な仮説を求める －オッカムの剃刀 決定木により単純かつ無矛盾な仮説が求まる アンサンブル学習は単独の学習より精度が良い －ブースティング法 仮説の精度と計算量間にはトレードオフが存在 46
© Copyright 2024 ExpyDoc
