Kerasによる深層強化学習(DQN)
最近はDeep Learningのモデルを書くときは大体Kerasを使っています。理由は
- Outputの次元を定義するだけで書ける
- Layer型のDNNライブラリでめんどくさそうなRNNやLSTMなどは標準で入ってる
- 学習が簡単(ミニバッチの生成などを余り考えなくてもかける)
- BackendがTensorflow
などです。Kerasを知らない人はこちら。
Tensorflow自体はDNNのライブラリというよりも行列演算と誤差のバックプロパゲーションのライブラリというのが正しいので、実際に使うと若干冗長になってしまいます。ただ逆に言えば、論文にしかないような最新のモデルなんかを書く時でも対応できる柔軟性があるとも言います。しかし私が書くのはそういう最新のモデルというよりは古典的なCNNとかAuto EncoderがメインですのでこういうKerasは大変助かるわけです。
さて、タイトルに有るDQNについて、Keras自体はサポートしてないもののKeras対応のDQNライブラリで使いやすい物がありましたのでご紹介します。
使い方は簡単で、Kerasインストール後、「pip install keras-rl」とやるだけ。
さらに「pip install h5py」でHDF5形式のファイルのアクセスライブラリを入れてから以下のスクリプトを実行すると、Open AI Gymの一つでDQNによる学習ができるようなデモが実行できます。
keras-rl/dqn_cartpole.py at master · matthiasplappert/keras-rl · GitHub
DQN自体は本来は24時間ぐらい学習させないとあまり進化しないので微妙なところですが、可視化の画面もついてるので結構わかりやすいかと。
そもそもDQNとはなんぞやという人は、まず強化学習の一つであるQ学習について一通り見たあとにDeepMindで配っている論文を見るとよいです。要はQ学習のQ関数としてDeep Learningを使用したものになります。
第１６回日本情報オリンピック 予選 E - 尾根 (Ridge)
H*Wの高度マップが与えられる。水をあるマスに流すと、低い高度で隣接するマスに流れ、自マスからは水が消滅する。そのようなマスが2個以上隣接してる場合は、そのようなマス全てに水が流れる。周りがすべて自マスより高い高度の場合はそのマスに水がたまり、それ以上他に流れない。水を流したときに、最終的に2マス以上に水が貯まるマスを尾根と定義するときに、尾根は何個あるか？
2次元dp。マスをナンバリングし、マスごとに最終的に1個に流れるならばそのマスの番号(>0)、2個に流れるならば-1としてあるマスからdfsで状態を埋めていく。最初に流すマスを(1, 1)から(H, W)まですべて計算しても、dpテーブルは使いまわして良いので計算量はO(HW)になる。
第１６回日本情報オリンピック 予選 D - ぬいぐるみの整理 (Plush Toys)
M種のぬいぐるみをN個並べる。N個の中から一斉に幾つか取り出し、順番を変えて元に戻した時同一種類のぬいぐるみは全部隣り合う用に並べたい(11112222223333 のように) 取り出す数の最小値を求めよ。
Mが20程度なのでBitDPを疑う。M種の中からK種を選び、そのK種が左から順番に並んでいる状況を考えると、これはK-1種(これはK通り)を順番に並べた時からもう一種追加した、という遷移に等しい。このようなdpで取り出すぬいぐるみの数の最小値を計算する。
左のlからrにかけてある1種のぬいぐるみを並べるときに取り上げなくてはならないぬいぐるみの数は累積和などをあらかじめ計算しておくことでO(1)で計算可能。よってdpの遷移はO(M)で行える。総計算量はO(2^M * M)。
ちなみにdpでやる方法は難しい(ビットがk個立ってるという順列を作る方法が難しい)のでメモ化再帰でもいいかもしれない。
追記
こういうbit DPを組むときは一つ前を考えるのではなく、一つあとを考えると良いらしい。つまりdp[s] = ～～～ではなく、dp[s | (1 <<i)] = Math.min(dp[s | 1(<<i)], dp[s] + x)のように遷移させると、0～1<<M までの遷移が順番に並ぶ。これは覚えておきたい。
ARC074 F - Lotus Leaves
2次元マップ上の複数の場所oとスタートとゴールが与えられる。が与えられる。x軸またはy軸が等しい場所o及びスタート、ゴールはワープすることができる。このとき、スタートからゴールにたどり着けなくするためにoを取り除きたい(スタートとゴールは取り除けない)。取り除くoの数の最小値はいくつか。全部取り除いてもたどり着けてしまう場合は-1を出力せよ。
取り除く最小値なので、互いに行き来できるo及びスタート、ゴールにエッジをつなぐことで何らかのグラフを構成し、最小カットという方針がうかぶ。
ただし、例えばoをノードにして同じ行や列にあるノードをクリークにする、という方針では最小カットで考えにくい(最小カットはあくまでもエッジをカットするということであり、ノードの除去はこの方針に対応しない。
そこで、[1, ... , H]及び[1, ..., W]という列及び行という(H+W)要素をノードとして、o間の移動はこの要素を経由して移動するという考え方をする。すると、これらのノード間に対して、oをエッジだと思いグラフを構成すると、辺のコスト1とした時の最小カットの数が答えになる。辺の貼り方は両方向、スタート・ゴールのみ一方通行とすればよい。O(HW)。
ARC074 E - RGB Sequence
(l[i], r[i], x[i])の組がM個与えられる。Nマスを赤 緑 青で塗り分ける時、[l[i], r[i]]の範囲はx[i]色になるという制限を課す。塗り分け方は何通りか。
何通りか、なのでdpで考える。
n番目まで色を塗って、一番最後に塗った色と初めて異なる色が塗られたところがp, もう一つ異なる色が塗られた場所がq(つまりp>q)とするとき、dp[n][p][q] 通りの塗り分け方があったとする。これについて次の色を塗った時 dp[n+1][p][q], dp[n+1][n][p], dp[n+1][n][q] の三通りの遷移が存在する。特に色数の制限がないときは単純に配るdpをすればよい。n番目まで色を塗った時、[l[i], r[i]=n] が x[i]色という制限があったとする。このとき、上の3通りのうち、pやqとl, rの大小関係でその範囲内にある色数が決定するので、その範囲を満たさない場合は遷移が出来ない(配るdpができない)
これを繰り返した後、dp[N][i][j]のうち、i、jを動かした総和が答え。O(N^3)。
注意点としてdp[N+1][N+1][N+1]をやると空間計算量もO(N^3)になるが、これは3000万ほどの配列であり、JavaだとMLEになる。(おそらくC++なら大丈夫なのだろうが)
そこで、dp[2][N+1][N+1]で計算する。
また、n=r[i]の制限を発見するために線形探索は絶対にしてはいけない。ハッシュでも良いが、処理計算量1000万ほどであるため、かなり高速にしておく必要がある。
ARC074 D - 3N Numbers
長さ3Nの数列a[i]が与えられる。この中から2N個を選び「前半N個の総和 - 後半N個の総和」を最大化せよ。
前半N要素が全て入っている範囲を[0, k), 後半N要素が全て入っている範囲を[k, N)として、N<=k<N*2 の範囲で最大値を求めればよい。ナイーブにやるには毎回ソートして前半であれば最大値からN番目までの和を求めれば良いが、これでは計算量がO(N^2)なので間に合わない。
そこで、PriorityQueueを使ってある時点kでの総和の最大値から、k+1での総和の最大値をO(logN)で計算する。具体的にはa[k]をQueueに追加し、最小値minを取り出す。するとdp[k + 1] = dp[k] - min + a[k] となる。これを前半後半両方で2個dpすると、その差の最大値が答え。O(N logN)。
「インドのプログラマーでちゃんと自動コンパイルできるコードを書いているのは36％」の意味
「自動コンパイル」という謎の造語が出てきて、コメント等をみてもいまいち記事が正確に伝わってない気がします(Gigazineの翻訳の問題かもしれませんが…)。英語の原文だと「Compilable」とかになっていましたが、これはオンラインのコーディングチェックとか競技プログラミングをやったことある人じゃないとかなり伝わりにくい内容に見えました。
これはざっといえばAtCoderやPaizaなどのオンラインのコーディングチェックのような問題を2問出して、Submitできてかつコンパイルエラーにならなかった人が36％しかいなかった、という意味になります。以下で詳しく説明します。
まず、オンラインのコーディングチェックというのは通常次のような形式で問題が提出されます。
入力A(1<=A<=1,000,000,000,000)に対して、A+1を標準出力に出力するようなプログラムのソースコードを提出せよ。実行時間は2秒以内とする。入力はすべて標準入力からなされる。
注意すべきところは 提出すべきものはA+1はなく、実行バイナリでもなく、ソースコードであるという点です。これを提出すると次のような作業が始まります。
この時、1番でコンパイルエラーにならなかった人が全体の36％というのがこの記事の言いたいことです(少なくともそう読み取れました)。
さて、ここまで書くとそもそもコンパイルできないソースしか書けない人なんているのか？という話はあるのですが、実はこれ思っているよりも結構難しいです。
例えばソースコード提出時に言語を選ぶのですが、この言語を間違って選択してしまった場合や、提出するコードにゴミが混じってしまっていた、認められてない(サーバ側にインストールされていない)ライブラリを使ってしまっていた、gccのバージョンが違っていた、Javaであればパッケージを分けてしまっていた、などの可能性が考えられます。
また、問題が難しくてそもそもどういうコードを書けばいいかわからなかったというのもあるでしょう。(上の例ではそんなことありませんが、難易度の高い問題だと結構あります)
原文のレポートはこちらにあるのですが、さらに3.が終わってすべてのテストケースに通った人は全体の2.21％だったそうです。
また、このシステムの目的として更にテストケースに通った人の中でメンテ可能なコードを書ける人、効率的なコードを書ける人の割合を示しており、いずれの要素も満たすプログラマは2.21％の中の更に6割ぐらいしかいなかった、と書いてありました。
