卒論名言集

1年前の卒論関連のSlackを見返していたらわりと面白かったのでまとめます

ちなみに締切は2/1だったみたいです。

1/19

DDCCの装置実装部門の話で盛り上がっている

1/20

けんしん「またライブラリの闇と戦っていたら1日が終了しかけている」

1/21

（ラボ内締切というか、校正が必要なので初稿を1/24までに出してくださいみたいな話だった気がします）

1/22

ぼくがこどふぉで黄色になってやっとDiv2 & えづほから開放される

1/23

1/24

けんしんがnumpyの仕様と一日中戦っていた

1/25

1/26

1/27

けんしんがインフル新薬の耐性菌のせいで熱が続いていてまだ登校できない問題

1/28

けんしんの熱が下がる

やっと実験結果が出たらしい

じょえたぷにきあくん笑が初稿を提出する。30枚5800 words

1/29

熱は下がったけど登校できないけんしん

1/30 締切前日

やっとけんしんが登校。ほぼ大学にいたのであんまりSlackで話したことがない

2/1 締切

必死すぎてSlackの投稿が皆無。たぶんけんしんは一晩で2000 wordsぐらい生成してそう

define-by-runじゃないと困る問題

Hanjun-Daiのgraphnnがdefine-by-runじゃないせいで困った

複数グラフの、頂点ごとの確率を推論して、CrossEntropyしたい状況

• batchあたりのlossを定義するために入力は複数グラフ(ひとつずつやってlossを足すということはできない)
• グラフごとにCrossEntropyを計算したい
• グラフの最大ノード数を固定したくない
• でもsoftmaxするときに最大ノード数でreshapeしたい
• muriyarokonnnan

強化学習アルゴリズム整理

久しぶりにPolicy Gradientやろうとしたら全部忘れていた

DQN

アルゴリズム

• とりあえずプレイアウトしてをreplay memoryに保存する
• と、そのステップ後のを取り出してきて、後者の価値を古いネットワークで推定し、そこからrewardを逆算した前者の価値に近づけるように、新しいネットワークを学習させる
• 数iter学習したら古いネットワークを新しくする

いいところ

• replay memoryに保存してまとめてとってくるので、まとめて推論できて、高速だしsample efficient

Policy Gradient

アルゴリズム

• 期待報酬を最大化するように学習する
• は確率的
• この勾配はpolicy gradient theoremによって求まる

sykwerくんの記事が優秀

sykwer.hatenablog.jp

いいところ

• まあこれもエピソード分の推論は同時にできるしそんなにスピード悪くなさそう
• DQNに比べて何がいいのかわからんな

MCTS

アルゴリズム

• 未展開ノードについたらその評価を推論して、そこまでのノードの評価をupdateする
• visit回数に応じて、より強いpolicyを構築し、それに合わせるように学習する
• スコアは相対的なものにする

いいところ

• 探索があるので、一般に普通の評価より強いと思う
• DQNのやつと組み合わせたらさすがにDQNより強いはずでは

Dynamic Connectivityについて

kopricky.github.io

なんかやばすぎる記事を発見した。めっちゃ研究を追ってみたいけど人生が終了しそう

2020年の抱負

今年の目標は

• ICML/NeurIPS/AAAI/ICLRのどれかに通す
• グラフアルゴリズム系の学会のどれかに通す
• 強いメンタルをもつ

です。がんばるぞ〜

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やめろ

概要

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

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

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

X3C

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

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

帰着

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

まず、カバーすべき集合をとしたとき、集合を考える。また、とする。

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

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

であることと同値。

としては上図のように構成する。上図のノード数はみやすさのため少なくなっているが、は実はになっており、たとえばはになっている。ポイントはノード数がたかだかの多項式のサイズなので、X3Cのインスタンスが与えられると多項式時間で構築できることである。

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

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

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

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

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

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

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