旅まとめ

ESA2008 と NLP week（言語処理若手の会、言語処理研究会）に行ってきました。
随時学会の内容をアップする予定でしたが、旅中はなんとなく更新しませんでした。

記憶も曖昧になっているので箇条書きで

・ESA2008 @ カールスルーエ
カールスルーエはドイツの南西にある比較的小さな街だが、街並みはきれいで街中を走るトラムが便利だった。ビールはコンスタントに飲んでました。発表内容自体は、ちょっと違う分野になるとついていくのが大変

自分の発表 "An Online Space-Efficient Algorithm for Searching the Longest Match String" (予稿: pdf 発表資料: ppt pdf)はスライドが化けたが、まぁ発表して、詳しい人からとその後ちょっと議論できた．

気になった発表は（論文はタイトルで検索すると大抵でてきます）
"Better and simpler approximation algorithms for the stable marriage problem" ベストペーパー。安定結婚問題の最大マッチング近似を簡単なアルゴリズムで改善した
"More Robust Hashing: Cuckoo Hashing with a Stash" Cuckooで逃げ場所(Stash)をほんの少し用意しておくだけで作り直す確率はものすごく小さくなる．解析が激しい
"Bloomier Filters: A second look" Bloom Filterでキーがあるかどうかだけではなく，関数もサポートするようなもののより簡単な解析 途中から数論っぽい議論がでてきて、違う世界にとんでいった
"Succinct Representations of Arbitrary Graphs" グラフの簡潔表現の（ほぼ）決定版？　今までは平面グラフとか分割が簡単なグラフに対する簡潔表現が提案されていたが、この研究では、全てのグラフに対する簡潔表現を提案．実用的なところへの工夫はまだか。グラフの冗長性とかはまだ残されている
"A Practical Quicksort Algorithm for Graphics Processors" GPS上でQuick Sort．現時点で大部分のデータに対して一番最速
"Randomized Competitive Analysis for Two-Server Problems" 乱拓アルゴリズムを使って最悪値を大分減らせるという話．その後いろいろTwo-Server問題について詳しく聞かせてもらったがディスクのデフラグとかがまさにこの問題にあたるらしい．
"Flexible Path Planning Using Corridor Maps" 招待講演。ゲームの研究で（ゲームの研究はヨーロッパとかではかなり真面目にやられているらしい）、CGがリアルになるにつれ、より自然な振る舞いが重要になってきている。で、特に大量のキャラクターを自然に動かすのが大変。これは、A地点からB地点まで障害物や人を避けて外乱に対してロバストに自然に動くことを現実的な計算量で求めたい．これは、あらかじめCorridor Mapというのを作っておくと非常に効率的に求まる．発表者が発表中に手品をしていた．

アルゴリズム系の学会は、発表のスタイルが自然言語処理とか機械学習と違って面白いですね。下限をまず示して、上限は実際にアルゴリズムを構成して調べるとか。問題をどんどん拡張して作っていくところとか。

・NLP若手の会 @ 熱海
オーバーブッキングのためドイツからの帰国が遅れ家についたのが日曜の夜になり、次の日からNLP week．ポスターやら発表資料を作り（確信犯的に）寝坊した．
自分は今まで作ってきたtxやらbepやらollを学会とかで発表したことないなぁということで、広告っぽく宣伝してきました．pdf(poster)．みんなでかいデータを扱うのに困っている人が多くて、実際に使ってるという声も頂いてうれしかったです
他の方の発表もツールやらコーパスやら、ちょっと論文にするには難しいけど、実際の場面では重要なものを多く発表されていたような気がします。こういう場所は重要だと思います。

・NL研 ＠熱海
若手の会に続いてNL研．自分の発表は4年ぶり．
私は、"全ての部分文字列を考慮した文書分類" (予稿 pdf 発表資料 ppt pdf）というタイトルで発表．接尾辞配列、L1正則化、Graftingなどの合わせ技になっております．

こういう学会やらシンポジウムでは重要度としては、発表したり発表内容を聞くのが1/3ぐらいで、2/3がいろいろな人と出会い交流を持つことにあるとおもいます。今回もいろいろな人と出会いより交流を深めることができました。
しばらく肝臓を休ませます。