Joeの精進記録

旧：競プロ練習記録

TSP in Solid Grid Graphs

cs.smith.edu

Grid Graph Gがsolidであるとは、格子点における Gの補グラフの連結であるということである。

グリッドグラフ上でのハミルトンパス（もしくはサイクル）問題は、solidなグリッドグラフ（穴を含まない）なら多項式時間で解くことができるが、一般のグリッドグラフ上ではNP-hardである。

一般グリッドグラフ上のTSPが解けると、一般グリッドグラフ上のハミルトンパス問題が解けてしまうので一般グリッドグラフ上のTSPはNP-hard.

solid grid graphにおけるTSPは未解決

DPC広島に参加しました

優勝しました！

これでやっと競プロのコンテスト優勝者を名乗れる…

f:id:xuzijian629:20191117194317j:plain

申し込み

f:id:xuzijian629:20191117194457p:plain

ICPCとかぶっているということで、賞金チャンスがかなり高まったのでモチベがあがります。

Girigiriは仲がいいのでこういう情報はちゃんと隠されずにシェアされてうれしいですね〜〜〜〜〜〜〜

広島へ

会場がかなり山奥にあって電車によるアクセスが困難なので、チームメイトに運転してもらいます（ぼくは免許もってない）

写真を撮り忘れたのですが、会場前の建物に"Ogino"と刻まれていておもしろかった

DPC参加する人を事前チェックしていたのですが、ほぼ知り合いがいなそうだと思った割にはいました。kaitoくんに会ってみたかったのであえてよかったです。

コンテスト

形式

問題例は公式サイトをご覧ください。

コンテストの形式はちょっと特殊で、手元実行した結果をフォームに入力して提出します。テストケースは3つぐらいしかないです。ケースも比較的小さいので手元で計算できちゃうレベルなんですが、一応ルールで埋め込みは禁止されています。実行時間に制限はないので、ルール上は手元で長時間回すことが可能です。

問題の性質上、最後の問題は計算が困難な離散最適化問題がでがちです。残り4題は普通の競プロといったところでしょうか。

入力の受け取りがかなり特殊なんですが、ソースコードへの入力データコピーが可能なので、そのままファイルに貼り付けるのが楽です。

コンテスト中

1, 2, 3, 4問目を大きなミスなく解きました。多分デバッグに使った時間は2分以下な気がします。3, 4問目で多少冗長なコードを書いた自覚がありますが（ちょっと詰めれば短く書けたと思う）、まあ早解きとのトレードオフがあるので、総合するとかなりよくできたかなと思います。

5問目に一時間半を残したわけですが、結局正解することができませんでした。終了後に、実は条件を誤読していた（各トラックが1台まで、ということを知らなくて、何台もトラックを発進していた）ことが判明し、コンテスト時間がもう少し長くてけんしんが5問目を通していたらかなり危なかったようです。

コンテスト中は最適解よりもいい答えを出してしまったのでかなりびっくりしていました（悪あがきでbin packing問題のヒューリスティクス解＋乱択で解を出しました）。

結果

4完内ならさすがに一番早いだろうとは思っていたのですが、チームメイト残り2人から最後の問題の正しい設定と解法（荻野とけんしんは別の解法だけどどっちも合ってそう）を聞いて、あ〜〜〜〜〜これなら解けてる人がいてもおかしくなさそう、だと思ってドキドキしていました。受付の人から東京から5人来ている、という情報を聞いていたので自分たち以外に2人謎の人物がいて、隠れレッドコーダーとかやめてくれよおおお〜〜〜〜〜ってなっていました。

結果、初優勝！！！！！！

盾をもらったり取材を受けたりしました。盾は後日配送みたいです。 盾に書いてもらう名前のふりがなを登録時に「じょえにきあ」にしたのですが、ふりがなは振られませんでしたし表彰時は本名で呼ばれました。

けんしんはあと数分あれば1位になっていたようなのですごく危なかったです（けんしんが1位のほうがチームとしての獲得賞金額は多かったのですが）

観光

コンテスト後、フェリーで江田島という島に向かいます。夜遅かったので急いで宿にチェックインすると、かなり豪華な夕食が待っていてテンションが上がりました。

刺し身がめちゃめちゃうまい

次の日、島を観光しました。海上自衛隊の術科学校があるみたいで、中を見学させてもらいました。最初90分で、なげーと思っていたのですが、博物館のような建物があって一瞬で時間が過ぎ去ってしまいました。あと、けんしんが一般道と間違えて自転車で術科学校の敷地に突入したところ、警備員に止められていてかなりおもしろかったです。

自転車を借りて島を回りました。さすがに最高

f:id:xuzijian629:20191117201231j:plain フェリーから見る日没。ところでフェリーは船内できっぷを買うことが多いみたいで、駆け込み乗船が可能なのでオタクにやさしかった。

f:id:xuzijian629:20191117201309j:plain 広島焼きをやべて帰国。

最後に

ICPC横浜とかぶっているのが本当にでかすぎた。少なくともここ数年以内は他のコンテストで優勝できる気がしないし、なんなら賞金をもらうのさえ難しい気がするので、今回のこのあまりに運のよかった大会でちゃんと優勝できて本当によかった。

Convolutional Rectifier Network as Generalized Tensor Decomposition

http://proceedings.mlr.press/v48/cohenb16.pdf

を読んだ。

概要

ConvNetの理論解析をテンソル分解で行っている。 結果として、ReLU + max-poolでのuniversality, ReLU + ave-poolでのnon-universality, depth efficiencyなどを解析している。

Related Work

かなりおもしろい。 f:id:xuzijian629:20191114232344p:plain

解析

f:id:xuzijian629:20191114232008p:plain

ネットワークを離散化して有限次元テンソルにする。 N個の入力それぞれがある M通りの固定された値(templates)から選ばれるとして、 M^N通りの出力をテンソルとしてメモをする。これは、入力を離散化した場合のネットワークそのものの情報を表す。

f:id:xuzijian629:20191114232013p:plain shallow networkの場合、これがちょうどGeneralized CP decompositionの形でかける。CP decompositionはweighted sumの項数を十分増やせば任意のテンソルを表せるので、universalityがあるね！みたいな事を言う。

もちろん、テンソルは離散的なのに、ネットワーク自体は連続なので、明らかにuniversalityは言えない。しかし、画像データのように、取れる値がそもそも離散的である場合は、 Mを十分大きくとれば実際に任意のネットワークを表せることになる。

templateがネットワークの構造をだたひとつ決定するとき、そのtemplateはcoveringという。universalityの存在を言うにはcovering templatesが存在を仮定しなければいけない。

感想

covering templatesの存在、強烈すぎるだろ。無限次元テンソル解析は無理なの？

平面グラフ判定＆描画アルゴリズム

元論文はhttp://hinkali.com/Education/PlanarityTesting.pdf

ここが日本語で説明してくれている http://www.th.cs.meiji.ac.jp/assets/researches/2007/toyota/index.html

アルゴリズム

  • グラフをdfsし、訪れた順にidを振っていく。dfs木と後退辺を覚えておく
  • 各辺の優先度を \min{u, v}とする。つまり両端のidのmin
  • 辺を優先度の大きい順に追加していく
  • そのときに2連結になるように、頂点を適宜増やしていく
  • 新たなループが生成されるとき、externally activeな頂点を外平面に向けるようにflipする(将来的に処理される辺はすべて外平面に来ているはず)
  • 最後まで追加できれば描画完了。無理なら平面グラフでない

f:id:xuzijian629:20191111195449p:plain

externally active

優先度 pの辺を処理している時点で、 wがexternally activeであるとは、 wがidが pの頂点が属する2連結成分の要素ではなく、かつ \mathrm{lowpoint}(w) \lt pであることをいう（後者が重要）。

f:id:xuzijian629:20191111194641p:plain

□が頂点vを処理段階でのexternally activeな頂点。

正当性

証明が複雑すぎて追いきれていないが、方針としては

  • もしグラフが平面グラフなのに、後退辺を追加できなかったとする
  • 後退辺を遮るexternally activeな頂点が存在する
  • それらの位置で場合分け
  • いずれも K_{3,3}をマイナーにもつので平面でない
  • 矛盾

みたいな方針

Stability and Generalization of Graph Convolutional Neural Networks

https://arxiv.org/pdf/1905.01004.pdf

を読んだ。

問題設定

データセットと学習アルゴリズムを固定したときに、入力に対する予測の誤差の期待値を抑えるのではなく、その期待値と、有限個の入力での誤差の平均の差(Generalization Error)を抑える。

→何個ぐらいからなるデータセットを用意すればいいかがわかる

  • Single Layer GCNNを考える。フィルターは f(X, \Theta) = \sigma(g(L)X\Theta)の形をしている
  • 固定されたグラフ上でのSemi-supervisedという設定
  • つまり、データセット内の z_i=(x_i, y_i)（頂点属性）のペアは未知の分布に従う \mathcal{D}からサンプルされたものだとする
  • SGDで学習しているとする
  • activation function \sigmaはリプシッツ連続かつリプシッツスムーズ
  • loss関数もリプシッツ連続かつリプシッツスムーズ

証明の重要ポイント

  • データセットの一要素が変わった場合を考える。このとき影響を受けるのは \Thetaのみ。 \Thetaの差分による寄与と、その他の係数に分ける。

やばい点

f:id:xuzijian629:20191110160939p:plain で \lambda_G^{\mathrm{max}}のオーダー表記が正しいのは、最大固有値が1より大きい場合であるがこれは一般に成り立たない。さらに悪いことには g(L) = A+ Iのときには1以下なので困る。

隣接行列とグラフラプラシアンの固有値について

頻繁に忘れるのでメモしておく

隣接行列

  • 固有値の和は0
  • \mathrm{diam}(G) \le t - 1. ただし tは異なる固有値の個数
  • 最大固有値は平均次数以上最大次数以下
  • Gが2部グラフであることと、固有値が0について対称に現れることは同値

http://www.kurims.kyoto-u.ac.jp/~kyodo/kokyuroku/contents/pdf/2001-02.pdf

グラフラプラシアン

wikiなど