事前学習を含めたMCTSNetの学習結果

探索系NN

　以下の続き。

　前回はエンコーダ部分(MCTSNetのEmbedネットワーク)だけ事前学習したものを用いた。結果的に0回探索でも事前学習より悪い損失に留まり、また探索回数を増やしたときに性能向上しなかった。対策案として今回は次の2点について修正を行った。

  • 勾配計算をMCTSNetの論文が主張する通りのものに修正した
  • 事前学習したネットワークのヘッド部分もMCTSNetのSimulationネットワークおよびReadoutネットワークの初期値として用いることにした

実験結果

学習損失

f:id:tokumini:20200902195811p:plain

　点線(損失2付近に収束しているもの)が10回探索後の推論結果(MCTSNetの勾配第一項)であり、その他各探索が損失低下に寄与した程度とその状態に至る確率の積(MCTSNetの勾配第二項)である。

　10回探索後の損失値が順調に減っていることは良いが、第二項の方は0最初に0になってからほとんど変わっていないのは良くないかもしれない。が、よく考えれば第二項は符号反転しているため負になることが望ましいが、値としてはそこまで大きくなり得るわけではないので0付近であることは仕方ないか。

　簡単に計算してみると、0回探索から10回探索をしたところで、大きく見積もってもPolicy損失の低下は0.5程度が関の山かと思われる。そしてそこへその状態へ至る確率がかけられるので、よっぽどPolicyが偏る局面でない限りこれの1/10としても約0.05程度となるので-0.05が理想的な値だろうか。

検証損失

f:id:tokumini:20200902200205p:plain

　残念ながら結果としては0回探索が常に一番下にあり、探索による性能向上は見られなかった。0回探索のものも徐々に損失値が悪化している点は気になる。事前学習の最終ステップでは1.877444だった損失値が、最終的には1.901313になってしまった。

3Mステップ時点での検証損失

f:id:tokumini:20200902194858p:plain

　わかりやすいように最終ステップでの検証損失を抜き出してプロットすると上のようになる。綺麗に右肩上がりとなっており、理想とは程遠い。

対局による検証

　損失の値が悪くともひょっとすると強くなっている可能性があるかもしれないため、実際に対局させることで性能の比較を行った。学習済みの同じパラメータを用いて、探索回数0回でReadout Policyに従って指すモデルと、探索回数10回でReadout Policyに従って指すモデルで1000局の対局を行った。序盤30手以内ではPolicyのSoftmaxに従う確率で指し、それ以降は最も確率が高い行動を選択するようにした。

　結果は10回探索側から見て

勝数 引分数 負数 勝率 Eloレート差
364 8 628 36.8% -93.9

であった。損失値の悪化通り、対局でも性能が落ちていることがわかった。

今後

　要するに現状はMCTSNetの再現がさっぱりできていない。実装ミスや理解の勘違いを含めもう一度見直して、とりあえずまず再現できることを確認しなくては始まらない。

　MCTSNetの元論文は一人ゲームで実験しており、二人ゲームに適用する上で視点が反転する（評価値で言えば符号が反転する）という事象が起こることで何か不具合が起きていないか気になる。Backupネットワークは全結合なので影響は考慮できると思っているし、Backupネットワークには常に(手番が自分の局面の表現, 次の相手が手番の局面の表現)という順番になっているのでそこでも悪影響はでないと考えているが……。なにか見落としているかもしれない。

エンコーダを凍結した探索系NNの学習結果

探索系NN

　以下の続き。

　前回の学習の反省としてエンコーダ側を事前学習し、凍結することにした。事前学習でのPolicy損失は1.85であった。

実験結果

全体の結果

　前回に比べて値が安定するようになり、MCTSnetはかなり低い値まで下がっていった。しかし単純な探索なしである事前学習よりも損失が高い値で留まっているため、探索が有効に機能しているわけではないことがわかる。

　提案手法とStacked LSTMはあまり値が下がらず、なんらかのミスを感じる。

MCTSnet

　学習初期こそ探索回数に応じて損失値が小さくなってはいるが、学習が進むとほとんど差がなくなってしまっている。

提案手法

　1,2回目よりは3回目以降のほうが損失値が小さくなっているが、7回を超えたあたりからまた上がり始めてしまっている。

Stacked LSTM

　提案手法とだいたい同じ傾向にある。

考察

　簡便さや統一性のため学習方法として「10回の探索（MCTSnetの場合はシミュレーション）を行い、各回の探索後にReadout方策を計算してそれと正解ラベルから交差エントロピーを算出し、最小化」という方法を取っているのだが、よく考えるとこれではReadout方策のみが学習可能でSimulation方策は勾配が流れてきていなさそうであることに気づいた。なのでどの手法もSimulationがほぼランダムに行われている状態のようなものに思われる。

　サボらずにMCTSnetの学習手法をちゃんと模倣するべきだが、そうなると少なくともStacked LSTMには同じ手法が使えないので平等な比較というのは難しくなる。とりあえず提案手法は同じ手法で学習できるはずなのでその2者での比較になるだろうか。もう少しMCTSnetの学習に対して理解を詰めてから実装パートへ向かう予定。

囲碁のルールについてのメモ

　Miacisをコンピュータ囲碁にも対応させようかと思って調べてみているが、意外と詰まるところが多そうだ。やっぱりあまり知らないゲームの実装は難しい。とりあえずここまでの考えをメモしておく。

プロトコル

　基本的にはGo Text Protocolに対応していれば良いのだろうか。

　まだちゃんと把握しているわけではないが、ボードサイズを可変にできるようにしないといけないとしたら少し実装を考えないといけないかもしれない。

ルール

　ルールがとにかく大変。プログラム的に実装しやすいのは中国ルールだと聞いたことがある気がするので「囲碁 中国ルール」などで調べてみたが、それでも問題が全くないわけではなさそう。

　というかそもそも終局判定が難しく、「パスが2回続いたら終了」が基本路線になるのだろうか。ただ気になるのは、自分の眼を潰すような手もルール上非合法手ではないとしたら、「パス = 合法手0」ではなくなる。自分の眼に打つと二眼がなくなるので相手に取られるようになり、でも相手もまたいずれ二眼を自ら潰すので……ということで合法手からランダムに選択するエージェント同士では何手やっていても合法手が0にならなさそう。

　コンピュータ将棋が基本的に歩とか香車の不成を生成しないのと同じようなノリで自分の眼には打つ手は生成しないということにするのだろうか。そうなると合法手生成自体にいくらか思考が混じっているような感じがして少し心地悪い感じがある。実際に自分の眼に打つことがときに有効手となったりしないのかどうか、囲碁に詳しくないのでさっぱりわからない。

　とりあえず

  1. 自分の眼には置かないという条件で合法手生成をして、その合法手が0だった場合のみにパスをする
  2. パスが連続したら終局とし、中国ルールで勝敗を計算する

という基準でなら想像する限りなんとかなりそうではある。当面はこれを実装予定。

　余談だが、仮にこれが正しいとすると、合法手がなくなるまで打つエージェント同士の対局の最後は、自分の陣地に打ち合うようなあまり勝敗に影響しない手が多くなりそうではある。AlphaZeroが自己対局において勝率予測95%だかなんだかで投了（自己対局の5%では予測が合っているか確認するために最後まで打つ）みたいな処理をしていたのはそういう理由があったからなのかなと思ったりした。将棋では入玉形にでもならない限り正直そういうことをする意義があまりない気がする（実際にMiacisでは簡単な詰み探索を入れつつ最後まで指すようにしている）。

　さらに余談。全くのゼロから強化学習をすることを想定すると、「合法手からランダムに選択するエージェント同士の対局が終わらない」ようなゲームは鬼門だったりするんだろうか。適当な手数で打ち切るとしても、途中局面での勝敗が決定できないとするとまともな報酬を得るのが難しそう。報酬が疎であるような環境の一種と言えばそれだけのことではあるのかもしれないが。

探索系NNの学習結果

探索系NN

　とりあえず試しで回した学習が一通り終わったので結果をまとめる。

実験設定

　将棋での教師あり学習でモデルの学習を行い、Policy損失を比較した。

比較手法

  1. 探索なしの全結合ネットワーク
  2. MCTSnet
  3. 提案手法
  4. Stacked LSTM(Deep Repeated ConvLSTMを意識したもの)

各手法の詳細

前提

　4つの手法はどれも同じアーキテクチャの状態エンコーダを用いる。これは3つの残差ブロックの(6層CNN)からなり、将棋の盤面を 32 \times 9 \times 9 = 2592次元の表現ベクトルへと変換する。

1.探索なしの全結合ネットワーク

　先のエンコーダによって得られた表現ベクトルを全結合層に入力し、 27 * 9 * 9 = 2187次元で表される行動について方策を得る。

2.MCTSnet

　先のエンコーダによって得られた表現ベクトルをMCTSnetにおけるEmbedネットワークとして利用し、それ以降はMCTSnetの動作に従う。

3.提案手法

　先のエンコーダによって得られた表現ベクトルをLSTMに対する入力とし、そこから探索方策用LSTMを用いて方策を出力し、最大の確率を持つ行動を選択し、次の状態に移る。ここで探索方策は一局面戻るという行動も付け加えており、2188次元の出力を持つ。

　最終的に得られた表現ベクトルの系列全体を最終決定用LSTMに全て入力し、実際に取るべき行動を選択する。ここでは一局面戻るという選択肢はないため出力は2187次元となる。

4.Stacked LSTM

　先のエンコーダによって得られた表現ベクトルを最初だけLSTMに入力し、以降は方策RNNと遷移モデルRNNと見なす2つのLSTMによってLSTMの推論のみで探索のようなことを行う。

　厳密にはDeep Repeated ConvLSTMとは違うところが多いが、探索という行為をLSTMに全て任せるということを試すために比較手法として採用した。

学習方法

探索なしの全結合ネットワーク

　単純にネットワークが出力した方策と正解ラベルから交差エントロピーを算出し最小化

MCTSnet、提案手法、Stacked LSTM

　10回の探索（MCTSnetの場合はシミュレーション）を行い、各回の探索後にReadout方策を計算してそれと正解ラベルから交差エントロピーを算出し、最小化

　MCTSnetの正しい学習方法とは異なるが、学習条件を平等に揃えることを重視した。

実験結果

全体の結果

　simple mlpの性能が妙に低くて違和感がある。やはりバッチサイズ1だと性能が悪くなってしまうのだろうか。また他のネットワークは同じ局面を10回の探索分学習しているので、擬似的に10倍の学習をしているとも考えられる。

　学習は全て3Mステップで統一したが、横軸をかかった時間でプロットすると次のようになる。

　時間で見ればsimple mlpも悪くはないのでやはり学習量の問題なのかもしれない。

個別の結果

MCTSNet

　シミュレーション回数が1回だろうが10回だろうがほとんど損失の値が変わらない。

提案手法

　探索回数（遷移回数）が増えるとむしろ性能が落ちる。全然ダメ。

Stacked LSTM

　探索回数（遷移回数）が1回よりは2回以上のほうが良くなっているところがあるが、探索回数が多くなればなるほど下がるという傾向は見られない。

結論

　全体的にそもそも学習があまり上手くいっていない感じがあった。バッチサイズ1というのが難しいのかもしれない。学習のバッチ化は各手法でそれぞれ個別に実装しなければいけなさそうなので実装量が重い気がしている。次はとりあえずBatch Norm以外のものを試してみる予定。

　またエンコーダ部分は事前学習してフリーズさせるのも再検討してみたい。表現ベクトルの次元数も、32chなので小さいように思えるがこれにボードサイズの9×9がかかると意外と大きくなるということに気がついていなかったのでこのあたりも変えてみるか。

128チャンネルで1ヶ月学習(2回目)

コンピュータ将棋

　5月の世界コンピュータ将棋オンライン大会が終わってから、実験サイクルを早めるため学習は64チャンネルのネットワークで行っていた。しかしlibtorch1.5.0版に対応した影響で後方互換性がなくなり、すぐ動かせる強いパラメータが手元ないと細かい動作の検証で困るため、128チャンネルのネットワークで1ヶ月の学習をやり直した。

実験

　ほぼMiacisのWCSOC2020版

と同じ内容で実験を行ったが、「学習スレッドのスリープ時間と学習速度の関係」から生成量2倍で学習ステップ数1/2にしてもほぼ変わらないという結果を得ており、それを追試も兼ねてそこ（と学習率の減衰）についてだけ変更を行った。

変更のある項目 今回 前回
生成量 1ステップあたり256局面 1ステップあたり128局面
学習ステップ数 1M 2M
学習率 学習の80%経過時点で1/10 学習の50%経過時点、75%経過時点で1/10

学習結果

　横軸に学習時間、縦軸にfloodgate棋譜を用いた検証損失を取りプロットすると次のようになった。

f:id:tokumini:20200727100602p:plainf:id:tokumini:20200727100604p:plain
左:Policy損失　右:Value損失

　今回の学習の方が進みが良く、前回の学習の学習率減衰が起きた後と同じくらいの損失値を学習率減衰が起こる前で実現できていた。

　横軸を学習ステップ数にして比較した結果も載せておく。

f:id:tokumini:20200727102916p:plainf:id:tokumini:20200727102920p:plain
左:Policy損失　右:Value損失

　最終的な学習時間は649時間28分(≒27日)であった。前回の672時間32分より約一日短くなったが、これは学習ステップ数が少なくなった影響である。

　最終ステップでの損失は具体的には

手法 Policy損失 Value損失
今回 1.897591 0.672531
前回 1.923749 0.677997
差分 -0.026158 -0.005466

となった。以前の検証ではEloレートと損失の間に線形な関係を仮定すると係数はPolicy:-2135、Value:-8649と算出され、今回の結果と合わせるとPolicy損失の差分から計算すると55.8、Value損失の差分から計算すると47.3のEloレート向上が予想できる。

対局結果

　Miacis(1手1秒)とYaneuraOu/Kristallweizen(1手0.2秒、4Thread、定跡オフ)で対局を行った。

手法 勝数 引分数 負数 勝率 相対Eloレート
前回 317 0 183 63.4% 95.4
今回 697 2 301 69.8% 145.5

　約Eloレート50の伸びであり、ほぼ想定通りといったところ。

　YaneuraOu/Kristallweizenは持ち時間を増やしていくとかなり強くなる印象なのでなかなか同条件で互角というところまではまだ遠そうだが、また少しは近づいたか。

MCTSnetの学習（仮）

探索系NN

　MCTSnetのだいたいの実装が終わり、将棋での教師あり学習を回し始めている。

　簡単に回してみたところ、Backupネットワークでの振る舞いが上手くいっていないように思えたので、論文の3.4 Design choicesに記載されているように、Backupネットワークをゲート付きの差分更新にして学習を行った。

f:id:tokumini:20200723101650p:plain

実験

　floodgateの2016年〜2019年の棋譜を用いて、棋譜で指された行動をOnehotの教師信号として交差エントロピーで損失を計算した。MCTSnetの正しい学習方法は以前記事に書いた通りだが、今回はとりあえず簡便のため、 M = 10回の探索まで都度ルートノードからReadoutを行い、教師と比較して損失を計算したものの和

\displaystyle \sum _ {m = 1} ^ {M} l _ m

という単純な損失について学習を行った。

結果

f:id:tokumini:20200723095000p:plainf:id:tokumini:20200723095015p:plain
左:学習損失　右:検証損失

　図には1回探索後から10回探索後まで10本の学習曲線があるわけだが、それらがほぼ全て重なるような形になっている。学習が安定したようにも見えるが、Backupネットワークにゲートを追加した結果ゲートが常にOFFになるよう学習され、探索によってルートノードの埋め込みベクトルが全く更新されなくなっただけの可能性もある。

　ちなみにこのPolicy検証損失値が4.0付近という値は非常に悪い。今までのAlphaZeroモデル(10ブロック128チャンネル)などでほぼ同じデータに対して検証損失を計算すると、教師あり学習の場合なら1.5、強化学習の場合でも1.9ほどまでは落ちる。精度が低い原因としては

  • 埋め込みネットワークが3ブロック64チャンネルと小さい
  • バッチサイズ1なのでBatch Normalizationが機能していない
  • そもそも学習もやや足りていない

などが考えられる。どれも基本的にどうしようもない問題なので改善は難しいかもしれない。ネットワークは大きくしたくないし、バッチサイズ複数に対応するのもあまり現実的ではないように思える（MCTSのパスの長さが都度異なるのでどう実装すれば良いのかわからない）。今回の学習量でもかかった時間は2080tiのマシンで14時間ほどで、バッチサイズが1なのでどうしても学習速度は高くならない。

　そもそも探索回数10程度で将棋ではっきり強くなるかはやや疑問であり、どちらかというとオセロの終盤での評価がまともになる可能性を感じているため、オセロでどうにか棋譜を探して教師あり学習をやるというのが現実的な線だろうか。

時系列モデルが木構造を学習できることの検証

探索系NN

　前回の考察では、時系列モデルが暗黙のうちに木構造を学習できるので木の遷移履歴を時系列展開しても良いという仮説を立てた。この仮説を多少なりとも検証するため、今回は木に関する簡単なタスクを考えて、それが学習可能かどうかを実験により確かめた。

実験

　タスク概要:「木についての深さ優先探索での訪問順が与えられるので、幅優先探索での訪問順を出力せよ」

具体的なデータ生成手順

  1. N頂点の木をランダムに生成する
  2. 生成した木についてランダムに根を決定
  3. 根から深さ優先探索を行い、訪問順を記録(これを時系列モデルへの入力とする)
  4. 根から幅優先探索を行い、訪問順を記録(これを正答とする)

例

f:id:tokumini:20200708111225p:plain

細かい点

  • DFSでは戻る際の訪問も記録しているので、系列から完全に木を復元可能（だと思う）
  • BFSにおける同じ深さでの優先度はDFSで先に探索された順と同じとする
  • ノードを入力する際はOnehotベクトルの形式にして入力
  • N頂点の木から得られるDFSの系列（入力）は 2N - 1

実装

実験結果

頂点数 N = 6

f:id:tokumini:20200708111650p:plain

　単純なLSTMおよび以前実装したDNCのいずれにおいても50000データほど学習させると正答率（BFS順を完全一致で出力できた割合）が100%になった。 N = 6という小さい木ではあるが、訪問順を詳細に記録しておけば木構造を認識することはできていそうである。

頂点数 N = 20, 50

　LSTMについて N = 20, 50として実験を行った。

f:id:tokumini:20200710135415p:plain

　20ノード, 50ノードのものはバッチ学習として1ステップ32データにしているので、データ数としては5 * 32 = 160万データとなる。それだけ学習させると20ノードのとき正答率93.7%、50ノードのとき正答率8.0%となった。

頂点数 N = 50 その2

　50頂点くらいはなんとか学習してほしかったので、GPUを使うようにプログラムを変更してバッチサイズを256、学習ステップ数を20万(計データ数は5億程度)にして再度実験を行った。

f:id:tokumini:20200711101243p:plain

　最初は隠れ層の次元数512（青線）でやったところ正答率60%程度で頭打ちになり最後は突然nanになって崩壊してしまった。1024（赤線）でやり直したが、学習は遅いうえ損失も（nanではないが）爆発して正答率が崩壊するのは同様だった。LSTMで記憶容量を超えるとこういう感じで崩壊してしまうものなのだろうか。

雑記

　特に工夫していない1層のLSTMではそこまで長い系列（大きい木）は扱えないかもしれない。DNCをバッチ学習に対応させて可能性があるかどうか、あるいは違う系列モデルを実装するか。 N = 50だと入力系列の長さは 99であり、自然言語処理で考えて99単語からなる文となると長めではあるか。

　一方で30頂点くらいでもちゃんと探索できれば探索なしよりは強くなるんじゃないかという気もする。この記事でやっている実験は実際のゲーム木探索での状況とはやや異なるので、これの性能を追い求めていてもなぁとも思うところ。MCTSnetも実装するべきことを考えると結構実装が重たいので早めに実際の利用環境で試してみたいという気持ちはある。どちらの方針を取るにしてもとにかく実装を進めねば。

MCTSnetの損失計算部

論文

　MCTSnetの解説は他にもある

ので、そちらも参照されたし。この記事では損失計算部分にだけ注目して記述する。

　arXiv版とOpenReview版は式番号が異なるので注意。OpenReview(ICLR2018)で一回Rejectになって、ICML2018に通っていて、arXivの最新版はそのICMLにある版のと近そうなので、とりあえずこの記事では基本的にarXiv版に準拠する。

3.5 MCTSnetの訓練

　MCTSnetの読み出しネットワークは、最終的に探索全体を考慮した行動決定および評価を出力する。 この最終出力は、基本的に値ベースの学習や方策勾配法などの損失関数に従って（つまり強化学習によって）訓練できるが、簡単のため以下では各状態で教師行動が決まっているもとで教師あり学習でMCTSnetを学習することを考える。

　記号の定義

  • z _m : m回目のシミュレーションで確率的にサンプリングされた行動系列
  • z_{\le m} : m回目までのシミュレーションで確率的にサンプリングされた行動系列の系列
  • \boldsymbol{\mathrm{z}} : 確率変数としての z_{\le m}
  • M : 総シミュレーション回数

　基本的には M回シミュレーションを行った後の最終的な出力方策 p _\theta(a|s, \boldsymbol{\mathrm{z}})について、教師行動 a ^ *について交差エントロピーを計算する。

\displaystyle l(s, a ^ * ) = \mathbb{E} _ {\boldsymbol{\mathrm{z}} \sim \pi(\boldsymbol{\mathrm{z}}|s)} [ -\log p _\theta(a ^ *|s, \boldsymbol{\mathrm{z}}) ] \tag{8}

　上式は周辺分布についての対数尤度の下限としても解釈できる（※ここはよくわからない）。

　そして現実的に \boldsymbol{\mathrm{z}}全てについて計算できるわけはないので、一つのサンプルについて勾配の推定を行う。（Schulman et al., 2015が引用されているのでちらっと見てみたがよくわからなかった）

\displaystyle \nabla _ \theta l(s, a ^ * ) = -\mathbb{E} _ {z} [\nabla _ \theta \log p _\theta(a ^ *|s, \boldsymbol{\mathrm{z}}) + (\nabla \log \pi(\boldsymbol{\mathrm{z}}|s; \theta _ s)) \log p _\theta(a ^ *|s, \boldsymbol{\mathrm{z}}) ] \tag{9}

　（この式中の \boldsymbol{\mathrm{z}}は zの間違いである気もするが、とりあえず論文通りの記述にしておく）

　最初の項は単純に上の損失をそのまま微分したもの。

　2番目の項はシミュレーション分布に関する勾配に対応し、REINFORCEアルゴリズムあるいはActor-Criticのようなやり方によって学習する。この項において \log p _\theta(a ^ *|s, \boldsymbol{\mathrm{z}})が報酬信号の役割を果たす。これが大きくなるようなシミュレーション系列は良いシミュレーション系列だったと見なすことができるため。

　（式としては記述がないが？）シミュレーション方策 \pi(a|s; \theta _ s)に負のエントロピー正則化項を追加する。

3.6 信頼割り当ての工夫

　REINFORCE勾配は不偏だが分散が大きい。最終的な行動 a ^ *を決定するまでに M回のシミュレーションが寄与していて、各シミュレーション中でもどのノードを選択していくかという問題があるため計 O(M \log M)から O(M ^ 2)ほどの行動決定があり、信頼の割り当てが難しい。これに対処するため一つの逐次的決定問題のサンプルからBias-Varianceのトレードオフを調整できる手法を提案する。

　 M回のシミュレーションを行うとして、 m = 1, \dots, Mのいつでも最終的な行動決定分布 p _\theta(a|s, z_{\le m})を考え、損失 lを計算することはできる。 m回時点での損失を l _ m = l(p _ \theta(a|s, z _ {\le m}))と定義する。

　最終目標は -l _ Mの最大化である。 l _ 0 = 0としたとき、この最終的な損失は次のように変形できる。

\displaystyle -l _ M = -(l _ M - l _ 0) = \sum _ {m = 1} ^ {M} -(l _ m - l _ {m - 1})

　 \bar{r} _ m = -(l _ m - l _ {m - 1})と置くと、これは m回目のシミュレーションで損失が減少した量であると見なせる。ここで、 m回目以降のこの量の累積和を R _ m = \sum _ {m' \ge m} \bar{r} _ {m'}と置くと、最終的に求めたい量は - l _ M = R _ 1である。

　式(9)のREINFORCE項について -(\nabla \log \pi(\boldsymbol{\mathrm{z}}|s; \theta _ s)) \log p _\theta(a ^ *|s, \boldsymbol{\mathrm{z}}) = Aと置くと、

\displaystyle A = \sum _ m (\nabla \log \pi(z _ {m}|s; \theta _ s)) R _ 1 \tag{10}

　（次の式以降そうなるのだが、ここも多分 \pi(z _ {m}|s; \theta _ s)ではなく \pi(z _ {m}|s, z _ {\lt m}; \theta _ s)だと思われる。まぁ自明なものとして省略しているのか）

　ここで z _ mにおける確率変数は m以降の部分にしか影響を及ぼさないことから R _ 1の部分は R _ mに置き換えることができ、

\displaystyle A = \sum _ m (\nabla \log \pi(z _ {m}|s, z _ {\lt m}; \theta _ s)) R _ m \\ = -\sum _ m (\nabla \log \pi(z _ {m}|s, z _ {\lt m}; \theta _ s)) (l _ M - l _ {m - 1}) \tag{11, 12}

とすることができる。つまり、 m回目のシミュレーション終了時点では、最終損失をそのまま強化信号として使うのではなく、最終損失と m回目時点での差分を使用する。これによってバイアスは生じないまま分散は小さくなる。

　さらに割引率 \gammaを導入してバイアスと分散のトレードオフを行う。 m回目のシミュレーションは m回目に続く近いところで多く貢献していると考え、遠い未来についての貢献は多少考慮する量を減らすという意味合いがある。 R ^ \gamma _ m = \sum _ {m' \ge m} \gamma ^ {m' - m} r _ {m'}と置いて、MCTSnetの最終的な勾配計算は

\displaystyle \nabla _ \theta l(s, a ^ * ) = -\mathbb{E} _ {z} [\nabla _ \theta \log p _\theta(a ^ *|s, z) + \sum _ m \nabla \log \pi(z _ m | s; \theta _ s) R ^ \gamma _ m ] \tag{13}

木探索についての考察2

探索系NN

　以下の続き。

　木探索がそもそもどういうものであるかと考えると、状態をノード、行動をエッジとして構築されるグラフ上を遷移しつつ、ノード上の価値を更新していく作業だと思われる。モンテカルロ木探索の選択ステップに「一個親のノードへ戻る」という選択肢を加えれば、理論上は木の自由な遷移ができるので、たとえば以下のようなことができる。

　ステップ1

　ステップ2

　ステップ3

　ステップ4

　結局各ステップで解きたい問題は「木の遷移履歴が与えられるので、現ノードを適切に評価し次に遷移するエッジを決定する問題」としてまとめられそうだ。ここで、木の遷移履歴は状態を訪問順に並べた単なる時系列入力として扱える。（無茶かなぁ……）。状態の分散表現取得や、状態価値の評価にはAlphaZero的なモデルの分岐直前までの部分などを使うとして、次のようなやり方を今のところ想定している。

f:id:tokumini:20200704173449p:plain

　木のような句構造を持つことが多い自然言語文の処理ができることから、LSTMなどには時系列入力から木構造的なものを読み取る力があることが示唆される。

　なので多少はこういう無茶なことをやっても効果があるのではないかという気はする。少なくとも探索なしよりは強くなるんじゃないかと願望込みで。いや、実際のところはあまり上手くいく気はしないが……。とりあえず致命的な勘違いがなければこの方針で実装をしてみる予定。

　あれ、しかしこれどうやって学習させるんだ？ 学習方法の問題を完全に見落としていた。各ステップで取るべき正解はわからないのでラベルは作れなくて、方策勾配法すら適用できない気はする。MCTSnetと同じトリックを使えばなんとかなる？ ちゃんとMCTSnetの論文を読み返してみないとな……。

　というところまで。

Differentiable Neural Computersの実装

探索系NN

で書いた通り、ワーキングメモリモジュールを持つ探索マネージャについて考えている。

　ワーキングメモリモジュールとしては

あたりが可能性ありそうなのかなと思うところ。調べているとLSTMに木構造的なものを導入する研究もある1,2。

　とりあえず今回はDifferentiable Neural Computer(DNC)を実装してみて、単純なタスクで上手くいくのかどうかを確かめてみた。

実装

　DNCの実装では、コントローラ部分にもLSTMを使うようではあったが、LSTMを使ってしまうと以降の部分が間違っていてもそこで学習できてしまう可能性を危惧してとりあえず普通の全結合層とした。

実験

　やったタスク : 10種類の記号(1~10)の系列をOnehotベクトルとして入力し、それらとは別の「入力終了」を示す記号(-1)が入ってきたタイミングから、それまでの入力と全く同じ記号系列を出力する。-1以降の入力は0(Onehotベクトルとしてもどの要素も経っていない0)。

例

入力: 3,4,1,2,-1,0,0,0
正答: X,X,X,X,3,4,1,2(Xは何でも良い)

　系列長は4から7まで一様ランダムに生成。記号も1~10でランダムに生成。長さが揃ってないというのもあってバッチ学習とかはせず1系列ごとに学習。

実験結果

f:id:tokumini:20200701115259p:plain

　DNCの方もなんだか学習出来ている気配はあるが、非常に不安定でなにか実装ミスがあるのではないかと疑いたくなるところ。

　いろいろ考えているうちに実はメモリモジュールにこだわる必要がなく、ただの時系列モデルを使えれば良いのではないかと思えてきたところもあるので、とりあえずLSTMで上手くいくかを試してみることを優先するのが次の工程か。