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

 自分用メモ

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

 ここではニューラルネットワークは除いて、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; // 1回の更新で、最大何点まで各パラメータを動かすか
constexpr float kRmsPropDecay = 0.9975f; // どの程度過去の勾配を重視するか(大きいほど過去の勾配を重視)
constexpr float kRmsPropEpsilon = 1e-4f; // ゼロ除算を防止するために分母に加算される、非常に小さな数

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

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

  // 更新幅の設定(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でいいのでは。

CODE FESTIVAL 2017 予選B 参加記

結果

 A,B問題2完の741位。うーむC問題が解けないのはちょっと苦しいところか。精進が足りない。レート1535→1516(-19)

A問題

 後ろから8文字を削除するだけ。

#include <bits/stdc++.h>
using namespace std;
 
int main()
{
    string S;
    cin >> S;
    cout << S.substr(0, S.size() - 8) << endl;
}

B問題

 mapで各難易度について必要数と作成済数を記録していけば解けると思ったんだけど、先に必要な数を引いていくとREが出てしまった。mapだからデフォルトは0で、引いたらなにかおかしいことがあるのかな? ちょっとよくわからなかったけど先に足すようにすれば通った。

#include <bits/stdc++.h>
using namespace std;
 
int main()
{
    int N;
    cin >> N;
    vector<int> D(N);
    map<int, int> mp;
    for (int i = 0; i < N; ++i) {
        cin >> D[i];
        mp[D[i]]++;
    }
    int M;
    cin >> M;
    vector<int> T(N);
    for (int i = 0; i < M; ++i) {
        cin >> T[i];
        if (mp[T[i]] == 0) {
            cout << "NO" << endl;
            return 0;
        }
        mp[T[i]]--;
    }
 
    cout << "YES" << endl;
}

C問題

 これが全然わからなかった。考察のとっかかりすらうまくつかめなくて、座っているだけの時間が多くなってしまった。明らかにN, Mが大きいので、まともな最短経路を求めてなんとかしていくわけではないだろうとは思った。そして、頂点の偶奇がちょっと怪しいかと思ってコードを投げてみたりもしたんだけど、片方だけ通すことすらできなかった。

 解説を読んだけど、まず2部グラフという用語の定義すらちゃんとわかってなかった。知識が圧倒的に足りない。

CODE FESTIVAL 2017 予選A 参加記

結果

A,B,C問題を解いて3完。C問題でかなり手間取ってしまったのが痛かった。時間があってもD問題を解けたがどうかはわからないが、しっかり考えてみたかった。

 一応CODE FESTIVALの方にエントリーはしてみているけど、まぁ無理だわな。

A問題

 substrで先頭4文字だけ取ってきて比較するだけ。今考えると4文字未満のときを考慮してなかったのでC++の仕様に救われたか。まぁ親切にも入力例3で3文字のケースがあるので、問題があってもWA出す前に気づけてはいたと思うけど。

#include <bits/stdc++.h>
using namespace std;

int main()
{
    string S;
    cin >> S;
    if (S.substr(0, 4) == "YAKI")
        cout << "Yes" << endl;
    else
        cout << "No" << endl;
}

B問題

 2回押すと元に戻るだけだから各ボタンについて押すか押さないかだけが重要。

 行ボタンのうちi個、列ボタンのうちj個を選ぶと  i \times M + (N - i) \times j - i \times j 個が黒くなるはずで、それで解ける。

 コードだと頭が悪くて列を先に押すのと行を先に押すので結果が変わると勘違いしている。何をやっているんだ。普通に二つとも同じ式じゃないか……。というか順番によって結果が変わると思ってしまうのがかなりセンス悪い気がする。頑張ろうな。

#include <bits/stdc++.h>
using namespace std;

int main()
{
    int N, M, K;
    cin >> N >> M >> K;

    for (int i = 0; i <= N; ++i) {
        for (int j = 0; j <= M; ++j) {
            if (i * M + (N - i) * j  - i * j== K
                    || j * N + (M - j) * i - i * j== K) {
                cout << "Yes" << endl;
                return 0;
            }
        }
    }
    cout << "No" << endl;
}

C問題

 最初は

  • HとWが両方奇数のとき、奇数個の文字が1個、それ以外の文字は偶数個
  • そうでないとき全部の文字が偶数個

で解けると勘違いしてコードを書き始めてしまったんだけど、入力例2で失敗してちょっと困る。ここで小手先の回避方法として

  • HとWが両方2以上の時は4回以上表れている文字が最低1個は必要

という条件を付け足して、とりあえずサンプルだけ通るようにして提出してしまい、当然WA。

 しばらく考えてから、4個必要になる領域は角だけじゃないことに気づいて、HとWの偶奇によって偶偶 or 奇奇 or 偶奇(奇偶)で場合分けして書き直したが、まだ1個だけWAが出るようになった。

 どうしてもわからなかったのでそれぞれの場合分けに一個ずつassert(false)を仕込んでみたところ、奇奇のところでWAがREになったので、ここで変なことが起きていると判断した。今回はペナルティがなしということだってのでこういう邪悪なハックをやることに対する抵抗がちょっと小さかった。

 で、何が間違っていたかというと、4個以上出てくる文字が奇数になっている場合というのを考慮していなかった。たとえばaが5個出てきて、1個を中央に使って4個を対象的に使うとか、そういうことがありえるんだ。気づいたらすぐ直せてAC。結構大変だった。

#include <bits/stdc++.h>
using namespace std;

int main()
{
    int H, W;
    cin >> H >> W;
    vector<string> a(H);
    vector<int> num(26, 0);
    for (int i = 0; i < H; ++i) {
        cin >> a[i];
        for (char c : a[i]) {
            num[c - 'a']++;
        }
    }
    int odd_num = 0;
    int num4 = 0;
    for (int i = 0; i < 26; ++i) {
        num4 += num[i] / 4;
        if (num[i] % 2 == 1) {
            odd_num++;
        }
    }

    if (H % 2 == 0 && W % 2 == 0) {
        if (odd_num == 0 && H * W / 4 <= num4)
            cout << "Yes" << endl;
        else
            cout << "No" << endl;
    } else if (H % 2 == 1 && W % 2 == 1) {
        if (odd_num == 1 && (H - 1) * (W - 1) <= num4 * 4)
            cout << "Yes" << endl;
        else
            cout << "No" << endl;
    } else {
        //必ずHが奇数ということにする
        if (H % 2 == 0)
            swap(H, W);

        if (odd_num == 0 && (H - 1) * W / 4 <= num4)
            cout << "Yes" << endl;
        else
            cout << "No" << endl;
    }
}

 場合分けが美しくないと思ったのでちょっと書き直してみた。まぁ本番でこれを書きにいくことはしないかなぁ。でもこれの方が解法をちゃんと理解した上でのコードっぽい気はする。

#include <bits/stdc++.h>
using namespace std;

int main()
{
    int H, W;
    cin >> H >> W;
    vector<string> a(H);
    vector<int> num(26, 0);
    for (int i = 0; i < H; ++i) {
        cin >> a[i];
        for (char c : a[i]) {
            num[c - 'a']++;
        }
    }
    int odd_num = 0, num4 = 0;
    for (int i = 0; i < 26; ++i) {
        num4 += num[i] / 4;
        if (num[i] % 2 == 1) {
            odd_num++;
        }
    }

    //4個使う領域(たとえば右上)を求めるときの長さ
    int h = (H % 2 == 0 ? H / 2 : (H - 1) / 2);
    int w = (W % 2 == 0 ? W / 2 : (W - 1) / 2);

    if (odd_num == (H % 2 == 1 && W % 2 == 1)
            && h * w <= num4)
        cout << "Yes" << endl;
    else
        cout << "No" << endl;

    return 0;
}

D問題

 時間もなかったので、単純にRYGBの順で塗れるだけ塗ってみるとか、できるだけバランスよく塗ってみるとか、簡単な方法で貪欲にやっていくのを試してみたけどWA。間違ってるパターンをいろいろ出してみて眺めているうちに時間切れ。

 ある場所に対して同じ色を塗れない位置が角の利きに似ているので一瞬Rotated Bitboardみたいな考え方が頭をよぎったんだど、それを推し進めることができなかった。マンハッタン距離は45度回転させてみるというの、ちょっと気に留めておいていいパターンだと思う。