PRoxy Diary

_ [研究] Additive Combinatorics

最近新しいこと勉強してないなと思ったので、CSの一部で大流行しているAdditive Combinatoricsを始めてみることにしました。まだ内容は部分的にしか理解していませんが、Additive CombinatoricsではSum Product Theoremが中心的な話題のようです。体Aに対してA+A={a+b:a∈A,b∈A}, A*A={a*b:a∈A,b∈A}と定義すると、Sum Product Theoremというのは、あるεが存在して、任意の体Aに対して、|A+A|>|A|^(1+ε)または|A*A|>|A|^(1+ε)が成り立つという定理です。有限体バージョンも有ります。で、組み合わせ幾何とか数論とかグラフ理論とか確率的検査証明とかに応用できるらしい。応用できすぎ。グラフ理論では主にSzemeredi's Regularity Lemmaという補題に名前を変えて現れます。

Additive CombinatoricsというとTao and Vuが有名ですが、いきなりこれを読んでも挫折する気がしたので、PrincetonのAdditive Combinatorics Minicourseというのを参考にしてます。講義ノートもしっかりしているし、何よりビデオが公開されているので良いです。

_ [研究] 乱拓アルゴリズム

周りでも何人か読んだ方がおられるようですが(おかだいさん, 稲葉さんなど)、僕も乱拓アルゴリズム読みました。僕はこの本を読んでランダマイズドアルゴリズムという分野の歴史を知ることが出来ました。学会とかジャーナルの論文リストだけ見ていると、どうにも雑多な話題がたくさん並んでいるように見えてしまうのですが、それを時間軸でつなげるとやはり流れがあるのだなというのを実感できる本です。

_ [イベント] SuperCon 2008

今日、高校生向けのプログラミングコンテストSuperCon 2008の結果発表会が行われました。このコンテストは、スーパーコンピュータを利用して、与えられた問題を解くプログラムを3〜4日間かけて作成し、その性能で競うというコンテストです。僕も今年もチューターとして参加させていただきました。

今回出題された問題は、東工大の岡本さんの日記に詳しく解説が載っていますので、そちらを参照してください。簡単に言うと、格子点上の点がN個与えられるので、それらを全て結ぶ単純多角形で面積が最少のものを求めなさいという問題です。

基本的に今回はチューター業に従事していたのですが、問題が与えられたら解きたいというのは、これは抑えられない欲望なので、合間の時間にこそこそ実装もしていました。僕の作ったプログラムは結構良い解を出してくれていて、高校生からもどういうアルゴリズムか教えて欲しいと言われていたのですが、あまり時間をとって解説できなかったので代わりにここに書くことにしたいと思います。

僕がこの問題を見た時に最初に思ったのは「多角形が交差していても、交差をほどくという操作を有限回繰り返せば、交差していない多角形に変形できるよね」ということです。証明はちゃんとする気が無かったのでしていないですが、同じ交差が二度発生することは無いと思われるので正しいでしょう。ただし並行な線分どうしが重なっているのをほどくのは特別扱いをしてあげる必要があります。とりあえずこれで任意に点をたどる順番を与えれば、それをほどくことで単純多角形が得られて、面積も出せるようになりました。

後は最適化問題に対して非常に効果的な焼きなまし法を試すことにしました。つまり手元に有る単純多角形を少し変形し、交差が出来たらそれをほどき、得られた面積がもとの多角形の面積より小さければ採用、そうでなくてもある確率で採用するわけです。変形の部分は、最初は各頂点を順にランダムな場所に移動するということをさせました。ランダムな頂点をランダムな場所に移動するのでも良いのですが、それだと局所解を見つけてくれない可能性があるなと思ったので、各頂点を順にランダムに移動することにしました。ここまでが1日目にやったことです。チューターしながら方法は考えていたので何とも言えませんが、実装は1時間ぐらい？今回の問題の特徴的なこととしては、ちょっと頂点の順番を変えるとほどく操作の過程で、がらっと多角形の形が変わるので、色々な多角形を意図せず見て回ることが出来るということですね。おかげで焼きなましが効くこと効くこと。

その後は変形に色々バリエーションを付け足してました。二頂点選んで、その間の頂点の順番を逆にするとか、リバース3回で頂点の並びをブロック単位で入れ替えるとか、あとは連続した4,5頂点を取り出して並び替えを全て試し、その中で一番解が良かったものを選ぶとか。そういうことをしていると、少しずつ解は良くなった気がします。MPIによる並列は、基本はそれぞれ別個に動いているのですが、誰かが解を更新したらそれを全員に伝搬するというごく単純なものです。4並列までしか動かしていません。

時間が無かったので諦めたこともいくつかあります。一つ目が点の並びをリストで管理すること。こうすると点の挿入とか逆順にするとかは非常に速くなる。後は交差を見つける時に、n^2回ループするのではなく、交差の存在しうる場所だけ調べること。例えば点の場所をランダムな場所に移動するという操作では、交差を誘発する線分というのは3本だけ考えれば十分です。こういった高速化をすると、さらにたくさんの多角形を調べることが出来て、もっと良い解も見つかるだろうと思います。

今回の問題は高校生には少々厳しかったのではないかと思います。まず幾何というのが非常に辛い。例えば交差判定は非常にコーナーケースが多く、知識無しで正確に交差判定を行うのは難しいでしょう。そういうあまり本質ではないところではまってしまって、肝心のアルゴリズムや並列化といったところに時間を割けなかったチームも多かったのではないかなぁと思います。その辺は来年は改善するべきところだと思います。

最後に、僕がコンテスト用Wikiに書いたスコアの証拠映像を貼り付けておきます。それぞれ50点と75点の入力に対する解です。

_ [研究室] グラフ理論の講義資料

Waterloo大のグラフ理論の講義資料が公開されていたのを発見したので、ずっと読んでいました。この授業は普通の入門的なグラフ理論(最短路とか最大流とか彩色とかクリークとか)の話でもなく、Extremal Graph Theory(ラムゼーとかチュランとかセメレディとか)でもなく、ちょっとマニアックだけどマニアックすぎないグラフのクラスの諸性質や諸アルゴリズムについて扱ったものです。伝わるのかな、こんな説明で(笑)。マニアックだけどマニアックすぎないというのは、例えばchordal, interval, comparability, perfect, series-parallel, planar, outerplanar, k-tree, partial k-treeと言った面々です。僕もこのへんは流石に名前や定義は知っていましたが、諸性質や諸アルゴリズムとなると、今までまとまった文章に出会ってなくて余り知らなかったので、凄い勉強になりました。

平面グラフの最大カットが多項式時間で解けることを示すところが凄くアクロバティックで、「最大カット」⇒「二部グラフにするのに取り除かないといけない枝の最小数」⇒「オイラーグラフにするのに縮約しなければならない枝の数」⇒「最小重みマッチング」と帰着して解くようです。他にも平面グラフ中の最大流をO(nlogn)(最終的に最短路に帰着するのでO(n)でも出来るでしょうね。)で求めたり、あとPQ-Treeを実際に使う例がいくつか出てきたり、かなり興奮してしまいました。大体読みきって後は16章を残すのみ。

_ [研究室] ICALP

先日アイスランドで開催されたICALP 2008から帰って来ました。ここまで期間が長くて規模が大きい学会に行くのは初めてということで、かなり楽しかったです。各論文の発表は、流石に2,30分の説明ではそもそも何がどう嬉しいのか分からないことも多かったですが、広く浅く知識を広げるのには役立ったという感じです。一応、僕も発表してきました。

Invited Talkで印象深かったものとしては、まずMuthukrishnanの広告とオークションの話があります。これは、ある一般化したオークションのモデルを考えると、Googleで現在使われているGSP(Generalized Second Price)というモデルと、その後継として期待されているVCG(Vickrey-Clarke-Groves)というモデルを特殊ケースとして含むようなモデルが作れるよという話。彼はブログも書いていますね。研究者のブログはあまり多くないので貴重です。

後はWinklerの数学パズルの話。見事にツボにはまって、その後数日間考え込んでしまいました。

それとSpielmanの話も面白かった。線形計画問題を解くSimplex法は計算量自体は指数なのに、どうして実用上速いのかというのを、Smoothed Analysisという概念を持ち込んで説明したということです。このことが評価されて、ゲーデル賞が授与されました。ゲーデル賞は理論計算機科学におけるチューリング賞のようなものですね。Smoothed Analysisの考え方は計算量以外の世界にも持ち込めそうなので、ネタ帳に記入しておこう。

こういうイベントは発表そのものよりも、人と会うことに意義があると思うのですが、流石に見ず知らずの人に声をかけるのはなかなか難しかったです。何とか共通の話題を持つ人たちに話しかけることには成功しましたが…。イスラエルの人とあんきもの話をしたり、台湾の人と松嶋菜々子の話をしたり。後は研究分野が似通っているポーランド人とか。皆賢くて困る(笑)。

_ [PFI] はてなブックマークの関連エントリー機能開発

そろそろこの日記がプライベートなものなのかパブリックなものなのかの位置づけを考えなくてはいけなくなって来ましたが…。

先日、株式会社はてなの皆さんと共同で開発合宿を行いました。その時の様子はnaoyaさんの日記に詳しいので、そちらに譲ることにします。naoyaさんがオフィスをスキップしながらデータのダンプをされていたのが印象的でした。

PFIには色々な自然言語関連の技術が溜まっているのですが、それをWikipediaのような限定的なデータではなく、はてなブックマークやその他を通して日本語のWebデータ全体に適用させることが出来たのはとてもエキサイティングな経験でした。各技術を実装した時に、Web全体に使えたらこういうことが出来るのになぁと妄想してたことのうちいくつかが実現しそうで、そのうちの一つが今回の関連エントリー機能です。

まず最初に今回の機能の(僕の個人的な)思想を述べます。

・Webの検索を単語でしか出来ないのはおかしい。

・かといってPowersetのような自然言語で入力するのは、精度の意味でも、ユーザの手間の意味でも大変そう。

・今見ているページがそのページを見ている人が見たいものを明確に表しているのだから、これを使わない手は無いではないか。

・じゃぁ今見ているページに似ているページをWeb全体から検索できるようにするべきだよね。

大体こんな感じです。なので、ニュース速報だとか、各ユーザに対する静的なリコメンドだとかが念頭にあるわけではありません。

アイデアもライブラリも既に有ったので、はてなさんと提携することになったとなれば、後は実行するだけでした。一般的にはページとページとの関連は、文書中に現れる単語を用いるのだと思いますが、残念ながら、これを実行するのは簡単ではありません。ページには良く広告だとか目次だとかが付属するのですが、これを機械的に正確に取り除くのは難しいですし、そもそも量が多すぎます。そこで、最初はどのユーザがどのページにブックマークを付けているかという情報を用いて、ページとページの関連を計ることにしました。イメージは「このページを見ている人はこんなページも見ています」というものです。ところが、これが精度が悪い。何故なのかを考えたのですが、僕が思うに、この考え方は直近のブックマークに絞って用いるべきものだったのだのでしょう。人の趣味や嗜好というのはかなり多様で、過去に各人が行ったブックマーク全てに対して、この考え方を用いると、出てくる結果もかなり雑多なものになってしまう。なので、趣味や嗜好が限定的な直近のブックマークに絞れば良い結果が得られるでしょう。最近diggというサイトがリコメンドを出しましたが、彼らの考え方はこれに近いようです。

その後、色々試行錯誤して、結局ページとタグの関係を用いるのが一番精度が良いというのに行きつきました。今、関連エントリを見ている方は恐らく新しいエントリの関連エントリを見ていることかと思いますが、今回のはタグが沢山付けば付くほど精度が上がります。少し古めの専門性の高い記事を見るのが良いでしょう。例えばnaoyaさんのHadoopに関する記事などです。5件しか表示されないのが残念ですが、こういう記事に対してはかなり精度は良いです。タグが少ない新しいエントリに対しては精度が不十分であることは自覚しています。アドホックな対応はしているのですが、根本的にモデル化から見直すのが良いかもしれません。

ところで、僕が最初に掲げた思想を実現するものを、はてなの方が試しに作ってくださいました。これはあくまで実験でこちらから表に出す予定は無いのですが、もうすぐWeb APIも公開されるようですし、皆さんの手に届くのも時間の問題かと思います。以下の画像はkzk君の日記に僕の野望を乗っけたスクリーンショットです。右下の関連エントリに注目。Google Perftoolsに関する記事に対して、それを補佐するかのような記事が出ています。これが全てのWebページに対して現れるとしたら…凄いと思いませんか？Wikipediaでリンクをたどっていたらいつの間にか日が暮れていたという経験を持っている方は多いかと思いますが、それが日本語のWeb全体に拡張されたようなイメージです。

_ [ICPC] 国内予選

今日、ICPCの国内予選が開催されました。コンテスタントの皆様お疲れ様でした。京大からは少なくとも二チームはアジア予選に行けそうです。みんなよく頑張ったと思います。問題はここにあります。

今年は僕はコーチとしてただ見守っていただけですが、やはり問題を見ると解かないわけにはいかないということで、EとFだけ裏でこそこそ解いていました。Eは解法は自明なので省略することにして、Fは次のように考えました。

最終的に二つの同じ形(それぞれAとBと名付けることにしましょう)が切り出された時のことを念頭に、まずチョコレートの一番左下の正方形の上向きが、どの正方形のどの向きに対応するかというのを全通り列挙します。これでA中の特定の正方形とB中の特定の正方形が対応づいたことになります。次に全ての正方形について、もしそれがA中の正方形で有ったとしたら、B中の対応する正方形はどこにあるかというのを求めます(勿論存在しない場合もあります)。

チョコレート中の正方形の数をnとすると、ここから自然に二部グラフ(A,B,E)(|A|=|B|=n)を作ることが出来ます。各正方形に対応する頂点がAとBに一つずつあり、v∈A, u∈Bの間に対応関係があるときに(v,u)という枝があるような二部グラフです。

次に、ある大きさn/2のS⊂Aが存在して、S中の頂点に対応する頂点の集合T⊂BがSとdisjointであり、かつSとTがそれぞれ連結になるかどうかを調べることで、チョコレートを同じ形に分けれるかどうかが分かります(グラフ中の頂点とチョコレート中の正方形を同一視してますが、分かってもらえると思います)。これは適当に各頂点をS側にいれるかT側にいれるかを全通り試せば良いです。枝刈りの条件がかなり厳しいので計算量はたいしたことはありません。

そんなこんなで150行ぐらいのコードが出来上がりました。サンプルインプットに対しては、非力な僕のノートPCでも実行させた瞬間に答えが出るぐらいの速度が出ています。問題文中に中に空洞は無いと書いてあるのは、ジャッジの意図している解法が実際に切り取り線を探索させるものだったのかもしれませんね。

_ [コンピュータ]

今週末は久々に僕が割合得意とする一発ネタ系自然言語処理プログラムをしていました。おかげ様で結構、納得のいくものが出来てきました。久々に紙と鉛筆ではなく、キーボードと24インチディスプレイで作業していたわけですが、やっぱりプログラムを書くのは楽しいですねぇ。

_ [研究室]

Amazonで異様に評判のいいEnumerative Combinatorics vol1/vol2という書籍を購入。来週一週間も日本を空けるので、その間に読んだり写経したりしようかと。組み合わせ論は数学の中では潰しが利く分野の一つなので出来れば身につけたいものの一つです。

_ [Daily] 近況

久しぶりにblogでも書いてみる。相変わらず元気にやっております。

最近それなりに研究もしていまして、4月終わりは香港に行ったりしてました。7月頭はアイスランドに行く予定。こちらは昔のICPCのワールドチャンピオンも来るみたいで(しかも僕と同じセッション)、やっぱりそういう人はどこ行っても活躍するんだなぁと感じています。色んな学会でちょくちょくICPCのOBの名前を見ます。

研究を少しやってみた感想ですが、何というか先人の研究が膨大すぎて、自分がオリジナリティを発揮する前に先人のやったことをサーベイするだけでも一苦労。しばらく力をためないと継続的に成果を出すのは大変そうです。

_ [ICPC] 模擬国内予選

殆ど運営は東京のメンバーに任せっきりでしたが、僕もジャッジとしてICPCの模擬国内予選に関わっていました。このままだと今年は東大の一強時代になりそうですねぇ。とりあえず彼らに勝ちたければ1000問ぐらい解くのが良いと思います。

_ [イベント] イベント色々

アイスランドに行くのは楽しみなのですが、おかげでGoogle TechTalkだとかICFP コンテストだとかには参加できなさそうです。残念…。

_ [ICPC] ICPC終焉

今、カナダのバンクーバーでICPC世界大会旅行の最後の夜を過ごしています。結果はご存知の方もいるかと思いますが、47位という少々不本意な結果でした。正直言って本来持っている力を出せなかったのですが、一発勝負なのでこういうこともあるのは仕方がありませんね。結果については多少後悔が残りますが、旅行として見ればとても楽しいものでした。

これで僕のICPCライフは終焉を迎えます。これまでの3年間を思い返すと色々なことがありました。最初は大学の友人に薦められて軽い気持ちで参加したのが始まりです。八王子大会の時です。当時はコンテストに興味があったわけでもなく、特に練習もせずに国内予選に参加したのですが、なんとかアジア予選に出場する権利を得ることができました。アジア予選は全く力不足で歯が立たなかったのですが、おかげでそこで自分の能力は大したことは無いということを知ることが出来ました。これはとても運の良いことで、京大の中にいるだけでは、自分の能力がいかほどなのかというのを客観的に見ることはできません。アジア予選に参加することで、やはり自分の能力は大したことがないということを確信することができました。負けず嫌いな性格なので、後はとにかく練習をするのみです。その頃からほかのチームと一緒に練習をするようにもなって、そこそこの結果を出すことが出来るようになってきました。

次の年の国内予選(横浜大会)は万全の気持ちで臨み、海外派遣も狙っていたのですが、結果的には8位などという悲惨な成績を残してしまいました。国内予選が終わった日は、悔しくて悔しくて泣いていたのをよく覚えています。その前の年でICPCを卒業した、即ちGNCとcombatの方々には少し期待してもらっていたのですが、その期待に応えられなかったのが情けなかったです。国内予選の後は、よく叱ってもらい、また励ましてもらいましたが、どうしてこんな辛い気持ちにならないといけないのだろうと苦しみました。この頃が一番コンテストに真剣に臨んでおり、また貪欲だったかもしれません。

結果が悪いとは言え、アジア予選には出れるわけなので、そこで頑張ろうと練習を積んだ結果、アジア予選では国内一位(全体二位)を取ることができました。これは本当に嬉しかった。嬉しかったというよりはホッとしたという感じかもしれません。ここで負けていたら自分は能力が無いと認めざるを得ないですし、国内予選で励ましてもらったのは何だったのだということになるので、背水の陣だったのです。それを何とか勝つことが出来て良かった。結果を残せたこのアジア予選で、僕の中である程度の区切りが付いたとも言えます。やはり結果を気にして戦うというのは心情的にしんどいものなのです。しんどいだけでは何故コンテストに参加するのか意味が分からないので、後は結果は気にせずとにかく楽しもうと考えました。周りからは世界大会ではメダルを取るべきだとか色々言われますが、それはあまり真剣に考えないで、気楽にやることにしました。

世界大会(@東京)は、折角世界中から人が集まっているので、色んなチームに話をしに行きました。パッと思い出せるのは、Warsaw, Saratov, MIT, SJTU, Tsinghua, Cape Town, Adelaide(だったかな？)といったあたり。Cape Townの人とは京都も一緒に観光しました。ちょっと連れまわしすぎて、僕は股関節がいたくなったけれども、彼らは大丈夫だったのだろうか。

その次の年の国内予選(東京大会)は4位という結果でした。前の年と比べると、1位と同じ問題数だったし、それなりに自分の力を出せたので気分は楽でした。というより意識的に気楽に考えたとも言えるでしょうか。

そしてアジア予選。これがもう半年も前のことだとは信じられませんが、中国に負けることもなく、本当の1位を取ることができました。最後の1分でsubmitした問題がYesとなり、逆転したのはあまりにも強烈な記憶です。この時も本当にうれしかったなぁ。努力していれば、たまに報われることもあると実感しました。

アジア予選が終わったあたりで、少々心がICPCから離れていったような気がします。練習は相変わらず続けていましたが、常に最適解が求まるタイプの問題に飽きてきてしまったのと、それまでの疲れが出てきたのでしょうか。どうしても以前ほどの熱意がICPCに対して出ないなと感じていました。どちらかというと研究とか仕事とかに意識がいってしまう。ICPCに手を抜く気は無かったのですが、こればっかりはどうしようも有りません。そんな状態で世界大会(@Banff)に参加したので、結果が振るわなかったのはある意味必然なのかもしれません。

3年間ICPCに参加して、得たものは凄く大きかった。確実にアルゴリズムを考える力は上がったし、プログラムを書く能力も上がった。いろんな人と出会うこともできた。PFIという会社で働く機会もえることができた。海外旅行もすることが出来た。これはICPCに参加しなければ、きっと得られなかったものばかりです。以前オープンソースソフトウェアにかかわっていた時も色んな経験をさせてもらいましたが、ICPCも良いものです。若い方々にはぜひお勧めします。

良い面もありましたが、上の文章にところどころ書いているように精神的にしんどい時期もありました。僕のチームはICPCにどうしも参加したい！という人が集まったチームではなくて、最初に友人だからという理由で作ったチームです。なので、どうしてもICPCに対する思いに差がある。先輩方には期待されるので、それを僕はどうにかしてチームの力に反映したい、けれどもそれが伝わらない。そんな雰囲気は最後の最後まで有ったように思います。しかし逆に考えると、僕の我儘に3年間も付き合ってくれたチームメンバには感謝せざるを得ません。彼らがいなければ、世界大会に2度も参加する機会には恵まれなかったと思います。そう思うと、これ以上何かを望むなんてことは出来ません。

これで僕のICPCライフは終焉を迎えます。僕自身としてもコンテスタントとしてICPCに参加するのはそろそろ潮時と思っているところです。これからはおそらく研究とPFIでの仕事に精を出すことになるでしょう。ただICPCは僕を育ててくれた大会なので、何とかして恩返しはしたい。コーチとして、OB/OG会としては関わっていきたいと思います。

後輩の皆さんが、僕の文章を読んで何かを感じていただければ幸いです。今回の世界大会中の細かい話は、また別の機会に譲ります。それでは。

_ [ICPC] ACM/ICPC World Finals