The Natural Language of Actionsを読んだ際のメモ

出典

 International Conference on Machine Learning 2019に採択

読んだ理由

 うさぴょん外伝のアピール文書を読んでから行動表現の学習に興味が出ている。自然言語処理における分散表現の考え方に近いなと思いながらICML2019の論文一覧を見ていたところ、かなり明示的にそういったことを主張していた論文があったので読んでみた。

概要

 行動ログ(コーパス)から行動表現を学習するための手法Act2Vecを提案。

詳細

 基本的にSkip-Gramの考え方をそのまま行動表現の学習に適用する。

学習

 既存の行動・状態ログがあると仮定し、そこから状態s_t,行動a_tに対する幅wのコンテキストc_w(s_t, a_t) = (s_{t - w}, a_{t - w}, \dots, s_{t-1}, a_{t-1}, s_{t+1}, a_{t+1}, \dots, s_{t+w}, a_{t+w})を得る。表記の簡略化のため状態行動とそれに対するコンテキストのペア \lt (s,a), c_w(s, a) \gt(a, c)で表すものとする。

 行動aの分散表現を\vec{a}、コンテキストのcの表現を\vec{c}としたとき、このペア(a, c)がデータの中にある確率をモデル化する。シグモイド関数\varsigmaとして $$ P(true; a, c) = \varsigma(\vec{a}^{\mathrm{T}} \vec{c}) $$ とする(この定式化がSkip-Gramのそれと一致しているのかがよくわからない)。

 ネガティブサンプリングも入れて、P_cを周辺ユニグラム分布として損失は $$ l(a, c) = \log{\varsigma(\vec{a}^{\mathrm{T}} \vec{c})} + k \mathbb{E} _{c_N \sim P_c} \log{\varsigma(-\vec{a}^{\mathrm{T}} \vec{c_N})} $$ とする(ネガティブサンプリングサンプリングって逆方向のドロップアウト的なものかと思っていたがそういう式になっているのかわからない)。

利用法1:行動価値の近似

 行動の表現を\psi(a)、状態の表現を\phi(s)としたとき、行動価値を次のように推定する。

$$ \hat{Q}(s, a) = \psi(a)^{\mathrm{T}} \phi(s) $$

利用法2:効率的な探査(k-Exp)

 行動の分散表現はk-means法などでk個のクラスタに分割できる。

  1. クラスタをランダムに選択する
  2. クラスタ内から行動をランダムにサンプリングする

とすることで意味的に異なる行動を均一にサンプリングできるので効率の良い探索が行える。

実験

Drawing

  • 正方形(長方形?)を描くタスク
  • 行動は上下左右4方向と、上右、右上など4方向を組み合わせた8方向(上下など真逆の行動対は無し)の計12種類
  • 描画が完了したときにだけ、描かれた形状が長方形のときに正の報酬を付与
  • 人間がやったコーパスから事前にAct2Vecを学習

f:id:tokumini:20190617185613p:plain

  • 行動表現が点対称のように学習されている(一番左の図)
  • 実際に用いるとOnehotやrandomで与えるよりもAct2Vecの方が高性能

Navigation

  • 障害物を避けながら特定の場所へ進むタスク
  • 前進、左右に向きを変えるの3つの行動が可能 →行動の系列を考えると表現に意味が出る
  • 考慮する系列長kとしてk=1,2,3の場合について学習

f:id:tokumini:20190617185652p:plain

  • k=2,3の場合が左二つの図
    • やはり意味ごとに行動が分解されており、また垂直軸に対して対称性
  • 性能ではk=1よりk=2とした方が良く、k=3では伸びなかったがk-Expを入れると向上

Star CraftⅡ

  • 人間プレイヤーの行動ログから学習

f:id:tokumini:20190617185713p:plain

  • 全て混合で学習してもキャラクターの種別ごとに行動が分離できており、その中でも意味的なまとまりができている

所感

  • 実験結果が少し微妙な気はするけど考え方が面白くて発展の余地がありそう
  • うさぴょん外伝でもそうだったが、状態表現との内積で行動価値を表現しているのが気にかかった。既存研究にもそのようなものがあったようだが、このやり方の意味がよくわからない
  • 結局実験では行動コンテキストのみから表現を事前学習しており、価値を学習する段階でも表現の学習を行えると良いのではないかと思った

AtCoder Beginner Contest 130

結果

 D問題までの4完で久しぶりにレートが下がった。

A問題

 最近はA問題でもちょいひねりが入ったりしていた気もするが今回はいやに簡単だった。

 提出

B問題

 特になし。

 提出

C問題

 半分に切る場合が最大というのはすぐわかったが、それが複数ある場合の条件については確信が持てなかった。結局いくらか例を考えてたぶん複数ありえるのは両辺の半分ずつの点にある場合だけだろうと理屈はわからないままに提出してAC。解説PDFを見て中心がどうのこうのということに気づく。なるほどそういうことか(まだ微妙だけど)。

 やや面倒だけど浮動小数点数std::coutを使って出力するように意識付けしている最中。ようやく調べずにstd::fixstd::setprecision(15)が思い出せるようになってきた。

 提出

D問題

 尺取り法が書けない人間なので二分探索を書く。尺取り法でできるものはおおむね累積和+二分探索でもできているので痛い目を見ない限りこのまま尺取り法を回避していくのだろうなぁ。

 提出

E問題

 パッと見で最長共通部分列問題っぽいなと思ったし制約もO(NM)でやってねというふうに見えたのでずっとそういうDPを考えていたが結局解けなかった。最長共通部分列問題っぽいと思いながら片方の文字だけで遷移を考えようとしていたのはひどい。

 終了後少し落ち着いて考えたら変化分だけ考えて累積和取って前の結果に足すということをやれば大丈夫なことに気づいてAC。終わって11分後に通せたわけだけど、実際コンテスト時間があと11分あれば通せたかというとたぶん無理だった。無駄な考察をしてドツボにはまっている時間が長すぎたわけだし、残り30分くらいになったタイミングで一度冷静になるべきだった。

 提出

F問題

 コンテスト後に少し考えてみたがわからず解説を見てAC。

 端に来うるものだけを考えれば、たとえば右や上の最大値は「1減り続ける→変化なし→1増え続ける」となるのはすぐわかった。下限も反対の変化になるので、x_{max} - x_{min}y_{max} - y_{min}はそれぞれ凸っぽい感じになると思って、ならこれらの掛け算も凸になる? と思って三分探索してみたけどWA。凸にならないこともたくさんありそう。

 切り替わりタイミングだけしか候補になりえないというのは言われてみれば確かにというくらいで思いつきそうにない。実装もかなり重複の多いものになってしまって時間もかかったし、minとmaxを書き換え忘れるバグで1WA出してしまった。難しい。

 提出

diverta 2019 Programming Contest 2

結果

 D問題までの4完。Highestが更新されていく。

A問題

 K = 1での場合分けを間違えて1WA。サンプルにあるのに合ってないものを提出してしまうとは。自動でサンプルの成否確認して提出するプログラム欲しいと思うこともあるけど、コンテストに出る際の環境が複数ありえるのがちょっと困りどころで。

 提出

B問題

 斜め方向をstd::mapに詰めていくとできる。C++STL(Standard Template Library)はかなり強い。

 提出

C問題

 問題の見た目がそうなので正だけ負だけと正負混合で場合分けだなというのはすぐ見えるしそこから実現可能な最大値はすぐわかるけど、手順を出す方ところでちょっと手間取る。ソートして先頭 or 末尾にほとんど吸収させる方針で考えるのが個人的には楽だった。

 場合分けに気づくところではパターンマッチ感が強く、思考している感じがなかった。競技プログラミングに最適化してしまっているだけではと思ってしまう。棋は別智。

 提出

D問題

 自分の解法が合っているのか自信がない。

 まず交換は何度でもできるので、Bでは最初にまず全てどんぐりに戻して良いことに気づく。というわけでBの最初で持てるどんぐり数をまず最大化したくなり、それはAで金を買う数(0から最大5000) * 銀を買う数(0から最大5000)を全探索すれば銅の数はレートを見てO(1)でどうすればいいかわかるので求まる。

 そしてBでどう金銀銅を買うかだけど、だいたい気持ちとしては一番レートが良いものをできるだけ買い、次に二番目にレートが良いものをやっぱりできるだけ買い、最後に三番目にレートが良いものをB→Aのレートが上昇するかを見て決める。ただし、端数の関係で一番、二番目にレートが良いものも限界まで買い切らない方がよい可能性がある。よって限界から限界 - 5000までを試してみる。こうすると通る。レートが良い順番もまじめに求めるのが面倒くさかったので3!を総当たりした。よくわからない解き方をしてしまった。

 解説PDFを見たけどDPなんですか。はぁ。多分僕の解き方は正当ではない気がする。最小公倍数が大きくなるケースが怪しいのかとは思いつつ、具体的に落ちるケースを示せと言われたら無理。

 提出

優先度付き経験再生の実装・実験

要約

 優先度付き経験再生はAlphaZero方式の学習でも効果がありそう。

背景

 以前の記事でも軽く触れたが、優先度付き経験再生という手法がある。

 大雑把に言うとリプレイバッファからのサンプリング確率を一様ランダムではなく優先度で重み付けするものである。i番目のサンプルの優先度をp_iとしたとき、このサンプルを確率

$$ P(i) = \frac{p_i^\alpha}{\sum_j p_j^\alpha} $$

でサンプリングする。優先度をTD誤差に応じて適切に設定すればより重要なデータを多く学習することができ、学習速度や性能が向上するとのことである。Actor-Learnerを並列で動かす場合にはかなり性能が良いという報告もある。

 つまりAlphaZero方式の学習でも効果がありそうだと感じたので実装してみた。

 元論文では優先度の付け方として

  1. TD誤差の絶対値の大きさによって順位付けし順位の逆数を優先度とする
  2. TD誤差の絶対値をそのまま優先度とする

という2つの手法が提案されていたが、ここでは(2)を採用することとする。若干の変更点としてTD誤差の絶対値ではなく損失関数の値を利用する。

実装

 現状はMiacisのperブランチで開発を行っている。十分な安定性が確認できたらいずれmasterブランチにマージする。replay_buffer.cppやsegment_tree.cppが重要な部分となる。

更新・サンプリングの実装

 (2)の手法はSum-Tree(セグメント木)を用いて実装することで、優先度の更新、サンプリングがO(\log{N})でできる。学習データを保持する配列に加えて、各データの優先度を保持するセグメント木を別に持つことになる。

 優先度の更新は通常のセグメント木の更新そのものとなる。

void SegmentTree::update(uint64_t x, float v) {
    sum_[x + n_ - 1] = v;
    for (uint64_t i = (x + n_ - 2) / 2; ; i = (i - 1) / 2) {
        sum_[i] = sum_[2 * i + 1] + sum_[2 * i + 2];
        if (i == 0) {
            break;
        }
    }
}

 サンプリングは0から損失の総和までの一様乱数をサンプリングし、値に応じて最下段まで木を降りていくことで実現する。

uint64_t SegmentTree::getIndex(float value, uint64_t k) {
    if (k >= n_ - 1) {
        //最下段まで来ていたらindexを返す
        return k - (n_ - 1);
    }
    return (value <= sum_[2 * k + 1] ? getIndex(value, 2 * k + 1) : getIndex(value - sum_[2 * k + 1], 2 * k + 2));
}

 データは通常の経験再生と同じように古い順に削除する。前回データを入れた位置を保持しておき、バッファをリング状に巡回する。

uint64_t SegmentTree::getIndexToPush(uint64_t k) {
    return (++next_push_index_) %= n_;
}

新データの挿入

 元論文では新しく生成されたデータは格納されている中で最大の優先度と同じ優先度を与えるとしているが、今回は置換表に保存していた情報から仮の損失値を計算し、それをもとにリプレイバッファへ格納する。

//このデータを入れる位置を取得
int64_t change_index = segment_tree_.getIndexToPush();

//そこのデータを入れ替える
data_[change_index] = std::make_tuple(pos.toSFEN(), teacher);

//priorityを計算
float priority = -2 * std::log(nn_output_policy[move.toLabel()] + 1e-10f) 
+ std::pow(nn_output_value - teacher.value, 2.0f);

//segment_treeのpriorityを更新
segment_tree_.update(change_index, std::pow(priority, alpha_));

 仮の損失値を計算する上での注意点として、置換表に保存されているPolicyやValueは局面に対するニューラルネットワークの生の出力とは異なる。たとえばPolicyでは置換表には合法手でマスクしたのちにSoftmax関数をかけたものを保存しているため、全指し手についてSoftmax関数をかける通常の出力より精度が良くなる。よってこの仮損失を2倍した値を利用している。この2倍という値に根拠はなく、ただの勘により定めた。

 また、今実装を見直していて気づいたのだが、Policyの仮損失の計算が、実際に指された指し手のみをOnehotベクトルとして計算するものになっている。教師を分布化する前に実装したものをそのままにしていたのだった。どうせ仮の値なのでそこまで影響を与えないとは思うが、いずれ修正する。

 これもまた実装を見直していて気づいたのだが、Valueを漸進的に更新するように実装を変更したのでValue側は探索を終えて精度がかなり高まったものを利用して損失を計算することになっている。上の件とも含めて、仮損失が良い推定値にはなっていないように思える。

 以下の実験はこの実装で計測してしまったのだが、新しいデータのサンプリング確率が不当に低くなっている可能性がある。

重点サンプリングによる補正

 論文で言及されている通り、一様分布ではない分布からサンプリングをするとバイアスが生じてしまうため、本来は重点サンプリングの理論から更新時に補正を行う。しかし今回はそれを入れなかった。なにかの論文でこの補正は行わなくても精度が落ちなかったというような記述を目にした覚えがあるが、どの論文だったか忘れてしまった。

実験

実験設定

 GTX 1080を2枚搭載したマシンでAlphaZero方式の学習を行った。2枚とも自己対局に使用している場合にデータ生成速度は33 pos / secほどとなる。学習1ステップごとに1秒のスリープを行ったため、ステップあたりのデータ生成速度もほぼ33 pos / stepと考えて良い。バッチサイズは128で学習をしたため、同じデータが何度か学習される設定となっている。そのような設定でこそ優先度に応じたサンプリングをする意味があるのではないかと思われる。

 \alpha = 0,1,2,3の4通りについて実験を行った。元論文では\alpha = 0.7などとしているが、扱う値がTD誤差と損失値と違うのでとりあえず大きい値で実験を行ってみることとする。\alpha = 0のときは結局優先度が全て1で等しくなるので通常の一様ランダムでサンプリングを行う経験再生に一致する。

実験結果

棋譜から計算する検証損失

 floodgate2016年の棋譜から計算した検証損失は次のようになった。

f:id:tokumini:20190613092231p:plainf:id:tokumini:20190613092232p:plain
左:Policy損失 右:Value損失

 Value損失ではほとんど差がなかったが、Policy損失では\alphaを大きくした方が良い結果となった。優先度とする損失にはPolicy損失とValue損失を1:1で和をとったものを利用しているので、異なるデータ間で値の大小を比較する上ではPolicy損失の影響が大きいのではないかと思われる。Policy損失とValue損失に係数をかけて比を変えられるようにはしているが、このパラメータもチューニングしなければいけないとなると大変である。

技巧2との検証対局

 各\alphaで学習したパラメータを用いて技巧2(深さ制限4)と1手0.25秒でそれぞれ500局の対局を行った。対局時にはRTX 2080ti1枚を搭載したマシンを利用した。

\alpha 勝率 レート差
0 34.6% -100.6
1 32.6% -126.2
2 57.5% +52.5
3 54.5% +31.4

 今回試した中では\alpha = 2としたときが最も良い結果となった。元論文の結果からするとかなり大きい値に思われるが、TD誤差から優先度をつけている元論文とは異なり、損失で優先度をつけていることが影響しているのかもしれない。たとえばPolicy損失では教師信号が探索回数を正規化した分布になるので、交差エントロピーには定数値として教師信号の自己エントロピーが足されている。Value損失に関しても、報酬の範囲を[0,1]として最終層がsigmoid関数で交差エントロピーを損失とする場合には、教師信号が0.5(引き分け)であれば損失の最小値が0ではない。微分を計算する際には定数値のシフトによる影響はないのだが、今回の手法では問題になり得るのかもしれない。

今後

 今回は\alphaを固定して100kステップの学習を行ったが、元論文で提案されている通り、学習を進めるにつれて\alphaを小さいくしていくことは自然である。前述した通り優先度の初期値についても実装にミスがいくらかあり、まだ改善の余地はあるのではないかと思われる。

 ここのところステップ数を短くして実験サイクルを多く回せるようにしているが、最終的に行う学習の設定と乖離しているのでは結局2度手間になってしまうかもしれないとも思い始めてきた。そろそろ試すアイデアも少なくなってきたので、ステップ数を大きくして性能が収束しきるまで学習させてみようと思う。

AtCoder Beginner Contest 129

結果

 E問題までの5完。Fを解けている人が少なく、Eまでの早解きゲームになっていたようだ。近のRatedでは6回連続でレートが伸びており、たまたま上手くいっている感じは否めないが気分は良い。

f:id:tokumini:20190610095604p:plain

A問題

 ちゃんと問題文を読めているかちょっと不安になりつつの提出だった。

#include"bits/stdc++.h"
using namespace std;
using ll = int64_t;

int main() {
    ll P, Q, R;
    cin >> P >> Q >> R;
    cout << P + Q + R - max({ P, Q, R }) << endl;
}

B問題

 脳を使いたくなかったのでO(N^2)で大丈夫であることを確認した後は問題文に書いてある通りのことを実装した。

#include"bits/stdc++.h"
using namespace std;
using ll = int64_t;

int main() {
    ll N;
    cin >> N;
    vector<ll> W(N);
    for (ll i = 0; i < N; i++) {
        cin >> W[i];
    }

    ll ans = INT_MAX;
    for (ll T = 0; T < N - 1; T++) {
        ll S1 = 0, S2 = 0;
        for (ll i = 0; i < N; i++) {
            if (i <= T) {
                S1 += W[i];
            } else {
                S2 += W[i];
            }
        }
        ans = min(ans, abs(S1 - S2));
    }

    cout << ans << endl;
}

C問題

 最初は2個前までの数字だけを保持して上手くやろうと考えていたけどこんがらがってしまったのでおとなしくdp配列を使うわかりやすい形で実装した。

#include"bits/stdc++.h"
using namespace std;
using ll = int64_t;

int main() {
    ll N, M;
    cin >> N >> M;
    vector<ll> a(M);
    for (ll i = 0; i < M; i++) {
        cin >> a[i];
    }

    vector<bool> ok(N + 1, true);
    for (ll i = 0; i < M; i++) {
        ok[a[i]] = false;
    }

    constexpr ll MOD = 1e9 + 7;
    vector<ll> dp(N + 1, 0);
    dp[0] = 1;
    dp[1] = (ok[1] ? 1 : 0);
    for (ll i = 2; i <= N; i++) {
        if (ok[i]) {
            dp[i] = (dp[i - 1] + dp[i - 2]) % MOD;
        } else {
            dp[i] = 0;
        }
    }

    cout << dp[N] << endl;
}

D問題

 上下と左右それぞれでどれだけ繋がっているかを事前計算する部分で手間取ってしまった。累積和とって後ろからmaxを取り直していくだけなんだけど、障害物マスをINT_MAXとかで初期化すれば上手いこと場合分けいらなくなるのでは? とか余計なことを考えたのがまずかった。おとなしく毎回場合分けを書いてAC。もっと簡単に実装できたのにやっているときにはなかなか思い浮かばない。

#include"bits/stdc++.h"
using namespace std;
using ll = int64_t;

int main() {
    ll H, W;
    cin >> H >> W;
    vector<string> S(H);
    for (ll i = 0; i < H; i++) {
        cin >> S[i];
    }

    vector<vector<ll>> row(H, vector<ll>(W, 0));
    vector<vector<ll>> col(H, vector<ll>(W, 0));

    for (ll i = 0; i < H; i++) {
        for (ll j = 0; j < W; j++) {
            row[i][j] = (S[i][j] == '.' ? 1 : 0);
        }
        for (ll j = 1; j < W; j++) {
            row[i][j] = (S[i][j] == '.' ? row[i][j] + row[i][j - 1] : 0);
        }
        for (ll j = W - 2; j >= 0; j--) {
            row[i][j] = (S[i][j] == '.' ? max(row[i][j], row[i][j + 1]) : 0);
        }
    }
    for (ll j = 0; j < W; j++) {
        for (ll i = 0; i < H; i++) {
            col[i][j] = (S[i][j] == '.' ? 1 : 0);
        }
        for (ll i = 1; i < H; i++) {
            col[i][j] = (S[i][j] == '.' ? col[i][j] + col[i - 1][j] : 0);
        }
        for (ll i = H - 2; i >= 0; i--) {
            col[i][j] = (S[i][j] == '.' ? max(col[i][j], col[i + 1][j]) : 0);
        }
    }

    ll ans = 0;
    for (ll i = 0; i < H; i++) {
        for (ll j = 0; j < W; j++) {
            ans = max(ans, row[i][j] + col[i][j]);
        }
    }

    cout << ans - 1 << endl;
}

E問題

 桁DPを書くだけとは思いつつ慣れていないのでこれがまた苦労する。普通のdpでも実装はメモ化再帰に頼りがちではあるけど、桁dpは特にforループで書く方法がわからない。特に困っていないので習得しようという気にもあまりならない。

 解説PDFを読んでみて、dp配列を二つ持たないといけないやつも今回みたいな以上・未満で二つ考えるのと同じことなのだなと思った。そう考えるとdp配列を二つ持たないといけない問題もめちゃくちゃ突飛な発想を求められているわけでもないのか。桁dpならすぐ見えることをちょっと見た目が変わっただけでわからなくなるのは寂しい。

#include"bits/stdc++.h"
using namespace std;
using ll = int64_t;

string L;
constexpr ll MOD = 1e9 + 7;
vector<vector<ll>> memo;

ll solve(ll i, bool small) {
    if (i == L.size()) {
        return 1;
    }

    if (memo[i][small] != -1) {
        return memo[i][small];
    }

    ll result = 0;
    if (small) {
        result = 3 * solve(i + 1, small) % MOD;
    } else {
        if (L[i] == '0') {
            //(0, 0)だけ
            result = solve(i + 1, false);
        } else {
            //(1, 0), (0, 1), (0, 0)
            result = (2 * solve(i + 1, small) % MOD + solve(i + 1, true)) % MOD;
        }
    }

    return memo[i][small] = result;
}

int main() {
    cin >> L;
    memo.resize(L.size(), vector<ll>(2, -1));
    cout << solve(0, false) << endl;
}

F問題

 数列の[i, j)範囲について問題の答えを返す関数solve(ll i, ll j)を作ったとき、solve(0, L) = pow(10, d) * solve(0, L / 2) + solve(L / 2, L) (dは[L / 2, L)内にある数の桁数の和)という感じで分解できそうだという方針でやっていたけどサンプル3が合わず撃沈。どれくらい合わないのか確かめるために提出してみたらいくつもWAになったしTLEまでたくさん出たので全然ダメだった。

 解説PDFを読んでなんとかAC。桁が同じものはまとめて計算できそうというところにそもそも気づいていないし、気づいてもそこから行列累乗まで落とし込める気はしない。2段階考察が足りていなかった。

#include"bits/stdc++.h"
using namespace std;
using ll = int64_t;

ll L, A, B, M;

vector<vector<ll>>& operator*=(vector<vector<ll>>& lhs, vector<vector<ll>> rhs) {
    auto result = lhs;
    for (ll i = 0; i < result.size(); i++) {
        for (ll j = 0; j < result[i].size(); j++) {
            result[i][j] = 0;
            for (ll k = 0; k < lhs.size(); k++) {
                (result[i][j] += lhs[i][k] * rhs[k][j] % M) %= M;
            }
        }
    }
    return lhs = result;
}

int main() {
    cin >> L >> A >> B >> M;

    ll ans = 0;
    ll pre = 0;
    ll s = A;
    for (ll d = 1; d <= 18; d++) {
        ll target = 1;
        for (ll j = 0; j < d; j++) {
            target *= 10;
        }
        ll low = pre - 1, eq_high = L;
        while (low != eq_high - 1) {
            ll mid = (low + eq_high) / 2;
            ll s_mid = A + B * mid;
            (s_mid < target ? low = mid : eq_high = mid);
        }

        ll C_d = eq_high - pre;
        pre = eq_high;

        vector<vector<ll>> mat = {
                { target % M,     0, 0 },
                {          1,     1, 0 },
                {          0, B % M, 1 }
        };

        vector<vector<ll>> result = {
                { 1, 0, 0 },
                { 0, 1, 0 },
                { 0, 0, 1 }
        };

        while (C_d) {
            if (C_d % 2 == 1) {
                result *= mat;
            }

            C_d /= 2;
            mat *= mat;
        }

        vector<ll> v = { ans, s, 1 };
        ans = 0;
        s = 0;
        for (ll i = 0; i < 3; i++) {
            (ans += v[i] * result[i][0] % M) %= M;
            (s += v[i] * result[i][1] % M) %= M;
        }
    }

    cout << ans << endl;
}

Sarsa-UCT(λ)の実装・実験

要約

 Sarsa-UCT(λ)のλを調整しても明確な性能向上は見られなかった。

背景

 以前の記事の通りMCTSにおける価値の漸進的更新を実装した。

 これにより単なる平均を求める手法とは異なる手法へ改造することが容易になった。特に以前紹介したSarsa-UCT(λ)は自然な形で導入ができるため、パラメータを調整しつつ性能を実験した。

実装

 バックアップの際、\lambdaで現在の値とバックアップしていく値の内分を取っていく。これは実質的に表形式のSarsa(\lambda)に相当する。つまり\lambda = 1とするとモンテカルロ法(平均化)と同じことになり、通常のMCTSと一致する。更新ステップ幅alphaの調整も可能だが、今回はとりあえず平均化する場合と同じ値とした。

void backup(std::stack<int32_t>& indices, 
            std::stack<int32_t>& actions) {
    auto leaf = indices.top(); indices.pop();
    auto value = hash_table_[leaf].value;

    //Sarsa-UCT(λ)のλ
    static constexpr float LAMBDA = 0.9;

    while (!actions.empty()) {
        auto index = indices.top();  indices.pop();
        auto action = actions.top(); actions.pop();

        //手番が変わるので符号反転
        value = -value;

        //現在注目しているノード
        UctHashEntry& node = hash_table_[index];

        //探索回数の更新
        node.N[action]++;
        node.sum_N++;

        //値の更新
        auto curr_v = node.value;
        float alpha = 1.0f / (node.sum_N + 1);
        node.value += alpha * (value - curr_v);

        //現在の値との内分を取って次のノードへ
        value = LAMBDA * value + (1.0f - LAMBDA) * curr_v;
    }
}

実験

 \lambda = 1, 0.9, 0.75について技巧2(深さ制限5, 定跡オフ)と1手0.5秒(RTX 2080tiを使用)で300局対局を行った。

\lambda 勝率 相対Eloレート
1 52.0% +13.9
0.9 56.7% +46.6
0.75 54.3% +30.2

 あまりはっきりとした差は出なかった。元論文では探索回数が少ない場合により顕著な差が出るとのことだったので、追加で技巧2(深さ制限4, 定跡オフ)と1手0.25秒(RTX 2080tiを使用)で500局対局を行った。

\lambda 勝率 相対Eloレート
1 53.9% +27.9
0.9 56.0% +41.6
0.75 50.2% +1.4

 むしろ差が縮まった。プレイアウトの有無など元論文とは異なる点もあるため同じようにはいかないのかもしれない。

AtCoder Grand Contest 034

結果

 A,Bの2完でレート+1。C問題を解けないようでは厳しい。

A問題

 C,Dのうち右にある方を先に移動させたいという気持ちから考えていって方針は早い段階で立ったのだが、実装で悩んでしまった。最終的には多少冗長でも1マスずつ見ていくようにループを書くのが見通しが良かった。こういうのをもっと短い時間ですっきり実装できるようになりたい。

#include"bits/stdc++.h"
using namespace std;
using ll = int64_t;

int main() {
    ll N, A, B, C, D;
    string S;
    cin >> N >> A >> B >> C >> D >> S;
    A--; B--; C--; D--;

    if (C < D) {
        //普通にBから移動
        bool ok_B = true;
        for (ll i = B + 1; i < D; i++) {
            if (S[i] == '#' && S[i + 1] == '#') {
                ok_B = false;
                break;
            }
        }

        bool ok_A = true;
        for (ll i = A + 1; i < C; i++) {
            if (S[i] == '#' && S[i + 1] == '#') {
                ok_A = false;
                break;
            }
        }

        cout << (ok_A && ok_B ? "Yes" : "No") << endl;
    } else {
        bool ok_B = false;
        for (ll i = B; i <= D; i++) {
            //左右が空ならOK
            if (S[i - 1] == '.' && S[i] == '.' && S[i + 1] == '.') {
                ok_B = true;
                break;
            }
        }

        bool ok_A = true;
        for (ll i = A + 1; i < C; i++) {
            if (S[i] == '#' && S[i + 1] == '#') {
                ok_A = false;
                break;
            }
        }

        cout << (ok_A && ok_B ? "Yes" : "No") << endl;
    }
}

B問題

 AAA...AAAABCとなっている場合Aが並んでいる数だけ操作できる。AAA...AAAABCBCとなっている場合、2回目のBCにもその前に並んでいるAがそのまま流れ込んでくる。そんな感じで実装する。

#include"bits/stdc++.h"
using namespace std;
using ll = int64_t;

int main() {
    string s;
    cin >> s;
    
    ll ans = 0, A_num = 0;
    for (ll i = 0; i < (ll)s.size() - 1; i++) {
        if (s[i] == 'A') {
            A_num++;
        } else if (A_num > 0 && s[i] == 'B' && s[i + 1] == 'C') {
            ans += A_num;
            i += 1;
        } else {
            A_num = 0;
        }
    }

    cout << ans << endl;
}

C問題

 解説PDFの問題の言い換えはできていたし、二分探索で操作回数を決めて、「1個以上X − 1個以下の要素を選ぶ数列が高々1つ」なのでll a = mid / X, b = mid % X;という分解ができるのもなんとなく考えていたが詰めきれなかった。X個選んだときの利得でソートして上位k個を無条件に選び、残り分をpriority_queueに入れて上から取っていくというような実装をしてみたが半分ほどしかACにならなかった。確かによく考えてみると上位k個の中にb点までの利得が高いものがあり、k個以外の中にはb点までの利得が良くないがb点以上の利得がそこそこなものがあるような場合で、後者をX点まで選んで前者からX点未満まで選ぶ方が良くなるのか。少し気づきにくいところでもある気がするが、解きたい問題ではあった。もう少し時間があれば可能性があったかもしれないし、それはA,B問題をもっと早く解けていればということでもあって、力をつけていくしかない。解説を読めばすぐ通るコードは書けた。本番で解くとしたら落ち着いて計算量を考え直して、判定部分でO(N)が許される→探索できそうというように思考が流れれば良いのだろうか。次こそは。

#include"bits/stdc++.h"
using namespace std;
using ll = int64_t;

int main() {
    ll N, X;
    cin >> N >> X;

    struct Test {
        ll b, l, r;
    };
    vector<Test> tests(N);
    for (ll i = 0; i < N; i++) {
        cin >> tests[i].b >> tests[i].l >> tests[i].r;
    }
    sort(tests.begin(), tests.end(), [&](Test& lhs, Test& rhs) {
        ll lv = (X - lhs.b) * lhs.r + lhs.b * lhs.l;
        ll rv = (X - rhs.b) * rhs.r + rhs.b * rhs.l;
        return lv > rv;
    });
    vector<ll> score(N);
    for (ll i = 0; i < N; i++) {
        score[i] = (X - tests[i].b) * tests[i].r + tests[i].b * tests[i].l;
    }
    vector<ll> score_sum(N + 1, 0);
    for (ll i = 0; i < N; i++) {
        score_sum[i + 1] = score_sum[i] + score[i];
    }

    ll default_sum = 0;
    for (ll i = 0; i < N; i++) {
        default_sum -= tests[i].b * tests[i].l;
    }

    ll ok = X * N, ng = -1;
    while (ok != ng + 1) {
        ll mid = (ok + ng) / 2;

        ll a = mid / X;
        ll b = mid % X;

        bool flag = false;
        for (ll i = 0; i < N; i++) {
            ll curr_sum = default_sum;

            //iを除いた上位a個の和
            curr_sum += (i >= a ? score_sum[a] : score_sum[a + 1] - score[i]);

            //iからb個選ぶ
            curr_sum += tests[i].l * min(tests[i].b, b);
            curr_sum += tests[i].r * (b - min(tests[i].b, b));

            if (curr_sum >= 0) {
                flag = true;
                break;
            }
        }

        (flag ? ok = mid : ng = mid);
    }

    cout << ok << endl;
}

M-SOLUTIONS プロコンオープン

結果

 A→B→D→Cと解いて4完。もっと早く解けるべきだとも思うけれど、これくらいが実力だとも感じる。

 直近4回のRatedでは全てレートが上がっていて計+120、Highest更新中。特に訓練しているわけではないので単なる上ブレっぽくはあるが。

A問題

 えー公式なんて覚えてないし難しいかもと思ったけど、なんとか外角の和が360度になることから計算できた。100点のA問題で紙とペンを使うことになるとは。

#include"bits/stdc++.h"
using namespace std;
using ll = int64_t;

int main() {
    ll N;
    cin >> N;
    cout << 180 * N - 360 << endl;
}

B問題

 最初問題文を読み間違えていて15回分の結果が入力されるのかと思っていた。負けの数を数えた方が簡単だったか。

#include"bits/stdc++.h"
using namespace std;
using ll = int64_t;

int main() {
    string S;
    cin >> S;
    ll win = 0;
    for (char c : S) {
        if (c == 'o') {
            win++;
        }
    }
    win += 15 - S.size();

    cout << (win >= 8 ? "YES" : "NO") << endl;
}

C問題

 B問題の後は順番通りこれを解いていたんだけど順位表を見ていると早い段階からD問題がC問題と同じかそれ以上に解かれていたので先にそっち行った。Dを解いた後に戻ってきて1時間くらいかけてなんとかAC。解けたはいいが、未だにこの問題に対する良い思考の組み立て方がよくわからない……。

 解けた際の思考順としては

  1. 1回勝敗が付くまで対戦して高橋くんが勝つ確率およびその時のゲーム数の期待値を立式
  2. ゲーム数の期待値はCにしか依存しないっぽいと気づく
  3. Ni敗で終わる確率と、その時の期待ゲーム数を別々に計算して掛け合わせれば良さそう

という感じだった。式をいじり回しているとなんとかなるタイプの問題ではあったか。直前に目にしたぷよぷよについての

というツイートに結構助けられた説もある。

 そもそも期待値をこういうふうにMOD取って計算できるのもあまり腑に落ちていないまま適当にやったら通ったという印象。期待値の線形性がうんぬんかんぬんで上手くいくということなんだろうと思っている。以下の解答はコンテスト後書き直したもの。

#include"bits/stdc++.h"
using namespace std;
using ll = int64_t;

constexpr ll MOD = (ll)1e9 + 7;

ll MODpow(ll n, ll m) {
    ll result = 1;
    while (m) {
        if (m % 2 == 1) {
            result *= n;
            result %= MOD;
        }

        m /= 2;
        n *= n;
        n %= MOD;
    }

    return result;
}

class Combination {
public:
    Combination(ll max_num, ll mod) {
        fact_.resize(max_num + 1, 1);
        inv_fact_.resize(max_num + 1, 1);
        mod_ = mod;
        for (ll i = 2; i <= max_num; i++) {
            fact_[i] = i * fact_[i - 1] % mod_;
            inv_fact_[i] = MODpow(fact_[i], mod_ - 2);
            assert(fact_[i] * inv_fact_[i] % mod_ == 1);
        }
    }
    ll operator()(ll n, ll m) const {
        if (m < 0 || m > n) return 0;
        return fact_[n] * inv_fact_[n - m] % mod_ * inv_fact_[m] % mod_;
    }
private:
    vector<ll> fact_, inv_fact_;
    ll mod_;
};


int main() {
    ll N, A, B, C;
    cin >> N >> A >> B >> C;

    Combination comb(2 * N, MOD);

    //1回どちらかに勝ち負けが付くとしてそれぞれが勝つ確率
    ll probA = A * MODpow(100 - C, MOD - 2) % MOD;
    ll probB = B * MODpow(100 - C, MOD - 2) % MOD;

    //1回勝ち負けが付くまでにかかる期待ゲーム数
    ll one_step = 100 * MODpow(100 - C, MOD - 2) % MOD;

    ll ans = 0;
    for (ll i = 0; i < N; i++) {
        //高橋君がN勝 i敗となる確率
        ll p1 = comb(N - 1 + i, N - 1) * MODpow(probA, N) % MOD * MODpow(probB, i) % MOD;

        //青木君がN勝 i敗となる確率
        ll p2 = comb(N - 1 + i, N - 1) * MODpow(probB, N) % MOD * MODpow(probA, i) % MOD;

        //N + i回の勝ち負けで終わる確率
        ll p = (p1 + p2) % MOD;

        //N + i回勝ち負けが付く場合の期待ゲーム数
        ll exp_game_num = one_step * (N + i) % MOD;

        //答えに足す
        (ans += p * exp_game_num % MOD) %= MOD;
    }

    cout << ans << endl;
}

D問題

 解いている人が多いのでそれほどひねった解法ではないんだろうと思って望んだ。気持ちとして次数が一番大きいノードに一番大きい数を割り当てて、隣接ノードに二番目以降のものを割り当てるということしたくなる。それを実装する。通る。

 解説PDFを見るともっと単純にできたようだ。自分のコードもよく見てみればそういうことになっている(st.empty()が真になるのは最初だけ)のでひどい。考察が甘いから実装が大変になって時間がかかってしまう。

#include"bits/stdc++.h"
using namespace std;
using ll = int64_t;

int main() {
    ll N;
    cin >> N;
    vector<vector<ll>> connect(N);
    for (ll i = 0; i < N - 1; i++) {
        ll a, b;
        cin >> a >> b;
        a--; b--;
        connect[a].push_back(b);
        connect[b].push_back(a);
    }
    vector<ll> c(N);
    for (ll i = 0; i < N; i++) {
        cin >> c[i];
    }
    sort(c.begin(), c.end(), greater<>());

    struct Node {
        ll node, num;
        bool operator<(const Node& rhs) const {
            return num < rhs.num;
        }
    };

    priority_queue<Node> pq;
    for (ll i = 0; i < N; i++) {
        pq.push({ i, (ll)connect[i].size() });
    }

    vector<bool> used(N, false);

    ll score = 0;
    vector<ll> ans(N);

    stack<ll> st;
    for (ll i = 0; i < N; i++) {
        if (st.empty()) {
            while (true) {
                auto t = pq.top();
                pq.pop();

                if (used[t.node]) {
                    continue;
                }
                used[t.node] = true;

                ans[t.node] = c[i];

                for (auto next : connect[t.node]) {
                    st.push(next);
                }

                break;
            }
        } else {
            while (true) {
                auto t = st.top();
                st.pop();

                if (used[t]) {
                    continue;
                }
                used[t] = true;
                for (auto next : connect[t]) {
                    st.push(next);
                }

                ans[t] = c[i];
                score += c[i];
                break;
            }
        }
    }

    cout << score << endl;
    for (ll i = 0; i < N; i++) {
        cout << ans[i] << " \n"[i == N - 1];
    }
}

E問題

 コンテスト中はほとんど読んでもいなかった。今解いてみたがわからず解説を見てAC。解説の方針でも割り算のところとかこれで上手くいくものかパッとは自信持って断言できないし、例外処理も難しくて何度もしくじりWA出した。難しいですね。

#include"bits/stdc++.h"
using namespace std;
using ll = int64_t;

constexpr ll MOD = (ll)1e6 + 3;

ll MODpow(ll n, ll m) {
    ll result = 1;
    while (m) {
        if (m % 2 == 1) {
            result *= n;
            result %= MOD;
        }

        m /= 2;
        n *= n;
        n %= MOD;
    }

    return result;
}

int main() {
    ll Q;
    cin >> Q;
    vector<ll> x(Q), d(Q), n(Q);
    for (ll i = 0; i < Q; i++) {
        cin >> x[i] >> d[i] >> n[i];
    }

    constexpr ll max_num = 1e6 + 2;
    vector<ll> fact, inv_fact;
    fact.resize(max_num + 1, 1);
    inv_fact.resize(max_num + 1, 1);
    for (ll i = 2; i <= max_num; i++) {
        fact[i] = i * fact[i - 1] % MOD;
        inv_fact[i] = MODpow(fact[i], MOD - 2);
        assert(fact[i] * inv_fact[i] % MOD == 1);
    }

    for (ll i = 0; i < Q; i++) {
        if (d[i] == 0) {
            cout << MODpow(x[i], n[i]) << endl;
        } else {
            ll x_var_d = x[i] * MODpow(d[i], MOD - 2) % MOD;
            if (x_var_d == 0 || x_var_d + n[i] - 1 >= MOD) {
                cout << 0 << endl;
            } else {
                ll a = x_var_d + n[i] - 1;
                ll b = x_var_d - 1;
                cout << MODpow(d[i], n[i]) * fact[a] % MOD * inv_fact[b] % MOD << endl;
            }
        }
    }
}

a crowd of rebellionの好きな曲

 音楽について語れるような知識もないのでYoutubeから好きな曲を貼っていくだけの記事です。動画を貼っておきながらあれなんですけど、なんとなく楽曲のイメージを固定化したくないのでMVは一切見ていません。アーティストの顔写真とかもできれば見たくないなぁと気をつけているところもあるので。ライブとかも一切行ったことないし、基本的にApple Musicにあるものしか聴かないという感じの浅い聴き方をしている人間の適当な記事です。

 というわけでa crowd of rebellionの話。個人的にここ1年くらいで一番聴いている時間が長いバンドだと思います。今までこういうジャンル(デスボイスが入るタイプのやつ)はあんまり聴いていなかったんですけどなんかハマってしまいましたね。もとから声高めの男性ボーカルが好きなところはあるのでそこまで違和感のあるハマり方でもないといえばそうなんですが。

 a crowd of rebellionで最初に聴いたアルバムが『Ill』で、曲としてもこれが印象深いです。この曲に限らず歌詞をちゃんと読んだことはないんですが、2番のサビあたりの語感は素敵だと思います。あとは「Break」のところとかも。

 普段はアルバムの楽曲を順番通りそのまま流すことが多く、続けてよく聴く『Sign.』も好きです。当然サビも良いんですけど、そこへの入り「ひとつふたつ」のあたりが好みですかね。

 『Ill』は序盤のこの2曲でテンションが上がりますね。終盤の『Noah』、『THE TESTAMENT』も好きで、特に後者がお気に入りです。歌いだしからして好きなんですが、2番サビの「ねぇ神よ僕を縛ってまで」の歌い方がもろにストライクゾーンといった感じです。

 他のアルバムだと『Gingerol』、『Xanthium』をよく聴きます。というか『Ill』を含めたこの3枚しかほとんど聴いてなくて、それ以前のものはまた少し毛色が違って少し上級者向け? みたいな印象があります。

 曲としてはそれぞれアルバムの最初と最後に好きなものが多い気がします。アルバムってそういう曲の置き方をするのが一般的だったりするんでしょうか。何か作業しながら聴くことが多い関係で中盤はあまり意識できていないだけという可能性もありそうです。改めてアルバム中盤あたりの曲名を見渡してみても、まだ頭の中で曲名と曲の内容を結び付けられてないものがいくらかあるような……。

 『Gingerol』だと2,3曲目の『HOPE』『Nex:us』、11,12曲目の『リビルド』『karma_葬』が明確に好きと言えるところで、ここでは代表して『Nex:us』を。やはりこの手の曲が好きという傾向があるとは思うんですけどこういうのをなんていうのかよく知りません。

 『Xanthium』だと1曲目『M1917』、12曲目『The Crow』が好きですね。『M1917』の動画は再生数が一番多いということで、一般的にも人気ということなんでしょうか。銃の効果音が一瞬ダサく聴こえる気もするけど強引にいやこれはかっこいいんだと納得させられる感じもあります。「両手結って祈ったって」の部分がフレーズとして好みです。

 音楽に対する語彙・表現力はどのようにしたら蓄えられるのでしょうね。いずれより明瞭な形で言及できればなぁと思いつつ、とりあえず現時点での感想として以上の内容を残しておきたいと思います。

SENetの導入

要約

 SENetの構造を導入することによってネットワークの性能が向上した。計算量はやや多くなるが、全体として棋力は向上した。

背景

 山岡さんのブログで将棋ソフトでもSENetの構造が有用であるとの実験結果が示されていた。

 このような簡単な変更かつ僅かな計算量の増加で精度が高くなるなら導入しない手はない。

実装

 実際のコードは

にある通りだが、主要な部分を抜粋する。多少改編も加えている。

 モデルのクラス変数に各ブロックで用いる全結合層を追加。

std::vector<std::vector<torch::nn::Linear>> fc(BLOCK_NUM, std::vector<torch::nn::Linear>(2, nullptr));
for (int32_t i = 0; i < BLOCK_NUM; i++) {
    fc[i][0] = register_module("fc" + std::to_string(i) + "_0",
 torch::nn::Linear(torch::nn::LinearOptions(CHANNEL_NUM, CHANNEL_NUM / REDUCTION).with_bias(false)));
    fc[i][1] = register_module("fc" + std::to_string(i) + "_1",
 torch::nn::Linear(torch::nn::LinearOptions(CHANNEL_NUM / REDUCTION, CHANNEL_NUM).with_bias(false)));
}

 ブロックでの処理において畳み込み2回の後にグローバルアベレージプーリングや全結合層2回の処理を追加。

for (int32_t i = 0; i < BLOCK_NUM; i++) {
    auto t = x;

    x = conv[i][0]->forward(x);
    x = bn[i][0]->forward(x);
    x = torch::relu(x);

    x = conv[i][1]->forward(x);
    x = bn[i][1]->forward(x);

    auto y = torch::avg_pool2d(x, {9, 9});
    y = y.view({-1, CHANNEL_NUM});
    y = fc[i][0]->forward(y);
    y = torch::relu(y);
    y = fc[i][1]->forward(y);
    y = torch::sigmoid(y);
    y = y.view({-1, CHANNEL_NUM, 1, 1});
    x = x * y;

    x = torch::relu(x + t);
}

実験

学習

 floodgateの2015~2018年の棋譜からR2800以上同士の対局を抽出して約1千万局面を教師データとした教師あり学習を行った。Policyの教師は棋譜で指された指し手、Valueの教師は棋譜の最終結果による-1 or 1である。

 上記実装においてREDUCTION = 8とした。これはもともとCNNのチャネル数が64と小さいため16で割るのは過剰ではないかと考えたためである。

 全結合層についてバイアスあり・なしの2通りを実験した。ベースラインとしてSENet構造を入れてないものと比較した。検証損失の推移を以下に示す。

f:id:tokumini:20190529104048p:plainf:id:tokumini:20190529104054p:plain
左:Policy損失 右:Value損失

 どれも38エポックを経過した段階で最も損失和が低くなっており、その時点での値を以下に示す。

モデル Policy損失 Value損失 学習時間の比
baseline 1.732598 0.409436 1
SENet 1.707092 0.402247 1.138
SENet with bias 1.710603 0.400820 1.149

 バイアスあり・なしのいずれにおいてもベースラインより低い損失となった。ベースラインのモデルが10ブロック・64チャネルという比較的小さなネットワークのためか、SENet構造を入れることによる学習時間の増加は13%~14%と大きめになっている。学習に比べて対局時にはネットワーク以外の処理も含まれるためNPSの低下はこれよりも小さいはずであり、影響は少ないと思われる。

検証対局

 それぞれのモデルを用いて技巧2(深さ1)と1手1秒で200局対局を行った。

モデル 技巧2に対する勝率 Eloレート差
baseline 48.0% -13.9
SENet 74.8% +188.5
SENet with bias 65.8% +113.3

 SENet構造を導入することで探索速度の低下を補ってあまりある程の棋力向上が見られた。全結合層のバイアスはないものの方が高い勝率となったが、ここまで大きな差がつくのは損失の違いがわずかであったことからすると意外な結果である。偶然の影響が大きそうな気はするが、勝率だけでなく損失も悪くないためとりあえずバイアスなしのSENetで強化学習を試してみることとする。結果はいずれにここに追記する。

 以下2019/06/02追記

強化学習

 バイアスなしのSENetを用いてAlphaZero方式の強化学習を試した。

f:id:tokumini:20190602163454p:plainf:id:tokumini:20190602163457p:plain
左:Policy損失 右:Value損失

 検証損失はベースラインよりも低い値となった。また技巧2(深さ5)と1手1秒で300局対局させた結果も

モデル 技巧2に対する勝率 Eloレート差
baseline 56.0% +41.9
SENet 72.0% +164.1

となりやや性能が上がった。