様々なシミュレーション手法(3) 強化学習/カオスとフラクタル

Slides:



Advertisements
Similar presentations
Division of Process Control & Process Systems Engineering Department of Chemical Engineering, Kyoto University
Advertisements

シミュレーション論 Ⅱ 第13回 カオスとフラクタル. 前回のレポート 解答例 図の S1 からスタートし、「上」 → 「下」 → 「左」 → 「右」の順に行動が選択された場合、各状態の Q 値がど うなっているか計算せよ。ただし Q 値の初期値はすべて 1とする。
シミュレーション論Ⅰ 第 12 回 様々なシミュレーション手法. 第11回のレポート回答例 (例) 講義に出席するかどうかのシミュレーション ・セルオートマトン法を用いて、ある講義の出席人数をシ ミュレーションする ・各セルを受講者とし、隣接するセルを各自の友人と考え、 「自分の友人のうち半数がサボったら自分も講義を休む」
シミュレーション論Ⅰ 第 7 回 待ち行列のシミュレーション(2). 第 6 回のレポート(解答例) 乱数表より乱数を記入し、到着間隔・サービス時間にした がってグラフを作成する 例) 最大待ち人数:2人 最大待ち時間:5分 平均待ち時間:3分.
ファーストイヤー・セミナーⅡ 第13回 2次元グラフィックス(1). 2次元グラフィックス Ultra-C では、これまで利用してきた「標準入出力」 以外に「グラフィックス画面」があり、図形などを 表示できる C 言語のグラフィックスには細かな規定がなく、こ れから学ぶ内容が他の環境、システムでは利用でき.
初年次セミナー 第13回 2次元グラフィックス(1).
第1回 確率変数、確率分布 確率・統計Ⅰ ここです! 確率変数と確率分布 確率変数の同時分布、独立性 確率変数の平均 確率変数の分散
初年次セミナー 第14回 2次元グラフィックス(2).
初年次セミナー 第8回 データの入力.
シミュレーション論 Ⅱ 第5回 ランダムウォーク.
ファーストイヤー・セミナーⅡ 第8回 データの入力.
エージェントモデル シミュレーション.
「Self-Organizing Map 自己組織化マップ」 を説明するスライド
5.チューリングマシンと計算.
スペクトル法による数値計算の原理 -一次元線形・非線形移流問題の場合-
5.チューリングマシンと計算.
マルチエージェント・シミュレーション(2)
マルチエージェント・シミュレーション(2)
シミュレーション論 Ⅱ 第12回 強化学習.
遺伝アルゴリズムによる NQueen解法 ~遺伝補修飾を用いた解探索の性能評価~
シミュレーション論Ⅰ 第4回 基礎的なシミュレーション手法.
先端論文紹介ゼミ Role-based Context-specific Multiagent Q-learning
エージェントアプローチ 人工知能 21章 B4 片渕 聡.
4.2 連立非線形方程式 (1)繰返し法による方法
流体のラグランジアンカオスとカオス混合 1.ラグランジアンカオス 定常流や時間周期流のような層流の下での流体の微小部分のカオス的運動
非線形方程式の近似解 (2分法,はさみうち法,Newton-Raphson法)
シミュレーション論 Ⅱ 第5回 ランダムウォーク.
Lorenz modelにおける 挙動とそのカオス性
プログラミング基礎a 第8回 プログラムの設計 アルゴリズムとデータ構造
線形フィルタと畳み込み積分 マスクによる画像のフィルタリング 1.入力画像中の関心の画素のまわりの画素値
シミュレーション論 Ⅱ 第12回 様々なシミュレーション手法(3) 強化学習.
第6章 連立方程式モデル ー 計量経済学 ー.
協調機械システム論 ( ,本郷) 協調機械システム論 東京大学 人工物工学研究センター 淺間 一.
ベイジアンネット混合モデルによる 強化学習エージェントの方策改善
1DS05175M 安東遼一 1DS05213M 渡邉光寿 指導教員: 高木先生
モデルの逆解析 明治大学 理工学部 応用化学科 データ化学工学研究室 金子 弘昌.
OpenGLライブラリを用いた3次元フラクタルの描画
あらまし アンサンブル学習の大きな特徴として,多数決などで生徒を組み合わせることにより,単一の生徒では表現できない入出力関係を実現できることがあげられる.その意味で,教師が生徒のモデル空間内にない場合のアンサンブル学習の解析は非常に興味深い.そこで本研究では,教師がコミティマシンであり生徒が単純パーセプトロンである場合のアンサンブル学習を統計力学的なオンライン学習の枠組みで議論する.メトロポリス法により汎化誤差を計算した結果,ヘブ学習ではすべての生徒は教師中間層の中央に漸近すること,パーセプトロン学習では
第14章 モデルの結合 修士2年 山川佳洋.
カオス水車のシミュレーションと その現象解析
第7章 疎な解を持つカーネルマシン 修士2年 山川佳洋.
(昨年度のオープンコースウェア) 10/17 組み合わせと確率 10/24 確率変数と確率分布 10/31 代表的な確率分布
Data Clustering: A Review
プログラミング基礎a 第8回 プログラムの設計 アルゴリズムとデータ構造
電機情報工学専門実験 6. 強化学習シミュレーション
Genetic Algorithm-based Partial Least Squares GAPLS Genetic Algorithm-based Support Vector Regression GASVR 明治大学 理工学部 応用化学科 データ化学工学研究室 金子 弘昌.
様々なシミュレーション:社会現象のシミュレーション
シミュレーション論Ⅰ 第14回 シミュレーションの分析と検討.
「データ学習アルゴリズム」 第3章 複雑な学習モデル 報告者 佐々木 稔 2003年6月25日 3.1 関数近似モデル
ベイズ最適化 Bayesian Optimization BO
情報経済システム論:第13回 担当教員 黒田敏史 2019/5/7 情報経済システム論.
シミュレーション論 Ⅱ 第1回.
シミュレーション論Ⅰ 第7回 シミュレーションの構築と実施.
5.チューリングマシンと計算.
保守請負時を対象とした 労力見積のためのメトリクスの提案
パターン認識 ークラスタリングとEMアルゴリズムー 担当:和田 俊和 部屋 A513
人工知能特論II 第8回 二宮 崇.
クローン検出ツールを用いた ソフトウェアシステムの類似度調査
情報工学概論 (アルゴリズムとデータ構造)
様々なシミュレーション:社会現象のシミュレーション
アルゴリズム入門 (Ver /10/07) ・フローチャートとプログラムの基本構造 ・リスト ・合計の計算
2008年6月5日 非線形方程式の近似解 2分法,はさみうち法,Newton-Raphson法)
確率的フィルタリングを用いた アンサンブル学習の統計力学 三好 誠司 岡田 真人 神 戸 高 専 東 大, 理 研
Cプログラミング演習 ニュートン法による方程式の求解.
情報数理Ⅱ 第10章 オートマトン 平成28年12月21日.
確率的フィルタリングを用いた アンサンブル学習の統計力学 三好 誠司 岡田 真人 神 戸 高 専 東 大, 理 研
各種荷重を受ける 中空押出形成材の構造最適化
混合ガウスモデル Gaussian Mixture Model GMM
アルゴリズム ~すべてのプログラムの基礎~.
教師がコミティマシンの場合のアンサンブル学習 三好 誠司(神戸高専) 原 一之(都立高専) 岡田 真人(東大,理研,さきがけ)
Presentation transcript:

様々なシミュレーション手法(3) 強化学習/カオスとフラクタル シミュレーション論 Ⅱ 第12回 様々なシミュレーション手法(3) 強化学習/カオスとフラクタル

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

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

Q-learning 強化学習の代表的アルゴリズム Q値と呼ばれる「環境と行動の組み合わせ」の評価値を逐次修正してゆき、最適な行動を探す方法

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

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

ごく単純な強化学習のモデル 壁に囲まれた通路を歩いて、ゴールを目指すモデルを考えよう 計算式が複雑になるので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 playと言われる方法) ゴールに到達したら終了とし、「評価値をキープしたまま」、再度スタート地点から繰り返す

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

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

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

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

手作業でのシミュレーション 先ほどの例題を手作業で試してみてください ゴールに到達したらまたスタートからはじめ(評価値はそのまま)、またゴールしたらスタートへ、という形で3回ゴールするまでやってみてください 同じ評価値の行動がある場合には乱数表を使用して行動を決定してください(3つある場合は1~3の乱数表を使用)

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

カオス 1960年代、ローレンツにより発見 対流問題に関する3変数の微分方程式があるパラメータ領域において不規則な挙動をしめす リーとヨーク 「カオス」と命名 3周期の周期点があればカオスが存在する リーとヨークの定理

カオスの定義 カオスの厳密な定義は研究者によって異なる カオスの必要条件 時間の経過とともに変化する決定論的なシステムにおいて、初期値に敏感に反応する非周期振動 (伊藤俊秀、草薙信照「コンピュータシミュレーション」オーム社 より引用) カオスの必要条件 非周期である 何らかのリターンマップによって記述できる リャプノフ指数が正である

ロジスティック曲線 ロジスティック曲線:人口増加や製品の普及率などの記述に使用される曲線で、以下のような関数(ロジスティック関数で表される) ロジスティック曲線の例

ロジスティック曲線のカオス性 ロジスティック関数を差分方程式であらわすと以下のようになる このとき a の値によって xnの値が大きく変化する

ロジスティック曲線のカオス性(2) a の値によって xnが以下のように変化することがわかっている 0≦a≦1 ・・・ 0に収束 1<a≦2 ・・・ 1ー1/ a に収束 2≦a<3 ・・・ 振動しながら1ー1/ aに収束 3≦a≦3.569… ・・・ 2k 個の周期点で振動 3.569… ≦a<4 ・・・ カオス性を示し、非周期で振動

様々なロジスティック曲線の挙動

製品普及シミュレーションでの曲線の変化 以前に紹介した製品普及シミュレーションでも同様の変化が観察されている 現実にもこのような挙動は多く観察される

初期値とカオス カオスの特徴のひとつに「初期値に敏感に反応する」というものがある 先ほどの例は全て初期値( x0 )= 0.01の場合であるが、わずかに変えるだけで挙動が大きく異なる

(参考)リターンマップ リターンマップを用いるとロジスティック関数の挙動の違いが分かりやすい a = 4, x0 = 0.01

(参考)リャプノフ指数 リャプノフ指数:初期値が変化したときにその後の挙動がいかに変化するかを示す指数 カオスであるかどうかを判断する指標のひとつとされる この数値が正であることがカオスである条件のひとつとされている

フラクタル フラクタルの厳密な定義は非常に難しいが、直感的には「図形の部分と全体が自己相似」になっているものなどが挙げられる 例)海岸線の形状、木の枝、血管の形状など

フラクタル研究の歴史 始まりは、イギリスの気象学者ルイス・フライ・リチャードソンの国境線に関する検討である。国境を接するスペインとポルトガルは、国境線の長さとしてそれぞれ987kmと1214kmと別の値を主張していた。リチャードソンは、国境線の長さは用いる地図の縮尺によって変化し、縮尺と国境線の長さがそれぞれ対数を取ると直線状に相関することを発見した。この様な特徴をフラクタルと名付けて一般化したのがマンデルブローである。 マンデルブローによるフラクタルの定義:「ハウスドルフ次元が位相次元を厳密に上回るような集合」  (以上Wikipediaより引用)

フラクタル図形 自然界に存在するもののほかに、人工的なフラクタル図形が数多く考案されている セルオートマトンの練習問題であらわれたシェルピンスキー・ガスケットも代表的なフラクタル図形である

コッホ曲線 コッホ曲線:代表的なフラクタル図形 直線を3等分して中央に正三角形の2辺を描く →この操作を繰り返すと、全体と部分が相似になる図形が    描かれる

さまざまなフラクタル図形

フラクタルの応用 CGや図形の描画 破壊の進展や強度の測定 山岳や海岸線の描画 CGによる芸術作品 岩石の強度診断 ・・・岩石に圧力がかかった際のクラック(ひび割れ)の進展をフラクタル次元を用いて計測し、破壊の様子と強度を測定する フラクタル次元:フラクタル図形の複雑さを示す指標             いくつかの計算法が提案されている             例)相似次元、ディバイダ、ボックスカウント法など

第11回のレポート オリジナルのフラクタル図形を考えて描画せよ コッホ曲線やシェルピンスキー・ガスケットなどを参考にするとよい 自分で考えたものであれば既に提案されているものであったとしても問題ない