ELF OpenGo: An Analysis and Open Reimplementation of AlphaZeroを読んだ際のメモ

論文

出典

　International Conference on Machine Learning 2019に採択。arXivには2月ごろに投稿されていたので以前もちらっと読んだことはあったが、一応再確認。

概要

　AlphaZeroのオープンソースによる再実験を行い、学習や推論における挙動について分析

詳細

実験設定

  • 自己対局中は常に温度1(つまり探索回数に比例した確率で行動を選択)
    • Miacisでもこうしている。理論的な正当化に必要な気がしたのでこうしているが、実際終盤の精度がどうなっているのかは未確認
  • c_{puct} = 1.5 (arXiv版AlphaZeroの定式化を利用)
    • 手元で\logを使うScience版AlphaZeroの定式化は試してみたが、あまり性能向上が見られないので大差ないのかなという印象
  • リプレイバッファサイズ 500,000ゲーム
    • 囲碁の平均手数を200手くらいとすると約20Mデータとなるか。Miacisでは1Mにしているのだが、小さすぎるかもしれない
  • 自己対局中は1,600探索
    • 単純に2倍の計算資源(あるいは時間)が必要になるのでここを増やすのはきつい
  • 256フィルタ, 20ブロック
    • 本当にこんなに巨大なネットワークを使う必要があるのかなというのは疑問なのだが
  • 学習率は0.01から始めて0.5Mステップ経過ごとに1/10(全学習ステップは1.5M)
    • AlphaZeroも学習率0.2から始めているとあるけど、実は囲碁では0ステップ後に学習率を1/10するとあるから0.02スタートではある(Science版)。チェス、将棋だと10倍も大きい学習率で始めて良いというのが直感的には納得し難いが、そういうものなのかもしれない
  • バッチサイズは2048
    • AlphaZeroに比べて1/2だがステップ数を2倍にしているのでほぼ同等の学習になっているのだろう
  • ステップあたりの生成量と学習ミニバッチサイズの比は約13:1
    • Miacisでは1:4くらいでやっている。ここがかなり効いてくるのかもしれないとは思う

学習推移の分析

性能

f:id:tokumini:20190711134123p:plain

  • (a)最初の方にValue損失が0に近くなっている
    • Valueの評価が偏ってどちらかが勝つデータしかなくなるため
    • 先手が勝つデータと後手が勝つデータの割合を一定にすることで解決
    • 将棋では起こりにくいことかもしれない
  • (b)対戦相手を固定した場合の勝率推移
    • 結構分散が大きく、学習率を小さくしても分散は小さくならない
  • (c)プロ棋士の棋譜との一致率はすぐ飽和するので当てにならない
学習の段階性とシチョウの学習

f:id:tokumini:20190711134228p:plain

  • (a)(b)終盤の方から徐々に学習が進んでいくという仮説に対してやや否定的な結果
    • 中盤と終盤で学習速度はあまり変わらず、序盤も過学習のせいらしい(ここはよくわからなかった)
  • (c)シチョウの予測(盤面全体に関わり手数が多いため難しい)は学習後半のモデルでも不十分
    • 探索回数を増やしても改善しきらない

パラメータ探索実験

c_{puct}

f:id:tokumini:20190711134535p:plain

  • 1.5が良さそう
バーチャルロス

f:id:tokumini:20190711134614p:plain

  • 1が良さそう
探索回数による性能の変化

f:id:tokumini:20190711134654p:plain

  • 持ち時間を2倍にしたときの性能の上がり方が先後で異なる
  • ベースの探索回数を増やすと先手は2倍にしても勝率が上がらなくなる
    • これは囲碁特有の問題かと思わないでもないが
  • プロトタイプとの対局によると基本的に探索回数2倍でEloレート+200
    • ここもゲームに依存する性質かもしれない

Discussion

　AlphaZero型学習の問題点など

  • 学習に必要な対局数が膨大
  • シチョウが学習できていない
  • 性能が不安定
    • 学習率を下げるとむしろさらに不安定に→ほとんど変わらないモデルによる同じような対局ばかりになってリプレイバッファ内に多様性がなくなることが問題？
  • 終盤から徐々に学習されていくわけではなさそう

所感

　AlphaZeroの学習はとにかく膨大な量を必要とする点が実験していく上で非常につらいので、何はともあれ高速化をしなければ話にならないという気持ちが強い。その点で終盤から徐々に学習されるわけではなさそうという指摘は大きいものなんじゃないかと感じられる。手元での学習推移や学習途中のパラメータにおける指し手の傾向を見ても、どちらかといえばPolicyの偏りが原因で(強化学習の意味での)探索が上手く進んでいない可能性はありそうに思える。ディリクレノイズによるランダム性の与え方をもう少し工夫できないかなと考えたいところだが、探索を促進する内発的動機づけとかそちらの論文を読んでみるのが良いのだろうか。

AtCoder Beginner Contest 133

競技プログラミング

結果

　E問題までの5完で157位。パフォーマンス2118でレーティングは1854 → 1883 (+29)。F問題が難しい(というか重実装だった)影響でEまで早く解けていればそこそこな順位になった。始まる前から疲れていて不安だったがなんとかなってくれて良かった。

A問題

　そうですね。

　提出

B問題

　根号取ったものが整数になるか判定するところでやや悩み、結局普通に2乗が超えるまでループで回してみて一致する整数があるか判定した。計算量は確かめてないけど小さめだったからなんとかなるだろうという勘。解説PDFを見るにそれで良かったようだ。

　提出

C問題

　R - Lが2019より大きいかどうかで場合分け。小さい場合にループ中で普通に掛け算してから剰余計算してしまったがL,Rが大きいとまずいので制約に救われた。手癖で全ての整数型をll(int64_t)で確保するという脳死ムーブが強すぎるのでメモリ量で痛い目を見たい。

　提出

D問題

　適切にぐちゃぐちゃやっていけばなんやかんや式が立ちそうだなとは思ったが全然上手くやれなくて呆れながら解いていた。山1の右半分へ流れる量を変数においてヒュッとやるのが最終的にはわかりやすかったか。

　提出

E問題

　わりと何も考えず再帰関数の中でダメな条件を順番に弾いていくとなんとかなった。これが早く解けたのが順位的には大きかったけどよくわからないままに通ったという感じでやや釈然としない。

　どうでもいいことだけど、エッジを辿る場面では次のノードをnextと命名することが多いんだけど普通にstd::nextが存在するのでやめたほうが良さそうだなとAtCoderのシンタックスハイライトを見ていて思った。

　提出

F問題

　パッと見で最小共通祖先を使うんじゃないかなという感じで、考えていくとなかなか惜しいところまではいく。しかし各色について各ノードまでに辺が何本あるかを保持するとO(N^2)になるのでいやー難しいと思っているうちに時間が経ってしまった。このあたり疲労感が強くて椅子に座っていられず寝転がって(つまり紙とペンを使わず)考えていたもの響いたか。

　必要な情報をメモしておいてDFSしながら答えていけばなんとかなるかもしれないとは思ったけど実装が非常にやばいことになりそうで手を付けるか迷っているうちに残り20分くらいになる。そこから書き出したが時間切れで終了。

　解説PDFを見て結構方針としては合ってそうだった。ほぼ想定した書き方をしてACする。AtCoderで150行近く書くのやば。

　日頃変数はmainスコープの中で書き始めるので再帰関数を外に書こうとすると変数をグローバルに置き直す作業が必要になったりするのがちょっと嫌。なので最近は単純なDFSならstd::stackを使って書いているんだけど、色情報を一つ持って更新しながらやっていくには再帰関数で書く方法しか思い浮かばかなかった。main関数の中にラムダで書いてみたけど、これもどうだろうか。

　最小共通祖先はこれで検索して一番最初に出てきたページをほぼそのまま写経した。原理は全然わかってない。ライブラリを整備する元気もあまり出ず。マクロとかスニペットとか自動サンプルチェックとか、そういうのも入れた方が良いんだろうなとは思いつつ、しかし最近はむしろusing ll = int64_t;すら消したいよなという気分にすらなっていて……。

　提出

思考時間とレートの関係

コンピュータ将棋

要約

　Miacisではおおむね思考時間を2倍でレート+100となる。MCTSのスケール性もαβ探索と比べてあまり変わらないのではないか。

背景

　AlphaZeroの論文(arXiv版)には1手の思考時間とレートの関係が図で表されている(Figure 2)。以下に将棋の方だけを切り抜いたものを示す。このAlphaZeroは40,000NPSほどのものであり、基準としているソフトはelmo(1手の思考時間40msec)である。

f:id:tokumini:20190626181852p:plain

　uuunuuun氏はこの図から思考時間を10倍にするとレートが800伸びるという関係を読み取っている。対局数は少ないが実験も行われている。

　またAlphaZeroの論文(Science版)では、1手の思考時間固定ではないが、思考時間を対戦相手に比べて短くした際の勝率が棒グラフで示されている(Fig. 2B)。これは58,000NPSでの結果と書かれている(Table S4)。

f:id:tokumini:20190626172925p:plain

　将棋についてこの棒グラフの幅から勝率を読み取ってレート推移を作ったものが以下のグラフになる。

f:id:tokumini:20190626183451p:plain

　こちらでは、特に比が1/3以上の領域において、思考時間10倍でレート+160ほどとなっている。あまり伸びが良くないように思われる。

　Science版の方では比が1のとき、持ち時間3時間+1手ごとに15秒追加なのでもともと持ち時間は多めである。1手の思考時間として残り時間の1/20を使うとあったため、次のような思考時間になっている。

f:id:tokumini:20190701095624p:plain

　1/100の持ち時間でも序盤は1手数秒あり、NPS自体も上がっていることを考えると、冒頭のarXiv版論文で示されたグラフの右側にやや重なるような位置関係なのではないかと思われる。

　elmo側はエンジンで定められた持ち時間制御をそのまま用い、これは1手1秒のelmoに対して98.85%(R+773.7)だったとある(Table S5)。これらの結果から適当に縮尺を合わせて貼り付けると次のようになる(位置関係はかなり適当なのでイメージ程度に)。

f:id:tokumini:20190701145242p:plain

　もとのグラフがどのように計算して出されていたものかわからないが、スケール性に関してはやや怪しく、特に持ち時間が長くなるとそこまで伸びないのではないかと思われる。実際にarXiv版ではMCTSがαβ探索に比べて持ち時間に対するスケール性が良いのではないかという主張があったが、Science版では(私が確認した限り)なされていない。

　このような事実を念頭に置いて、自作の将棋ソフトについても思考時間とレートの関係を推定した。

実験

　前回得られたパラメータを用いて技巧2(深さ制限9, 10)と持ち時間を0.25秒、0.5秒、1秒、2秒の4種類についてそれぞれ500局対局を行った。http://www.uuunuuun.com/englishから技巧2(深さ制限9,10)のレートをそれぞれ2663, 2808として推定されたレートを次に示す。

f:id:tokumini:20190701100814p:plain

　大雑把に見積もって思考時間2倍でレート+100という結果となった。

所感

　αβ探索でも異なるソフトに対しては思考時間2倍でレート+100とある。

　C_{PUCT}など調整が不足している可能性はあるだろうが、MCTSでもαβ探索でもスケール性に関しては大差ないのではないかというのが現状の推察となる。

AtCoder Beginner Contest 132

競技プログラミング

結果

　E問題までの5完で365位。変な勘違いばかりして解くのが遅く、全然ダメだった。

A問題

　すっきりとしたやり方がわからなくて結局std::mapに各文字の出現回数を詰め込むというオーバーキル気味なことをやった。解説PDFにあるソートして比較が一番スマートなのかな。

　提出

B問題

　いつも開始直後は問題の読み込みが遅くて、B問題から解き始めれば回避できるのかなと思ってこちらから解き始めたがあまり違いはなかったか。

　提出

C問題

　ソートして切れ目を考えるだけ。ちゃんと考えを詰めきってから短いコードを書くようにできたのでそこは良かったと思う。ここまではそこそこ順調だったんだけど……。

　提出

D問題

　「同じ色のボールは区別が不可能」という文字を目は認識していたのに脳は認識してくれなくてずっと区別できる状態での解法を考えていた。区別できる状態での解法をひねり出すのにも時間がかかり、実装したら全然サンプルが合わないところでようやく気付いてまた考え直してということでひどかった。こんなのコンビネーション計算するだけなのに時間をかけてしまい、順位がめちゃくちゃ悪くて冷や汗が出始める。

　提出

E問題

　まず有向グラフだということに気づいていなくて時間がかかり、その後もその混乱を引きずって隣接にはコスト1で行けると思い込んだままよくわからない解法を考え続けていた。残り27分くらいのタイミングで一度落ち着こうと思って問題文を眺めなおすと頂点を拡張するいつものダイクストラということがわかってようやく解けた。これがすぐ見えないのは完全に練習不足。提出時点でE問題を解いている人の数がめちゃくちゃ多くて冷えていたけど、ノーペナだったおかげか意外と順位はひどいことにならなくて軽傷で済んだのは良かった。

　提出

F問題

　O(NK)のDPを書いてじっと睨んでいたが残り10分ちょいでは全然見えてこなくて終了。解説PDFを読んで、まぁそれはそうだと思ったけどこれを本番中に思いつける気がしない。実装も難しくて割った数でまとめる際にその数に何個なるかを事前計算しておかないと扱いきれない抽象度だった。難しい。

　提出

長時間学習の結果/選手権以降にやったことのまとめ

コンピュータ将棋

要約

　2週間弱かけて1Mステップの学習を行ったところレート2600程度になった。パラメータとWindows向けバイナリはGitHubで公開している。

背景

　第29回世界コンピュータ将棋選手権以降、一通り試したいことはやったのでここで一度長時間の学習を行った。選手権時からの改良点をまとめると以下のようになる。

　雑に見積もってレートは+770となる。選手権時点では技巧2(深さ2)に対して勝率71%、レートにして1946.5だったので、だいたいR2700程度になると予想した。

実験設定

　ランダムに初期化したパラメータから1Mステップの強化学習を行った。

学習

項目 値
バッチサイズ 128
学習率 0.015(固定)
オプティマイザ Momentum(0.9)
TD(\lambda)の\lambda 0.75
優先度付き経験再生の\alpha 2.0
引き分けとする手数 512
学習スレッドのスリープ時間 1ステップごとに1秒
リプレイバッファサイズ 2^{20}
1局面あたりの探索回数 800
C_{PUCT} 2.5
Residualブロック内のCNNのチャンネル数 64
Residualブロックの数 10

　学習に使用したマシンはGTX1080を2枚搭載したものであり、データ生成速度は33.8 pos / secであった。スリープ時間が1秒、バッチサイズが128なので、1ステップあたりに生成する量に対してバッチサイズが4倍ほどであり学習データの重複は多めだと思われる。

検証損失

　floodgateの2016年の棋譜からレート2800以上同士の対局のみを抽出し、そこからランダムにサンプリングした409600局面についてPolicyとValueの損失を計算した。Policy損失の計算では棋譜上で指された手を教師信号とし、Value損失の計算では最終結果を教師信号とした。

検証対局

　100Kステップごとに得られたパラメータを用いて深さを制限した技巧2(定跡オフ)とそれぞれ500局の対局を行った。検証対局で使用したマシンはRTX2080tiを1枚搭載したものであり、探索速度は初期局面で10K NPSほどになる。Miacis側の持ち時間は0.25秒とした。対局は256手で引き分けとし、引き分けは0.5勝0.5敗として勝率を計算した。

実験結果

　学習にかかった時間は約302時間(2週間弱)であった。

検証損失

f:id:tokumini:20190625132252p:plain

　予想できていたことだが、1Mステップでもまだ収束しきっていないように見える。以前実験した通りバッチサイズと学習速度はほぼ比例するため、バッチサイズ4096で700KステップのAlphaZeroと同等の学習をするには、バッチサイズ128にした場合22.4Mステップが必要になる。AlphaZeroとは手法やモデルの大きさが違うことやそもそもAlphaZeroも後半350Kステップはほぼレートが伸びていないことを考えれば、この半分から1/4程度で許してもらえないかと考えたいところだが、それにしても5Mステップくらいは回し続けないといけないかもしれない。学習率の減衰をどう入れるかも悩ましいところである。

検証対局

　100Kから500Kステップまでは深さ4~6, 500Kステップ以降は加えて深さ7とした技巧2と対局を行った。図中で示す技巧2のレートはhttp://www.uuunuuun.com/englishに記載されているものとなる。

f:id:tokumini:20190626114658p:plain

　損失推移同様、まだ収束しきっている様子ではない。小さいネットワークを使っているのでそこまで伸びないとは思うがもっと長時間学習させてみた方が良さそうだ。

　本来はどの深さ制限の技巧で測っても全く同じEloレーティングが得られることが理想なのだが、実際には相性の問題や計測誤差があるため完全には一致しない。特に深さ4に対しては500K時点で勝率が90%を超えているため、信用度の低い測定になっているかもしれない。

　平均値では1Mステップ時点でR2618.1となる。深さ4に対しての計測で高めに出ていることを割り引いて考えて、だいたい2600といったところだろうか。予想してた2700よりはやや低いが、かなり雑に見積もっていたことからすればむしろ驚くくらいの伸びではある。

　気になる点としては、700Kステップ時点で一度レートが落ちていることと、900Kステップ時点で深さ6に対してだけ相性が悪いことがある。対局を見ていたところ、やや指し手に偏りがあり同じような戦型ばかりになっているのではないかと感じた。先日山岡さんが指摘していたように、データ生成時にルート局面以外のノードについて探索情報を再利用していることが影響している可能性もある。

AtCoder Beginner Contest 131

競技プログラミング

結果

　E問題までの5完。

内容 値
順位 292nd / 5123
パフォーマンス 1869
レーティング 1861 → 1862 (+1)

A問題

　特になし。

　提出

B問題

　脳みそを使いたくなかったので問題文の通りまず総和を計算して各iに対して絶対値の差が小さくなるものと探索してそれを出力するということを愚直にやった。絶対値が一番小さいものを選ぶのが最適とかそういうことでできるのはそうだろうけどそこで時間かけるのとどっちが速く解けたかは微妙なところか。

　提出

C問題

　問題を細かく分解していく感じが楽しくて妙にコメントを丁寧に書いてしまった。閉区間で実装してしまったのが少し微妙だったか。

　提出

D問題

　リアルタイムシステムの講義でEarliest Deadline First(EDF)というやつをやったなぁというのを思い出しながら解いた。

　提出

E問題

　最初は全てのノードを一列に並べた状態からなんとかできないかとか考えていたけどどうにもならず。スター型のグラフが最大になるっぽいことに気づいて、そこから減らしていく方針が思いついてからはすぐだった。

　提出

F問題

　方針としては間違ってなかったと思う。最終的に点が置かれる位置の数を列挙して、そこから最初のN個を引く。ただ最終的に点が置かれる位置の数を列挙する部分が上手くできなかった。概ね共通するグループのXの数×Yの数で出すというところも間違ってはいなかったんだけど……。各yに属するxの集合を取って、そのxに属するyの集合の和を取るということで集合のマージテクを使う方針でやっていたがWAもTLEも出るので全然ダメだった。

　解説PDFを読んで普通にDFSするだけと把握してAC。言われてみればそれはそうなのに思いつかない不思議。

　提出

Learning Action Representations for Reinforcement Learningを読んだ際のメモ

論文

出典

　International Conference on Machine Learning 2019に採択

読んだ理由

　前回に続いて行動の表現を学習する手法についてのものがICMLにあった。特に昨日の論文が行動ログから事前学習という形のものだったのに対して、より強化学習の学習ステップに明示的に組み込まれているようだったので読んでみた。

概要

　行動決定を(1)行動表現空間への方策計算(2)サンプリングされた表現から行動への復元 という2ステップに分ける手法を提案。行動空間が大きい場合に対する強化学習で性能が向上する。普通の方策勾配法に組み込むことができるので汎用的に適用できる。

詳細

　全体としての方策を\pi_o、表現部分への確率分布を示す方策を\pi_iとして、行動を次のように2段階で決定する。

f:id:tokumini:20190614185200p:plain

　式としては次のように行動決定する。

$$ E_t \sim \pi_i(\cdot|S_t), \qquad A_t = f(E_t) $$

\pi_iを固定した際のfの学習方法

　まず前提として二つの連続した状態が与えられた際の行動推定は、行動の表現を介して次のように表せる。

$$ P(A_t | S_t, S_{t + 1}) = \int_{\varepsilon} P(A_t|E_t = e)P(E_t=e|S_t, S_{t+1}) \mathrm{d}e $$

　右辺の二つの要素をそれぞれ\hat{f},\hat{g}としてパラメータを持つ関数で近似することを考える。\hat{f}はそのまま表現から実際の行動への復号関数fの推定として推論時にも用いるが、\hat{g}は\hat{f}を学習するためだけに用いるものとなる。推定値は次のようになる。(以下式番号は論文中のものと揃えた)

$$ \hat{P}(A_t | S_t, S_{t + 1}) = \int_{\varepsilon} \hat{f}(A_t|E_t = e)\hat{g}(E_t=e|S_t, S_{t+1}) \mathrm{d}e \tag{3} $$

　これらの式をカルバックライブラー情報量で評価する。

$$ D_{KL}\left(P(A_t | S_t, S_{t + 1}) || \hat{P}(A_t | S_t, S_{t + 1})\right) = -\ln \mathbb{E} \left[ \left(\frac{\hat{P}(A_t | S_t, S_{t + 1})}{P(A_t | S_t, S_{t + 1})} \right) \right] \tag{4} $$

　この式の最小化を考えると、分母は定数なので関係なくなる。結局得られた遷移の3つ組(S_t, A_t, S_{t + 1})について損失関数は次のようにすれば良い。

$$ \mathcal{L}(\hat{f}, \hat{g}) = -\mathbb{E}\left[ \ln\left(\hat{P}(A_t | S_t, S_{t + 1}) \right) \right] \tag{5} $$

　報酬は関係しないので遷移からそのまま教師あり学習を行うだけとなる。

　(付録D)実際には表現eについての積分にかかる計算量を抑えるため、積分を取り払って

$$ \hat{P}(A_t | S_t, S_{t + 1}) \approx \hat{f}\left(A_t | \hat{g}(S_t, S_{t+1}) \right) $$

として近似する(これはどの程度正当性があるのだろうか。かなり大胆な近似をしているように思える)。\hat{f}(a|\hat{g}(s, s'))は

$$ \hat{f}(a|\hat{g}(s, s')) = \frac{\exp{\frac{z_a}{temp}}}{\sum_{a'} \exp{\frac{z_{a'}}{temp}}} , \qquad z_a = W_a^{\mathrm{T}} \hat{g}(s, s') \tag{22} $$

とする。tempは温度変数(はてなブログの数式モードではギリシャ文字のtauが表示できなくて困った)。W \in \mathbb{R}^{d_e \times |\mathcal{A}|}は各列が各行動のd_e次元の表現となる行列。W_a^{\mathrm{T}}は行動aに対応する列を抜き出して転置を取ったベクトル。つまり\hat{g}が予測する表現と今までに学習した表現の内積になっている。

fを固定した際の\pi_iの学習方法

　単純に方策勾配法を用いて学習する。特に全体方策\pi_oではなく内部方策\pi_iに対するパフォーマンス関数の微分で方策勾配法を考えればよい。復号関数fが確定的な関数ならば $$ \frac{\partial J_o(\theta, f)}{\partial \theta} = \frac{J_i(\theta)}{\partial \theta} $$ となるためである(証明は付録B)。これによりf^{-1}を計算する必要はなく、内部方策\pi_iに対する状態価値関数v^{\pi_i}(s)を考えてパフォーマンス関数 $$J_i(\theta) = \sum_{s\in\mathcal{S}} d_{0}(s) v^{\pi_i}(s) $$ に対する微分を考えれば良くなる。(付録D)内部方策\pi_iとして実験ではガウス分布を仮定してその期待値を近似するようなニューラネットワークを学習させた。

同時学習

　以上の結果から次のようなアルゴリズムで学習を行えば同時に学習していくことができる。

f:id:tokumini:20190614171905p:plain

　1行目の部分では、最初にランダム方策による行動から行動表現部分だけを多少学習させる。

実験

迷路タスク

f:id:tokumini:20190614182615p:plain

　星がゴールの位置。n方向に独立なアクチュエータがあり、可能な行動としては全部で2^n通りになる。

実験結果

f:id:tokumini:20190614182650p:plain

　普通のActor-Criticと比較して、nが大きいほど提案手法を入れた場合に性能が伸びやすい。つまり行動が多い場合に有効。

得られた表現

f:id:tokumini:20190614183457p:plain

　左の図はデカルト座標における各行動の遷移先であり、右は表現空間での各行動の座標。左右で同じ行動には同じ色が与えられている。つまり右の図で近い色は近い場所に集まっていることから、同じような行動をまとめることができていると思われる。また特定の方向で最大限移動するような方策がそれぞれ縁にあって区別しやすいように表現が学習できている(？)。

現実世界の推薦システム

　ビデオチュートリアルの推薦とマルチメディア編集ソフトの推薦。ユーザの使用履歴・満足度からMDP環境を作り、そこにおける報酬を最大化するタスク。前者は1498個、後者は1843個の行動(選択肢)が存在。

f:id:tokumini:20190614183645p:plain

　提案手法を入れた方が性能が良く、学習も速い。

所感

  • 言われてみれば自然なやり方に思えるが、実際のところ近似が上手くいくのかどうかが怪しいと感じるところもないわけではない
  • 特に内部方策はガウス分布で近似されており、多次元空間の確率分布はモデル化が難しそうだがもう少し表現力が高そうなものを用いたい気もする
  • 自分の将棋プログラムでは9 \times 9 \times 27 = 2187種類の行動から選択するように実装しているため、だいたい同じくらいの行動の量で性能が上がるなら試してみる価値はありそう。AlphaZero形式の方策学習が方策勾配法とどのような関係にあるのかは理解できていないが、AlphaGoなどでは明示的に方策勾配法が使われていたので応用はできるはず

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::fixとstd::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なんですか。はぁ。多分僕の解き方は正当ではない気がする。最小公倍数が大きくなるケースが怪しいのかとは思いつつ、具体的に落ちるケースを示せと言われたら無理。

　提出