2020-01-01から1年間の記事一覧
木分解上のDPによってtreedepthを求める。 アルゴリズム自体が結構むずかしく、正当性は非自明 木分解上の各bagは、「そのbag以下の部分木のbagのUnionに含まれるノードについてのtreedepth decompositionのpartial decomposition」をもつ。partial decompos…
タイトルの通り アルゴリズムの概略は以下の通り ほぼ愚直なアルゴリズムがあり、アルゴリズムの探索空間を狭めた、を構築して、大部分の問題を解く。 うまく行かない場合のグラフは、任意のminimalな分解がproblematic node を含む形になっている。 グラフ…
普通に木DPをします。 ei1333.hateblo.jp
NHK杯で羽生結弦を(オンサイトで)見ていたら予選出れなかった じょえくんとしてDDCCに参加していません— 卒論に内容はいらない!🐄 (@ei1333) January 25, 2020 うしくんもぐもぐ笑 これはなに? たぷりすたべる
Feedback Vertex Set (FVS)とは、グラフの頂点の部分集合で、その頂点を取り除いたとき、グラフが閉路をもたなくなるようなもののことです。 最小のFVS, すなわち、最小何頂点取り除いたときにグラフがcycle-freeになるかを求める問題はNP困難な問題として知…
1年前の卒論関連のSlackを見返していたらわりと面白かったのでまとめます ちなみに締切は2/1だったみたいです。 1/19 DDCCの装置実装部門の話で盛り上がっている 1/20 けんしん「またライブラリの闇と戦っていたら1日が終了しかけている」 1/21 (ラボ内締切…
Hanjun-Daiのgraphnnがdefine-by-runじゃないせいで困った 複数グラフの、頂点ごとの確率を推論して、CrossEntropyしたい状況 batchあたりのlossを定義するために入力は複数グラフ(ひとつずつやってlossを足すということはできない) グラフごとにCrossEntrop…
久しぶりにPolicy Gradientやろうとしたら全部忘れていた DQN アルゴリズム とりあえずプレイアウトしてをreplay memoryに保存する と、そのステップ後のを取り出してきて、後者の価値を古いネットワークで推定し、そこからrewardを逆算した前者の価値に近づ…
kopricky.github.io なんかやばすぎる記事を発見した。めっちゃ研究を追ってみたいけど人生が終了しそう
今年の目標は ICML/NeurIPS/AAAI/ICLRのどれかに通す グラフアルゴリズム系の学会のどれかに通す 強いメンタルをもつ です。がんばるぞ〜