コンピュータ将棋における勾配降下法の最適化アルゴリズム

コンピュータ将棋

　自分用メモ

　勾配降下法を用いてパラメータを更新していくときに、どういった更新式を使えばいいのか気になってきたのでいくつかのソフトについて調べてみた。

　ここではニューラルネットワークは除いて、3駒関係や2駒関係の特徴量を使っているソフトに絞って調べた。ボナンザメソッドと自己対局からの学習とでは事情が違う可能性もあるが、とりあえずは気にしないことにした。

　まず更新式の基本についてはここにあることで学んだ。このページの「どのオプティマイザを使うべき？」のところでは、スパースなデータに対しては学習率を適応させていく手法が良いとあって、つまりはAdaGradとかその派生形のことだと思う。3駒関係等の学習はスパースなので、それらの中から選んでいくことになるんだろう。

やねうら王

2017年11月16日時点では

// ----------------------
//        更新式
// ----------------------

// AdaGrad。これが安定しているのでお勧め。
// #define ADA_GRAD_UPDATE

// 勾配の符号だけ見るSGD。省メモリで済むが精度は…。
// #define SGD_UPDATE

// RMSProp風のAdaGrad
// #define ADA_PROP_UPDATE

という記述がある。RMSProp風のAdaGradというのはよくわからないけど、とりあえずいろいろ試されたらしい雰囲気は見て取れる。AdaGradはどんどん更新量が小さくなっていってしまうのが気になるんだけど、それが一番安定しているのか。

技巧

learning.ccによるとRMSPropを使っているみたいだ。

// 学習率の設定（RMSpropの設定）
constexpr float kRmsPropStepRate = 5.0f; // １回の更新で、最大何点まで各パラメータを動かすか
constexpr float kRmsPropDecay = 0.9975f; // どの程度過去の勾配を重視するか（大きいほど過去の勾配を重視）
constexpr float kRmsPropEpsilon = 1e-4f; // ゼロ除算を防止するために分母に加算される、非常に小さな数

とあるが、kRmsPropStepRateに対するコメントがよくわからない。単なる学習率ではない？ 勾配が正規化されているのだろうか(そんなことしていいのか？)

2017/11/20 追記。僕が勘違いしていた。AdaGradやRMSPropの挙動を全然理解していなかった。

また気になるところとしては、勾配の二乗和の指数移動平均を取っていくところで

  // 更新幅の設定（RMSprop）
    a = a * kRmsPropDecay + (g * g);
    const PackedWeight eta = kRmsPropStepRate / (a + kRmsPropEpsilon).apply(std::sqrt);

となっているのだが、RMSProp等の解説でよく見る感じでは a = a * kRmsPropDecay + (g * g) * (1 - kRmsPropDecy)
と計算しているのが多い気がする(内分を取っている？)。今回の勾配の二乗に(1 - kRmsPropDecy)をかけるかどうかというのは別に本質的な違いではない(展開してみると結局全体に(1 - kRmsPropDecay)かかるかどうかというだけな気がする)ようにも思えるけど、一番最初の更新でちょうどgが打ち消されるのがわかりやすいので技巧のようにするのが良さそうか。

　いやでも数式的な意味としてはかける方がそれっぽい気がする。最初の一回だけは特別扱いした方が良さそう？ 指数移動平均でググると t \ge 3とか書いてある。3なのはちょっとわからないけど、最初は特別視して良さそう(面倒か？)

Apery

learner.hppはあるけどlearner.cppはなくてよくわからない。learner.hppも別に学習用のクラスとかが定義されているわけじゃないし、何か別のファイルにあるのか公開されてないだけかな。

読み太

まだ電王トーナメントのソースは更新されてなくてWCSC27時点のコードだけどSGDとAdaGradが実装されているのは確認できた。読み太はどの程度やねうら王に近いのかがよくわかっていない。

shogi686

SDT5バージョンによるとAdaGradを使っているらしい。

その他

もうコンピュータ将棋からは引退されているけどAkiさんもAdaGradをすすめる記事を書いていた。ここの

線形モデルの学習に限った話。(特に、コンピュータ将棋の評価関数、進行度、実現確率とかでの経験に基づく話。)
非線形モデル(というかNN)の場合は挙動がそれほど素直じゃないので、指数移動平均を使うアルゴリズム(AdamとかRMSPropとか)の方が合っていると思う。

というのが気になる記述で、指数移動平均を使うかどうかっていうのはそこが問題だったのか。

疑問点など

　AdaGradは確かに挙動がわかりやすそうで扱いは楽に思える。しかし更新量がどんどん減少してしまうのがちょっと気になるっちゃ気になるところで、ある程度学習した重みに対して学習をしなおす場合、勾配の二乗和を前のものから取ってくるのと0から始めるのでも大きく結果が変わりそうなのがなんかしっくりこない。

　その点はRMSPropの方がまだいいかなぁという気もするんだけど、技巧しか採用していないというのがなんとも。逆に言えばあの技巧が採用しているんだからまったく合わない方法ではないんだろうけど。

　2駒と3駒の違いとか、自己対戦からの学習かそうでないかの違いなどが影響しているのだろうか。よくわからない。とんでもない高次元空間の関数を最適化しようとしているわけで、常識がどの程度通用するのかもわからない。

まとめ

　AdaGradでいいのでは。

コメントによる指摘(2017/11/19追記)

　darumaさんからAperyのボナメソ及びelmo絞り、nozomi、Squirrelについての情報も提供していただいたので下方のコメントも参照のこと。