2011年12月19日

面白CS論文紹介

この記事は、今年読んだ面白CS論文紹介カレンダー( http://bit.ly/vKrdxq )6日目の参加記事です。CSの中でも、ちょっと数値系に偏った記事になります。

Quasi-Newton Methods for Markov Chain Monte Carlo


http://homepages.inf.ed.ac.uk/csutton/publications/hmcbfgs.pdf

これはなに?



メトロポリス法(ボルツマンサンプリング)はCSにいたら一度ぐらいは聞いたことがあるかとおもいます。TopCoderのマラソンマッチに出たことがある人にはこれを用いた焼き鈍し法がおなじみではないでしょうか。また、機械学習タスクを楽しまれる淑女紳士の皆さんには、メトロポリス法は非常になじみ深いものかと思います。メトロポリス法は、構造空間を広くサンプルし、かつ目的関数の値が充分に低い場所をまとめて拾ってくるには便利な方法です。

しかし、メトロポリス法は、対象が高次元だったり目的関数の異方性が強かったりする場合には、なかなか効率よく空間をサンプル出来ません。この論文で紹介するHMCBFGS法は、こうした問題に対処する新しいサンプラーを提唱しています。

アイディア



異方性が問題になるなら、異方性が消えるように空間をねじ曲げてスケールしてしまえばいいじゃないか……というのが答えになるわけですが、単純に目的関数をスケールして正しいサンプラーを組み立てることは非常に難しい作業です。著者はHamiltonian Monte Carloという力学系を用いたサンプラーの先行研究をまず紹介します。実は、統計力学では、質量をどんなに適当にいじっても、無限時間が経った後の系の確率密度は同じであることが保証されていますから、質量に異方性を入れてスケールすれば、異方性をうまく消しながら空間をサンプルすることが可能になります。あとは、良い質量の決め方を探すだけです。

出会い



この論文は、NIPS2011のaccepted papersを眺めていたときに出会いました。タイトルで一目惚れした論文です。

なんでそんなに気に入ったのか



一つには今の自分の研究が力学系だし良いサンプラーを必要としている、というのがあります。もう一つ、単純ながら置き換えの効かないメトロポリス法を倒せる可能性のある候補である、というのがあります。メトロポリス法が作られたのは実に1953年ですから、50年も生き延びている優秀なアルゴリズムなわけです。これに勝てるかもしれない、って聞くと、みなさんワクワクしませんか?

Fixed block compression boosting in FM-indexes


http://arxiv.org/pdf/1104.3810

これはなに?



FM-indexという、文字列を圧縮したまま検索したり、元の文を復元したりできる不思議なデータ構造があるのですが、そのきわめて簡単で且つ圧縮率の高いな実装方法を見つけたよ、という話です。FM-indexの実装においては、文字の出現頻度だけを見て圧縮するwavelet treeという高速で実装も単純な方法が知られています。しかし、この手法では文字の出現頻度しか見ないため、文章のなかでたとえば頻出単語が存在する場合、圧縮率がもっと伸ばせるのに……という事態が起こりえます。

アイディア



この論文では、まずFM-indexを構成する要素であるBurrows-Wheeler Transform(BWT)を適切にぶった切れば圧縮率が理論上界まで伸ばせることを示し、しかる後に適当にぶった切っても圧縮率が大して悪化しないことを示します。

中身については、PFI社の岡野原さんもちょっと触れていますのでご参考まで。
http://www.slideshare.net/pfi/succinct-data-structure-for-analyzing-document-collection

出会い



同じくSPIRE2011のaccepted papersを眺めていたときに見つけました。Juha Karkkainen, Gonzalo Navarro, Veli Makinen その他の各先生の著作はストーキング対象です。

なんでそんなに気に入ったのか



「やぁみんな。複雑な方法で今まで、k次経験エントロピーサイズまで圧縮する面倒な手法を実装してただろう? もうそんなことは必要ない。今日からは、BWTの文字列を、ただぶった切れば良いんだ(意訳)」って言われたら、そりゃ惚れますよ。

Accelerating nearest neighbor search on manycore systems


http://people.kyb.tuebingen.mpg.de/lcayton/papers.html

これはなに?



「点の集合が与えられたとき、その点に一番近い点を求めなさい。」はい、よくある最近点・最近点対問題です。この問題を解くのには、k-D treeなどといった木のデータ構造を作成するのが普通です。これは確かに効率は良いのですが、並列化向きでないという問題があります。

アイディア



点の中からランダムに、代表点を複数抽出します。代表点の近くにある点を、順番に決まった個数取り出し、最長距離を覚えておきます。この処理はきわめて容易に並列化できます。これをインデックスとしましょう。

クエリが来たら、代表点との距離をまず測り、最長距離を用いて枝狩りをして生き残った候補との距離を測ります。この処理もまた、きわめて容易に並列化できます。これで近い順に点を出力すれば終わりです。

出会い



この問題を解く、state-of-artな方法を探していたときに見つけました。

なんでそんなに気に入ったのか



原理単純、実装単純、それでいて理論的にも実際にも優秀な性能のためです。SIMD命令を手で加えて高速化したANNとの速度比較を実際に行ってみましたが、シングルコア・マルチコア共に本手法の方が高速だったので、惚れました。行列積さえ実装できれば良いのでGPGPUでも動かせます。また、手法が単純なため容易に拡張できる点も素晴らしいです。ちょっと考えれば代表点を階層的にしてvan Emde Boas tree作ったりとか、面白そうな遊びを思いつきますよね?



ちょっと連続系的な話に偏ってしまいました。次は @kmizu さん、よろしくお願いします。/h2
posted by chun at 22:50| 日記