LibTorch(PyTorch C++API)の使い方

 英語を読める人は素直に公式のドキュメントおよびチュートリアルを読むべき。翻訳ソフトを使ってでもこれらを読んだ方が良いと思う。

 以下の作業は少なくともcuda10.0,cudnn7という環境では動くと思われる。(Dockerでnvidia/cuda:10.0-cudnn7-devel-ubuntu18.04イメージから新しいコンテナを作ってそこで作業した)

簡単なサンプルのビルドまで

 まずダウンロード。以下のページ

から適切にバージョンを指定して落としてくる。

f:id:tokumini:20190824075901p:plain

以前はABIのバージョンがどうこうという問題があって自前でビルドしなければならない場合もあったが(※参考)、今見ると二つ用意されているようなので自分の環境に合わせた方をダウンロードすれば良いと思われる。

 解凍するとlibtorchというディレクトリが得られる。LibTorchを使うときは基本的にcmakeでこのlibtorchディレクトリを指定してコンパイルすることになる。cmakeはCLionでもVisual Studioでも使えるのでそこまで使い勝手は悪くないと思う。

 このページで示されているexample-appというものをコンパイルしてみることとする。example-appというディレクトリを作って、そこにexample-app.cppCMakeLists.txtという2つのファイルを用意する。

example-app/
    CMakeLists.txt
    example-app.cpp

 example-app.cppは例そのままのtensorを作って表示するというものになる。

#include <torch/torch.h>
#include <iostream>

int main() {
  torch::Tensor tensor = torch::rand({2, 3});
  std::cout << tensor << std::endl;
}

 CMakeLists.txtの方も例とほぼ同じなのだが、一点だけ使いやすいように修正する。というのも、もとの例ではビルドするタイミングでlibtorchのパスを指定しているのだが、いちいちコマンドライン引数にパスを付け加えるのは嫌だし、IDE側から見つけるためにもlibtorchのパスをCMakeLists.txtに書いてしまう。find_package(Torch REQUIRED)の前の行にlist(APPEND CMAKE_PREFIX_PATH ~/libtorch)としてcmakeがパッケージを探すパスを付け加えることができる。今はホーム直下にlibtorchを置いたのでこうしているが、各自ダウンロードしたところへ適当にパスを合わせて書けば良い。

cmake_minimum_required(VERSION 3.0 FATAL_ERROR)
project(example-app)

list(APPEND CMAKE_PREFIX_PATH ~/libtorch)
find_package(Torch REQUIRED)

add_executable(example-app example-app.cpp)
target_link_libraries(example-app "${TORCH_LIBRARIES}")
set_property(TARGET example-app PROPERTY CXX_STANDARD 11)

 cmakeではソースコードを置いているディレクトリを汚さないようにbuildというビルド専用のディレクトリをその階層に作るのが普通らしいのでそのようにする。

mkdir build
cd build
cmake ..
make

 これでexample-appを実行すると

 0.8291  0.0013  0.0553
 0.3590  0.1988  0.3392
[ Variable[CPUFloatType]{2,3} ]

と表示された。

ニューラルネットを書く

 ニューラルネットなどの例は公式GitHubののexamplesを見るのが良いと思う。mnistを分類するような簡単なCNNだとmnist.cppにあり、学習の仕方も含めてだいたいはこれで理解できるはず。というわけでこの例で足りない部分についていくらか記述する。といっても正直なところ自分もよくわかっていないところが多いのでむしろ指摘をもらいたい……。

自作モジュールを作る

 ニューラルネットの部分的モジュールなどを書く(たとえばMyModuleというモジュールを作るとする)場合はtorch::nn::Moduleを継承してMyModuleImplというクラスを定義し、最後にTORCH_MODULE(MyModule)というマクロを呼び出すという手順をする(チュートリアルの中程にある)。これによってMyModuleという名前のtorch::nn:ModuleHolderが定義される。Linerについての例だと以下のような感じ。

struct LinearImpl : torch::nn::Module {
  LinearImpl(int64_t in, int64_t out);

  Tensor forward(const Tensor& input);

  Tensor weight, bias;
};

TORCH_MODULE(Linear);

 なぜこんな面倒なことをするかというと、torch::nn::Moduleは大きいクラスになるので、たとえば関数の引数に与えるときに値渡しをすると非効率的になる。C++なのだから参照渡しをすることも容易なんだけど、Python的と同じ書き方で同じ効果を持った方がわかりやすい。Pythonの関数は参照の値渡しなので、C++でそれを実現するにはtorch::nn::Moduleを直接渡すのではなくそれへのstd::shared_ptrであるtorch::nn:ModuleHolderを渡すようにするのが自然。英語があまり読めなかったので適当なことを言っているかもしれない。

モデルをセーブ・ロードする

 torch::nn:ModuleHolderであるnnという変数があったとき、

torch::save(nn, "path_to_model_file");
torch::load(nn, "path_to_model_file");

とする。先のチュートリアル中に

the serialization API (torch::save and torch::load) only supports module holders (or plain shared_ptr).

とあるので、試したことはないがtorch::nn::Moduleはセーブできないのだと思われる。サンプルのmnist.cppとかはtorch::nn:ModuleHolderを使わず書いているのでセーブできなさそうなのだが、そんなものをexampleとして出すのはどうなんだという気もする……。

計算結果を取り出す

 そもそもモデルを定義した後は一度model.to(device);(mnist.cppの129行目)のようにしてGPUにモデルを転送するという作業が必要になる。入力、教師データも同様にauto data = batch.data.to(device), targets = batch.target.to(device);としてGPUに飛ばしてから計算を走らせる。結果を取り出す際には計算結果を示すtorch::Tensorを一度CPUに戻してくる。その後torch::Tensorのメソッドdata<T>()を使って、型Tに対するポインタとして先頭のポインタを得る。自分のコードでは、たとえば1バッチについてDATA_DIM次元のベクトルを計算するデータを取り出す場合は以下のような感じにしている。

    //計算結果を格納するstd::vector
    std::vector<std::vector<float>> results(batch_size);

    //計算してCPUに持ってくる
    torch::Tensor nn_result = model->forward(input).cpu();

    //データの先頭へのポインタを取得してstd::vectorにバッチごとに突っ込む
    float* p = nn_result.data<float>();
    for (uint64_t i = 0; i < batch_size; i++) {
        results[i].assign(p + i * DATA_DIM, p + (i + 1) * DATA_DIM);
    }

 LibTorchどうこうという話ではなくC++としてデータをstd::vectorへと変換するところで非効率的なことをやっている気がする。C++よくわからん。

その他

 一応拙作のMiacisという将棋ソフトでもAlphaZero的なResidual Blockを持つCNNを実装しているため、参考になれば。

 ニューラルネット部分はだいたいsrc/neural_network.cppにある。

価値のソフトマックス分布を教師としたAlphaZero学習(最終結果)

要約

 価値のソフトマックス分布を選択および教師に利用することでレートが150程度上がったが、これはMiacis特有の事情である可能性がある。

背景

 前回、価値のソフトマックス分布を教師としたAlphaZero学習は少なくとも最初の方では学習が上手く進んでいることがわかった。そのまま続けて回し続けたこの学習が(大学の停電により)終わったため結果を記す。

実験結果

 探索回数を正規化した分布に従うものを探索分布、価値のソフトマックス分布を用いるものを価値分布と呼ぶことにする。前回は価値分布を選択のみに用いるものも検証したが、選択と教師の両方に利用した方が良さそうだったので、今回は両方に利用するもののみを計測している。

検証損失

f:id:tokumini:20190817111505p:plainf:id:tokumini:20190817111514p:plain
左:Policy損失 右:Value損失

 価値分布は1.7Mステップまでしか回せなかったが、明らかに損失は小さくなっている。

検証対局

f:id:tokumini:20190820071508p:plain

 深さを制限した技巧2との対局からも、だいたいレート150程度高くなっている。

探索回数800回での対局

 前回も簡単に検証した通り、性能が良くなっているのは得られた棋譜の質が高くなっているからだと思われる。行動選択方法による棋力の違いを検証するために、学習中にデータを生成する条件に近い設定で対局を行った。具体的には1局面あたり800回の探索、置換表はルート局面以外を再利用した。並列化なしだと非常に遅かったためバッチサイズ8での並列化をした点、ディリクレノイズを付与しない点がデータ生成時と異なる。

 以下ではある手数まで分布に従った行動選択をし、その手数以降は探索回数最大の指し手を貪欲に選択することとする。

 複数の条件について今回の行動選択条件(256手まで温度0.01の価値分布に従う)とそれぞれ100局対局させた。256手に到達した場合引き分けとし、千日手を含む引き分けは0.5勝0.5敗で計算した。対局結果は次のようになった。

名前 価値分布に対する勝率 レート差
探索分布(256手まで) 7.0% -449.4
探索分布(30手まで) 52.0% 13.9
価値分布(30手まで) 63.5% 96.2

 まず常に探索分布に従って指すものは非常に弱かった。前々回までデータ生成をこの条件で行っていたので棋譜の質が低かったのだと思われる。

 次にAlphaZeroの論文通り30手以降は探索回数最大の行動を選択するものではほぼ互角になった。つまりちゃんと忠実にAlphaZero再現実験をしている場合、価値分布を使うことによる恩恵はほとんどないか、むしろ劣化するものと思われる。ここについてはMiacisはカテゴリカル分布を用いており普通のMCTSとは異なる選択を行っている点も影響しているかもしれない。個人的に検討などでMiacisを使っていて、価値が最大の手と探索回数最大の手が異なる場合が多いように感じている。

 また、価値分布も30手までに制限した方がやや強かった。自明なようにも思えるが、先に述べた通り価値が最大の手と探索回数最大の手が異なることが多く、31手以降は探索回数最大の指し手を選択することが良いかどうかは明らかではない。価値最大の手が全然探索されていないこともままあるので、やはり選択の式で価値を考慮する項を導入したほうが良いかもしれない。また序盤の多様性が足りていないようにも思えるので、ソフトマックス関数を適用するときの温度を高めにして30手までに制限することを試してみたい。

AtCoder Beginner Contest 138

結果

順位   267th / 5238
パフォーマンス   1919
レーティング  1881 → 1885(+4)

 前日のAGCでレート-4だったので二日間でプラマイゼロ。このあたりが適正か?

A - Red or Not

 これAtCoderの色システムと対応しているの? 上のほうがどうなっているのかよく知らないし3200以上がredなのかとやや混乱しかけた。

 提出

B - Resistors in Parallel

 doubleを信じて愚直に計算するだけ。解説PDFを見ていて気づいたんだけど、桁数を指定して出力するときstd::setprecisionだけで良いのか。std::fixedも指定しなきゃいけないのかと思っていたが、0が続く場合にそれが出力されるかどうかという違いがあるだけっぽい。機械学習とかで損失の桁を揃えて綺麗に表示したいときは当然これ使うわけだけど競プロではいらなかったか。

 提出

C - Alchemist

 無駄にstd::priority_queueを使ってしまったが混ぜることで大きくなるわけがないんだからソートして小さい方から混ぜていくだけで良かったか。

 提出

D - Ki

 妙に簡単で拍子抜けした。最近はdfsをstd::stackを使ってそのまま書くことがマイブーム。

 提出

E - Strings of Impurity

 最初、順番を考慮せずにtで各文字が出現した回数を上回るような位置を二分探索すればいけるじゃんと思って書き始めたが途中でミスに気づく。時間をロスして焦り始めたが、冷静になればsにおける各文字の位置を記録して、次に到達するべき文字で二分探索すれば良いとわかって落ち着いた。細かいところだけど出現位置をstd::vectorで取って毎回二分探索するんじゃなくてstd::setで保持して降りていくだけの方がなんか好みの実装だったな。書いていたときはそうできなかったが……。

 提出

F - Coincidence

  x yの最左ビット以外を適当に降ろしたものだというのは実験してなんとなくわかったけど、 L \le xとか x \le Rとかそういう制約を考えると数えられない。ある yを固定したときの適切な xの数は O(\log L)で求められる(たぶん)んだけど、そもそも y Lから Rまでループするということができないので……というところで思考が詰まって終わった。

 えーこれ桁DPで数えられるのかという感じ。2つの数字を上手くいじりながら数えることができるんだなぁ。実装例をほぼ写経する感じでAC。こういうのが数えられると知っていれば今後はなんとかなる、かなぁ。

 提出

AtCoder Grand Contest 037

結果

順位   393rd / 2317
パフォーマンス   1841
レーティング  1885 → 1881(-4)

 800点のC問題を通せて喜んでいたけどレートは下がるのか。

 AtCoderをやっている上でmerom686氏のレートを超えるというのを一つ目標としてきていたのだけど、今回提出せず撤退もできたmerom686氏が最後C問題出してWAになってレート大暴落が発生しており、なんか超えてしまった。自分のレートも下がっているのでひどく微妙な感じだ。こういう事故っぽいのではなぁというのもあるし、そもそも黄色くなっていない時点で論外というのもそう。はい。漫然と黄色を目指します。

A - Dividing a String

 3文字以上の塊は出てこなさそうだなと直感で判断してDPをし始めた。初期化とか遷移での添字とかいろいろ手間取りつつWAも出しつつなんとか通したという感じでまったくスマートではない。

 提出

B - RGB Balls

 コンテスト中には解けなかった。A問題解いた直後に30分くらい考えてわからなかったので順位表の様子を見てC問題へ行った。C問題を解いた後戻ってきたけど方針すらさっぱり立たない感じで時間切れ。サンプルが見るからに掛け算をしてくださいという出力になっていることはわかったけどなにをどう数えつつ掛けていけば良いのかさっぱりわからなかった。今日解いてみたけど、解説PDFはなんだかよくわからなくて、とりあえずわりと貪欲っぽくやっていくとなんか数が合って通った。類問出されても解ける気がしない。

 提出

C - Numbers on a Circle

 後ろからやっていくということに気づいて、配列の中から最大値のインデックスを取り出すというところにやや悩んだ挙句セグメント木を持ち出してくるということをやった。冷静に考えればstd::priority_queueで十分なのに。まぁ将棋ソフトの方でセグメント木を使った最小位置の取得というのは書いていて、それをコピペするだけだったので時間の短縮にはなっていたかもしれない。

 B_i = A_iとなった場合に最大値として再び取り出すことがないようにセグメント木上では0にしておく変な実装になってしまい、初期化の部分でそれを忘れて2WAほど。綺麗な実装がよくわからなかった。

 提出

AtCoder Beginner Contest 137

結果

順位   462nd / 5218
パフォーマンス   1685
レーティング  1906 → 1885(-21)

 D問題までの4問しか解けなくてひえーって感じだったけど失敗に優しいAtCoderなので。

A - +-x

 素直なA問題でやりやすかった。

 提出

B - One Clue

 こういうの境界のあたりでバグらせそうで非常に怖い。

 提出

C - Green Bin

 各文字列について各26文字の出現回数を記録したstd::vectorstd::mapに詰めていく。こういうSTLSTLを突っ込むみたいなSTLを信じ切った解法だと内部的な振る舞い(メモリがどうなっているのかとか)がさっぱり想像できなくて不安だけどできるものはできる。

 提出

D - Summer Vacation

  M - i日目には遅延が i日以内のものから最大のものを選びたくなった。報酬の遅延日数で昇順ソートして、std::priority_queueに詰めながらやっていくと通る。ここまでは結構順調に解けていたのだが……。

 提出

E - Coins Respawn

 85分ずっとこの問題に取り組んで結局解けず。原因は簡単で、ベルマンフォード法とワーシャルフロイド法が頭の中で混じってしまい、ベルマンフォード法は O(|V|^3)だからダメだよなぁと早々に切ってしまったから。ダイクストラを適当にいじってなんとかする方針でずっと考えてハマり続ける展開になってしまってはもうダメ。

 こういう勘違いを、コンテスト中の振る舞いを変えることで回避することができるのかよくわからない。頭の中だけで切らず文章として残そうとすれば気づけただろうか。しかし「メモを丁寧に取ろう」みたいな心がけに頼ってなんとかしようとするのはどうせ数回でまたもとに戻ってしまうと経験上わかっているので良くない。メモを取るのが嫌な理由として紙にペンで文字を書くのが遅いという点はあるし、パソコンで書くのはありかもしれない。グラフとか図とかは書きづらいので思考部分のみにはなりそうだけど。

 あとはもっとWeb検索を用いたほうがいい。今回詰まっている間は一回も検索してなくて、コンテスト終わった後にふと「負の閉路」で調べてベルマンフォード法をちらっと見ただけであーこれは……という感じになったので。基本的に自分の頭で考えてなんとかなることはそんなに多くない。

 まぁコンテスト中の振る舞いというよりは、どちらかというとアルゴリズムの知識があやふやだった、訓練不足だったというところが大きいとは思う。あまり競技プログラミングをがっつりやっていくという気分ではないのでこうやってコンテストでやらかして覚えるということになっていくのだろうけど。

 提出

F - Polynomial Construction

 今日1時間ほど考えてみたけどさっぱりわからなくて解説を見てAC。根本的に考察の方針として「 b_0 O(p)で決めて、次に b_1 O(p)で決めて……」みたいな考え方ばかりを探っていたのでこういうなんかひねり出すみたい解法にはさっぱり近づけない。難しい。

 提出

AtCoder Beginner Contest 136

結果

順位   315th / 5109
パフォーマンス   1843
レーティング  1913 → 1906(-7)

A - Transfer

 一度間違えてサンプル3の入力を提出欄にコピペして出してしまったがCEになったのでペナルティは付かなかった。あぶねー。

 提出

B - Uneven Numbers

 整数を Nまでループしてstd::stringに変換してサイズを偶奇判定。std::to_stringがどんな実装になっているかは知らないけどまぁ桁数くらいの計算量だろうしそれなら間に合うはずという判断。最大ケースもサンプルにあったし。

 提出

C - Build Stairs

 右から見ていって左の方が高ければ一つ削る。まだダメならNoだし良ければ次へとやっていく。無駄な分岐も作ってしまったしあまり綺麗なコードになってないな。

 提出

D - Gathering Children

 サンプルを手で考えているとR...RL...LとなっているRLの部分に最大1の差で集まるんだなということがわかるので、あとは偶奇を冷静に考えていると解けている。解説PDFのダブリングによる解法は典型っぽいので覚えておいた方が良さそうだなぁ。

 提出

E - Max GCD

 総和が不変ということにはすぐ目が向くが、その先の考察が進んでいかない。というのも O(N \sqrt{N \max{A}})が間に合わないと勘違いしていて、しばらくして Nは小さいからこれでいけるということに気づいて約数列挙→最低操作回数計算という流れで解けた。 O(N\log N \sqrt{N \max{A}})になるのでやや不安だったけどこれが余裕なんだな。

 途中でちらっと見たとき解いている人が少なかったので難しいのかと思ったけど解けてみたらあまりそうでもなく、ACした後に順位表みたら順位がひどかった。最初のはF問題の欄を見間違えていたのかな。

 提出

F - Enclosed Points

 残り30分くらいしかない状況で入ったのでやや諦めつつの考察だったけど、しばらくして「ある点が何回囲われるか」という視点で考えれば解けそうだと気づく。 x,yの範囲が広いので座標圧縮して、 xでソートしてセグメント木で yの位置を取りつつ、重複して数えるのを除いて……というのを10分程度で実装できるわけもなく終了。

 後日解いた感じでもあと30分は必要そうだった。実行時間が1336msecもかかっているし、コードも140行を超えていてもっと簡単に書けそうな気はするんだけどよくわからない。

 仕組みが変わってからのABCは特に時間が足りないことが多いしライブラリの重要性が増していると思う。座標圧縮くらいさっとやれなければな。

 提出

Temporal Difference Variational Auto-Encoderを読んだ際のメモ

出典

 International Conference on Learning Representations 2019に採択。

所感

 長くなってしまったので最初に所感を。

 初めて読んだときはなんだかよくわからず挫折してしまったけど、4.2節あたりの気持ちをちゃんと読んでみると多少わかってきた。詳しい式変形はよくわからないままだがTD誤差と言いたくなるのはそうかもしれない。

 確かにジャンプ予測は実現できたら面白いものの一つだと思う。しかし、Predictronとかもそうなのだけど、この手の環境モデルは時系列データの遷移を予測するだけで自分の行動を考慮できていないので、実践的には使い勝手が悪そう。結論の節で「プランニングへの応用を目指している」と書いてあるし当然こういった問題を認識していないわけはないが。

 各タイムステップで行動選択が可能であると考えると、単純に状態系列に行動も含めれば上手くいくわけではないだろう。個人的には行動自体の表現を考えて抽象化することで漫然とした(長いタイムステップの)行動を考えられるようになるのではないかと考えているが。

 将棋的に言うと「金銀を盛り上げていけば模様がよくなりそう」とか「飛車を振って美濃囲いにすれば勝ち」とかそういう方針的なものを……ってそれはむしろ階層的強化学習とかの分野なのかもしれない。どちらかというと「▲2四歩△同歩▲同飛△2三歩▲2九飛」を一気に飛ばせるとかそういう話か。しかしポリシーが偏っていれば1手ごとの展開でもそこまで計算時間のロスは大きくないだろうし、やはり観測が完全なドメインではあまり活きない話なのかもしれないとも思ったり。

概要

 以下の3つの特徴を持つ環境モデルとしてTD-VAEを提案

  • 状態の抽象表現を獲得
  • 状態の不確実性を表現する信念を形勢
  • 複数ステップ一気にジャンプする遷移を予測可能

1 Introduction

  • 強化学習における部分観測環境
    • 不確実性の表現が可能である必要性
    • 記憶を持つエージェントならモデルフリー手法でも可能?
      • 報酬のような教師信号では不確実性を学習するのは難しい/遅い可能性
  • 望ましい性質
    • データの抽象的な状態表現を学習し、観測レベルだけでなく状態レベルで予測
    • ある時点までの観測値を全て考慮した符号(信念状態)を学習
    • 複数ステップを一気にジャンプする予測が可能
  • これらの要求を満たすものとしてTD-VAEを提案

2 モデルに要求されること

2.1 隠れ状態空間の構築

自己回帰モデル
  • チェインルールを用いたモデル化{}

$$ \log p(x_1, \dots, x_T) = \sum_t \log p(x_t | x_1, \dots, x_{t - 1}) $$

  • RNNを用いると隠れ状態 h_t = f(h_{t - 1}, x_t)でデータに文脈を付与して予測を行うことになる
  • 観測空間でそのまま予測をするのでデータの圧縮した表現を学習できない
状態空間モデル
  • 潜在変数を用いて状態間の確率的遷移をモデル化

  • \boldsymbol{z} = (z_1, \dots, z_{T})を状態系列、\boldsymbol{x} = (x_1, \dots, x_T)を観測系列としたとき同時確率を次のようにモデル化

$$ p(\boldsymbol{x}, \boldsymbol{z}) = \prod_t p(z_t|z_{t-1})p(x_t|z_t)$$

  • 事後分布 q(\boldsymbol{z}|\boldsymbol{x})による下限によって学習(VAEと同様)
  • \phi_tを、\boldsymbol{x} = (x_1, \dots, x_T)をフィルタリング、平滑化する関数とすると事後分布は自己回帰的に分解可能(これ自明? よくわからなかった)

$$ q(\boldsymbol{z}|\boldsymbol{x}) = \prod_t q(z_t | z_{t - 1}, \phi_t(\boldsymbol{x})) $$

  • 変分下限(よくわからん。VAEの式変形を調べないとダメそう)

$$ \log p(\boldsymbol{x}) \ge \mathbb{E}_{\boldsymbol{z}\sim q(\boldsymbol{z}|\boldsymbol{x})} \left[ \sum_t \log p(x_t|z_t) + \log p(z_t | z_{t-1}) - \log q(z_t | z_{t-1}, \phi_t(\boldsymbol{x})) \right] $$

2.2 信念状態のオンライン生成

  • 過去の系列は十分な表現力を持つ変数 b_t = b_t(x_1, \dots, x_t)によって近似できるとする

$$ p(x_{t+1}, \dots, x_{T}|x_1, \dots, x_t) \approx p(x_{t+1}, \dots, x_{T}|b_t ) $$

  • RNNだと隠れ状態 h_t b_tに相当

  • 状態空間モデルでは潜在変数 z_tを媒介

$$ p(x_{t+1}, \dots, x_{T}|x_1, \dots, x_t) = \int p(z_t|x_1, \dots, x_t) p(x_{t+1}, \dots, x_{T}|z_t) dz_t $$

  • 上の式と同様に p(z_t|x_1, \dots, x_t) \approx p(z_t|b_t)と近似できるとする

  • 古典的な状態空間モデルではこのような b_tは考えられてこなかった

    • 事後分布を自己回帰的に計算する q(\boldsymbol{z}|\boldsymbol{x}) = \prod_t  q(z_t | z_{t-1}, \boldsymbol{x})と、 z_tの周辺事後分布に関するいくらかの不確実性がサンプル z_{t-1}にリークする可能性がある(とは?)
    • サンプルは確率的なので、 z_tに関する全ての情報を(x_1, \dots, x_t)から得るために、 z_{t-1}を再サンプリングする必要がり、順々に z_{t-2}から z_1まで再サンプリングする必要がある
    • (この2点が何を言わんとしているのかあまりよくわからなかった。なんとなく b_tを考えた方が良さそうという気分は読み取れたが……)

3 系列TD-VAEのための信念状態ベースELBO

  • 状態空間モデル p(\boldsymbol{x}, \boldsymbol{z}) = \prod_t p(z_t|z_{t-1})p(x_t|z_t)を考える
  • 目標はデータの対数尤度\log p(\boldsymbol{x})最大化
    • 自己回帰的に分解して\log p(\boldsymbol{x}) = \sum_t \log p(x_t|x_{\lt t})
    • 所与の tに対して、条件付き尤度 p(x_t| x_{\lt t}) z_{t-1} z_{t}で条件付け
      • 尤度の変分下限は

$$ p(x_t| x_{\le t}) \ge \mathbb{E}_{(z_{t-1}, z_t) \sim q((z_{t-1}, z_t)|x_{\lt t})} \left[ \log p(x_t|z_{t-1}, z_t, x_{\lt t}) + \log p(z_{t-1}, z_t | x_{\lt t}) - \log q(z_{t-1}, z_t | x_{\le t}) \right] $$

  • ここで
    • 状態空間モデルにはマルコフ性が仮定されるので p(x_t | z_{t-1}, z_{t}, x_{\lt t}) = p(x_t|z_t)かつ p(z_{t-1}, z_t|x_{\lt t}) = p(z_{t-1}|x_{\lt t})p(z_t | z_{t-1})
    •  q(z_{t-1}, z_t | x_{\le x})を自己回帰的に分解して q(z_{t-1}, z_t | x_{\le x}) = q(z_t|x_{\le t})q(z_{t-1}|z_t, x_{\le t})

$$ \therefore p(x_t| x_{\le t}) \ge \mathbb{E}_{(z_{t-1}, z_t) \sim q((z_{t-1}, z_t)|x_{\lt t})} \left[ \log p(x_t|z_t) + \log p(z_{t-1} | x_{\lt t}) + \log p(z_t|z_{t-1}) - \log q(z_t|x_{\le t}) - q(z_{t-1}|z_t, x_{\le t}) \right] $$

  •  p(z_{t-1}|x_{\le t - 1}) q(z_t | x_{\le t})は時刻が異なるだけ
    •  b_t = f(b_{t-1}|x_t) z_tに対する信念状態の符号として p_B (z|b)で近似
    • 同様に z_{t-1}の平滑化事後分布を q(z_{t-1}| z_t, b_{t-1}, b_t)として表現
  • 最終的に損失関数は

$$ -\mathcal{L} = \mathbb{E}_{z_t \sim p_B(z_t|b_t), z_{t-1}\sim q(z_{t-1}|z_t, b_t, b_{t-1})} \left[ \log p(x_t|z_t) + \log p_B(z_{t-1}|b_{t-1}) + \log p(z_t|z_{t-1}) - \log p_B(z_t|b_t) - q(z_{t-1}|z_t, b_{t-1}, b_t) \right] $$

4 TD-VAEと飛躍状態モデリング

4.1 TD-VAEモデル

  • 離れた2つのタイムステップに対応するために3章で示したものを改良
  • モデルの全体図

f:id:tokumini:20190803122158p:plain

  • 損失関数は前章のtt_2に、t-1t_1に置き換わって、

$$ -\mathcal{L}_{t_1, t_2} = \mathbb{E}_{ (z_{t_1}, z_{t_2}) \sim q(z_{t_1}, z_{t_2} | b_{t_1}, b_{t_2}) } \left[ \log p(x_{t_2}|z_{t_2}) + \log p_B(z_{t_1}|b_{t_1}) + \log p(z_{t_2}|z_{t_1}) - \log p_B(z_{t_2}|b_{t_2}) - q(z_{t_1}|z_{t_2}, b_{t_1}, b_{t_2}) \right] $$

4.2 TD-VAEの直感的背景

 時間 t_1までに得た全ての情報から将来の時刻 t_2の状態を予測したいとする。時間 t_1までの観測情報は b_{t_1}に圧縮されている。また観測 x_tの背後にはマルコフ性を満たす隠れ変数 z_tがあるとする。

 今時刻が t_2であるようなエージェントを考える。このエージェントは信念モデル p_B(z_{t_2}|b_{t_2})からサンプリングすることによって隠れ状態を推測することができる。状態 z_{t_2}は観測値 x_{t_2}を伴うはずなので、まず p(x_{t_2}|z_{t_2})を最大化したくなる(損失関数第1項・再構成誤差)。そして b_{t_2}を通じて x_{t_2}の情報がリークしすぎないように変分ボトルネックペナルティとして - \log p(z_{t_2}|b_{t_2})を最大化したくなる(損失関数第4項・気持ちはわかる気がするが、この定式化が正しいのかはわからない。意味合い的には尖りすぎないようにする効果が出る? 式変形で出てきた者に対する解釈ということなのだろうか。あと論文中では第2項と書いてあるけど第4項だと思う)。

 そして t_2における状態が t_1における状態から予測できて欲しい。まず t_1における状態がなんであったのかを予測する必要がある。これは単に b_{t_1}を使って求めるよりも x_{t_1 + 1}, \dots, x_{t_2}の情報を使った方が良い予測ができそう。よって q(z_{t_1} | z_{t_2}, b_{t_1}, b_{t_2})という平滑化分布を考えてこれにより z_{t_1}を予測する。この z_{t_1}を用いてジャンプモデル p(z_{t_2} | z_{t_1})を最大化する(損失第3項)。

 最後に平滑化分布と b_1だけで求めた分布の距離を最小化する(これがTD誤差っぽい部分だと思う)。多分平滑化分布の方が良い予測ができるはずで、それを b_1だけから求められるようになると嬉しいので。これは p_B(z_1|b_1) q(z_{t_1} | z_{t_2}, b_{t_1}, b_{t_2})のKL距離を考えて展開すると \log p_B(z_1|b_1) - \log q(z_{t_1} | z_{t_2}, b_{t_1}, b_{t_2})(第2項と第5項)が出てきそう(だけど正確にはよくわからない。 p_B(z_1|b_1) z_1について積分するはずだけどそれは上手く消えるのかな)。

 これらの損失の和を考えると上のような式になっている。

4.3 TD学習との関係

 強化学習だと状態について収益の分布を考える。多くの場合、状態価値や行動価値として収益の期待値だけを近似する。場合によっては収益の分布そのものを近似しようとすることもある(Categorical DQNなど)。

 TD-VAEでは収益ではなくて状態の分布 p_B(z_t|b_t)を近似することになる。 t_1時点における状態を t_2における予測値でブートストラップ的に学習するので時間差分(Temporal Difference)的な学習である。

5 実験

5.1 部分観測ミニパックマン

  • 実験内容:自分自身の周囲 5 \times 5しか見えないパックマン(の表示を簡単にしたやつ)において観測系列をモデリング
  • 比較手法
    • フィルタリングモデル:  q(\boldsymbol{z} | \boldsymbol{x}) = \prod_t q(z_t | z_{t-1}, b_t), \mathrm{where}\, b_t = \mathrm{RNN}(b_{t-1}, x_t)
    • 平均場モデル:  q(\boldsymbol{z} | \boldsymbol{x}) = \prod_t q(z_t | b_t), \mathrm{where}\, b_t = \mathrm{RNN}(b_{t-1}, x_t)
    • TD-VAE(ジャンプなしの連続モデル)
  • 評価指標
    • ELBO(低いほど良い)
    • テストセットにおける負の尤度(低いほど良い)
  • 結果

f:id:tokumini:20190802143455p:plain

  • 平均場モデルが最も性能が悪く、つまりただ単に b_tを信念状態として扱うだけでは性能が悪化することがわかる。TD-VAEによる工夫を導入することで b_tを正しく信念状態として扱うことができるようになる。

5.2 ムービングMNIST

  • 実験目的:ジャンプ予測が可能であることの実証
  • 実験内容:横移動するMNISTの画像を予測
  • 手法時刻 tからロールアウトした結果を出力
    1. 時刻 tまでの観測から b_tを計算
    2.  z_t p_B(z_t | b_t)からサンプリング
    3.  z = z_tから始めて z \leftarrow z' \sim p(z' | z)によって zの系列を取得
    4.  p(x|z)によって zの系列から xを復元
  • 結果

f:id:tokumini:20190802145208p:plain

5.3 ノイズ付き調和振動子

  • 実験目的:観測の情報が少ない場合でも状態予測が可能であることの実証
  • 実験概要:ノイズの多い
  • 階層的TD-VAEを利用
    • 集約部分で積んだLSTMを使う?
  • 結果

f:id:tokumini:20190802145356p:plain

5.4 DeepMind Labでの実験

  • 実験目的:より複雑なドメインでの性能検証
  • 実験概要:DeepMind Lab環境において画像のジャンプ予測を実行
  • 各モジュールにCNNを用いたモデル(Figure 8)を使用
  • 実験1:最初に3つの z_1, z_2, z_3をサンプリングし、これらとこれらからジャンプした後の潜在変数を復元

f:id:tokumini:20190803112200p:plain

  • 直接復元では z_1, z_2, z_3はどれも同じように見えるが、遷移した後の状態は異なる

    • 見かけの観測の背後にある状態の違いを認識できている
  • 実験2:ロールアウトの実験

f:id:tokumini:20190803112617p:plain

  • 複数ステップのジャンプ予測を行っても回転や前進の遷移を上手く捉えられている

AtCoder Beginner Contest 135

結果

ユーザ名 tokumini
コンテスト名  AtCoder Beginner Contest 135
順位  327th / 4583
パフォーマンス   1795
レーティング  1925 → 1913 (-12)

 難しかった。

A問題

 見た目が難しくてびびった。

 提出

B問題

 脳みそを使わない力のこもった三重ループを投げつけた。

 提出

C問題

 証明とかよくわからないけど貪欲にやっていけばできるっしょ! というノリ。最大流で考えるのかぁ。

 提出

D問題

 桁DPっぽい雰囲気も感じたけどその方針にはあまり深入りせず考えていたらDPっぽい遷移が見えたので実装し始める。しかしいつも通りちゃんと詰めてはいないので書いてからサンプル合わないし遷移の式がよくわからんという感じになって二度手間になるやつ。

 意識はしていなかったけどDP配列を2つ分しか用意しない省メモリの実装になっていた。普通に「dp[i][j] := 先頭 i 文字として考えられるもののうち,13 で割ったあまりが j であるものの数」とした方が混乱せずに済むのでそうしていれば良かったのに。初期化のところも汚くてひどい実装になってしまった。

 提出

E問題

 なにこれ難しすぎる。X,Yが小さくて回り道しなければいけないサンプル1と、貪欲に近づいてから最後調整するだけでは最適にならないサンプル3のコンビネーションが強くてなにもわからなかった。マンハッタン距離なので45度回転みたいなご利益もわかっていない念仏を唱えてみたりもしたけど別になにも起こらず。

 解説PDFを見てもはぁそうですかという感じで実装に数時間かかった。個人的には行き方のパターンA, Bで分類するよりもX + Y \lt Kかどうかで分類したほうがわかりやすかった。

  X \ge Yとするように変換し忘れていたり負の数の剰余を取っていたりとバグらせまくってひどい有様に。自分の提出ページが2ページまでいってしまった。きつかった。

 提出

F問題

 コンテスト中は開きもしなかった。順位表も見ていないのでどのくらい解かれているのかも知らないけど、もしF問題が簡単めでみんなそっち解いているとかだったらパフォーマンスがひどいことになっていただろうな。別に簡単ではなかったようで良かった。

 30分くらい考えてみたけど全然わからなくて解説を見てAC。Zアルゴリズムで検索できるというのも知らなかったしグラフに落としてからもなんだか芋臭い実装しかできなくてしっくりこない感じがある。難しい。

 提出

価値のソフトマックス分布を教師としたAlphaZero学習

要約

 価値のソフトマックス分布を行動選択および教師分布として利用することで学習が2倍から3倍程度速くなった。

背景

 前回、生成している棋譜を分析したところ、評価値を大きく損ねる悪い手が多く選ばれすぎていると感じられた。この原因として探索回数をもとにした分布によって行動選択をしていることが考えられるため、代わりに価値にソフトマックス関数を適用したものを用いるように変更して実験を行った。

用語の定義

 「ソフトマックス分布」で検索してもあまり用例が出てこないので適切ではないのかもしれないが、とりあえずこの記事では実数ベクトルに対してソフトマックス関数を適用したものをソフトマックス分布と呼ぶことにする。ここでソフトマックス関数には温度tというパラメータがあるものとして、ベクトル\boldsymbol{Q}に対応するソフトマックス関数適用後のi番目の要素の確率p_i

$$ p_i = \frac{\exp(Q_i / t)}{\sum_j \exp(Q_j / t)} \tag{1} $$

と定義する。tは大きくすればするほどQ_iの値によらずどれも等確率で選ばれるようになっていき、逆にtを小さくしていくとQ_iの大小関係がより強調されるようになる。

実験設定

 AlphaZero式の強化学習を行った。細かい設定はこの記事を参照のこと。

 各局面で800回の探索を行った後、式(1)のように価値のソフトマックス分布を計算して行動選択分布や教師分布として用いた。価値は[-1,1]の値をとり、温度はt = 0.01とした。

 次の3パターンについて比較を行った。

名前 行動選択分布 Policy教師分布
従来 探索回数に比例した分布 探索回数に比例した分布
選択のみ 価値のソフトマックス分布 探索回数に比例した分布
選択/教師 価値のソフトマックス分布 価値のソフトマックス分布

 (注)探索回数に比例した分布とは各行動についての探索回数を探索回数の総和(今回の場合だと800)で割ったものである。

$$ p_i = \frac{N(s, a_i)}{\sum_j N(s, a_j)} $$

 従来手法の結果としては新規に実験を行ったわけではなく前回得られた結果をそのまま用いた。

実験結果

  • floodgateの棋譜に対する損失

f:id:tokumini:20190726150627p:plainf:id:tokumini:20190726150633p:plain
左:Policy損失 右:Value損失

 価値のソフトマックス分布を使う手法はまたそこまで学習を回せていないが、同じステップ時点の従来手法よりも良い性能になっていることがわかる。特に「選択/教師」では従来手法で2Mステップ回した時点の結果よりもすでに良い結果となっている。

  • Gikou2(深さ8)と1手0.25秒で500局対局した結果から推定されるEloレート

f:id:tokumini:20190726164312p:plain

 実際の棋力としても「選択/教師」が同ステップ時点での比較では最も良い性能となっている。学習途中なので最高到達点が上がっているかはまだ不明だが、少なくともここまでの段階で学習が2~3倍は高速になっている。

学習中に生成した棋譜の分析

 学習ステップ数や棋譜を保存する間隔等が違うので公平な比較にはなっていないが、参考程度に眺めると一応傾向は見られた。

 まず手数は次のようになった。

手法 平均 中央値 最大値 最小値
従来 75.7 74 317 14
選択のみ 110.6 107 512 25
選択/教師 107.3 104 512 32

 全体的に手数が伸びており、512手に到達したことによる引き分けもいくらか見られた。一般的に強いソフト同士の対局の方が手数は長くなりやすいと言われている。

 もちろん「強い⇒手数が伸びる」が成り立っていても「手数が伸びている⇒強い(良い棋譜を生成している)」とは言えないが、無理やり手数を伸ばさせる工夫を他に入れたわけでもないので傍証にはなっているのではないかと感じる。

 別のデータとして、1手進んだ局面での探索結果と現局面での探索結果の差の絶対値の統計を調べると次のようになっている。

f:id:tokumini:20190726150812p:plain

 探索回数に比例した分布で行動選択をやめることで評価値が大きく動くことが少なくなったことがわかる。これも根拠はない話だが、基本的にはあまり大きな変動がない方が良い棋譜なのではないかと思われる。

所感

 個人的な感覚では、将棋は可能な指し手の集合において悪手の割合が高いゲームであり、さらに「何度か探索した結果悪手だと判明する」頻度が高いのではないかと感じる。そのような場合に探索回数に比例した分布で行動選択をすると価値を大きく損ねる手が多く選ばれすぎるのではないか。これはゲームに依存する性質の可能性はあり、たとえば囲碁で価値のソフトマックス分布を使ってもあまり性能は伸びないかもしれない。

 またもとから30手を超えた場合には探索回数最大の行動を選択するようにしているならこの変更による恩恵は少ないかもしれない。個人的にはできるだけ恣意的な切り替えは避けたいのでこれで同じ結果が得られるならこちらで良いのかなと感じる。

 この変更に伴うパラメータの調整を考えると、価値のソフトマックス分布を使う方法では方策に対する依存性がやや弱まると思われるのでディリクレノイズが不要になったりしないだろうか。悪い手を指さないことと、いろんな指し手を試してみることのバランスを上手く調整することが学習の高速化で重要な点に思える。

余談

 Eloレートを計算する際の対局においても、同じ対局が何度も行われないように30手までは探索回数を正規化した分布に従って指し手を選択している。対局を見ていると30手までで大きく形勢を損ねていることもあり、価値のソフトマックス分布に修正すると見た目のレートはやや改善する可能性もあると感じた。本質的な改善ではないのであまり気も進まないが……。

AtCoder Grand Contest 036

結果

tokuminiさんのAtCoder Grand Contest 036での成績:254位
パフォーマンス:2080相当
レーティング:1906→1925 (+19) :)
Highestを更新しました!

 B問題を自分としては素早く解けたがC問題に歯が立たなくて座っているだけの時間が長かった。

A問題

 一つを原点に置いて良いことに気づかず、長方形から3つの三角形を引くことを考えて時間がかかった。

f:id:tokumini:20190722150522j:plain

 いやこれだって左右反転してX軸方向にずらせば一つは原点になるんだが……。気づかないときは気づかない。

 立式したら引き算が出る影響でSの大きさでも場合分けしまくるひどいコードになってしまったし考察の方針が悪すぎた。直接公式が思い出せずとも外積で計算できるってことは知っているんだから一つは原点に置いて良いというのは当たり前に近いなぁ。

 提出

B問題

 サンプルが多めなので異常なひらめき系ではないのかなとかメタ読みを挟みつつサンプルを手で解いていたところ、同じ数字が出るところまでで消えるからその次へ辺を張って……

f:id:tokumini:20190722150749j:plain

という感じで上図が出て周期性がありそうだなと実装開始。考察を詰めきらずに実装を始める無謀さは人よりありそうだと思っていて、今回はそれが良い方へ作用したか。本番でのコードのわりにはそこまで見通し悪くないような気がするしWAも出さなかったのでなんとか。

 提出

C問題

 なんか図形的に格子点の一部を除外する感じかなぁと考えていたが、普通に必要十分条件を出して数え上げる問題だったのか。しかし解説PDFを読む限り、条件を出せてもそれを数え上げる方法をひねり出すのも難しそうだし、これは難しい。

 ほぼ解説通りのコードで通したけど、2で割った余りを出すつもりが1で割った余りを計算していてWAを出しまくりきつかった。サンプルにMが奇数の場合がないという罠。

 提出