JOI 2018/2019 春合宿 講義５「競技プログラマーからみた機械学習」

（個人用のメモにつき解読不能です）

機械学習
ゲーム以外にも様々な応用
強化学習のプログラムは特にゲーム AI で多く登場する
他にも自動運転やロボット操作などにも応用される

ベンチマーク
OpenAI Gym という制御問題，物理シミュレーション，Atari ゲームなど様々なタスクを含んだ環境がよく用いられる

ディープラーニングは関数を近似するものとしてしか使わないことが多い，ほかにも本質がある
現状ではうまくデータセットやアルゴリズムを用意する必要がある

強化学習
報酬を大差異化することが強化学習の課題になる
例：迷路
迷路生成アルゴリズムを見て最適化することは禁止されている
入力は移動ルールや周辺情報，出力はソルバー
例：Mountain car problem

環境の中身を直接見て最適化することはできない
→ 環境内で実際に動かして得られた結果から推論する必要がある
探索と最適化を同時にしなきゃいけない
どちらか一方だといつまでも最適化されなかったり，局所解に陥ってしまうかもしれない

（ある行動の優先度）＝（行動結果の期待値）＋（不確定さ）
あまり調査されていない行動を優先して解析するようになる
自動的に優先度が調整される

次の状態を推定するために必要な観測情報全てを知ることが出来る設定を考える
→ マルコフ決定過程と呼ぶ
状態の集合，行動の集合，状態遷移確率関数 P，報酬関数 R
状態と過程が決まっているものがマルコフ報酬過程
次の状態が観測できない相手の戦略に依存しているものなどはマルコフ過程ではない

方策は各状態から次の行動を出力するための関数
方策が決定的か確率的かによって出力が異なる
報酬関数は現在の行動の良しあしを定義する実数値報酬を出力する
知りたいのは行動によって得られる補修ではなく，将来的に得られる報酬の総和
価値関数を定義する
割引率は将来に得られた報酬が現在の価値観数に対してどれだけ割引いて影響を与えたかを表している
大きいと長期的に考えられるが，学習が安定しにくい
小さいと短期的に最適化するが，学習が相対的に安定しやすい

環境から状態と報酬をもらい，学習しつつ次の行動を出力することを繰り返す
学習方針
価値関数を計算する方針
方策を直接計算する方針
Actor - Critic 法

価値関数の求め方
方策を状態に対して常に行動を返すよう決定的な方策であるものとする
動的計画法を用いて解くことが出来る
遷移確率が未知なので，このまま適用することは出来ず，シミュレーター上で方策に基づいて解を改善する方針を考える
行動価値関数もどうように計算できる
実際のがぞうなどの解析には適用できない

ニューラルネットワーク
ニューロンと呼ばれる入力信号を受け取って，出力信号に値を出力するものを多層に重ねたもの

Deep Q-Network
ゲームの画面自体を状態として学習させる条件下で人間に匹敵するスコアを獲得できた

経験再生 (Experimental Replay)
今までに得られたデータを保存して，学習時に過去の方策に従って行動した時のデータを無作為に取り出せるようにする
発展的な方法として，過去の経験に重みをつけて，有意義なデータを取りやすくする手法もある
ターゲットの固定 (fitted Q)
Double Q-Learning では，目的関数を２つのネットワークで表現する
一方のネットワークで選ばれた行動の結果を，他方のネットワークを使って評価することで，より安定させて学習させる

最適方策を計算する方針
方策勾配定理
REIN FORCE

Actor-Critic法
Actor：最適な方策を勾配に従って計算，Critic：状態価値関数を計算
Asynchronous Advantage Actor-Critic (A3C)
Actor-Critic を並列計算とアドバンテージ関数の２操作をつけ足して効率化した手法
Deep Deterministic Policy Gradient (DDPG)
Twin Delayed DDPG (TD3)
過大評価を抑制する
Trust Region Policy Optimization (TRPO)
Proximal Policy Optimization (PPO)

報酬関数設計の問題
報酬関数として一番簡単なのは「成功すれば１，失敗すれば -1」
→ これはランダムに行動したときのような成功率が低いタスクの場合，学習がほとんど成功しない
報酬関数を手動でチューニングするという方法もあるが，問題ごとに設計しなきゃいけない
→ ズルい方針を立ててしまった学習例

Intrinsic Curiosity Module
好奇心というパラメータを定義したアルゴリズム
状態から抽出した特徴量ベクトルに対して，次の特徴量を予測する関数をつけ足して，予測値と実際の差を追加の報酬とする
自分が影響を及ぼせる状況の変化のみを対象とする

模倣学習
最適な行動からうまく方策や報酬を推定したい場合がある
→ 車を運転する場合，ぶつからないように報酬を設計するのは大変，最適な行動のデータは収拾することは出来る
このような枠組みを模倣学習 (Imitation Learning) と呼ぶ
学習は難しい
未知のデータに対しては何も学習されない，微小な推論誤差を修正できず，そのうち大きな誤差になってしまう

Generative Adversarial Imitation Learning
敵対的ネットワークを組み合わせることで学習する手法が提案された
Generator, Discriminator の２ネットワークを同時に学習させる
Generator：教師データと思わせるようなデートを出力する
Discriminator：教師データなのか Generator 由来なのか見分ける

部分観測マルコフ決定過程 (Partialy Observed MDP)
深層学習のライブラリ
Chainer
多くのアルゴリズムが実装されている
OpenAI Gym
ベンチマークの例：ViZDoom, Obstacle Tower Challenge