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

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

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

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

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

Reduction

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

  1. 頂点 vがself-loopをもつ場合、その頂点を削除し、問題の kを1減らす。
  2. 多重度3以上の辺がある場合、多重度を2にする。
  3. 次数が1以下の頂点がある場合、削除する。
  4. 次数2の頂点 vがある場合、 vを削除し、 vにつながっていた2頂点を新たに辺で結ぶ。
  5.  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ページあたり)

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

卒論名言集

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ぐらい生成してそう

【小学校の試験の採点基準的な】よくツイッターでみるやつについての見解

ツイッターでもう見飽きた話題の一つなんですが、話題自体としてはそこそこ議論の余地があるものなので見解をまとめておきます。

ざっとツイッターを見る限り、算数・数学の試験を

  • 算数・数学をわかっているかのチェック
  • 課程を理解しているかのチェック

と捉える2通りの視点があって、これによって論争が生じている気がします。

ぼくは後者派です。したがって、りんごが6個入っているパックを3パック買ったときのりんごの個数は小学校の試験では(後述するような例外を除いて) 6 \times 3と答えたほうのみを正解とする立場です。

これだけを言うと一気にクソリプが飛んできそうなので、予め立場をざっくり紹介しておきます。

  • もちろん整数の乗算が可換であることは重要な性質
  • しかし、教科書を読むと、掛け算の説明には絶対意味論付きで教わるし、先生も授業中にそう説明しているはず
  • 教科書をちゃんと読むか、先生の話を聞いていれば、パターン認識的な解き方になるかもしれないが、想定解にはたどり着けるはず
  • 分かっている生徒は、可換性などをわかっている上で別にちゃんと想定解を書くので問題ない(経験)

さらに

  • もし問題が複雑で(たとえば式変形が複数回あるような)、上述したケースよりもずっと難しい内容が問われているなら別に掛け算の順序はどうでもいいです
  • なぜなら作題者は掛け算の順序がわかっているか確認するためにそんな複雑な問題は出さないからです。
  • でも掛け算一回で終了するレベルの問題を聞かれているなら、教科書にそってやるべき(自分で学習して学校で未習のことを分かっているのはとてもいいことですが、自分が学校で習ったことを”分かっている”と教師に伝えられる回答を書くのも実力のうちです)
  • 問題を解く人は、問題を解いているときに、何の能力を図られているか理解して回答を書くべき

という感じです。というか、本当に自分の周りの優秀な人で、これを逆に書いて減点されたとか、そういう話を聞いたことがありませんし(みんな想定されている順序の回答をする)、普通にツイッターで見かける諸々の回答を書いている生徒は、授業わかっていないのでは?という気持ちになる。親が騒いでいるだけかな? 本当に教科書の意味が分かっていないならそれはそれで問題で、ちゃんと教科書を読んでください。

Tea Break

さて、まだなお前者の考え方を持っている人にもう少しお話します。多分あなたは優秀なんだと思います。ところであなたは高校で習う極限や連続性の文脈で、ああいった曖昧な説明をするよりイプシロンデルタ論法による厳密な極限の定義を導入したほうがいいと思いますか? ぼくは思いません。まあ生徒の平均的なレベルが非常に高い中学・高校なら導入したほうがいいかもしれませんが、少なくとも日本の平均的な高校生に対する需要が皆無だからです。ぼくは”教育”は平均的な生徒のレベルでなされるものだと思っています。なので高校の物理の先生が、物理の公式を語呂合わせで教えていたのにも納得していましたし、平均点をあげるためには、最適戦略なのではないかとすら思っています。 優秀な生徒には申し訳ないです。自分で勉強してください。きっとあなたに合った環境は存在するはずなので大学を楽しんでください。

さて、ちょっと話がそれてしまいましたが、何を言いたかったかというと、学校教育では、自分で進んで勉強している人ではなく、平均的な人(知識の流入元が学校で行われた授業しかないような人)に合った試験を採用して、彼らの理解度を図るべきであり、そうすると、やはりテストの採点基準が、数学を分かっているかではなく「課程を理解しているか」になります。これは、進んで勉強している人にとっては少しイライラすることかもしれませんが、教育の役割を考えると納得できることなのではないでしょうか?

中学校以降・大学入試編

基本的に「何が問われているかを理解して、想定解を書く」という筋道は変わりません。

なのでだいたい以下のような主張です

習っていない定理を(証明無しで)使ってはいけない

まあ、いいんですが、証明なしで使う分には減点は覚悟してくださいという感じです。課程を理解している人なら解けるように作られている問題なのですから、課程を理解しているなら、その知識だけで回答を書いてください。

式変形を想定されているまでやらないと減点

たまにツイッターとかで、二重根号を外していないから減点を食らった!とか、見ますが、まあそれはそうです。教科書は二重根号を外していますし、仮にぼくが受験者だったとしても、外せないような形でない限り外します。外していない人とは点数上の差別化をしてほしいです。たとえば、問題が非常に複雑で、そのごく一部で、さほど重要でない評価をするときには二重根号をわざわざ外さなくてもいいと思いますが、これも作題者が何を聞こうとしているかを汲み取って、ケースバイケースで判断してください。答え自体が二重根号になる場合や、簡単な計算問題の場合、外すべきなのは作題者の気持ちになれば明らかかと思います。

というか、等価な式を書いて正解、とかならいくらでも等価な回答が書けてしまう問題もありますし、やはり作題者の意図を汲み取ることは重要

まとめ

課程の内容を分かっているなら、自分が分かっていることが相手に確実に伝わるような回答を書いてください。

じょえチャンネル開設にむけて

  • ICML提出したら開設してみようかな〜と思っています
  • コンテストの解説とかをメインコンテンツにするつもりはまったくなくて、普通に競プロerたちがワイワイガヤガヤやって、界隈ならではの盛り上がり方ができるところを動画にしたいなと思っています
  • プログラミング始めたての人が見て、こいつらやべー(褒め言葉)と思ってくれるのを期待しています
  • 動画はさすがに不定期更新になると思います
  • なんか案外協力してくれるよと言ってくれている人が10人ぐらいいるので思ったより撮影に困りすぎるわけでもなさそう?
  • Slackみたいなのを作ってみんなの予定が合ったときに集まって企画みたいなのをやりたい(企画ごとに参加者は違っててもいいかなと思っている)
  • 出演者募集しています。team Girigiriはまあ呼べば出そう。catsatmatの人たちも呼べば出てくれそう。マリーさんもまあ出てくれそう。基本顔出しになると思います。動画のコンセプトとしても、そんなにコーディング画面映さないと思います(映したとしても画面5割程度)
  • レッドコーダーで出演依頼したら出てくれそうな人がcatupperを除くとyosupoさんとtempuraさんぐらいしか思いつかないのでこの2人を中心に人を増やしたい。さすがにじょえにきあと絡みがない人はじょえにきあにドン引きしていそうなので
  • 編集とかはとりあえず自分がやる予定だけどやりたい人がいたらお譲りします(さすがにいないだろ)
  • さらにクオリティの低い動画をサブチャンネルにあげるなどをしたい
  • じょえチャンネルをよろしくお願いします

研究がまた先行研究とかぶった話

まあ別に初めてではないのであれなんですが

今回はちゃんと1~2週間ぐらい網羅的にサーベイして、完全にかぶっていないことを確認したつもりだったんですが、

先行研究のciteが2とかだった上に、問題の英語名が特殊で、自分の検索ワードと全然マッチしなくて、

しかもその先行研究の先行研究は、分野外(ハードウェア系)の最適化問題で現れた問題で、完全に界隈外の学会だったので

まったく気づきませんでした。

30年ほど昔の研究でした。

GNNの研究をしていると最近の論文しかないため、論文をサーチすれば何ができていて何ができていないかは比較的簡単に分かるのですが

離散最適化など、何十年にも渡って研究されているトピックの場合、あまり世に広まっていない論文だと

全然気づかないこともあるみたいですね。

反省として、こういうときは論文ではなく教科書を先にサーベイすべきです。

東大の図書館、実は本郷にきてから初めて利用したのですが

教科書が無限にあってすごい(それはそう)

ところで、担当してもらっていた先生から励ましの言葉をもらいました

Finding a paper working in your problem is not a bad news at all. It is a process of shaping your topic to the latest one. I am sure that the ideas you have got so far will be applied to solve some research problem soon.

これまでわりと一人で研究をしてきたのでこういう言葉を初めてかけてもらった気がします。

涙がでちゃって、あーやっぱ悔しかったんだなあと客観的に思ってしまいました。

一人ってよくないですね。

ツイッターで言語不明瞭をしちゃうし。

ちなみにこのトピックですが、一応先行研究との差集合は存在するのでそれで続けるという方針はあるのですが

いま客観的にみても、メインの主張がすでに言われているので、まったく同じ分野だとあまりインパクトあることは言えないかなあ

という気持ちになっています。

まあ人生の記録としてブログに