シミュレーション論 Ⅱ 第12回 様々なシミュレーション手法(3) 強化学習.

Slides:



Advertisements
Similar presentations
HBSP モデル上での 行列積を求めるアルゴリ ム 情報論理工学 吉岡健太.
Advertisements

シミュレーション論Ⅰ 第 12 回 様々なシミュレーション手法. 第11回のレポート回答例 (例) 講義に出席するかどうかのシミュレーション ・セルオートマトン法を用いて、ある講義の出席人数をシ ミュレーションする ・各セルを受講者とし、隣接するセルを各自の友人と考え、 「自分の友人のうち半数がサボったら自分も講義を休む」
シミュレーション論Ⅰ 第 7 回 待ち行列のシミュレーション(2). 第 6 回のレポート(解答例) 乱数表より乱数を記入し、到着間隔・サービス時間にした がってグラフを作成する 例) 最大待ち人数:2人 最大待ち時間:5分 平均待ち時間:3分.
3次元nクイーン問題の 解に関する研究 論理工学研究室 伊藤精一
ゲーム理論・ゲーム理論Ⅰ(第2回) 第2章 戦略形ゲームの基礎
初年次セミナー 第8回 データの入力.
点対応の外れ値除去の最適化によるカメラの動的校正手法の精度向上
近似アルゴリズム 第10章 終了時刻最小化スケジューリング
強化学習 RT.
第11回 整列 ~ シェルソート,クイックソート ~
データ構造とアルゴリズム論 第6章 探索のアルゴリズム
シミュレーション論Ⅰ 第2回 シミュレーションとモデル化.
シミュレーション論 Ⅱ 第5回 ランダムウォーク.
ファーストイヤー・セミナーⅡ 第8回 データの入力.
エージェントモデル シミュレーション.
シミュレーション論Ⅰ 第9回 様々なシミュレーション:販売と在庫管理.
第4回 (10/16) 授業の学習目標 先輩の卒論の調査に協力する。 2つの定量的変数間の関係を調べる最も簡単な方法は?
「Self-Organizing Map 自己組織化マップ」 を説明するスライド
シミュレーション論 Ⅱ 第7回 シミュレーションの構築.
マルチエージェント・シミュレーション(2)
マルチエージェント・シミュレーション(2)
心理統計学 II 第7回 (11/13) 授業の学習目標 相関係数のまとめと具体的な計算例の復習 相関係数の実習.
シミュレーション論 Ⅱ 第12回 強化学習.
時空間データからのオブジェクトベース知識発見
遺伝アルゴリズムによる NQueen解法 ~遺伝補修飾を用いた解探索の性能評価~
シミュレーション論Ⅰ 第4回 基礎的なシミュレーション手法.
先端論文紹介ゼミ Role-based Context-specific Multiagent Q-learning
エージェントアプローチ 人工知能 21章 B4 片渕 聡.
EMアルゴリズム クラスタリングへの応用と最近の発展
強化学習 RT.
非線形方程式の近似解 (2分法,はさみうち法,Newton-Raphson法)
シミュレーション論 Ⅱ 第5回 ランダムウォーク.
プログラミング基礎a 第8回 プログラムの設計 アルゴリズムとデータ構造
スペクトル・時系列データの前処理方法 ~平滑化 (スムージング) と微分~
第6章 連立方程式モデル ー 計量経済学 ー.
協調機械システム論 ( ,本郷) 協調機械システム論 東京大学 人工物工学研究センター 淺間 一.
ベイジアンネット混合モデルによる 強化学習エージェントの方策改善
モデルの逆解析 明治大学 理工学部 応用化学科 データ化学工学研究室 金子 弘昌.
第7章 疎な解を持つカーネルマシン 修士2年 山川佳洋.
様々なシミュレーション手法(3) 強化学習/カオスとフラクタル
25. Randomized Algorithms
アクションゲームにおけるプレイヤのレベルに応じたマップの自動生成手法の研究
2009年12月4日 ○ 前田康成(北見工業大学) 吉田秀樹(北見工業大学) 鈴木正清(北見工業大学) 松嶋敏泰(早稲田大学)
アルゴリズムとプログラミング (Algorithms and Programming)
プログラミング基礎a 第8回 プログラムの設計 アルゴリズムとデータ構造
電機情報工学専門実験 6. 強化学習シミュレーション
Genetic Algorithm-based Partial Least Squares GAPLS Genetic Algorithm-based Support Vector Regression GASVR 明治大学 理工学部 応用化学科 データ化学工学研究室 金子 弘昌.
様々なシミュレーション:社会現象のシミュレーション
シミュレーション論Ⅰ 第14回 シミュレーションの分析と検討.
ベイズ最適化 Bayesian Optimization BO
シミュレーション論 Ⅱ 第1回.
シミュレーション論Ⅰ 第7回 シミュレーションの構築と実施.
パターン認識 ークラスタリングとEMアルゴリズムー 担当:和田 俊和 部屋 A513
保守請負時を対象とした 労力見積のためのメトリクスの提案
パターン認識 ークラスタリングとEMアルゴリズムー 担当:和田 俊和 部屋 A513
人工知能特論II 第8回 二宮 崇.
ITSにおける 知的ネットワークシステムの構築 - 知的信号機システムの提案 -
様々なシミュレーション:社会現象のシミュレーション
アルゴリズム入門 (Ver /10/07) ・フローチャートとプログラムの基本構造 ・リスト ・合計の計算
実験計画法 Design of Experiments (DoE)
2008年6月5日 非線形方程式の近似解 2分法,はさみうち法,Newton-Raphson法)
回帰分析入門 経済データ解析 2011年度.
確率的フィルタリングを用いた アンサンブル学習の統計力学 三好 誠司 岡田 真人 神 戸 高 専 東 大, 理 研
Q q 情報セキュリティ 第8回:2004年5月28日(金) の補足 q q.
情報数理Ⅱ 第10章 オートマトン 平成28年12月21日.
Q q 情報セキュリティ 第7回:2005年5月27日(金) q q.
アルゴリズム ~すべてのプログラムの基礎~.
ファーストイヤー・セミナーⅡ 第10回 if文による選択処理(2).
Presentation transcript:

シミュレーション論 Ⅱ 第12回 様々なシミュレーション手法(3) 強化学習

前回のレポート解答(1) 気温とおでんの売り上げが以下の表のようになった。 相関分析をおこない、気温とおでんの売り上げに相関があるかどうか調べよ 相関係数 R = -0.9834 データ数が4組の場合、|R| > 0.950 だから5%水準で有意であり、|R| = 0.9834とかなり 1に近いため 気温とおでんの売上には高い負の相関があるといえる

前回のレポート解答(2) 次に回帰直線を求める データ数 n = 4 で、データの組はそれぞれ a, b は以下の式で求められる ただし

前回のレポート解答(3) B~Eを求めると

前回のレポート解答(4) a, b の式に代入して よって回帰直線の式は Y = -1.13X + 21.59

強化学習 強化学習:試行錯誤をくりかえして、よりよい行動方針を獲得する手法 状態と行動をセットにして記述し、うまくいった場合に「報酬」、失敗した場合に「罰」を与えることでよりよい行動を獲得するようになる 教師データが不要なため、未知の環境への応用が可能 ロボットの行動獲得などによく利用される

強化学習のしくみ 強化学習では学習をおこなう「主体」と「環境」がある 主体は環境の状態を観測し、行動を選択する 行動選択の結果として、環境から「報酬」または「罰」を得る(報酬は毎回与えられるとは限らず、特定の状況でのみ与えられる場合もある) 例)ロボットの行動 左右と後ろが壁である環境 ロボットは周囲の状況を観察し、進む方向を決定する 無事進行できた場合→報酬 壁にぶつかった場合→罰 これを繰り返すことで、環境に応じた行動を選択できるようになる

ごく単純な強化学習のモデル 壁に囲まれた通路を歩いて、ゴールを目指すモデルを考えよう 計算式が複雑になるのでQ-leaning等の定式化は用いず、ごく簡単なモデルで強化学習のイメージをつかんでみよう

単純な強化学習のモデル(2) 行動する主体(エージェント)の行動について以下のように仮定する 上下左右の1マス分を観察できる 1回につき1マス移動できる 無事に進めたら報酬、壁にぶつかったら罰を与えられる ゴールに近づいたら報酬、ゴールから離れたら罰を与えられる

単純な強化学習のモデル(3) 行動する主体(エージェント)にとっての環境は「観察できる範囲に壁があるか、ないか」で表される 観察できる範囲は上下左右の4マス また、エージェントは移動した位置がゴールに近づいたか離れたかを知ることが出来る 観察できる範囲

単純な強化学習のモデル(4) 先ほどの通路の例では、エージェントが観察できる状況は以下の4種類 ①左右と下が壁、上は空き ②左右が壁、上下は空き ③左と上が壁、右と下は空き ④上下が壁、左右は空き 簡単にするためエージェントは常に上を向いていると仮定する ゴールに到達したら終了

単純な強化学習のモデル(5) エージェントの行動は上下左右いずれかに1マス移動 先ほどの状態に応じてそれぞれ上下左右なので、 4×4=16のパターンが考えられる 以下の状態をそれぞれ状態1~4として、それぞれ行動との組み合わせを作成し、評価値を与える 左右と下が壁、上は空き  (状態1) 左右が壁、上下は空き   (状態2) 左と上が壁、右と下は空き (状態3) 上下が壁、左右は空き   (状態4)

単純な強化学習のモデル(6) 状態+行動の組み合わせは以下のようになる 初期状態での各行動の評価値を5としておく

単純な強化学習のモデル(7) 報酬と罰: エージェントが壁にぶつからずに進んだら+1、さらにゴールに近づいたら+1、ゴールから離れたらー1、壁にぶつかったら-1を評価値に加える 行動選択は「その状況において最も評価値の高いもの」を選ぶこととし、同じ評価値のものが複数ある場合はランダムに1つを選ぶ (greedy法と言われる方法) ゴールに到達したら終了とし、「評価値をキープしたまま」、再度スタート地点から繰り返す

実行例(1) スタート地点では(状態1) 行動の評価値は全て5なので、ランダムに行動を選択し「右」を実行したとする 壁にぶつかったので、(状態1-右)の組み合わせの評価値をー1とする 位置は変化しなかったので、同じ位置から次の行動を選択する

実行例(2) 位置は変化しなかったので、同じ位置(状態1)から次の行動を選択する 評価値は上・下・左が5で最大なので、この中からランダムに選ぶ 「上」が選択されたとすると1マス進めるので評価値に+1となる さらにゴールに近づいているので、評価値に+1となる

実行例(3) 位置が1マス動いたので、(状態2)になる このときの行動の評価値はすべて5なので、ランダムに1つ行動を選択する 「左」が実行されたとすると壁にぶつかるので(状態2-左)の評価値をー1とし、位置はそのまま

実行例(4) 以上の作業をくりかえし、評価値を変更しながら進めていく ゴールに到達したら終了とし、またスタート地点から繰り返す この作業を繰り返していくと、最終的にスムーズにゴールへ向かっていく行動が獲得できる(=学習した)

手作業でのシミュレーション 先ほどの例題を手作業で試してみてください ゴールに到達したらその時点の評価値をキープしたまま、再度スタートからはじめ2回ゴールするまでやってみてください ※15回行動選択をおこなってゴールしなければ終了して次   の回へ 同じ評価値の行動がある場合には乱数表を使用して行動を決定してください(3つある場合は1~3の乱数表を使用)

実際の強化学習アルゴリズム 通常の強化学習アルゴリズムでは評価値の計算方法などがもっと複雑になるが、基本は同様 一定期間ごとに、遺伝的アルゴリズム等を用いて行動の取捨選択などをおこなう場合もある 強化学習では「試行錯誤」の繰り返しで行動主体が自律的に学習するため、教師データが不要 また、未知の環境に対しても対応できる可能性が大きい 学習プロセスは生物や人間の行動パターンの再現などにも利用できるのではないか?

Q-learning 強化学習の代表的アルゴリズム Q値と呼ばれる「環境と行動の組み合わせの評価値」を逐次修正してゆき、最適な行動を探す方法 (1)エージェントは環境の状態  を観測する (2)エージェントは任意の行動選択方法(探査戦略)にしたがって行動 を実行する (3)環境から報酬  を受け取る (4)状態遷移後の状態   を観測する (5)以下の更新式によりQ値を更新: (6)時間ステップ  を    へ進めて手順(1)へ戻る

Q-learning の数値例 例)以下のような4マスの迷路を考える 各マスでの状態をそれぞれS1~S4とし、行動は上下左右の4種をとることができるものとする マスの一番外の枠は壁とし、壁方向へは移動できない(もとの場所にとどまる) 壁にぶつかったら報酬 -1、ゴールしたら +1、それ以外は報酬 0 とする 学習率α=0.5、割引率γ=0.9 とする

Q-learning の数値例(2) 各状態でのQ値の初期値を1とする S1からスタートし、行動「上」が選ばれたとすると

Q-learning の数値例(3) 次に、S1で行動「右」が選ばれたとすると →状態はS2へ移動、報酬は 0   →よって、Q値は

Q-learning の数値例(4) 次に、S2で行動「下」が選ばれたとすると →状態はS4(ゴール)へ移動、報酬は 1   →よって、Q値は

Q-learning の数値例(5) ゴールへ到達、または一定回数繰り返してゴールに達しなければスタートへ戻り、再度同じ手順を繰り返す

行動選択の方式 Q値から行動を決定する方法には以下のようなものがある ε-greedy εの確率でランダム、それ以外は最大の重みを持つルールを選択 ルーレット選択 Q(s,a)に比例した割合で行動選択 ボルツマン選択 exp(Q(s,a)/T)に比例した割合で行動選択、ただしTは時間とともに0に近付く ただし s は環境の状態、a は行動

Q-learning の特徴 Q-learningは行動により状態が変わった後の「仮定の行動」を用いて評価をおこなうもので、Off-Policyの方式と言われる これに対し、On-Policyと呼ばれるものは厳密に「自分が行動した結果」に基づいて評価をおこなうものである 代表的手法としてprofit sharing など(報酬を得た時点から過去の行動にさかのぼって報酬を与える方式) 強化学習には様々な方式があり、それぞれに特徴がある 状況や問題に応じて使い分ける

第12回のレポート さきほどの数値例と同じ条件で、図のS1からスタートし、「上」→「下」→「左」→「右」の順に行動が選択された場合、各状態のQ値がどうなっているか計算せよ。 ただしQ値の初期値はすべて1とする。 次回はノートパソコンを使用します。 しっかり充電したうえで持参してください(ノートPCをお持ちでない場合はなくても構いません)