![強化学習の定式化
26
? ??, ??, ???? に従う確率過程（マルコフ決定過程）を考える
? 価値関数：ステップ??から始まる報酬和の期待値
? 目的：価値関数を最大化する方策???
を獲得
???? ??1
|??0
, ??0
状態??0
で行動??0
をとったとき状態??1
に遷移する状態遷移確率
状態??1
??1
??2
??3
?? ??0|??0
状態??0
で行動??0
を
選択する方策関数
??1
行動??0
??2
??3
?? ??1|??1
状態??1
に遷移したときの報酬
????
??
(??) = Ε
?? ????|????
????(????+1|????,????)
??
??=??
??
??????? ?? ????, ????, ????+1 ???? = ??
?? ∈ (0,1] ：割引率
遠い先の報酬ほど割り引く
??1
??2
??3
初期状態??0
??1
= ?? ??1
, ??1
, ??2
状態?? ??+1
??1
??2
??3
??0
= ?? ??0
, ??0
, ??1
状態??2
に遷移したときの報酬
??? = argmax
??
????
0
(??)](https://image.slidesharecdn.com/ai20186rlbasic-181114041115/85/2018-6-21-320.jpg)
人工知能2018 6 强化学习の基础
- 1. 人工知能 第6回 強化学習入門 2018年5月25日 八谷 大岳 1
- 3. 内容 8 ? 教師あり学習 ? 教師あり学習の例と問題点 ? 強化学習 ? 強化学習の目的と成功例 ? 動物の行動学習 ? 強化学習の定式化 ? 動的計画法による最適化
- 4. 機械学習手法の種類 9 ? 問題（データの条件など）と目的に合わせて適切な 機械学習方法を選択する必要がある 問題 定義 代表的な方法 応用例 教師あり学習 入力と出力のデータに基づき、 入力を出力に変換する関数を 学習 SVM, 最小二乗法、 決定木、ランダム フォーレストなど スパム分類、顔検出、一 般物体認識、将棋局面 の評価など 教師なし学習 入力のみの事例に基づき、 入力の特性 （パターン、構造） を学習 PCA, LDA、HMMなど データの可視化 （クラスタリング、次元圧 縮） 半教師学習 入力のうち部分的に付与された 出力の事例に基づき 入力を出力に変換する関数を 学習 transductiveSVM, Laplacian SVMなど 画像、音声、Webログな どの大量データで、コス トの問題で一部のデータ のみしか出力（答え）が 付与されていない場合 強化学習 入力と、出力に対する報酬 （評価）のデータに基づき、 入力を出力に変換する関数を 学習 Q-learning、policy iteration, policy gradient ロボット制御、Web広告 選択、マーケティング
- 5. ロボット制御での教師あり学習 10 ? 方策関数（policy）：状態??を行動??に変換する関数 ? 教師あり学習：各状態??で取るべき正しい行動??のデータを用意 ? 目標：各状態で取るべき正しい行動を再現する方策?? ?? を獲得 出力：行動??入力：状態?? ?? = ?? ?? センサ アクチュエータ ??0 , ??0 , ??1 , ??1 , … , ?? ?? , ?? ?? = (???? , ???? ) ??=0 ??
- 6. 制御の例：Ball in a cup（けん玉） 11 ? 目標：ロボットにボールをカップの中に入れる方策?? ?? を獲得 ボール カップ ロボットアーム
- 7. 教師データの収集 12 ? 状態と行動の組のデータ： (????, ????) ??=0 ?? を収集 ? 状態?? ：各関節の角度?角速度、 行動?? ：各関節に加えるトルク量 ドイツ?マックスプランク研究所
- 8. 教師あり学習（回帰） 13 ? 学習データを用いて二乗誤差和を最小化する 方策関数???(??)を学習 人の教示による方策関数 状態?? 行動?? 学習する方策関数 ???(??) min ? ??=1 ?? ???? ? ???(????) 2 ??(??) 誤差 ? ???? ??1 ??2 ??1 ??2 ???? ????, ???? ??=1 ?? 学習データ：
- 10. 教師あり学習の問題点 15 ? 学習に十分な教師データを収集するのは困難 ? 教師データ数は最低でも学習パラメータの十数倍は必要 ? 教師データを用意するのは人なので、時間および人件費が大 ? 教師データが不正確（特にロボットでは） ? 人間とロボットでは、骨格、筋肉配置が異なるため、ロボットにとって 最適なダイナミックな行動（関節のトルク）を教えるのが困難 ? 人間の知識の限界 ? 人間が必ずしも最適な方法を知っているとは限らない 学習した方策関数： 良くて人間の模倣、コンピュータにとって最適とは限らない
- 11. 内容 16 ? 教師あり学習 ? 教師あり学習の例と問題点 ? 強化学習 ? 強化学習の目的と成功例 ? 動物の行動学習 ? 強化学習の定式化 ? 動的計画法による最適化
- 12. 機械学習手法の種類 17 ? 問題（データの条件など）と目的に合わせて適切な 機械学習方法を選択する必要がある 問題 定義 代表的な方法 応用例 教師あり学習 入力と出力のデータに基づき、 入力を出力に変換する関数を 学習 SVM, 最小二乗法、 決定木、ランダム フォーレストなど スパム分類、顔検出、一 般物体認識、将棋局面 の評価など 教師なし学習 入力のみの事例に基づき、 入力の特性 （パターン、構造） を学習 PCA, LDA、HMMなど データの可視化 （クラスタリング、次元圧 縮） 半教師学習 入力のうち部分的に付与された 出力の事例に基づき 入力を出力に変換する関数を 学習 transductiveSVM, Laplacian SVMなど 画像、音声、Webログな どの大量データで、コス トの問題で一部のデータ のみしか出力（答え）が 付与されていない場合 強化学習 入力と、出力に対する報酬 （評価）のデータに基づき、 入力を出力に変換する関数を 学習 Q-learning、policy iteration, policy gradient ロボット制御、Web広告 選択、マーケティング
- 13. 強化学習の目標 18 ? 人間が十分なデータを用意できない問題を解決 ? ロボット制御 ? Web広告の選択 ? 人間を超える新しい戦略の発見 ? 商品の販売戦略 ? 新薬の開発 ? 機械学習アルゴリズムの開発 ? 将棋、囲碁、ゲームの戦略
- 14. 強化学習のゲームにおける成功例 19 ? 将棋：2013年の電王戦（現役プロとコンピュータとの対局）にて コンピュータが3勝１敗１分けで勝ち越し ? 囲碁：2016年3月、Google DeepMind社の「Alpha Go」が世界 No.2の韓国の李セドル氏に4勝1敗の大差で勝利 ? 強化学習アルゴリズム同士の対戦を繰り返すことにより、人間が数千年 かけても見つけられなかった「定石」を発見 動画：https://newswebeasy.github.io/ja201710/news/web/movie/2017/10/19/k10011182291_201710190529_201710190530.mp4
- 15. 内容 20 ? 教師あり学習 ? 教師あり学習の例と問題点 ? 強化学習 ? 強化学習の目的と成功例 ? 動物の行動学習 ? 強化学習の定式化 ? 動的計画法による最適化
- 16. 動物の行動学習：試行錯誤学習 21 ? 心理学の行動主義者の学習の定義 ? 行動や反応の変化として表れ、外部から観察できる現象 ? 試行錯誤学習 Edward Thorndike（1874年?1949年） 迷路のような箱の中で，猫は試行錯誤的に様々な行動を取る。 偶然にでも外に出る行動を取り，それを何度か繰り返すと， やがて同じ行動が出現する頻度が高くなることを実験的に確認 猫が様々な行動をとる 偶然に外に出られた 強くなるロボティック?ゲームプレイヤーの作り方 八谷、杉山 2016 また箱にいれる 試行錯誤の過程を経て何度か繰り返すと、やがて同じ行動が出現する頻度が高くなる 【猫の問題箱実験】 行動後の「満足」または「不快」の度合いに応じて、 行動の出現頻度が学習の過程を経て変化
- 17. 動物の行動学習：報酬学習 22 ? 報酬学習 【スキナーの箱実験】 何度か繰り返すと、レバーを押す頻度が高くなる Burrhus Frederic Skinner（1904年?1990年） レバーを押すと餌が出る仕組みになっている箱の中で，ラット が偶然にでもレバーを押し，餌を得ることを何度か繰り返すと， ラットはレバーの近くにいることが多くなり，やがてレバーを押 す行動を取る頻度が高くなるのを実験的に確認 ラットが様々な行動をとる レバーを押す 餌が出る 満足を「餌」という「報酬」で明示的に与えた「試行錯誤学習」。 報酬に応じて行動の自発頻度が変化していく：報酬学習 強くなるロボティック?ゲームプレイヤーの作り方 八谷、杉山 2016
- 18. ロボット制御での強化学習 23 ? 試行錯誤学習の要素：方策関数を条件付き確率分布関数に拡張 ? 報酬学習の要素：報酬??の総和を最大化する方策を獲得 ? 報酬関数?? ??, ??, ??? は人間が設計：教師データを集めるより断然簡単 出力：行動??入力：状態?? ?? = ?? ?? センサ アクチュエータ ?? ?? = ??|?? = ?? 条件付き確率に従いランダムに行動を選択 報酬 ?? 環境 ?? = ?? ??, ??, ??? ???：次の状態
- 19. 強化学習の結果の例 24 ? 方策は報酬に基づき試行錯誤的に改善され、ボールをカップに 入れることができるようになる。 カップ ボール l l :ボールとカップの距離 報酬の例： ?? = exp(???)
- 20. 内容 25 ? 教師あり学習 ? 教師あり学習の例と問題点 ? 強化学習 ? 強化学習の目的と成功例 ? 動物の行動学習 ? 強化学習の定式化 ? 動的計画法による最適化
- 21. 強化学習の定式化 26 ? ??, ??, ???? に従う確率過程（マルコフ決定過程）を考える ? 価値関数：ステップ??から始まる報酬和の期待値 ? 目的：価値関数を最大化する方策??? を獲得 ???? ??1 |??0 , ??0 状態??0 で行動??0 をとったとき状態??1 に遷移する状態遷移確率 状態??1 ??1 ??2 ??3 ?? ??0|??0 状態??0 で行動??0 を 選択する方策関数 ??1 行動??0 ??2 ??3 ?? ??1|??1 状態??1 に遷移したときの報酬 ???? ?? (??) = Ε ?? ????|???? ????(????+1|????,????) ?? ??=?? ?? ??????? ?? ????, ????, ????+1 ???? = ?? ?? ∈ (0,1] ：割引率 遠い先の報酬ほど割り引く ??1 ??2 ??3 初期状態??0 ??1 = ?? ??1 , ??1 , ??2 状態?? ??+1 ??1 ??2 ??3 ??0 = ?? ??0 , ??0 , ??1 状態??2 に遷移したときの報酬 ??? = argmax ?? ???? 0 (??)
- 22. 期待値の定義 27 ? 1変数??の場合： ? 2変数??と??の和の場合： ? 変数??が??と観測された場合： E ?? ??|??(??|??) |?? + ?? ?? = ?? = ∑?? ?? + ???? ????|?? ????|?? E ?? ??(??) ?? = ? ?? ???? ???? ?? = ???? E ?? ??(??) ?? 確率変数 確率分布関数 期待値の記号 （Expectation） E ?? ??(??) ?? ??|??(??|??) ?? + ?? = ∑?? ∑?? ???? + ???? ????|?? ????|???? ???? ????
- 23. 価値関数の例 28 ? 各ステップの価値関数 ? 開始ステップが異なるが関数の形は同じ ???? 0 (??) = Ε ?? ?? ??|???? ????(????+1|????,????) ?? ??=0 ?? ?????0 ?? ???? , ???? , ????+1 ??0 = ?? ???? 1 (??) = Ε ?? ?? ??|???? ????(????+1|????,????) ?? ??=1 ?? ?????1 ?? ????, ????, ????+1 ??1 = ?? ???? 2 (??) = Ε ?? ?? ??|???? ????(????+1|????,????) ?? ??=2 ?? ?????2 ?? ????, ????, ????+1 ??2 = ?? ステップ0： ステップ1： ステップ2：
- 24. 価値関数の漸化式表現 29 ? 価値関数は漸化式で表現可能 ??0 (??) = Ε ?? ????|???? ????(????+1|????,????) ?? ??=0 ?? ???? ?? ???? , ???? , ????+1 ??0 = ?? = Ε ?? ??0|??0 ????(??1|??0,??0) ??? ??0 , ??0 , ??1 + Ε ?? ????|???? ????(????+1|????,????) ? ??=1 ?? ???? ?? ???? , ???? , ????+1 ??0 = ?? = Ε ?? ??0|??0 ????(??1|??0,??0) ??? ??0 , ??0 , ??1 + ?? Ε ?? ????|???? ????(????+1|????,????) ?? ??=1 ?? ?????1 ?? ???? , ???? , ????+1 ??1 ??0 = ?? = Ε ?? ??0|??0 ????(??1|??0,??0) |?? ??0 , ??0 , ??1 + ????1 (??1 ) ??0 = ?? ??1(??1)
- 25. 各ステップの価値関数 30 ステップ 0 ???? 0 (??) = Ε ?? ??0|??0 ????(??1|??0,??0) |?? ??0 , ??0 , ??1 + ?????? 1 (??1 ) ??0 = ?? ステップ N ???? ?? (??) = Ε ?? ?? ??|?? ?? ????(?? ??+1|?? ??,?? ??) |?? ?? ?? , ?? ?? , ?? ??+1 ?? ?? = ?? ステップ 1 ???? 1 (??) = Ε ?? ??1|??1 ????(??2|??1,??1) |?? ??1 , ??1 , ??2 + ?????? 2 (??2 ) ??1 = ?? ???? ???1 (??) = Ε ?? ?? ???1|?? ???1 ????(?? ??|?? ???1,?? ???1) |?? ?? ???1 , ?? ???1 , ?? ?? + ?????? ?? (?? ?? ) ?? ???1 = ??ステップ N-1 次のステップの 価値関数を参照 状態??1 ??1 ??2 ??3 ?? ??1 |??1 ?? ??1, ??1, ??2 ???? ??1 |??0 , ??0??1?? ??0 |??0 行動??0 ??2 ??3 ??1 ??2 ??3 初期状態??0 ?? ??0 , ??0 , ??1 ???? 0 (??) ???? 1 (??) ???? ?? (??) 状態?? ??+1 ??1 ??2 ??3 ?? ?? ?? , ?? ?? , ?? ??+1 状態?? ?? ??1 ??2 ??3 ?? ?? ?? |?? ?? ???? ?? ??+1|?? ??, ?? ????1 行動?? ?? ??2 ??3
- 26. 2状態チェーンウォーク問題 31 ? 決定的な方策関数 ? 確率「１」でどちらかの行動（??または??）を選択 ? 各状態に行動が２種類あるので、方策は以下の４種類 状態：?? ∈ ??, ?? 行動：?? ∈ ??, ?? ?? ?? ?? ??:右に移動 ?? ??：左に移動 報酬関数：?? ??, ??, ?? = 1 それ以外は０ 状態遷移確率 割引率：γ = 0.9 次の状態 ステップ数：?? =2 初期状態確率：???? A = 1 ??1 ?? = ?? ?? = ?? = 1 ??1 ?? = ?? ?? = ?? = 1 ??2 ?? = ?? ?? = ?? = 1 ??2 ?? = ?? ?? = ?? = 1 ??3 ?? = ?? ?? = ?? = 1 ??3 ?? = ?? ?? = ?? = 1 ??4 ?? = ?? ?? = ?? = 1 ??4 ?? = ?? ?? = ?? = 1 決定的な遷移：行動を取った方向に移動 部屋 部屋 A B ???? ? |A, L 1 0 ???? ? |A, R 0 1 ???? ? |B , L 1 0 ???? ? |B, R 0 1
- 27. 価値関数の計算 32 ? 方策??1の場合：?? ?? ?? = 1、?? ?? ?? = 1 A B ???? A, L,? 1 0 ???? A , R,? 0 1 ???? B , L,? 1 0 ???? B , R,? 0 1 状態：?? ∈ A,B 行動：?? ∈ L, R ?? B L R RL 報酬関数：?? ??, ??, B = 1 それ以外は０ 状態遷移確率 割引率：γ = 0.9 次の状態 ステップ数：?? = 2 初期状態確率：???? A = 1 ????1 2 ?? = Ε ??1 ??2|??2 ????(??3|??2,??2) |?? ??2 , ??2 , ??3 ??2 = ?? ステップ 2 ????1 2 ?? = Ε ??1 ??2|??2 ????(??3|??2,??2) |?? ??2, ??2, ??3 ??2 = ?? = ??1 ??|A ?? ??, ??, ?? ???? ??|??, ?? + ??1 ??|?? ?? ??, ??, A ???? ??|??, ?? =0 =1 =1=0 =0 =0 = 0 = ??1 ??|?? ?? ??, ??, ?? ???? ??|??, ?? + ??1 ??|?? ?? ??, ??, ?? ???? ??|??, ?? =1 =0 =1=1 =1 =0 = 1 行動Rをとる場合 行動Lをとる場合 行動Rをとる場合 行動Lをとる場合
- 28. 価値関数の計算 2 33 ? 方策??1の場合：?? ?? ?? = 1、?? ?? ?? = 1 状態：?? ∈ A,B 行動：?? ∈ L, R ?? B L R RL 状態遷移確率 割引率：γ = 0.9 次の状態 ステップ数：?? = 2 初期状態確率：???? A = 1 ????1 1 ?? = Ε ??1 ??1|??1 ????(??2|??1,??1) ??? ??1 , ??1 , ??2 + ??????1 2 (??2 ) ??1 = ?? ステップ 1 ????1 1 ?? = Ε ??1 ??1|??1 ????(??2|??1,??1) ??? ??1 , ??1 , ??2 + ??????1 2 (??2 ) ??1 = ?? = ??1 ??|?? ?? ??, ??, A + ??????1 2 ?? ???? ??|??, ?? = 1 ? 0 + 0.9 ? 0 ? 0 = 0 行動Lをとる場合 = ??1 R|B ?? ??, ??, ?? + ??????1 2 ?? ? ???? ??|??, ?? = 1 ? 1 + 0.9 ? 1 ? 1 = 1.9 行動Rをとる場合 A B ???? ? |A, L 1 0 ???? ? |A, R 0 1 ???? ? |B , L 1 0 ???? ? |B, R 0 1 報酬関数：?? ??, ??, B = 1 それ以外は０
- 29. 課題1 34 ? 方策??1のステップ0の価値関数を求め、方策??1について 考察しなさい。 ? ?? ?? ?? = 1、?? ?? ?? = 1 状態：?? ∈ A,B 行動：?? ∈ L, R ?? B L R RL 状態遷移確率 割引率：γ = 0.9 次の状態 ステップ数：?? = 2 初期状態確率：???? A = 1 ステップ0 ???? 0 (??) = Ε ?? ??0|??0 ????(??1|??0,??0) |?? ??0, ??0, ??1 + ?????? 1 (??1) ??0 = ?? ????1 1 ?? = 0 ????1 1 ?? = 1.9 ステップ1の価値関数： A B ???? ? |A, L 1 0 ???? ? |A, R 0 1 ???? ? |B , L 1 0 ???? ? |B, R 0 1 報酬関数：?? ??, ??, B = 1 それ以外は０
- 30. 価値の列挙法 36 ? 決定的な方策と、価値を列挙し、最大価値の方策を選択 ? 必要な演算数（価値関数の計算回数） ? 3ステップ2状態チェインウォークの場合：（2×2）×2×3＝24回 ? 実問題では状態数が膨大 （状態数×行動数） × 状態数 × ステップ数 方策の数 各方策で計算する価値の数 ゲーム 局面の数 将棋 10の226乗 囲碁 10の360乗 方策 価値 ??1 ????1 0 ?? = 0, ????1 0 ?? = 2.71 ??2 ????2 0 ?? = 0, ????2 0 ?? = 0 ??3 ????3 0 ?? = 0, ????3 0 ?? = 0 ??4 ????4 0 ?? = 1.71, ????4 0 ?? = 2.71 最大の価値 状態：?? ∈ A,B 行動：?? ∈ L, R ?? B L R RL 割引率：γ = 0.9 ステップ数：?? = 2 初期状態確率：???? A = 1 ??1 ?? = ?? ?? = ?? = 1 ??1 ?? = ?? ?? = ?? = 1 ??2 ?? = ?? ?? = ?? = 1 ??2 ?? = ?? ?? = ?? = 1 ??3 ?? = ?? ?? = ?? = 1 ??3 ?? = ?? ?? = ?? = 1 ??4 ?? = ?? ?? = ?? = 1 ??4 ?? = ?? ?? = ?? = 1 報酬関数：?? ??, ??, B = 1 それ以外は０
- 31. 内容 37 ? 教師あり学習 ? 教師あり学習の例と問題点 ? 強化学習 ? 強化学習の目的と成功例 ? 動物の行動学習 ? 強化学習の定式化 ? 動的計画法による最適化
- 32. 動的計画法 38 ? 価値関数の最大化を2ステップずつ解く ? ??ステップ目の価値を計算し、最大の価値????? ?? ?? を選択 ? 次の1と2を?? = ?? ? 1, ?? ? 2, … , 2,1,0と繰り返す 1. ??ステップの価値???? ?? (??)を、 ??+1ステップの最大価値????? ??+1 ?? を用いて計算 2. 最大の価値????? ?? ?? を選択 ???? ?? (??) = Ε ?? ?? ??|???? ????(????+1|????,????) |?? ????, ????, ????+1 + ??????? ??+1 (????+1) ????+1 = ?? ???? ?? (??) = Ε ?? ?? ??|?? ?? ????(?? ??+1|?? ??,?? ??) |?? ?? ??, ?? ??, ?? ??+1 ?? ?? = ??
- 33. 動的計画法の例 39 ? 価値の計算回数は１２回、最適な方策は?? R ?? = 1、?? ?? ?? = 1 ???? 2 ?? = 0 ????′ 2 ?? = 0 ?? ステップ2 ?? ????′ 2 ?? = 1 ???? 2 ?? = 0 ????? 2 ?? = 0 ???? 1 ?? = 0 ????′ 1 ?? = 0.9 ????′ 1 ?? = 1.9 ???? 1 ?? = 0 ????? 1 ?? = 1.9 ????? 1 ?? = 0.9 ????? 2 ?? = 1 ?? ?? ステップ3 ?? ?? ステップ1 ???? 0 ?? = 0.81 ????′ 0 ?? = 1.71 ????′ 0 ?? = 2.71 ???? 0 ?? = 0.81 ????? 1 ?? = 2.71 ????? 1 ?? = 1.71 ?? ?? ステップ0 状態：?? ∈ A,B 行動：?? ∈ L, R ?? B L R RL 報酬関数：?? ??, ??, B = 1 それ以外は０ 状態遷移確率 割引率：γ = 0.9 次の状態 ステップ数：?? = 2 初期状態確率：???? A = 1 ???? ?? (??) = Ε ?? ??0|??0 ????(??1|??0,??0) |?? ??0 , ??0 , ??1 + ?????? ??+1 (????+1 ) ???? = ?? A B ???? ? |A, L 1 0 ???? ? |A, R 0 1 ???? ? |B , L 1 0 ???? ? |B, R 0 1
- 34. レポートの提出方法 44 ? 演習レポート： ? タイトル「演習レポート」、日付?学生番号?氏名を用紙の一番上に記載 ? 課題レポート ： ? タイトル「課題レポート」、出題日?学生番号?氏名を用紙の一番上に記載 ? 2ページ以上になる場合は、ホッチキス留め ? A4サイズの用紙を使用 ? 一度に複数の課題レポートを提出する場合出題日ごとに別々に綴じる