コンピュータ将棋研究で得たQ学習に関する有用な知見

どうも、 **シオザキ** といいます。
 **桜丸** という名前で５年ほどコンピュータ将棋を研究しており、 **mEssiah** というソフトを作っています。
今回はコンピュータ将棋でQ学習を使うにあたり得た、Q学習についての基礎的な知見を紹介しようと思います。
なお、本記事に書かれていることは理論的に証明されていることはほぼなく、私が **実験で得た経験を元に考察したもの** ですので、最悪の場合全て間違っているということもありえます。
ですので、参考程度にとどめていただけると幸いです。

# Q学習とは

省略。解説しているページはいろいろあるのでそちらをご参照ください

# コンピュータ将棋でQ学習を使うにあたり得た有用な知見

### １、関数近似を使うQ学習とテーブル型Q学習の違い
### ２、精度が頭打ちになる理由とその見分け方
### ３、モデルの形、大きさによる精度の違い
### ４、試行方策の重要性


## １、関数近似を使うQ学習とテーブル型Q学習との違い
Q学習というのは元々 **表引きノード価値評価** を使用する前提で作られています。
 **表引きノード価値評価** というのはなんじゃらほい、という話になりますが、これはQ学習を使って解く問題に出現する **すべてのノードの価値** を **表** に記録しておき、それを学習によって更新して最終的に全てのノードの正しい価値を見つけ出すという方法です。
この方法には大きな弱点があり、問題に出現するノードの数が莫大になってしまうようなものであれば、全てを記録するにはハードウェアが十分でなく、不可能になってしまうということです。

そこで全てを記録するのではなく、 **関数近似** を使うことによって記録に使用するハードウェアを現実的なレベルまで削減したい、というのがQ学習で **関数近似評価** を使う理由です。
 **データの関数近似での記録** という方法は一般的には **機械学習** と呼ばれます。

しかし、Q学習で関数近似を使う場合に大きな問題となることがひとつあります。
 **Q学習は現状の評価を学習に使用する** という学習方法です。
学習により現状の評価精度がどんどん向上して、それによって学習がどんどん進むというのがQ学習のざっくりとした説明になりますが、ここで表引き評価では起こらなかった大問題が関数近似評価では起こることになります。
それは、 **「学習したノード以外の評価が学習によって変化してしまう」** ことです。
これは機械学習の利点 **「学習に使用していない未知のものに対しても正しい評価を行える可能性がある」** ということの要因ともなるのですが、Q学習で使うにあたっては致命的な問題となります。

それはQ学習では **「現状のノードの評価」** を使って **「現状のノードの評価」** を学習して更新していきますが、学習することにより **「学習していないノードの評価」** が変化してしまい、その作用によってノードの評価精度がどんどん向上していくというサイクルが **崩れてしまうこと** があるからです。

例をあげましょう。
まず **ノードA1** 、 **ノードB1** があり、そこからつながっている **ノードA2** 、 **ノードB2** があるとします。
 **ノードA1** を学習するには **ノードA2** の **「現状の評価」** を使用し、 **ノードB1** を学習するには **ノードB2** の **「現状の評価」** を使用するとすると、 **表引き評価の場合** は **ノードA1** の学習の影響を **ノードB1** が受けることはなく、 **ノードB1** の学習の影響を **ノードA1** が受けることはありませんが、 **関数近似の場合** はすべてのノードの評価がつながっているようなものなので、 **がっつり影響を受けてしまいます** 。
この影響はQ学習にとっては **深刻なノイズ** となり、学習が進まない主な原因となります。

これを防ぐにはどうしたらよいか？
完全に防ぐには **関数近似評価を使わない** という選択しかありませんが、ここで少し発想を変えます。
学習の影響が学習していないノード評価に影響してしまうことが全て **悪性ノイズ** となるでしょうか？

 **実はならない状態が存在します。** 

それは、 **他のノードの学習の影響** で **「精度が向上する」** 状態です。
 **他のノードの学習の影響** で **「精度が低下する」** から、どんどん学習によって精度が向上していくサイクルが **崩壊** するのであって、 **他のノードの学習の影響で精度が向上しさえすればいいのです。** 

 **具体的にどうすればよいか？** 
 **他のノードの学習の影響** を **「精度の向上」** に限定する方法は現在までに見つかってはいません。
ならどうするか？
上がるか下がるかの２択なので、 **上がる状態を引くまで学習すればいい** だけです。
上がる状態になるまで **「学習に使う評価」** を更新せず、学習したノードと、その影響を受けたノードの評価精度がともに上昇したら **「学習に使う評価」** を更新する、という手法です。
これがDQN等で使われる **「教師となるモデルを一定期間固定する」** 意味です。

## ２、精度が頭打ちになる理由とその見分け方
私の経験上、精度が頭打ちになる理由は２つ、 **近似関数の表現力オーバー** と、 **試行方策のランダム性が低すぎる** 場合です。
見分け方は、まず後述する **試行方策のランダム性についての試験** を行ったあと、それで反応がなければ近似関数の表現力オーバーかな、という感じです。
ここについては現在も研究中ですので、未来にはもっと新しいことがわかるかもしれません。

## ３、モデルの形、大きさによる精度の違い
 **モデルサイズ：** 大きいほうが精度が高い

 **モデルの横幅（Convolutionならフィルターサイズ、FullConnectならユニットサイズ)：** 広いほうが精度は高くなるが、後述する層数を増やす場合より精度向上/処理速度比が悪い

 **モデルの層数：** 層が多いほうが精度が高くなるがより発散しやすくなり、学習率を下げることが必須となり学習効率が悪くなる

 **Convolution or FullConnect：** Convolutionは学習の進みが早いが精度/処理速度パフォーマンスが低い。逆にFullConnectは学習の進みが非常に遅い（私の経験上、 **Convolutionの50倍くらいの学習が必要** ）が、精度/処理速度パフォーマンスが非常にいい

 **スキップ接続の形：** ResNet＜DenseNet 理論的にはそうらしいので現在実験中

## ４、試行方策の重要性
Q学習の収束条件に **「すべてのノードに無限回訪れて学習する」** とあり、それを実現するにあたり試行方策は **完全ランダムが理想的** ではあるが、現実的にQ学習を使用する問題の **目標精度を完全収束とするものはまずなく、ある程度実用的な精度であればよい** 、となることが多い。また、完全ランダムでは学習の進みが非常に遅く、実用的な精度になるまで **膨大な時間** がかかってしまう。

そこで **試行方策のランダム性を下げ** 、greedy方策に近づけることにより **学習の進みの遅さを改善すること** が可能である。しかし、その場合学習時に選択されなかったノードの精度向上が望めず、試行方策のランダム性が低すぎると本来近似関数が持ってる表現力を十分活用できず、早々に学習が進まなくなり精度が頭打ちしてしまう。

 **学習の進みは止まらないが、精度上昇が遅すぎない最適なランダム性を持たせることが非常に重要である。** 

### ランダム性が低すぎるときの判別法
 **１．まず精度上昇が頭打ちになるところまで学習を行う。** 
 
**２．その後、フルランダム方策でしばらく学習を行う。目安はランダム方策にしたことによる精度低下が止まり、その後ゆるやかな精度上昇に転じるまで** 

 **３．そうしたら試行方策のランダム性を元に戻してしばらく学習を行う。これで精度が頭打ちラインを越えたら、その試行方策はランダム性が低すぎるとわかる。** 

ちなみに頭打ちの原因が試行方策の問題ではなくモデルの表現力の枯渇である場合には、フルランダム方策にしたときにゆるやかな精度上昇に転じず横ばいになる、または試行方策を元に戻したあとに学習しても精度が頭打ちラインを超えないということで判別できる。


今回発表する知見は以上となります。









個人的な話になりますがこんなことを知ってる人材をあなたの会社におひとりどうですか？
また、日々こんな研究をしていますがとてもお金にこまってるのでスポンサーになってくれるという方はいませんか？
はぁ、最低限タバコが１日１箱買えるくらいの生活がしたい。。。