ラビットチャレンジレポート　深層学習　Day4　その１

Section1 強化学習

1-1強化学習とは

　長期的に報酬を最大化できるように環境のなかで行動を選択できるエージェントを作ることを目標とする機械学習の一分野である。
下記のように、ある方策Πに基づいた行動をとり、状態Sの変化を観測して価値Vを報酬として受け取るというプロセスが、強化学習のイメージである。この報酬を最大化するように方策を決定する。
　f:id:tibet:20211203153813p:plain

1-2 強化学習の応用例

　囲碁やチェスなどのゲームが有名だが、実用的には、例えばマーケティングへの応用が想定できる。
　エージェントはプロフィールと購入履歴に基づいてキャンペーンメールを送る。
　行動としては、顧客ごとに送信非送信のふたつの行動を選ぶことになる。
　報酬としては、キャンペーンのコストという負の報酬とキャンペーンで生み出される売り上げという正の報酬をうけることになる。

1-3探索と利用のトレードオフ

環境について完璧な知識があれば、最適な行動について完璧な予測が可能ではないかとも考えられる。例えば、どのような顧客にキャンペーンメールを送ると、どのような行動をとるか既知の状況である。
　強化学習では、上記仮定が成り立たないと考える。不完全な知識を元に行動しながらデータを収集し、最適な行動を見つけていく。
　ここで、過去のデータを元に最適な行動のみをとり続けるという方策をとるとする。この場合は、他に存在するかもしれないベストの行動を見つけることは出来ない。これは探索が足りない状態ということが出来る。
　一方で、未知の行動のみをとり続けるという方策をとると、過去の経験が生かせない。これは経験が足りない状態ということが出来る。
　両者の方策のトレードオフを、探索と利用のトレードオフと呼ばれる。行動の方策を決める場合は、探索と利用の間のバランスをとることが必要である。

1-4強化学習イメージ

計算のため、以上の強化学習のイメージを数式で表現する。
下図のように方策πに対しては、方策関数 \Pi(s,a)を定義、価値Vに関しては、行動価値関数 [tex;: Q(s,a)]を定義する。
f:id:tibet:20211204103102p:plain

1-5 強化学習の差分

　強化学習と通常の機械学習（教師あり/なし）との違いは、学習の目標が異なることである。
　・教師あり/なし学習では、データに含まれるパターンを見つけ出だすこと、及びそのデータから予測することが目標である。
　・強化学習では、優れた方策を見つけることが目標である。

1-6 強化学習の歴史

　強化学習の概念は以前からあったが、深層学習以上に計算能力が必要なため、コンピューティング能力が追いついておらず、注目されない冬の時代もあった。近年はコンピューティング能力が上がり、強化学習のコンセプトが実現可能になりつつあり、注目を集めている。
　また、関数近似法とQ学習を組み合わせる手法が登場し、注目を集めている。

  • Q学習：行動価値関数を、行動するごとに更新することにより学習を進める方法
  • 関数近似法：価値関数や方策関数を価値関数近似する手法のこと

1-7価値関数

価値関数とは、価値Vを表す関数で、状態価値関数と行動価値関数の二種類がある。
状態価値関数：状態sの価値を表す関数
行動価値関数：ある状態sの時の行動aの価値を表す関数

1-8方策関数

　方策ベースの強化学習手法において、ある状態でどのような行動をとるのかの確率を与える関数 \pi (s)=aのこと。
関数の関係
　 pi(s,a)は、VやQを元にどのような行動をするか決定する。
　 V^{\pi}(s):状態関数　[tex: Q^{\pi}(s,a) :状態+価値関数：ゴールまで今の方策を続けたときの報酬の予測値が得られる。
　

1-9方策勾配法について

　価値関数を求め、それを元に行動を決定するアプローチもあるが、 V^{\pi}や Q^{\pi}を求めるため、複雑でメモリを消費することや連続空間では扱いにくいといった課題がある。
　そのため、方策関数を直接学習するというアプローチも考えられる。これが方策勾配法である。
　θでパラメタライズされた方策関数π(s,a|θ)を考える。
　最適なθを求めるため、下記のような反復方法を考える。
　 θ^{(t+1)}=θ^{(t)}+ε∇J(θ)
∇J(θ)はニューラルネットワークの誤差関数、εは学習率に相当する。θの式では加算されているが、これはθの最大値を求めるからである。
　強化学習がパラメータの最適値を求める問題となり、ニューラルネットワークを使用することが可能になった。
　J(θ)は、方策の評価関数で、方策πとその時の報酬Qを用いて、下記のように書ける。
　 J(θ)=\displaystyle \sum_{a \in A} π_{θ}(a|s)Q^{π}(s,a)
　θによる微分を求めると、下記の期待値となる。
　 ∇_{θ}J(θ)=E_{π_{θ}}\lbrack (∇_{θ}logπ_{θ}(a|s)Q^{π}(s,a)) \rbrack

Section2 Alpha GO

ここでは、強化学習、及びAIに大きなインパクトを残したDeep Mindが開発したAlpha Goのアルゴリズムについて解説する。Alpha Goは2015年に人間のプロ棋士にハンディキャップなしで初めて勝利した囲碁プログラムとなった。次いで2016年に世界トップ棋士であるイ・セドル、2017年に柯潔に勝利し、コンピュータにとって、人間に打ち勝つことが最も難しいと思われた囲碁で人間に勝利したプログラムとして、世界に大きな衝撃を与えた。その後、過去の試合データを使用せず、自己対戦の強化学習のみで学習したAlpha ZeroがAlpha Goを上回る性能を示した。
ここでは、Alpha Go (Lee)とAlpha Zeroについて解説する。

Alpha Go (Lee)

Alpha Go(Lee)の学習プロセスは、下記のステップで進む。
1. 教師あり学習によるRollOutPolicyとPolicyNetの学習
2. 強化学習によるPolicyNetの学習
3. 強化学習によるValueNetの学習

Alpha Go(Lee)のPolicyNet

f:id:tibet:20211205213229p:plain
入力は、19×19の2次元で、48チャンネルである。
ネットワークは、CNNで、softMaxによって19×19の着手予想確率を出力する。
入力の48チャンネルはそれぞれ下記のような入力に対応する。
f:id:tibet:20211205213402p:plain

RollOutPolicy

PolicyNetはニューラルネットネットワークなので、盤面の推論の際の計算量が多く、時間がかかる。そこで、探索中に高速で着手確率を出すために使用されるためにRollOutPolicyという方策関数が用意されている。こちらは線形の関数のため、計算が速い（PolicyNetの約1000倍）。RollOutPolicyで打ち手を絞り込み、PolicyNetで精度の高い打ち手を出すといった使い分けが考えられる。
　RollOutPolicyの入力は以下である。
f:id:tibet:20211205215418p:plain

PolicyNetとRollOutPolicyの教師あり学習

　KGS Go Server(ネット囲碁対局サイト）の棋譜データから300万局面分の教師を用意し、教師と同じ着手を予測できるよう学習を行った。
具体的には、教師が着手した手を１とし、残りを０とした19×19次元の配列を教師とし、それを分類問題として学習した。
　この制度で作成したPolicyNetは57％程度の精度である。

PolicyNetの強化学習

　まず、PolicyNetの強化学習の過程を500Iterationごとに記録し保存して、PolicyPoolを作る。
　次に現状のPolicyNetとPolicyPoolからランダムに選択されたPolicyNetと対局シミュレーションを行い、その結果を用いて方策勾配法で学習を行う。
　現状のPolicyNet同士の対局ではなく、PolicyPoolに保存されているものとの対局を使用する理由は、対局に幅を持たせて過学習を防ごうというのが主たる理由である。
　この学習をmini batch size 128で1万回行った。

ValueNetの学習

　PolicyNetを使用して対局シミュレーションを行い、その結果の勝敗を教師として学習する。
　教師データ作成の手順は、
1. まずSL PolicyNet(教師あり学習で作成したPOlicyNet)でN手まで打つ。
2. N+1手目の手をランダムに選択し、その手で進めた局面をS(N+1)とする。
3.S(N+1)からRL PolicyNet(強化学習で作成しtあPolicyNet)で終局まで打ち、その勝敗報酬をRとする。
S(N+1)とRを教師データ対とし、損失関数を平均二乗誤差とし、回帰問題として学習した。
　この学習をmini batch size 32で5000万回行った。
　N手からN+1手からのPolicyNetを別々にしてある理由は、過学習を防ぐためである。

モンテカルロ木探索

　min-max探索やαβ探索では、盤面の価値や勝率予想値が必要だが、囲碁では
盤面価値や勝率予想値を出すことが困難とされてきた。
　そこで、盤面評価値によらず、末端評価値、つまり勝敗のみを使って探索を行うという発想で生まれた探索法である。囲碁の場合、他のボードゲームと違い、最大手数はマスの数でほぼ限定されるため、末端局面に到達しやすい。
　具体的には、現局面から末端局面までをPlayOutと呼ばれるランダムシミュレーションを多数回行い、その勝敗を集計して着手の優劣を決定する。
　また、該当手のシミュレーションが一定数を超えたら、その手を着手した後の局面をシミュレーション開始局面とするよう、探索気を成長させる。
　この探索木の成長を行うという点が、モンテカルロ木探索の優れているところである。
　モンテカルロ木探索は、この木の成長を行うことによって、一定条件下では探索結果は最善手を返すことが理論的に証明されている。
　Alpha Go(Lee)のモンテカルロ木探索は、選択、評価、バックアップ、成長という4つのステップで構成されている。

AlphaGo Zero

AlphaGo(Lee)とAlphaGo Zeroの違い

1. 教師あり学習を一切行わず、強化学習のみで作成
2. 特徴入力からヒューリスティックな要素を排除し、石の配置のみにした
3. PolicyNetとValueNetを1つのネットワークに統合した
4. Residual netを導入した
5. モンテカルロ木探索からRollOutシミュレーションをなくした

AlphaGo Zeroの学習法

　AlphaGo Zeroの学習は、自己対局による教師データの作成、学習、ネットワークの更新の3ステップで構成される。

  • 自己対局による教師データの作成

現状のネットワークでモンテカルロ木探索を用いて自己対局を行う。
　まず30手までランダムで打ち、そこから探索を行い、勝敗を決定する。
　自己対局中の各局面での着手選択確率分布と勝敗を記録する。
　教師データの形は、[局面、着手選択確率分布、勝敗]が1セットとなる。

  • 学習

　自己対局で作成した教師データを用い、学習を行う
　NetworkのPolicy部分の教師に着手選択確率分布を用い、Value部分の教師に勝敗を用いる。
　損失関数はPolicy部分はクロスエントロピー、Value部分は平均二乗誤差。

  • ネットワーク更新

　学習後、現状のネットワークと学習後のネットワークとで対局テストを行い、学習後のネットワークの勝率が高かった場合、学習後のネットワークを現状のネットワークとする。
　

AlphaGo ZeroのPolicyValueNet

　入力は17チャンネルの19×19の盤面で、途中からPolicy出力とValue出力に分れる。また中間にResidual Blockを挟む。
f:id:tibet:20211207204744p:plain　

Residual Block

ネットワークにショートカット構造を追加して、勾配爆発、勾配消失を防いだもの。
Residual Networkを使うことにより、100層を超えるネットワークでも安定した学習が可能になった。
また、Redisual Networkを使うことにより層数が異なるネットワークのアンサンブルの効果を得られるという話もある。
f:id:tibet:20211207205125p:plain

  • Residual Blockの工夫
    • Bottleneck

1×1 KernelのComvolutionを利用し、1層目で次元削減を行って2層目で次元を復元する3層構造にしたもの。2層のものと比べて計算量はほぼ同じだが、1層増やせるメリットがある

  • PreActivation

ResidualBlockの並びをBatchNorm→ReLu→Convolution→BatchNorm→ReLu→Comvolution→Addとすることにより性能が上昇した

  • Network構造の工夫
    • WideResNet

ConvolutionのFilter数をk倍にしたResNet。1倍→k倍xブロック→2k倍yブロックと段階的に幅を増やしていくのが一般的。Filterを増やすことにより、浅井層数でも深い層数のものと同等以上の精度となり、またGPUをより効率的に使用できるため学習も早い。

    • PyramidNet

WideResNetで幅が広がった直後の層に、過度の負担がかかり精度を落とす原因になっているとし、段階的にではなく、各層でfilterを増やしていくResnet。

AlphaGo Zeroのモンテカルロ木探索

　選択、評価及び成長、バックアップという３つのステップで構成される。
　評価及び成長時にRollOutは行わないところがAlphaGO(Lee)と異なる。