強化学習におけるマクロを用いた 行動系列の獲得

Slides:



Advertisements
Similar presentations
情報基盤アルゴリズムとして のメタヒューリスティクスの 研究 茨木俊秀、巳波弘佳、藤原洋志、 千葉英史、関口良行(関西学院大 学)、 藤重悟(京都大学)、 柳浦睦憲(名古屋大学)、 野々部宏司(法政大学)、 梅谷俊治(電気通信大学)
Advertisements

区間グラフにおける区間表現からMPQ-treeを効率よく構成するアルゴリズム
Building text features for object image classification
高度情報演習1A “テーマC” 実践 画像処理プログラミング 〜画像認識とCGによる画像生成〜 第四回 演習課題 画像中からの物体抽出処理(背景情報を手がかりとして) 芝浦工業大学 工学部 情報工学科 青木 義満 2006/05/15.
機械学習勉強会~強化学習~ 11/18 江原遥.
強化学習 RT.
秘密のリンク構造を持つグラフのリンク解析
スケールフリーネットワークにおける 経路制御のためのフラッディング手法の提案と評価
神奈川大学大学院工学研究科 電気電子情報工学専攻
モード付き並列機械における オンラインスケジューリング
2つのユニット:21個 3つのユニット:29個 4つのユニット:23個 5つ以上のユニット:27個 合計:100個.
シミュレーション論 Ⅱ 第12回 強化学習.
Object Group ANalizer Graduate School of Information Science and Technology, Osaka University OGAN visualizes representative interactions between a pair.
クロストーク成分の相互相関に 着目した音場再生システム
先端論文紹介ゼミ Role-based Context-specific Multiagent Q-learning
エージェントアプローチ 人工知能 21章 B4 片渕 聡.
“いじめ現象”の形式構造を探る ~人工学級のMulti-Agent Simulation~
強化学習 RT.
クラスター変分法と確率的情報処理 --Belief Propagation と画像処理アルゴリズム--
変数のスコープの設計判断能力 を育成するプログラミング教育
ベイズ基準によるHSMM音声合成の評価 ◎橋本佳,南角吉彦,徳田恵一 (名工大).
ベイジアンネットワーク概説 3.6 構造の探索アルゴリズム
集団的意思決定支援法の実験環境に関する研究
小標本検査データを元にした 疲労破損率のベイズ推定
二分探索木によるサーチ.
プログラム実行履歴を用いたトランザクションファンクション抽出手法
シミュレーション論 Ⅱ 第12回 様々なシミュレーション手法(3) 強化学習.
大阪大学 大学院情報科学研究科 博士前期課程2年 宮原研究室 土居 聡
協調機械システム論 ( ,本郷) 協調機械システム論 東京大学 人工物工学研究センター 淺間 一.
計算機実験の計画 References 研究目的 囲碁・将棋での強化学習 高信頼性人工知能システムへの展望 大規模な強化学習技術の実証と応用
識別子の命名支援を目的とした動詞-目的語関係の辞書構築
ベイジアンネット混合モデルによる 強化学習エージェントの方策改善
決定木とランダムフォレスト 和田 俊和.
オブジェクト指向プログラムにおける エイリアス解析手法の提案と実現
確率的学習アルゴリズムを用いた有限状態オートマトンの抽出に関する研究
Authoring Environment for Story-based Digital Educational Games
モデルの逆解析 明治大学 理工学部 応用化学科 データ化学工学研究室 金子 弘昌.
Online Decoding of Markov Models under Latency Constraints
WWW上の効率的な ハブ探索法の提案と実装
確率的学習アルゴリズムを用いた有限状態オートマトンの抽出に関する研究
音響伝達特性を用いた単一マイクロホンによる話者の頭部方向の推定
構造情報に基づく特徴量を用いた グラフマッチングによる物体識別 情報工学科 藤吉研究室  EP02086 永橋知行.
第7章 疎な解を持つカーネルマシン 修士2年 山川佳洋.
中京大学 工学部 電気電子工学科 白井研究室 4年 T 為房直人
分子生物情報学(2) 配列のマルチプルアライメント法
Cプログラミング演習 第10回 二分探索木.
ロボットの協調動作の研究: マップ作成とマップ情報を利用した行動計画
Data Clustering: A Review
東北大学 大学院情報科学研究科 応用情報科学専攻 田中 和之(Kazuyuki Tanaka)
Webコミュニティ概念を用いた Webマイニングについての研究 A study on Web Mining Based on Web Communities 清水 洋志.
電機情報工学専門実験 6. 強化学習シミュレーション
適応的近傍を持つ シミュレーテッドアニーリングの性能
階層的強化学習を適用したPOMDPに よるカーナビゲーションシステムの 音声対話制御
研究背景と目的 局面対による学習の高速化 学習器の説明 今後 大規模な強化学習技術の実証と応用 一方で、 強化学習手法の台頭
ベイジアンネットワーク概説 Loopy Belief Propagation 茨城大学工学部 佐々木稔
Data Clustering: A Review
シミュレーション論 Ⅱ 第1回.
クロスバリデーションを用いた ベイズ基準によるHMM音声合成
HMM音声合成における 変分ベイズ法に基づく線形回帰
ベイズ基準による 隠れセミマルコフモデルに基づく音声合成
人工知能特論II 第8回 二宮 崇.
ベイズ音声合成における 事前分布とモデル構造の話者間共有
制約付き非負行列因子分解を用いた 音声特徴抽出の検討
コストのついたグラフの探索 分枝限定法 A*アルゴリズム.
Webページタイプによるクラスタ リングを用いた検索支援システム
確率的フィルタリングを用いた アンサンブル学習の統計力学 三好 誠司 岡田 真人 神 戸 高 専 東 大, 理 研
長岡技術科学大学 大学院 工学研究科 機械創造工学専攻 髙山 誠 指導教員 小林 泰秀 准教授
回帰テストにおける実行系列の差分の効率的な検出手法
マルチエージェントシステムにおける 通信コストの構造依存性に関する解析
混合ガウスモデル Gaussian Mixture Model GMM
Presentation transcript:

強化学習におけるマクロを用いた 行動系列の獲得 北海道大学 大学院工学研究科 金澤 勇樹 

発表内容 研究背景 学習システム設計方針 マクロの実装方法 実装例 まとめ 2019/2/28 第5回WINGS      強化学習におけるマクロを用いた行動系列獲得

研究背景 強化学習 自律的に環境に適応する機械学習の一種 報酬入力のみを手掛りとして学習 マルチエージェント系や実制御問題に対して有効  強化学習  自律的に環境に適応する機械学習の一種  報酬入力のみを手掛りとして学習 マルチエージェント系や実制御問題に対して有効 在庫管理・生産ライン最適化問題(Wang, Mahadevan 99) 倒立振子の振り上げ安定化問題(Doya 96) 不完全な観測、非マルコフ的な振舞い  学習困難である問題が想定 2019/2/28 第5回WINGS      強化学習におけるマクロを用いた行動系列獲得

関連研究(1) 学習困難な問題に対して 経験強化型アプローチ(利益共有法など) 観測集合から行動集合への確率分布関数のみを推定  経験強化型アプローチ(利益共有法など)  観測集合から行動集合への確率分布関数のみを推定 一般に収束性は保証されない  メモリベース法(Chirisman 92, McCallum 95 )  状態推定器を用いて、経験から環境状態を推定 計算資源の範囲に依存 2019/2/28 第5回WINGS      強化学習におけるマクロを用いた行動系列獲得

関連研究(2) 階層的強化学習(Barto 03) 下位階層での部分観測性を上位階層で補う Precupらはマクロを用いてタスクの階層化を実現 強化学習 行動制御を提供するもの マクロ  状態空間の探索補助    ex. プランニング ・・・ 既存プランを汎化したもの      問題解決   ・・・ 推論のステップを一つにまとめたもの 2019/2/28 第5回WINGS      強化学習におけるマクロを用いた行動系列獲得

マクロとは (例) 一回周ってBow! ? + 三回周ってBow! どのようにして「一回周る」を表現するか? Action:{ 前進、右転回、左転回、Bow } Macro:{ 一回周る } + 三回周ってBow! どのようにして「一回周る」を表現するか? どのようにして「一回周る」を獲得するか? 2019/2/28 第5回WINGS      強化学習におけるマクロを用いた行動系列獲得

研究目的 汎用的な行動制御を提供可能なマクロの設計 経験を基としたマクロ生成方法の提案 マクロを利用した 強化学習エージェントの実装  汎用的な行動制御を提供可能なマクロの設計  経験を基としたマクロ生成方法の提案 マクロを利用した 強化学習エージェントの実装 簡便かつ有効に対処 学習効率の向上 学習困難な問題 2019/2/28 第5回WINGS      強化学習におけるマクロを用いた行動系列獲得

設計方針 エージェントと環境の相互作用図 Agent Environment Experience Chain Data Memory  エージェントと環境の相互作用図 Agent Experience select Chain Data Memory Action control make Macro Environment Reward Observation Action 2019/2/28 第5回WINGS      強化学習におけるマクロを用いた行動系列獲得

価値更新方法 エージェントはどのマクロで行動制御を行うかを選択 この価値によって方策が決定 マクロによる行動制御が終了する毎に更新 (マクロの行動制御は任意時間ステップ)  エージェントはどのマクロで行動制御を行うかを選択 : 観測状態 : マクロ : 割引報酬和 :   の時間ステップ数  観測状態 - マクロ対の価値を更新 この価値によって方策が決定 2019/2/28 第5回WINGS      強化学習におけるマクロを用いた行動系列獲得

実装マクロの構造 木構造で表現 マクロ ・・・ 行動制御を提供するもの Primitive action がラベル付け Macro  Primitive Action Node ・・・    マクロ ・・・ 行動制御を提供するもの Primitive action がラベル付け Macro  Macro Action Tree   ・・・  他のマクロの組合せで表現 木構造で表現   ,   は観測  で選択可能なマクロ 各々異なる観測がラベル付けされる            は、                で選択可能なマクロ ・・・ 2019/2/28 第5回WINGS      強化学習におけるマクロを用いた行動系列獲得

実装マクロの行動制御(1) Macro 制御(PAD図) 処理 順次 繰返し 選択 ・・・ 2019/2/28 第5回WINGS      強化学習におけるマクロを用いた行動系列獲得

実装マクロの行動制御(2) 構造化定理 「順次」「繰返し」「選択」の処理が可能なマクロは (ある程度)汎用的な行動制御が可能ではないか?  構造化定理  ・ 適正プログラムであれば、「順次」「繰返し」「選択」の3つの基本構造と   その組み合わせだけで、どのような処理も記述できる。 「順次」「繰返し」「選択」の処理が可能なマクロは (ある程度)汎用的な行動制御が可能ではないか? 2019/2/28 第5回WINGS      強化学習におけるマクロを用いた行動系列獲得

実装マクロ生成方法(1) 生成の手順 Step 1: 学習中に発生したデータを蓄積 データ: ( 観測,マクロ,割引報酬和,実行ステップ )  生成の手順 Step 1: 学習中に発生したデータを蓄積  データ: ( 観測,マクロ,割引報酬和,実行ステップ ) Step 2:  N個のデータを蓄積後、すべてのマクロに対し: ⅰ)可能な観測マクロ対を付加 ⅱ)付加されたマクロを評価 Step 3: 評価結果によってマクロを作成し、Step 1へ戻る 2019/2/28 第5回WINGS      強化学習におけるマクロを用いた行動系列獲得

実装マクロ生成方法(2) 新規作成: 条件: 蓄積データより推定 条件が満たされた場合、確率 で生成 利用可能なマクロの上限を下式で限定  条件が満たされた場合、確率        で生成  利用可能なマクロの上限を下式で限定 Primitive Action 数: 長さ のマクロの数: 2019/2/28 第5回WINGS      強化学習におけるマクロを用いた行動系列獲得

実装マクロ生成方法(3) 結合: 条件: 根ノードが一致しているマクロが存在 先に作成された方が優先 新たに次の観測までのマクロが作成 条件: 根ノードが一致しているマクロが存在  新たに次の観測までのマクロが作成      先に作成された方が優先 2019/2/28 第5回WINGS      強化学習におけるマクロを用いた行動系列獲得

実装例(1) ー State Office World States:    89(88+1) 位置×向き(N,S,E,W) Actions:    5 ( stay,move, turn left,turn right, turn around ) Observations:   16(14) ・ 前後左右の壁の有無を観測 ・ 正しい観測が得られる確率0.7   (確率0.3でランダムな観測) Rewards:   ゴール到達 : + 1.0   その他 : 0.0 Initial State:   ランダム Littman’s State Office World G 価値更新手法: Sarsa(λ)      学習率: 0.1      割引率: 0.9 2019/2/28 第5回WINGS      強化学習におけるマクロを用いた行動系列獲得

実装方法 ー State Office World  比較対象 Sarsa(0.9) Sarsa(0.9) + Macro ・・・ マクロを作成 Sarsa(0.9) + Good Macro ・・・ 理想的なマクロを付与 前: 前進 右: 右90度回転 後: 180度回転  左: 左90度回転  理想的なマクロ(10個) 観測: a b c d e f g h i j マクロ: 右 前 右 左 後 右 前 右 左 後 a b b b f g g g 前 前 2019/2/28 第5回WINGS      強化学習におけるマクロを用いた行動系列獲得

実装結果 ー State Office World Steps to task completion Sarsa(0.9) Sarsa(0.9)+ Macro Sarsa(0.9)+ Good Macro 50 100 150 200 250 300 350 400 450 500 600 700 800 900 1000 Trials 2019/2/28 第5回WINGS      強化学習におけるマクロを用いた行動系列獲得

結果考察 事前知識として適当なマクロを設定した場合 マクロを設定しない場合 エージェントは付与したマクロを用いた行動制御 学習効率向上  事前知識として適当なマクロを設定した場合 エージェントは付与したマクロを用いた行動制御 学習効率向上 提案マクロ構造が妥当  マクロを設定しない場合 エージェントはマクロを作成しながら環境に適応 徐々に事前知識を 与えた結果に接近 提案マクロ生成方法が妥当 2019/2/28 第5回WINGS      強化学習におけるマクロを用いた行動系列獲得

実装例(2) 犬と飼い主の問題 1 2 3 4 5 6 5 1 6 2 4 8 3 7 States: 32 位置×向き(N,S,E,W) 実装例(2) 犬と飼い主の問題 States:    32 位置×向き(N,S,E,W) Actions:    6 ( stay,move forward, turn left,turn right, turn around bow) Observations: Rewards:   1周+Bow: 10.0   2周+Bow: 100.0   3週+Bow: 1000.0   内or外: -0.1   その他: 0.0 Initial State:   ランダム 1 2 3 4 5 6 5 1 6 2 4 8 3 7 2019/2/28 第5回WINGS      強化学習におけるマクロを用いた行動系列獲得

実装結果 - 犬と飼い主の問題 Sarsa(0.9) Sarsa(0.9)+Macro steps 0.5 1 1.5 2 2.5 実装結果 - 犬と飼い主の問題 steps 0.5 1 1.5 2 2.5 50000 100000 150000 200000 250000 300000 rewards par step Sarsa(0.9) Sarsa(0.9)+Macro 2019/2/28 第5回WINGS      強化学習におけるマクロを用いた行動系列獲得

結果考察 提案エージェントは「一回周ってBow」マクロを獲得 獲得したマクロを選択することにより、 報酬(+10)までの行動制御が可能 初期段階における 報酬獲得効率上昇 ある程度段階が進むと 比較性能が悪化 局所的な報酬獲得の繰返し  提案マクロ生成方法に改善の余地が有る    ex. サブゴールの考慮 2019/2/28 第5回WINGS      強化学習におけるマクロを用いた行動系列獲得

まとめと今後の課題 まとめ 今後の課題 汎用的な行動制御を提供可能なマクロの提案 経験を基としたマクロ生成方法の提案  汎用的な行動制御を提供可能なマクロの提案  経験を基としたマクロ生成方法の提案  提案マクロを利用した強化学習エージェントの実装  非マルコフ性を有する環境での有効性を確認  提案マクロ生成方法の改善  提案マクロの特徴及び限界についての考察 2019/2/28 第5回WINGS      強化学習におけるマクロを用いた行動系列獲得

参考文献 Barto, A. G., Mahadevan, S., “Recent advances in hierarchical reinforcement learning,” Discrete-Event Systems journal, (2003). Chirisman, L., “Reinforcement Learning with Perceptual Aliasing,” 10th National Conference on AI, (1992). Doya, K., “Efficient nonlinear control with actor-tutor architecture,” Advances in Neural Information Prosessing Systems, (1996). McCallum, R. A., “Instance-based utile distinctions for reinforcement learning with hidden state,” Proc. of 12th Intern Conf. on Machine Learning, (1995). Precup, D. and Sutton, R. S., “Theoretical results on reinforcement learning with temporal resolution models,” Proc. of 10th European Conf. on Machine Learning, (1998) Wang, G. and Mahadevan, S., “Hierarchical optimization of policy-coupled semi-markov decision prosesses,” Proc. of 16th Intern Conf. on Machine Learning, (1999). 2019/2/28 第5回WINGS      強化学習におけるマクロを用いた行動系列獲得