Joeの精進記録

旧：競プロ練習記録

S2V-DQNコードリーディング

https://xuzijian629.hatenadiary.jp/entry/2019/07/27/154356

以前環境構築についてまとめた

今回は実装を読んでいく。

MVCについて読むが多分構造は他も一緒

構造

eps_start = 1.0
eps_end = 0.05
eps_step = 10000.0
for iter in range(int(opt['max_iter'])):
    if iter and iter % 5000 == 0:
        gen_new_graphs(opt)
    eps = eps_end + max(0., (eps_start - eps_end) * (eps_step - iter) / eps_step)
    if iter % 10 == 0:
        api.lib.PlayGame(10, ctypes.c_double(eps))

    if iter % 300 == 0:
        frac = 0.0
        for idx in range(n_valid):
            frac += api.lib.Test(idx)
        print 'iter', iter, 'eps', eps, 'average size of vc: ', frac / n_valid
        sys.stdout.flush()
        model_path = '%s/nrange_%d_%d_iter_%d.model' % (opt['save_dir'], int(opt['min_n']), int(opt['max_n']), iter)
        api.SaveModel(model_path)

    if iter % 1000 == 0:
        api.TakeSnapshot()

    api.lib.Fit()

流れはこんな感じ。もろもろの関数はmvc_lib.cppにある。

  • 5000 iterおきにグラフをgen_new_graphsをしている。内部的にはグラフのプールを更新している。プールには1000個グラフがある(main.py)
  • epsilon greedyのepsをだんだん小さくしているっぽい
  • 10 iterおきにPlayGameしている。10回最初からterminal stateまで実行して、結果の列をNStepReplayMemに格納する。毎回グラフをプールからサンプルするっぽい。
  • 1000 iterおきにSnapShotをとっている。これが実は本質っぽいんだけど、lossの計算ではこの記事の一番下に書いてあるように、Snapshotをとったold_modelと、新しいmodelでの2つの予測結果の二乗誤差を考えている
  • 毎iterでFitしている。これは、batch_sizeサンプルしてきて、nn_api.cppのFitを呼んでいる。
net->SetupTrain(batch_idxes, g_list, covered, actions, target);
net->fg.FeedForward({net->loss}, net->inputs, Phase::TRAIN);
net->fg.BackPropagate({net->loss});
net->learner->Update();

loss += net->loss->AsScalar() * bsize;

みたいなことが行われている。誤差の計算のところはmvc_lib.cppにあって

PredictWithSnapshot(sample.g_list, sample.list_s_primes, list_pred);

からの

for (int i = 0; i < cfg::batch_size; ++i)
{
    double q_rhs = 0;
    if (!sample.list_term[i])
        q_rhs = max(sample.g_list[i]->num_nodes, list_pred[i]->data());
    q_rhs += sample.list_rt[i];
    list_target[i] = q_rhs;
}

が行われている。PredictWithSnapshotは古いモデルでの予測結果っぽい。

のところ。

On the complexity of the embedding problem for hypercube related graphs

www.sciencedirect.com

説　明　が　ウ　ン　チ　ー　コ　ン　グ

writerやめろ

概要

「木 Tと、正整数 kが与えられたとき、 Tを k次元hypercubeに埋め込めるか」という判定問題はNP-Complete.

まあこれが成り立つので、 Tはより一般にグラフ Gに拡張できる。

証明がExact Cover by 3-sets (X3C)によるもので、これまたテクニカル

X3C

集合 Xの部分集合で、サイズ3のものをいくつか集めた集合 Cが与えられる(Cは集合の集合)。 Cの部分集合で、 Xのdisjointな分割になっているもの C'が存在するか(このとき C'は Xをカバーしている)

これはNP-Completeらしい。 Xの要素数が3の倍数でない場合は明らかに不可能なので3の倍数個としてよい。

帰着

X3Cインスタンスが与えられたときに、木 Tと kをうまく構築して、「木が k次元hypercubeに埋め込める」ことと「X3Cインスタンスが解をもつ」ことを同値にしたい。

f:id:xuzijian629:20191225183835p:plain

まず、カバーすべき集合を Xとしたとき、集合 S = X \cup {z}を考える。また、 k = |S|とする。

木 Tが k次元に埋め込めるかは、 Tのノードに、 Sの部分集合を割り当てたときに、

  1. 異なるノードについて異なる部分集合が割り当てられており
  2. 隣接するノードについて、部分集合のset differenceの大きさが1

であることと同値。

Tとしては上図のように構成する。上図のノード数はみやすさのため少なくなっているが、 Xは実は x_1, \ldots, x_{3q}になっており、たとえば XXは x_1x_1, \ldots, x_{3q}x_{3q}になっている。ポイントはノード数がたかだか 3q + 1 = |S|の多項式のサイズなので、X3Cのインスタンスが与えられると多項式時間で構築できることである。

図で Rの説明がものすごく雑だけど、 Rは q要素で、それぞれ XXX型の部分集合が割り当てられている。 C_4ノードが XXX\backslash Cの型を持っているので、 XXX型は C_4と Rに限られる。もし、 Tのノードに割り当てられる集合がすべて異なるなら、 R \subset Cが成り立つ。

Rと C_8の辺のつなぎ方も重要で、とりあえず Rの i番目のノードに割り当てる部分集合を x_{3i - 2}x_{3i-1}x_{3i}にしておく。これは本当はこうならないかも知れないけど、 x_kのネーミングはあとで適当にある順列によって差し替えることができるので、気にしなくていい。

とりあえずこれで構築は完了

X3Cインスタンスに解がある場合

解 C'は q要素からなるので、 Rと C_8を結ぶ辺は、 Rの j番目の要素とつながっている C_8の要素のラベルを、 C'の j番目の集合にすればいい。このとき、明らかにノードのラベルは全ノードで異なっているので、 Tは k-cubeに埋め込むことができる。

X3Cインスタンスに解がない場合

つまりどう選んでも、 C'の各要素(集合)がdisjointにならない場合。 Rが要素数が q'のtex: Cの役割を果たしているので、もし埋め込めるとしたら、そういう C'が見つかって矛盾。

The Complexity of Cubical Graphs

www.sciencedirect.com

概要

グラフ Gがcubicalであるとは、あるhypercubeが存在して、そのsubgraphとなることをいう。 Gが与えられたとき、 Gがcubicalであるか判定するのはNP-Complete

hypercube

頂点番号が 0から 2^n - 1からなり、頂点番号のbinary表現で1bitだけ異なる頂点間に辺が張られている。

証明

描画はNAE3SAT!!!で常勝！ｗと思っていたけど今回はEXACT COVERをしている。すげ絵

EXACT COVERインスタンスをcubical埋め込みオラクルによって解くことで示している。

Theorem 1

Gがcubicalであることと、 Gがproper coloringを持つことは同値

連結な {1,2}-Graphの辺彩色がevenであるとは、どの色についても偶数回現れることをいう。 Gの辺彩色がproperであるとは、 Gの部分グラフである連結な {1,2}-Graphが、サイクルである場合、そしてその場合に限りevenであることをいう。

構築

まず、いま考えているEXACT COVERの問題を整理する。

集合 Sの部分集合の族 \mathcal{F}を考え、 Sの各要素を含む \mathcal{F}の要素はちょうど3個ある。いま、 \mathcal{F}のdisjointな部分族で、 Sをちょうどカバーするものがあるかどうか調べたい。

f:id:xuzijian629:20191224172431p:plain

まず、 Sの各要素について、hexagonを作る。hexagonの上の辺同士を長方形でつなぐ。こうすると、proper coloringをもつとき、上の辺はすべて同じ色になる。

次に各 \mathcal{F}の要素について、それらに含まれる要素たちのhexagonの下3辺のうちどれか同士をladderで結ぶ。このとき、ladderの長さは、hexagonの上の長方形をたどって(上の1辺は通らない)、移動するときのコスト+2とする。これは一見複雑に見えるが、結んだ下の辺たちが同じ色になるように調整するためだけの理由。

あとは、これにproper coloringが存在するかを考えればいい。hexagonの上の辺のcolor (全部同じ)を0とすると、下3辺のうち、ちょうど1辺だけが0になりえる。0になった辺たちが、EXACT COVERに対応する。

逆にEXACT COVERが存在するときは、それに対応して割当を構築できる。

感想

これもかなり天才構築でびっくりする。研究は天才以外お断りパズル論文コンテストなのか

Neural Combinatorial Optimization with Reinforcement Learning

Euclidean TSPをやって、100頂点程度までなら最適解を出せた、という研究

この先行研究は1990年代とかでかなり古いっぽい。

入力は、2次元平面上の n点の座標で、出力は {1, 2, \ldots, n}のpermutation.

RLで、policy p(\pi | s)を学習するっぽい。

条件付き確率で分解する。

f:id:xuzijian629:20191222161236p:plain

ただし \pi ( \lt i)は先頭 i - 1個のpermutationを指す。

グラフの頂点数 nが違う場合にでも対応できるように、pointer networkというものを使っているっぽい。

とりあえずQiitaの記事があったけど、入力サイズが可変なときに対応できるらしい。

https://qiita.com/ymym3412/items/c84e6254de89c9952c55

意味不明なのでとりあえずここで終了

感想

policy based RLであることは我々の手法と同じだがさすがに時代が違いすぎてやっていることが違いすぎるのであんまり関係なさそう

結果も100頂点なのは小さすぎる

Learning Combinatorial Optimization Algorithms over Graphs

https://papers.nips.cc/paper/7214-learning-combinatorial-optimization-algorithms-over-graphs.pdf

NeurIPS 2019でもしゃべていたのでついにちゃんと読んだ

はじめに

界隈はこの論文を最強だと思っているらしい。多分グラフ機械学習で離散最適化やっている界隈は全員これを知っている。これを倒せば知名度上がりそう

先行研究との差分

この論文が先行研究としているのはこれ。

arxiv.org

まだ詳しく読んでいないが、policy gradientをtrainingに使っているらしく、それよりもDQNがいいよという流れで出てきたっぽい。 DQNはoff-policyで、experience replyができるため、policy gradientよりもsample efficientだと言っている。

トレーニング時にグラフのembeddingを更新していくのはこの研究の、先行研究に対する強みっぽい？（先行研究では最適解をembedしているらしい）

自分たちの手法との共通点・差分

共通点

action

actionは頂点のselection

reward

normalizeしていないのでまあ差分でもあるがMCTSしないので別にnormalizeしなくていい

差分

state, transition

stateの定義をグラフ、ではなく、actionで選んだ頂点の(ordered) sequenceとしている。グラフ自体は学習の中で不変。自分たちの手法だと、(少なくともMISについては)グラフをだんだん小さくしていたが、この手法だと最後に選んだ頂点に新しくラベルをつけていく遷移をするだけ。

Q-Learning

そんなに異常Q-Learningをしていなかった。

f:id:xuzijian629:20191222091348p:plain

アルゴリズム中のBatchサイズや nは解く問題によってかなり調整しているっぽい。

embedding

GNNよりも一般的なフレームワークに見える。4-hopしか見ていないのでかなり浅い。パラメータはたくさんある。自分たちのGNNだと1-dimensionalなembeddingをしていたような気がするが、とくにweightedグラフに弱すぎるし次元を増やした方がいい気がする。こちらの論文では64次元

グラフも前処理としてkNNをとっている。

感想

自分で実装し直したほうがいい気がする。仮に精度出なかったら工夫したであろうところにきづけるだろうし

Unit-Length Embedding of Binary Trees on a Square Grid

www.semanticscholar.org

を読んだ。

先行研究のミスを指摘していてワロタ。

概要

二分木をsquare gridに埋め込めるかどうかはNP-Complete

最大次数に注目すると、最大次数2のグラフはサイクルまたはパスグラフなので、埋め込みは自明に可能

最大次数を3に許容すると二分木となるが、この場合不可能であることが示されたのでギャップになっている

証明のテクは、正方形サイズの二分木で、一意な埋め込みがあるものを見つけ、あとはおなじみのlogic engineで証明する

f:id:xuzijian629:20191219170348p:plain

このグラフはU-Treeと呼ばれ、一意な埋め込みをもつっぽい。

あとは、extended skeletonをこれで置き換えて構築し（そのままでは次数４の頂点があるのでうまく置き換える）、似たようなことをやる

f:id:xuzijian629:20191219170542p:plain

これはいつものskeleton

感想

最大次数を3まで許容してしまうと二分木が許されるのがやばい。二分木は、ルートからの距離に比例してノード数が指数的に増えるが、一般の n次元グリッドは、ある点からのマンハッタン距離に対してノード数は多項式なので、明らかに任意の二分木を埋め込むことは不可能。

直感的には、どんな nに対しても、ある程度のサイズの二分木が存在して、一位に埋め込むことができそうで、あとは似たようにlogic engineを修正すれば埋め込みのNP-Completenessを示すことができそう。これはsquareグリッドに限らず、任意のパターンでおｋ

かなり汎用的なテクでびっくりしてしまう。

これ論文になるん？