Joeの精進記録

旧：競プロ練習記録

S2V-DQNをCPU環境で動かす

github.com

オリジナルの説明が全然役に立たないのでまとめ直す。

1. Build

1.1

git clone --recursive https://github.com/Hanjun-Dai/graph_comb_opt

唯一そのままでうまく動く

1.2 Build graphnn

github.com

一応こちらの説明に沿ってやる

1.2.1 CUDAをhttps://developer.nvidia.com/cuda-toolkitからダウンロードしインストールする

GPUが入ってなくても大丈夫。CPU環境で動かすのでそもそも必要ないと思うけどdependencyを気にするのが面倒だったのでとりあえず入れておいた。

1.2.2 .zshrc (.bashrc)を更新

export CUDA_HOME=/usr/local/cuda
export LD_LIBRARY_PATH=/usr/local/cuda/lib64:$LD_LIBRARY_PATH
export LD_LIBRARY_PATH=/usr/local/lib:$LD_LIBRARY_PATH

CUDA_HOMEは実際ここにちゃんとインストールされるはずなのでそのままで大丈夫

1.2.3 Intel MKLをhttps://software.intel.com/en-us/mkl/choose-downloadからダウンロードしてインストールする

インストール先のディレクトリは標準で/opt/intel以下になる。

source /opt/intel/bin/compilervars.sh -arch intel64 -platform mac

を同様に.zshrc (.bashrc)に追記する。

1.2.4 Intel TBBを入れる

ompみたいなやつ。brew install tbbする。

1.2.5 make_commonを用意する

dir_guard = @mkdir -p $(@D)

INTEL_ROOT := /opt/intel
MKL_ROOT = $(INTEL_ROOT)/mkl
TBB_ROOT = /usr/local
USE_GPU = 0

FIND := find
CXX := g++
CXXFLAGS += -Wall -O3 -std=c++11
LDFLAGS += -lm  -lmkl_rt -ltbb
ifeq ($(USE_GPU), 1)
    CUDA_HOME := /usr/local/cuda
    NVCC := $(CUDA_HOME)/bin/nvcc
    NVCCFLAGS += --default-stream per-thread
    LDFLAGS += -L$(CUDA_HOME)/lib64 -lcudart -lcublas -lcurand -lcusparse
endif

CUDA_ARCH :=    -gencode arch=compute_30,code=sm_30 \
        -gencode arch=compute_35,code=sm_35 \
        -gencode arch=compute_50,code=sm_50 \
        -gencode arch=compute_50,code=compute_50

USE_GPU = 0にする。コンパイラを変える場合はCXXの部分を変更する。 INTEL_ROOT, TBB_ROOTを調整する。

1.2.6 Makefileを変更する

include make_common

ifeq ($(USE_GPU), 1)
    build_root = build
else
    build_root = build_cpuonly
endif

include_dirs = $(CUDA_HOME)/include $(MKL_ROOT)/include $(TBB_ROOT)/include include
CXXFLAGS += $(addprefix -I,$(include_dirs))
CXXFLAGS += -fPIC

# cpp_files = $(shell $(FIND) src/ -name "*.cpp" -printf "%P\n")
cpp_files = nn/hit_at_k.cpp nn/optimizer.cpp nn/sparse_dense_matmul.cpp nn/cross_entropy.cpp nn/in_top_k.cpp nn/elewise_mul.cpp nn/sigmoid.cpp nn/param_set.cpp nn/inner_product.cpp nn/entropy.cpp nn/tanh.cpp nn/type_cast.cpp nn/binary_logloss.cpp nn/axpby.cpp nn/matmul.cpp nn/exp.cpp nn/relu.cpp nn/square_error.cpp nn/multi_matmul.cpp nn/elewise_minus.cpp nn/identity.cpp nn/fully_connected.cpp nn/jagged_softmax.cpp nn/kxplusb.cpp nn/moving_norm.cpp nn/softmax.cpp nn/is_equal.cpp nn/concat_cols.cpp nn/elewise_add.cpp nn/one_hot.cpp nn/variable.cpp nn/arg_max.cpp nn/factor_graph.cpp nn/row_selection.cpp nn/l2_col_norm.cpp nn/reduce.cpp nn/abs_error.cpp nn/multinomial_sample.cpp nn/msg_pass.cpp nn/nat_log.cpp nn/reduce_mean.cpp util/fmt.cpp util/mem_holder.cpp util/graph_struct.cpp tensor/cpu_row_sparse_tensor.cpp tensor/cpu_sparse_tensor.cpp tensor/cpu_dense_tensor.cpp tensor/t_shape.cpp tensor/t_data.cpp tensor/tensor.cpp
cxx_obj_files = $(subst .cpp,.o,$(cpp_files))
obj_build_root = $(build_root)/objs
objs = $(addprefix $(obj_build_root)/cxx/,$(cxx_obj_files))

ifeq ($(USE_GPU), 1)
    CXXFLAGS += -DUSE_GPU
    NVCCFLAGS += -DUSE_GPU
    NVCCFLAGS += $(addprefix -I,$(include_dirs))
    NVCCFLAGS += -std=c++11 --use_fast_math --compiler-options '-fPIC'
    cu_files = $(shell $(FIND) src/ -name "*.cu" -printf "%P\n")
    cu_obj_files = $(subst .cu,.o,$(cu_files))
    objs += $(addprefix $(obj_build_root)/cuda/,$(cu_obj_files))
endif

DEPS = ${objs:.o=.d}

lib_dir = $(build_root)/lib
gnn_lib = $(lib_dir)/libgnn.a

# test_src = $(shell $(FIND) test/ -name "*.cpp" -printf "%P\n")
test_src = cuda_test.cpp cpu_row_sparse_test.cpp test_main.cpp op_test.cpp gpu_tensor_test.cpp simple_test.cpp cpu_tensor_test.cpp
test_objs = $(subst .cpp,.o,$(test_src))
test_build_root = $(build_root)/test
test_target = $(addprefix $(test_build_root)/,$(test_objs))
DEPS += ${test_target:.o=.d}

all: $(gnn_lib)

$(gnn_lib): $(objs)
    $(dir_guard)
    ar rcs $@ $(objs)

ifeq ($(USE_GPU), 1)
$(obj_build_root)/cuda/%.o: src/%.cu
    $(dir_guard)
    $(NVCC) $(NVCCFLAGS) $(CUDA_ARCH) -M $< -o ${@:.o=.d} -odir $(@D)
    $(NVCC) $(NVCCFLAGS) $(CUDA_ARCH) -c $< -o $@
endif

$(obj_build_root)/cxx/%.o: src/%.cpp
    $(dir_guard)
    $(CXX) $(CXXFLAGS) -MMD -c -o $@ $(filter %.cpp, $^)

.PHONY: test

test: $(test_build_root)/test_main
    ./$(test_build_root)/test_main

$(test_build_root)/%.o: test/%.cpp
    $(dir_guard)
    $(CXX) $(CXXFLAGS) -MMD -c -o $@ $(filter %.cpp, $^)

$(test_build_root)/test_main: test/test_main.cpp $(test_target) $(gnn_lib)
    $(dir_guard)
    $(CXX) $(CXXFLAGS) -MMD -o $@ $(filter %.o, $^) -L$(lib_dir) -lgnn $(LDFLAGS) -lpthread -lgtest

clean:
    rm -rf $(build_root)

-include $(DEPS)

cpp_filesやtest_filesを(FIND)によって得る方法がLinuxのみの対応なのでもう全部書いちゃう。

1.2.7 ソースコードの変更

include/tensor/tensor.hのヘッダに #include <functional>を追加する。

diffの詳細はこんな感じ。

 #include <memory>
 #include <iostream>
 #include <exception>
+#include <functional>
 #include <string>

1.2.8 Make

これでやっとmakeが通る

1.3 S2V-DQNのbuild

1.3.1 Makefileの変更

GNN_HOME=../../../graphnn

include $(GNN_HOME)/make_common

lib_dir = $(GNN_HOME)/build_cpuonly/lib
gnn_lib = $(lib_dir)/libgnn.a

include_dirs = $(CUDA_HOME)/include $(MKL_ROOT)/include $(GNN_HOME)/include ./include

CXXFLAGS += $(addprefix -I,$(include_dirs)) -Wno-unused-local-typedef
CXXFLAGS += -fPIC
# CXXFLAGS += -fPIC -DUSE_GPU
# CXXFLAGS += -DGPU_MODE
# cpp_files = $(shell $(FIND) src/lib -name "*.cpp" -printf "%P\n")
cpp_files = nstep_replay_mem.cpp simulator.cpp mvc_env.cpp graph.cpp config.cpp qnet.cpp inet.cpp nn_api.cpp
cxx_obj_files = $(subst .cpp,.o,$(cpp_files))

objs = $(addprefix build/lib/,$(cxx_obj_files))
DEPS = $(objs:.o=.d)

target = build/dll/libmvc.so
target_dep = $(addsuffix .d,$(target))

.PRECIOUS: build/lib/%.o

all: $(target)

build/dll/libmvc.so : src/mvc_lib.cpp $(gnn_lib) $(objs)
    $(dir_guard)
    $(CXX) -shared $(CXXFLAGS) -MMD -o $@ $(filter %.cpp %.o, $^) -L$(lib_dir) -lgnn $(LDFLAGS)

DEPS += $(target_dep)

build/lib/%.o: src/lib/%.cpp
    $(dir_guard)
    $(CXX) $(CXXFLAGS) -MMD -c -o $@ $(filter %.cpp, $^)

clean:
    rm -rf build

-include $(DEPS)

buildをbuild_cpuonlyに変更する。とりあえず、GPUを使いそうなところをコメントアウトし、cpp_filesを直書きする。

1.3.2 Make

makeが通るはず。

追記：通らなかったら.zshrcをもう一度sourceしてみて

1.3.3 PythonをPython2に変える。

code/data_generator/mvc/run_generate.shとcode/s2v_mvc/run_nstep_dqn.shのpythonの部分をpython2にする。まあpyenvとかを調整してもいい。

1.3.4 必要なモジュールをインストールする。

入ってないかもしれなそうなモジュールはnetworkxとtqdm いずれもpipでインストールできる。

rpathを追加

このままだと.soファイルがうまく動かないので

$ install_name_tool -add_rpath /opt/intel/mkl/lib mvc_lib/build/dll/libmvc.so

する。mklは/opt/intel以下にあると思うけど違ったら適宜直して。

2. Experiments on synthetic data

動くと思う

自分用Makefileのメモ書き

基本構文

<target>: <files>
    <commands>
<target>:
    <commands>

実行

makeとやると、Makefileに定義された最初のターゲットが実行される。他のターゲットを実行するにはmake clean, make installなど臨機応変にターゲット名を入力。

特別なターゲット名

.PHONY

.PHONY test

とかよくみる。コマンド名とファイル名が重複するとき通常ファイルが優先されて実行されないが.PHONYを書いておくと実行ルーチンが作られるっぽい。

.PRECIOUS

このターゲットは処理が中断してもファイル等が削除されない。

他

ここが詳しい。 www.ecoop.net

特殊変数

詳しくはhttps://www.gnu.org/software/make/manual/make.html#Automatic-Variables

$@

targetを返す

$<

filesの最初の要素を返す

$^

filesのすべての要素を返す

まだまだあるので適宜上のを見ること

変数・関数

こんなん

cpp_files = $(shell $(FIND) src/ -name "*.cpp" -printf "%P\n")
cxx_obj_files = $(subst .cpp,.o,$(cpp_files))
obj_build_root = $(build_root)/objs
objs = $(addprefix $(obj_build_root)/cxx/,$(cxx_obj_files))

みたいにするだけ。substとかaddprefixとかは後述する特殊関数

特殊関数

多すぎ。ここが天才 qiita.com

自分で使うならともかく読む分には比較的読める

ワイルドカードとしての%

suffixの置換

SRC = main.cpp hello.cpp
OBJ = $(SRC:%.cpp=%.o)

targetとかにも使えるっぽい

$(obj_build_root)/cxx/%.o: src/%.cpp
    $(CXX) $(CXXFLAGS) -MMD -c -o $@ $(filter %.cpp, $^)

など。

リンク

この記事よりもうちょい詳しめ www.jsk.t.u-tokyo.ac.jp

まとめ

Makefile系イキリオタク滅びろ

A Persistent Weisfeiler–Lehman Procedure for Graph Classification

Persistent Homologyをまったく知らない人は先にhttps://xuzijian629.hatenadiary.jp/entry/2019/07/20/192722を読んでください。

Super Simplified Overview

f:id:xuzijian629:20190720203406p:plain

あまりに本質な画像なんですが、グラフのNodeにWeisfeiler-Lemanの方法に従ってラベルを付けていき、 h回目のイテレーションにおける、各辺の重みをmultisetの距離（後ほど定義）で与えてやり、重み付きラベル付きグラフを構成する。こうしてできたグラフについてPersistent Homologyを考えてやり、ラベル付きバーコードを生成することで、連結成分やサイクルの情報を含んだグラフの情報が得られる。

Weisfeiler-Lehman Stabilization

WLの詳細は省くが、 h回目のイテレーションにおける特徴量ベクトルは、色 i = 1, \ldots, mのラベルがこの時点でいくつ存在するかまとめた長さ mのベクトルで与えられる。 グラフ Gの特徴量ベクトルは、各イテレーションの結果の長さ mのベクトルをconcatして得られる。

有名な話だけどWL testでは区別できないグラフもある。より表現力を強めるためにトポロジカルな情報を含めたいというのがこの論文のモチベーション

Topological Features

位相空間 Mについて、 k次元のtopological featureとは、ホモロジー群 H_k(M)のことを指す。とくに、 k = 0, 1についてはそれぞれconnected components, cyclesと名前がついている。明らかに、同型なグラフはこれらの要素数が同じになる。

ホモロジー群の詳細は知らなくてもしばらくは読めそう。

Persistent Homology

ほとんどのグラフにおいて、連結成分数やサイクル数を見るだけだと情報が雑すぎるので、Persitent Homologyを考える。次のようなグラフのfilterationを考える。

\emptyset \subset G_0 \subset G_1 \subset \ldots \subset G_{k - 1} \subset G_k = G

ここで、それぞれの G_i = (V, E_i \subset E)は頂点集合は同じだが、辺の数が増えていっている。すなわち、連結成分数はかならず広義単調減少で、サイクル数は広義単調増加となる。

Persistent homologyは各 G_iの連結成分数とサイクル数を記録する。

もう少し詳しく読み込もうと思ったがしばらくNeurIPS rebuttalで忙しそうなので中断

参考文献

[1] A Persistent Weisfeiler–Lehman Procedure for Graph Classification

AtCoderで黄色になりました

伝統に従って記事を書きます。

やったこと

AtCoder, CodeForces, Topcoderのコンテストに（撤退することもあるけどとりあえず）出続ける

短期間で圧倒的精進する人にはやっぱり抜かれてしまうけどこれでレートが落ちることは（赤とかにならない限り）ないかなと思います。

青序盤との差分

数え上げの苦手意識が多少軽減した

いやまだ苦手なんですが。でも、数え上げはわりと1ステップ1ステップごとに考察を詰めやすくて構築みたいに一発天才ゲーではなく素直に考察すれば解けることが多いことに気づきました。橙目指すなら数え上げかなりうまくなる必要がありそうだと思う。

典型DPに慣れた

Earsのような状態変化を記録するタイプのDPは青帯の人にとってはわりとつまるところだと思う。これに慣れたのはでかい。挿入DP, 区間DP, O(3^n)のDP, O(N^2)の木DP, 約数の包除原理など。

知識

これは列挙しようと思ったんですがさすがに多すぎて思い出しきれないのでやめました。比較的最近勉強したHeavy-Light Decompositionはあまりに便利なので青の人でも一度勉強してみることをおすすめします。

ゴリ押し用のデータ構造（Implicit Treap: 要素の削除や挿入ができる遅延セグ木のようなもの, や要素の削除や挿入ができる上位k個要素のsumを返すデータ構造など）をいくつか常備していますが、2, 3ヶ月に一度ぐらい役に立つ印象です。

ConvexHullTrickとかFFT, NTTなども使えるようになりました。

あと問題を解くと、こういうふうに帰着しちゃうとヤバいみたいなのがいくつか経験からわかってきて余計な考察を省けたりします。

当面の目標

コンテスト中に1時間ぐらい同じ問題を考察してやっと解けた、みたいな経験が最近少なくて（ICPCとかは実装担当なのでほぼ考察をしていないし）、長時間系のコンテストが苦手になっている気がします。黄色になっちゃうとレート上げチャンスがAGCや企業コンになりますが、前者は長時間系コンテスト（Aはすぐ解けちゃうし、たいていCやBに各1時間以上費やすことが多そう）の代表なので考えることに慣れなきゃいけないなと思います。これなにをすればいいんでしょうかね、やはり精進しかなさそう

Persistent Homology

A Persistent Weisfeiler–Lehman Procedure for Graph Classificationを読んでいてPersistent Homologyとは？となったので、調べた内容をまとめる。

Motivation

f:id:xuzijian629:20190720184635p:plain [1]

目標として、データの幾何学的構造を捉えたい。リング状になっているデータ点の集合あったとして、点ごとに見ると、離散的でリングが見えない。点を肥大化していくとリングが現れるが肥大化しすぎるとリングが潰れてしまう。これを、あらゆる肥大化について考えることで（Persistent: 永続的 にすることで）、データの幾何学的構造をうまく見つけようというモチベーション。

f:id:xuzijian629:20190720185149p:plain [2]

１つ目の図では肥大化を、その点を中心とする球の大小みたいなイメージで説明したが、別に特定のメトリックならなんでもいい（後述）。２つ目の人っぽいやつの図はどんなメトリックによってresolutionを変えているかわからないけど球の大小みたいなのでなくても大丈夫。いずれにせよresolutionを変えるという表現はかなり適切っぽい。

Filteration

f:id:xuzijian629:20190720185831p:plain [2]

距離が定められた空間において、各点から距離が h以下になるような距離空間内の点からなる集合を M_hと定めており、距離の増加列 h_1, \ldots, h_nについて対応する M_{h_i}の列をfilterationという。

これはまさにMotivationのところで説明した解像度を変えたときのデータの列のことである。

barcode, BD図

各幾何学的特徴（後述；connected components, cycles, voidsなど）について、それらがどのタイミング（どの h_i）で発生し、どのタイミングで消失したかを表す図。

f:id:xuzijian629:20190720191531p:plain [1]

birthとdeathのペア (b_i, d_i)を二次元平面で表したのがBD図。数直線で表したものがバーコード。BD図は b_i \lt d_iなのですべての点は y = xより上側にある。また、 y = x付近の特徴はノイズとされることが多い。

f:id:xuzijian629:20190720202029p:plain [3]

幾何学的特徴の見つけ方

これが要するにHomologyらしい。Homologyについての知見が足りなさすぎるのであまり書けることがない。いつかまとめ直すかもしれない

f:id:xuzijian629:20190720201855p:plain [3]

図、わかりにくいかもしれないが黄色は面を表していて、白は空洞だと思う。図では穴が1つ

参考文献

[1] パーシステント図に対する統計的機械学習

[2] パーシステントホモロジーとその応用

[3] Persistent Homology An Introduction and a New Text Representation for Natural Language Processing

感想

調べたら近年のICMLにわりと関連研究があってそれなりに人気っぽい。聞いたことなかったけど。一旦知ってしまうとWL kernelに応用しようとするアイデアはあまりに自然に思えるけどここ数年まったく出なくてこのタイミング突然出てきたのはわりとびっくり。WL kernelが強くなるとGraph Isomorphism Networkが強くなるのでこれの応用が秋のもろもろの学会で大量に出そうな予感がする。

ICPC国内予選2019に出場しました

4完24位でした。 f:id:xuzijian629:20190712220639p:plain

感想

この一戦だけに絞って感想を言うなら、「Eをもう少し落ち着いて確実に合わせに行きたかった」となるのですが、さすがに今回のICPCは自分にとって最後のICPCであり、チームGirigiriとはこの一戦のみならず人としての付き合いが長いのでそれほどシンプルにまとめることができません。

やっぱりチームメンバーに一番伝えたい気持ちは感謝の気持ちです。team GIrigiriが競プロモードになったのは去年のICPC国内予選以来ですが、わりとそこから1年間、競プロ熱を一度も切らすことなく切磋琢磨してやってこれたのはチーム独特の雰囲気があったからだと思います。予選に通ることが人生の目標なら別のチームメンバーもありえたかもしれませんが、自分が最大限に成長できたのはやっぱりこのチームだったんじゃないかと思っています。

そんな大好きなチームメートと出た最後のICPCなので（海外Regionalは一応考えてはいますが、まあ実質最後なので）残念だと言って終わらせたくないです。正直レート的に見るとまあ妥当なラインだとは思いますし、ABCDノーペナなのは普通にすごいと思います。Dでぼくが初め考えた嘘解法の穴をいち早く指摘してくれた荻野やDのアルゴリズムを理解して代わりに実装してくれたけんしんはめちゃめちゃ仕事をしたと思うし、中の中の上ぐらいの出来なんじゃないでしょうか。去年は50位だったのでそれにくらべれば大進歩です。

ICPCは終わりましたがGirigiriは研究なりその他の競プロなりでこれからも長い付き合いになりそうなので、２人ともよろしくお願いします。

最後になりましたが、通過した東大チーム・他大チームの方々はアジア地区予選頑張ってください！！！！！

お疲れ様でした！！！

ライブラリ

team Girigiriのライブラリを公開しておきます。ご自由にお使いください。幾何がちょっと弱いので補強したほうがいいです drive.google.com

風景

f:id:xuzijian629:20190712223624j:plain

こんな感じの長机でやっていました。

機械学習におけるカーネルを一言で

2つのデータがどれだけ似ているかを返す関数です。

非負実数を返し、似ていれば値は大きく、似ていないと小さいです。

以上！

カーネルトリックについて

たいてい回帰問題の文脈で現れると思いますが、元のデータ点を直線（もしくは超平面）で回帰することはそう一般にうまくいきません。 そのため、ある関数 \phiによって元のデータを高次元空間にマップしてから、超平面で回帰することを考えます。このときに適切な \phiを知ることは至難の業ですが、実は \phiを直接知らなくとも、さまざまな計算をうまく変形して行うと、 \phi(x), \phi(x')の内積（ \phi(x)^T \phi(x')の形とは限らず、より一般に \phi(x)^T A\phi(x')の形で現れます）さえわかれば多くの場合で事足りることがわかります。そして、 \phiを定める代わりにこの内積関数をカーネルとして予め定めてあげることで、 \phiを陽に扱わずこの問題が解けることになります。これがカーネルトリックです。

最後に

なんで本の説明はどれを見てもあんなに長々しいんや