差分

このページの2つのバージョン間の差分を表示します。

この比較画面へのリンク

両方とも前のリビジョン前のリビジョン
次のリビジョン		前のリビジョン
markov_decision_process [2018/12/17 08:06] – watalumarkov_decision_process [2019/01/07 07:52] (現在) – [まとめ] watalu
行 1: 行 1:
 ==== マルコフ決定過程 ==== ==== マルコフ決定過程 ====
 +=== ４つの変数 ===
  
 マルコフ決定過程は、対象の状態S、状態の遷移P、行動A、状態の評価関数R、の４つのコンポーネントからなる確率事象に関する意思決定のモデルである。 マルコフ決定過程は、対象の状態S、状態の遷移P、行動A、状態の評価関数R、の４つのコンポーネントからなる確率事象に関する意思決定のモデルである。
 +
 +  - S 状態
 +  - A 行動
 +  - P 遷移
 +  - R 評価 (報酬・利得であればRと書いて最大化を考え、費用や損失であればCと書いて最小化を考える)
  
 状態Sの遷移Pには、次の２種類がある。 状態Sの遷移Pには、次の２種類がある。
行 30: 行 36:
 {{::usefullife_il001.png?400|}} [[https://www.nabcosystem.co.jp/support/replacement/usefullife.html|ナブコシステム]] {{::usefullife_il001.png?400|}} [[https://www.nabcosystem.co.jp/support/replacement/usefullife.html|ナブコシステム]]
  
-これらの図はリンク先の企業での劣化と保全の関係を表している。+上の図はリンク先の企業の事業における劣化と保全の関係を表したものである。保全は社会を支える重要な技術であり、大きな市場を形成している。
  
 行動の選択は、将来の状態の評価関数の予測を行い、最も評価が高くなるように行動を選択することが合理的である、という考え方に基づいて行う。将来の状態は、行動ごとに定められた遷移行列を繰り返し用いて行う。 行動の選択は、将来の状態の評価関数の予測を行い、最も評価が高くなるように行動を選択することが合理的である、という考え方に基づいて行う。将来の状態は、行動ごとに定められた遷移行列を繰り返し用いて行う。
行 36: 行 42:
 これらのことを、マルコフ決定過程はモデル化していく。 これらのことを、マルコフ決定過程はモデル化していく。
  
-=== 迷路の例 ===+=== 方策と迷路の例 ===
  
 ロボットの状態を次のように考える。 ロボットの状態を次のように考える。
行 92: 行 98:
 |2|正面に進めない| | |2|正面に進めない| |
  
 +この表を、方策policyという。
 状態ごとにどのような選択をするかを、将来の評価関数を高めるように選んでいく。 状態ごとにどのような選択をするかを、将来の評価関数を高めるように選んでいく。
  
-=== 状態の定め方 ===+=== 状態の定め方が大事 ===
  
 実は、上の２状態では、常にゴールにたどり着ける解法はもとまらない。 実は、上の２状態では、常にゴールにたどり着ける解法はもとまらない。
行 169: 行 176:
  
 === 方策の学習 === === 方策の学習 ===
 +
 +上にも述べたがマルコフ決定過程では、状態と行動を結びつける表を方策という。
 +方策の最適化が、マルコフ決定過程を用いた対象のモデル化の目標である。
  
 方策の候補をひとつ定める。 方策の候補をひとつ定める。
行 197: 行 207:
 このように方策を比較して、良い方策を得るように探索をしていくのが、マルコフ決定過程の基本的な考え方である。1980年代から2000年代までは、ボードゲームのコンピュータのプレイヤーを作るのに、マルコフ決定過程の考え方がよく用いられていた。どのようなボードゲームにも、神の手と呼ばれる、誰でもその手順に従えば勝てる、という方策は存在せず、相手の手に合わせて状況を評価し、最善の手を打っていくことになる。ゲームでは、状況の数が膨大になり、取り得る行動もたくさんあるため、すべての行動の順列を比較検討すると、組み合わせ爆発が生じる。その爆発した組み合わせを、アドホックに刈り込んで、必要な組み合わせだけを比較するようにして、計算量を軽減する工夫が行われていた。 このように方策を比較して、良い方策を得るように探索をしていくのが、マルコフ決定過程の基本的な考え方である。1980年代から2000年代までは、ボードゲームのコンピュータのプレイヤーを作るのに、マルコフ決定過程の考え方がよく用いられていた。どのようなボードゲームにも、神の手と呼ばれる、誰でもその手順に従えば勝てる、という方策は存在せず、相手の手に合わせて状況を評価し、最善の手を打っていくことになる。ゲームでは、状況の数が膨大になり、取り得る行動もたくさんあるため、すべての行動の順列を比較検討すると、組み合わせ爆発が生じる。その爆発した組み合わせを、アドホックに刈り込んで、必要な組み合わせだけを比較するようにして、計算量を軽減する工夫が行われていた。
  
 +
 +=== 強化学習 ===
 +
 +上ででてきたQという関数を、様々な状態の対象に様々な行動を適用して、その結果から試行錯誤を繰り返すことで学習し、その下で最適な行動を選択していく。必要に応じて、アクションごとの状態推移も学習する。
 +
 +https://gym.openai.com/envs/MountainCarContinuous-v0/
 +
 +強化学習の話は、この原稿のスコープを大きく超えるので、別の機会に譲る。
 +
 +==== マルコフ決定過程における方策の学習 ====
 === マルコフ性の活用と状態遷移行列の活用 === === マルコフ性の活用と状態遷移行列の活用 ===
  
-保全の問題では、対象システムに何も保全行動という介入しなければ、システムは劣化していく。 +保全を施さない場合のシステムの劣化が、次の図で表されるマルコフ連鎖に従うとする。
-ただしその状態の遷移は、現在の状態とマルコフ行列に記された条件付き分布に従う。 +
-ゲームはプレイヤーが複数いるのが通例だが、保全の問題では対象であるシステムが打ってくる手はとても単純で、保全行動を実行しなければ劣化による状態遷移が発生する。保全行動を実行すれば、その結果として状態が回復するという状態遷移が発生する。+
  
 {{:r:maintenance:trantisionmatrix-keep.png|}} {{:r:maintenance:trantisionmatrix-keep.png|}}
行 274: 行 292:
 現在の最適な行動と、その行動の帰結として将来に渡って発生する費用の総額は、勿論、将来の費用に依存する。t=∞の時点の費用が分かっていれば、例えば V∞(s)≡0ならば、そこから1時点ずつ遡ってVtを計算していくことが考えられる。この計算が、tを小さくするにつれて、つまり過去に遡るにつれて、ある一定の関数に収束するなら、その関数は次の方程式を満たす。 現在の最適な行動と、その行動の帰結として将来に渡って発生する費用の総額は、勿論、将来の費用に依存する。t=∞の時点の費用が分かっていれば、例えば V∞(s)≡0ならば、そこから1時点ずつ遡ってVtを計算していくことが考えられる。この計算が、tを小さくするにつれて、つまり過去に遡るにつれて、ある一定の関数に収束するなら、その関数は次の方程式を満たす。
  
-{{:bellman-equation-inifinite-horizon-reward.png?450|}}+{{::bellman-equation-cost-discounted.png?400|}}
  
-これがベルマン方程式である。+これがベルマン方程式である。ベルマン更新の式との違いは関数Vの添え字の有無しかない。でもこの違いは、Vが遷移している状態か、定常状態かの違いでもある。 
 + 
 +将来の費用関数をどのように算出するか、そして将来の状態をどのように予測するか、がマルコフ決定過程がうまく働くための鍵となる。 
 + 
 +== 報酬の場合 ==
  
 費用ではなく、報酬が得られる場合は、ベルマン更新が 費用ではなく、報酬が得られる場合は、ベルマン更新が
行 284: 行 306:
 定常状態におけるQ関数とベルマン方程式はそれぞれ次のようになる。 定常状態におけるQ関数とベルマン方程式はそれぞれ次のようになる。
  
-{{:bellman-equation-q-function.png?400|}}+{{::bellman-equation-q-function-reward-discounted.png?400|}}
  
 {{::bellman-equation-reward.png?400|}} {{::bellman-equation-reward.png?400|}}
- 
-そこで、将来の費用関数をどのように算出するか、そして将来の状態をどのように予測するか、がマルコフ決定過程がうまく働くための鍵となる。 
  
 == マルコフ連鎖に基づく予測 == == マルコフ連鎖に基づく予測 ==
行 347: 行 367:
 最終時点のVをひとつ与える。次にベルマン更新 最終時点のVをひとつ与える。次にベルマン更新
  
-{{:bellman-update-markov-chain.png?400|}}+{{:bellman-update-formula.png?400|}}
  
 によって、時点を１つ戻す。毎時点、費用を最小にするように状態sごとに行動aを選ぶ。 によって、時点を１つ戻す。毎時点、費用を最小にするように状態sごとに行動aを選ぶ。
行 358: 行 378:
 この関数を用いて、現時点で将来の推移を考慮しながら、最適な行動を選択する。 この関数を用いて、現時点で将来の推移を考慮しながら、最適な行動を選択する。
  
 +== 要検討課題 ==
  
 +価値反復と方策反復では、得られる方策の解が同じでも、総期待割引き報酬もしくは費用Ｖの値が異なる。なぜか？
 +==== Rでマルコフ決定過程の計算を行う ====
  
-=== 強化学習 ===+[[::r:markovchain]]はマルコフ連鎖(離散時間離散状態マルコフ過程)の遷移行列の推定や、マルコフ過程の性質の解析決定を行う。
  
-上ででてきたQという関数を、様々な状態の対象に様々な行動を適用して、その結果から試行錯誤を繰り返すことで学習し、その下で最適な行動を選択していく。必要に応じて、アクションごとの状態推移も学習する。+[[::r:mdptoolbox]]はマルコフ決定過程の最適方策の学習を行う。
  
-https://gym.openai.com/envs/MountainCarContinuous-v0/+この２つを組み合わせると、データから遷移行列を推定して、その遷移行列と評価関数に基づいてマルコフ決定過程に基づく最適方策の学習を行う、という一連の最適化プロセスを実装できる。 
 + 
 +==== 保全とマルコフ決定過程 ==== 
 + 
 +保全の問題では、対象システムに何も保全行動という介入しなければ、システムは劣化していく。 
 +ただしその状態の遷移は、現在の状態とマルコフ行列に記された条件付き分布に従う。 
 +ゲームはプレイヤーが複数いるのが通例だが、保全の問題では対象であるシステムが打ってくる手はとても単純で、保全行動を実行しなければ劣化による状態遷移が発生する。保全行動を実行すれば、その結果として状態が回復するという状態遷移が発生する。
  
-強化学習の話は、この原稿のスコープを大きく超えるので、別の機会に譲る。