2020-01-25

DDCC2020参加記

NHK杯で羽生結弦を（オンサイトで）見ていたら予選出れなかった

じょえくんとしてDDCCに参加していません
— 卒論に内容はいらない！🐄 (@ei1333) January 25, 2020

うしくんもぐもぐ笑

これはなに？

たぷりすたべる

2020-01-25

Minimum Feedback Vertex Setの乱択アルゴリズム

Feedback Vertex Set (FVS)とは、グラフ $G$ の頂点の部分集合で、その頂点を取り除いたとき、グラフが閉路をもたなくなるようなもののことです。

最小のFVS, すなわち、最小何頂点取り除いたときにグラフがcycle-freeになるかを求める問題はNP困難な問題として知られています。

この前NIIでwataさんに会ったときにかなり単純なアルゴリズムを教えていただいたのでまとめておきます（調べてもありえないぐらいヒットしなくて困りました）。

問題を判定問題として扱うために、入力はグラフ $G$ と整数 $k$ とし、 $G$ が大きさ $k$ 以下のFVSをもつか、を判定することにします。 $G$ の単純性は仮定しません。

Reduction

$G$ の最小次数を3以上にするために以下の操作を繰り返します。

頂点 $v$ がself-loopをもつ場合、その頂点を削除し、問題の $k$ を1減らす。
多重度3以上の辺がある場合、多重度を2にする。
次数が1以下の頂点がある場合、削除する。
次数2の頂点 $v$ がある場合、 $v$ を削除し、 $v$ につながっていた2頂点を新たに辺で結ぶ。
$k$ が負なら"No"を返してアルゴリズムを終了する。

すげー命題

最小次数が3以上のグラフ $G$ について以下が成り立つ。任意のFVS $X$ について、 $G$ の半数より多くの辺が $X$ に含まれる頂点を端点に持つ。

乱択アルゴリズム

上述した命題により、reductionを適用したグラフにおいて、一様ランダムにひとつ辺を選び、さらに一様ランダムにその端点を選ぶ（これは次数に比例してランダムに頂点を選ぶことと等価です）と、その頂点は1/4より大きい確率でFVSに含まれる、ということです。

なので、以下の乱択アルゴリズムを構成することができます。

「reductionを適用したグラフ $G$ において、閉路がなくなるまで、 $G$ での次数に比例した確率で頂点を $k$ 個まで順番に選んで削除し、閉路がなくなったらYesを出力する。閉路がなくならなかったらNoを出力する」

このアルゴリズムは、判定問題の答えがYesのとき、少なくとも $4^{-k}$ の確率でYesを返します。

参考：

https://www.mimuw.edu.pl/~malcin/book/parameterized-algorithms.pdf (101ページあたり)

う　し　た　ぷ　に　き　あ　く　ん　笑　（スター稼ぎ用）

2020-01-21

卒論名言集

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

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

1/19

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

1/20

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

1/21

f:id:xuzijian629:20200121162623p:plain

f:id:xuzijian629:20200121162615p:plain

f:id:xuzijian629:20200121162711p:plain

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

1/22

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

1/23

f:id:xuzijian629:20200121162914p:plain

1/24

f:id:xuzijian629:20200121162937p:plain

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

f:id:xuzijian629:20200121163049p:plain

1/25

f:id:xuzijian629:20200121163204p:plain

1/26

f:id:xuzijian629:20200121163241p:plain

1/27

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

f:id:xuzijian629:20200121163414p:plain

1/28

けんしんの熱が下がる

f:id:xuzijian629:20200121163446p:plain

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

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

1/29

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

f:id:xuzijian629:20200121163610p:plain

1/30 締切前日

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

2/1 締切

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

2020-01-06

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

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

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

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

2020-01-03

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

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

DQN

アルゴリズム

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