« August 2008 | Main | October 2008 »

2008.09.27

旅まとめ

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がいろいろな人と出会い交流を持つことにあるとおもいます。今回もいろいろな人と出会いより交流を深めることができました。
しばらく肝臓を休ませます。

| | Comments (12) | TrackBack (0)

2008.09.13

明日から1週間ほどドイツのカールスルーエで行なわれるESA 2008(ALGO 2008)に行ってきます。

帰って来て翌日から1週間ほど、熱海で行なわれるNLP若手の会とそれに続けて行なわれる自然言語処理研究会(NL研)に行きます。

自分の発表資料やら他の研究紹介などは随時していきます。

| | Comments (2) | TrackBack (0)

論文読み会

T-PRIMALの上半期の論文を読む会(ICMLが中心だがそれ以外もあり)で、先日ここでも取り上げた

Learning Bilingual Lexicons from Monolingual Corpora,ACL2008 元論文 [pdf]
を紹介しました [ppt], [pdf]

他の人に説明しようとなると、普通に読むより理解度は高まるわけですが、今回は正準相関分析(二つの特徴ベクトルがあって、それらの相関を求めたい場合)あたりの理解が深まりました。

他の方の発表も面白かったです。が、後半はちょっとばててしまいました。

ネタはいくらでもあるもんだなぁ

| | Comments (0) | TrackBack (0)

2008.09.08

博士課程

昨晩、学部時代に入っていたサークルのOB会がありました。
OB会といっても、集まった中で、私達の代が一番上の世代で、若い人達から非常にエネルギッシュなパワーをもらいました。

ふと、私が学部1年の時に博士課程の人がたまに来ていたのを思い出しました。
とても面白い人で漠然と博士課程とはこういうものなのかぁと思ってましたが、逆の立場になるとは。

その場で唯一博士課程に進んでいた私に対し、博士課程について、いろいろな質問をもらいました。進学するかどうかを迷っている人もいて、ちょっと酔ってましたが、真面目に答えました。

現在、巷で氾濫している博士課程の情報はかなり悲観的な状況のようです。
(例えば、博士課程で検索すると、就職、行方、お金などなどいろいろ悲観的な情報で氾濫しています。博士100人の村とかも有名ですね)

私が置かれている状況(コンピュータ系の研究、個人で研究できる、研究室はそこそこ大きい)ではどんな感じなのかを簡単に説明してみます。先程の3つの条件が下記のことは変わって来ると思います。例えば研究室によってもだいぶ違いますし、実験が中心かどうかでも全然違うと思います。あくまで一例ですが参考になれば。

まず、就職先です。
学校に残って研究を続ける場合は、学校のポストは限られているので、やはりポストドクターになる人が多いです。研究分野が狭い場合は更に長い道のりになるかもしれず、違った分野に移ることも考えてる人も多いです。
企業に行く人の場合は、企業の研究所に行く、普通に就職する、自分の技術を生かすべく、ベンチャーに行く、興すなどです。

工学系ということもあり就職先が全く無くて困っているという人は僕の周りではいないようです。
自分の研究が生かせるかは分かりませんが、少なくとも食ってはいけますし、自分の研究活動で培った基礎力が他の分野で生かせる場合も少なくありません。たとえ、研究に残ったとしても同じ分野だけで生き続けていくことは難しく、変えていく必要があると思ってます。博士でてもあと、30年ある。

海外の博士課程/卒の人からも話を聞いたことがありますが、アメリカやヨーロッパでも状況は大体同じようで、どこでも良いアカデミックポストを得るのは大変です。みんなグーグル、MSに行くのも同じです。ばりばり理論ばかりやっていると思った人がプログラミングとかシステムにもすごく強く「そうしないと、いい仕事につけないからね」と言ってたのが印象的でした。

次に、お金です。
これは一番シビアな問題だと思います。奨学金、学振、研究室からの援助(プロジェクトメンバーとして雇ってもらい仕事を少しする)、バイトなどいろいろ工面する必要があります。奨学金を借り続けて卒業と同時に数百万のお金を返し始めるという人も少なくありません。

私自身も、これは一番懸念の問題だったのですが、博士行くかもしれないということで、いろいろ準備しました。親は定年退職間近で、修士からは完全自腹になるのは覚悟してましたから(本当は仕送りをしないといけないくらいで、申し訳ないですが、それはいつか)、学士の頃から、貯金をしようと努力をしてました。私の場合はその後に幸いにも未踏プロジェクトや、ベンチャー企業でのバイトなどである程度の貯金を作れました。今も、その後興した会社からお金をもらってることもあり、奨学金を借りなくてもやれてます(学士の頃借りていた奨学金を返すまでにはいたっていないが)。

厳しいですが、お金を稼げる見込みが無く、良い奨学金ももらえなさそうということなら、働く道を考えた方がいいと思います。企業でも面白い研究や仕事をしているところはたくさんあるし、何より自分が大変だと思います。

#奨学金については、いくらあっても足りることは無いと思いますし、そのために社会がどうすればいいかは考えなきゃならないところだと思います。企業による奨学金はこの解決策の有力な候補の一つです。例え、それが青田刈りであってもいいと思います。入ってからの社会人博士もいいですね。

雑用が多いか、という質問については、まぁ、そうだと思いますが工夫次第で減らすことはできると思いますし、博士課程に限らず実社会に出ても同じ問題に遭遇するだろうとは思います。どうやって効率よくやるか、仕事が集中的に振ってこないようにするか(笑)などは年月がたつにつれうまくなった気がします。

博士にいっても博士号をとれるとは限らないではないか、ということについては、そうだと思いますし、私自身もとれるかは分からず、論文が連続で落ちまくった時は不安になったこともあります。
上の代や周りを見ている限りでは、真面目に研究を継続的に続けられた人は大抵とれています(しかし、そのような場合でも研究が不幸にもうまくいかないかず、そのまま修了する人もいます)。これについては、正直博士号が無くてもあまり変わらないと思います。どう過ごしたかが重要のように思えます。

この、真面目に研究を継続することは難しいことです。最近の研究では共同作業も多いですが、ある面では孤独との戦いも多くあり、精神的にもまいってしまうことが少なくありません。また、真剣に取り組めば取り組むほど、それが認められない時のショックは大きいです。

この不安を克服するには、研究を楽しむことに尽きると思います。世界初、世界最高、前人未到、には心を躍らされますし、他の人のすばらしい研究を見て刺激を受けるのも一つです。やる気を出すには自分で課題を見つけてくるのも重要だと思います。この研究がどのように社会で役立つかを想像してもいいかもしれません。

研究を続けていくとどうしても内に内に行き、うまくいっているときは突き進めばいいのですが、まずくなると途端に行き場がなくなり苦しくなります。外の世界とのつながりが重要で、外の世界へのアウトプットを多くする必要があると思います(そういうわけで私も意識的に専門分野のことをブログで書くようにしてます)。

--
実際何やってるのかについては、私の場合は次の通りです。

研究室ミーティングが大体週2回あり、そのほかは基本的に自由に時間を割り振れます。私は会社の営業とかもあり流動的ですが、大体午前中は論文をサーベイ(関連する研究、特に競争相手となる研究をざーっと調べる)したりメールを処理したりします。午後は自分の研究内容をプログラミングして実験したり、論文を書いたりします。週2ぐらいで、ソファースペースでお茶を飲みながら、ゆるーく自分のアイディアや他の人のアイディアを突っ込みあうのも重要な作業の一つです。更に研究室の外で共同研究している人も何人かいるので、そうした人たちとチャットやらメールで議論します。
学外の面白そうな研究会/勉強会も見つけて片っ端からいきます。大体(研究関連で)週1~2ぐらい外に出てます。アイディアとかは大抵人との出会いでうまれてきます。

そして、私の場合の特殊ケースですが、夕方ぐらいに会社に行きそれから、会社で終電まで仕事をします。
でかい本を一気に読むとか仕事をまとめて仕上げたい場合や、気分を変えたい場合は喫茶店やらに篭ります。見つけないでください。

昔は土日もプログラミングや論文読みをしていることも多かったのですが、最近は締切間際以外は意識的にそういうものに触れないようにして、全然関係ないことに熱中するようにしてます。その方が結果的に生産性が高いみたいです。

このボケーっと考えていろいろ試すのは、ものすごく時間がかかり、あっという間に時間が過ぎます。時間とエネルギーを湯水のようにジャブジャブ注がないと独創的なことはできないと誰か言ってましたが私もそう思います。会社でそういうことができるところはそうそうなくて、博士過程(ポスドクもある程度そうかな)が最後のチャンスだと思います。

--
多くの人と付き合うにつれ、若いうちに遊びであれ、仕事であれ、研究であれ、何かに打ち込めたかどうかが、その後の人の深みに関係していると思います。博士課程は研究に打ち込めるチャンスです。
私自身、研究が本当に面白くなってきたのも博士に入ってからでした。あとまだ1年半ありますが、いい研究活動をできたらと思います。

大学・研究室は違いますが、生駒日記にも、更に具体的にいろいろと書いてあります。

| | Comments (57) | TrackBack (0)

2008.09.02

透過的データ圧縮

可逆データ圧縮分野で、現在研究が盛んな分野の一つが、データを圧縮した状態のまま定数時間でランダムアクセスをサポートするデータ圧縮方式です(word RAMモデルでO(log n)サイズの復元が定数時間)。

これは、データをあたかも圧縮していないかのように扱えるため、透過的データ圧縮/構造と呼ばれています(英語だとまだ決まってない?)。

例えば1GBのデータを圧縮した状態で、途中300MB目から4Byteだけ復元しようというのが定数時間で実現できるわけです。これは理論的にもかなり強いことをいっていて,例えば今あるデータ構造やアルゴリズムが、O(T)時間である問題を解けるというのがあったら、それを全く同じO(T)時間のままデータ構造を圧縮し作業領域量を減らすことができます
(一応データ構造に対し読み込み操作しか無い場合。書き込みもある場合はまたちょっと面倒になる)

このデータを圧縮したまま扱う手法は古くからいろいろ試されています。一番簡単には、データを小さなブロック(例えば16KBとか)に分け,それぞれを独立に圧縮し、復元する時は関連するブロックだけ復元するという方法です。しかしこのような方法だとブロックサイズが小さくなるにつれ圧縮率は劇的に低下し、ブロック全体を復元するのもやはり大きなオーバーヘッドです。

私自身もずっと前にこの問題に取り組んだことがありました。
(2003年の未踏ユースあたりの発想でやったのがそれで、成果の一部は論文など発表しました, DCC 2005 [pdf]
これは、データ全体から予測接頭辞木を構築し、それを利用し次の文字を予測し圧縮するものです。通常のPPM(Partially Pattern Matching)が動的に予測接頭辞木を構築するのに対し、私の方法はデータ全体を見てから構築し、予測接頭辞木は別に保存します。木を静的に持っておくのでStatic Huffman法に対応して、Static PPM法と名づけました。
同じ予測モデルをどの位置でも使えるので、ブロックサイズをかなり小さくしても圧縮率は低下しません。実際ブロックサイズが256byte程度でbzip2と同じぐらいのデータ圧縮率でした。しかしこの手法は復元時に予測接頭辞木を保持しなければならない他(データ全体の数分の一のサイズだが)、復元も実用的には速いですが定数時間は保障されてません。

また、bzip2で使われているBurrows Whleer's変換(BWT)を利用したデータ圧縮でも、ちょっと工夫することで圧縮したまま一部分を復元することが可能ですが、同様に定数時間を実現するのは難しい状態でした。BWTの場合入力時連続していた文字列が変換後はいろいろな場所に散乱してしまうので復元時に定数箇所へのアクセスで復元することが難しかったためです。

このように、圧縮率を限界まで達成して(任意のkに対しk次経験エントロピーに漸近)、定数時間でアクセス可能なデータ圧縮は達成できるのか分からない状態がずっと続いてました。

そうした中、2000年以降、圧縮索引に牽引される形で簡潔データ構造の研究が進み,それらの成果を使って透過的データ圧縮は実現できるというのが分かりました(この仕事と圧縮全文索引で定兼先生はIBM科学賞を受賞されてます)。
K. Sadakane and R. Grossi, "Squeezing Succinct Data Structures into Entropy Bounds", SODA 2006 [pdf]
これは、(すごく間単に言えば)LZ78法をベースにしており、LZ78法で抽出されたフレーズ辞書からなるTrieをを簡潔データ構造で保存し、これを長いフレーズと短いフレーズに場合分けして、参照することで定数時間アクセスでの復元を実現しています。

できるというのがわかって以降、違う手法でも透過的データ圧縮が実現できることがわかってきました(不思議なもので、できると分かったら続々と出てくる)。
Rodrigo Gonzalez and Gonzalo Navarro, "Statistical Encoding of Succinct Data Structures", CPM 2006, [ps.gz]
P. Ferragina, R. Venturini. "A simple storage scheme for strings achieving entropy bounds", SODA 2007, [ pdf]

これらは、基本的にはデータを小ブロックに分け、それらを全体の統計量を用いて圧縮し、各ブロックには簡潔データ構造などで索引をつけておくことで、定数時間でアクセスできるようにするものです。

圧縮率については入力T[1...n]のk次経験エントロピー(k-1文字前までを使って次の文字を予測した時のエントロピー)をH_kとした時、nH_k + O(n / logn) bit ぐらいで保存できます。この第2項が実は結構厄介で、(nH_kに対し結構でかかったりします。

一般にブロックサイズがBの時にO(n/B)のオーバーヘッドでO(B)時間というトレードオフが限界だと思われていたのですが、つい最近出た、次の論文ではこの限界は破れるということが示されています。
Mihai Patrascu, "Succinter", FOCS, 2008 [pdf]
面白いことにブロック中の要素へのランダムアクセスは、ブロック毎に1bitのオーバーヘッドでは、ブロック全体を復元しないと実現できないが、2bitのオーバーヘッドならば、O(logB)時間でランダムアクセスができることが示されてます。

#(先程までの透過的データ圧縮も、一番小さいブロックサイズがO(log n)で、O(n/logn) bits作業領域量のオーバーヘッドという関係。ブロックサイズがεlogn bitだと、表引きできるので、一応定数時間)

---
次はこれらをどのように実用的なものにしていくかが面白そうです(私もやってます)。
興味がある方は是非いい実装方法を考えてみてください。

| | Comments (988) | TrackBack (0)

« August 2008 | Main | October 2008 »