面白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

Hello, javascript

あなたはホームページを運用するうちに、ページ来訪者と大いに語らう場を作りたくなりました。そこで、ブラウザ上で動くチャットルームを作ることにします。チャットルームには発言者の名前と、最新から20個の発言が順に表示されます。
まずはデータの格納先を定義しましょう。ユーザーの名前と、投稿テキストを格納する先を作ります。

// chatは投稿者名とテキストからなる
db /chat : {name: string; text: string}

Opaのデータベースは、実はデータベースに格納された過去値をすべて覚えています。そのため、これだけで「最新のn件」が取得可能です。この辺の仕様は誤って上書きしたデータを簡単に復元できるなど便利なことがある反面、データ容量や個人情報保護などの観点から問題が起きることもありますので、運用の際には注意してください。

  recents = Db.history(@/chat, 0, -num_print)

これで最新のnum_print件が取得できます。

ではまず、これを使い、チャットの表示更新のところを書いてみましょう。まず、得られたrecentsをxhtmlに変換します。

update_chat() = 
  // 最新の20件を取得
  recents = Db.history(@/chat, 0, -num_print)
  // 発言をxhtmlに変換
  lines = List.map((x -> <div class="line">
                           <div class="user">{x.name}:</div>
                           <div class="text">{x.text}</div>
                         </div>), recents)
  // 表示！
  Dom.transform([#chat <- lines])

あとはDom.transformで<div id=#chat>に書き出すだけです。

「え、この処理はどこで実行されるの？」と疑問に思う方もいるかと思います。答えは、ブラウザとwebサーバー両方です。Dom.transformなどの処理はブラウザでjavascriptとして実行され、Dbアクセスはwebサーバーで実行されます。Dbアクセスはブラウザ側のjavascriptからRPCとして呼び出され、実行されます。プログラマはこのRPCを個別に書く必要が全くありません！　これはOpaの非常によい特性であると思います。この機能を使う際にはCSRFに注意してください。見知らぬ人に「こんにちはこんにちは！」などと書かれることのありませぬよう。

最後に、ページを表示し、ボタンを押したら発言を更新するようにしましょう。これでとりあえず、手動更新のチャットの完成です。

// chatは投稿者名とテキストからなる
db /chat : {name: string; text: string}

num_print = 20

update_chat() = 
  // 最新の20件を取得
  recents = Db.history(@/chat, 0, -num_print)
  // 発言をxhtmlに変換
  lines = List.map((x -> <div class="line">
                           <div class="user">{x.name}:</div>
                           <div class="text">{x.text}</div>
                         </div>), recents)
  // 表示！
  Dom.transform([#chat <- lines])

submit_chat() = (
  name = Dom.get_value(#name)
  text = Dom.get_value(#text)
  // textが空でなければ発言
  do (
    if text != "" then
      do /chat <- {~name; ~text}
      Dom.clear_value(#text))
  // textの中身にかかわらず更新はする
  update_chat()
)

show_page() =
  <div>
    <input id=#name />
    <input id=#text onnewline={_ -> submit_chat()}/>
    <button type="button" onclick={_ -> submit_chat()}>投稿・更新</>
  </>
  <div id=#chat onready={_ -> update_chat()}></>

server = Server.one_page_bundle("Chat",
  [@static_resource_directory("resources")],
  ["resources/css.css"], show_page)

(次回に続く)

Hello, CSS

こうしてできたページを見てみると、微妙にweb0.9感が漂い、web1.0には何かが足りないことに気づきます。いったい何が不足しているのでしょう？

そうだ、web1.0時代はフォントの色やサイズを変えて遊ぶのが流行っていたのでした。黒背景に白文字・センタリング・フォントサイズ+4。早速これを実装してみましょう。

Opaでは、cssなどのファイルも、できるだけ実行ファイルに含めるような設計になっています。これは、scpなどで１ファイルだけコピーすれば設置が終わるようにという配慮です。細かいことですが、大量のサーバーに配置する際も設置に失敗して404ということが無くなりますし、テストサーバーから本番系に移設する際にも移行途中でのミスは起きません。代わりに、設置時にcssを書き上げておかねばならず、変更に伴い再コンパイルが必要になります。もちろん、開発中のことも考え、cssをon-the-flyで記述したり、ディスクから読むようにしたり、といったことも可能になっています。

server = 
  Server.one_page_bundle("Hello",
    [@static_resource_directory("resources")],
    ["resources/css.css"], hello)

/*
  resources/css.css
  */
body {
    background-color: #000000;
    color: #FFFFFF;
}

p {
    text-align: center;
    font-size: 32pt;
}

無事にソウルフルなページになりましたでしょうか？　これで<marquee>タグあたりを付けるとさらにweb1.0っぽくなりますが、悪ノリはとりあえずこの程度にとどめておきます。

＃ところで上のCSSを適用すると、Opera11.50でタブ全体ではなく文章の部分だけが黒背景になるのですが、この原因をご存じの方はいらっしゃいませんでしょうか……？

(次回に続く)

Hello, transaction

さて今回初めてデータベースを使ったわけですが、このカウンタには問題があります。ユーザーがきわめて多くなると、並列実行の問題から正常にカウントアップされないかもしれません！
このページが1000ページビュー/秒を達成したときに備え、トランザクションを用いてプログラムを書き直しましょう。

トランザクションを用いるには、２つの操作が必要です。
・DBに名前を付ける
・Db.transactionを用いてDBにアクセスする

DBに名前を付けるには、database文を使います。

database counter = @local("./hogehoge")

この場合、webサーバーを実行した際のカレントディレクトリ上に、hogehoge_から始まる一連のファイルを作成し、データベースをそこに保存する、という意味になります。

トランザクションを用いるには、トランザクション処理の開始から終了までをまとめた関数を作る必要があります。以前のincr_countをそのままリネームしてatomic_incrとしてしまいましょう。後はDb.transactionにDB名と、トランザクション処理関数を与えるだけです。

  result = Db.transaction(counter, atomic_incr);

トランザクションの実行が成功すると、実行結果が{ some=結果 }という値になって返ってきます。一方、トランザクションの実行途中に別のプロセスがDBの同じ値を書き換えてしまった場合、トランザクションの実行は失敗し{ none }という値が返ってきます。この値を取り出すには、match文を使います。

  match result with
    | { none } -> incr_count() // トランザクションをやり直す
    | { some = result } -> result

なお、{ some = result } -> result なんて書くのはかったるい！　という人のために、~{some} -> someという構文が用意されています。~{some}は{ some = some }の糖衣構文です。

これで、あなたのカウンタの1000ページビュー/秒対応が完了しました。あとは中身を充実させるだけですね？

database counter = @local("./counter") // DBに名前を付ける
db /counter/cnt : int // DBの"/counter/cnt"はint型

incr_count() = 
(
  result = Db.transaction(counter, atomic_incr);
  match result with
    | { none } -> incr_count() // トランザクションをやり直す
    | { some = result } -> result
)

atomic_incr() =
(
  c = /counter/cnt;
  do /counter/cnt <- c + 1;
  c + 1
)

hello() = 
  <p>
    あなたは{incr_count()}番目のお客様です。
  </>

server = 
  Server.one_page_server("Hello", -> hello())

(次回に続く)

Hello, counter

Web1.0時代は、「あなたは○○人目の来訪者です」というカウンタをつけるのが流行っていました。
このチープ感あふれる仕組みを含むページを作ってみましょう。

OPAには組み込みのデータベースがあり、dbの後に続けてパスを指定することでデータベースの構造を定義できます。データベースには「型」を指定する必要があります。カウンタはどう考えても整数ですから、整数を表すint型を指定しましょう。

incr_countは、データベースの値を取ってきて、1増やした値をデータベースに入れ、増やした後の値を返す手続き（opaではこれを関数と呼びます）です。あとは、incr_count()を呼ぶたびカウンタ増えるよぽぽぽぽ〜んという寸法です。簡単ですね？

データベースの初期値はどうなるか、気になる人も居ると思います。データベースの初期値は、型によって決まります。intの場合は0が入りますので、このdbの値は0からスタートします。1増やした後の値を返していたのはこういう理由からです。

あとは、ソースファイルをコンパイルすれば、サーバーができあがります。繰り返しますがopaのデータベースは組み込みですので、ライブラリを持って行ったり、DBの設定をする必要はありません。

この実装を見て「あれ、ロックは？」と思った方。ごもっともです。次の回で詳しく説明します。

db /counter : int

incr_count() = (
  c = /counter
  do /counter <- c + 1;
  c
)

hello() = 
  <p>
    あなたは{incr_count()}番目のお客様です。
  </>

server = 
  Server.one_page_server("Hello", -> hello())

（次回に続く）

Hello, OPA

プログラミング言語を遊ぶ以上、まずは何はともあれHello, Worldです。OPAで書かれたプログラムはコンパイルされ、単体でサーバーとして動作する実行プログラムを出力します。

// hello.opa
hello() = 
  <h1>
    Hello, World!
  </>

server = 
  Server.one_page_server("Hello", -> hello())

このファイルをhello.opaとして保存し、

$ opa hello.opa
$ ./hello.exe

とするとlocalhost:8080にwebサーバーが起動します。ページが見れましたでしょうか。Web0.1時代の開幕です。

(次回に続く)

Web1.0で遊ぶOPA

OPAをご存じでしょうか？ OPAはMLstateという会社が開発したweb開発用の言語です。
わたしはこのOPAがかなり気に入ってしまったので、これから数回にわたり、ちまちまと紹介記事を書こうかと思います。
といっても、わたしはあまりwebページの作成経験がないので、どちらかというとWeb 1.0的なテーマをネタに、サンプルを作ることになりそうですが。
わたしの思う、OPAの良いところリストは以下の通りです。
・パターンマッチ
・パターンマッチ
・パターンマッチ（大事なことなので３回言いました）
・代数型と、それと親和性の良いDB
・型検査（＋推論）
・サーバー側とクライアント側を同一の言語で書ける
これからのシリーズで、この特徴をいくつか見ていければ良いかなと思います。よろしくお願いします。

• Hello, OPA
• Hello, counter
• Hello, transaction
• Hello, CSS
• Hello, BBS

ICFPC2011

AIの挙動とかは後でチームの誰かが書いてくれるだろうし、覚えている限りでどういう戦い方をしたのか記録しておこうと思う。

続きを読む

続：Amazon Clusterインスタンスで計算

震災から2週間が過ぎました。
まず、今回の震災で被害に遭われた方々、またご家族が被害に遭われた方々にお見舞い申し上げます。

被災地域直接ではありませんが、震災の影響範囲に私なりに少しでも出来ることをと考え、この記事を書くことにしました。
ご存じの通り、現在の東日本では電力状況が切迫しており、輪番停電が実施されております。
これは、計算機クラスタを日常的に研究に使う者にとっては非常に厳しい状況です。
各研究室で所有しているクラスタも、節電と輪番停電のため動かせない状況が続いていると伺っています。
また、外部計算リソースについても、現在の日本の外部利用可能な計算機の状況を@plus7さんがブログで纏めて下さいました。これはほぼ壊滅的と言って良い状況です。
そこで、本記事ではAmazon Elastic Compute Cloud (EC2)を使って、即席計算リソースを作る手順を記述してみようと思います。操作環境はLinuxを想定しています。
続きを読む

2010年を振り返る

2010年は卒業含め色々と大変な年でした。

1・2月はほとんど卒業に向けての何かで過ぎていった記憶があります。3月には4年過ごした部屋を引き払って京都に移り住みました。引っ越し前後のスケジュールが悲惨きわまりない状況になっていたため、ボロボロになりながら京都に到着、京都に着いてからもさらに1日大変な目にあったのが良い思い出です。4月からは京都の宇治（京大化研）でポスドクを開始。いきなり研究室の引っ越しをしたりと色々大変でした。5月からは事情により大学の仕事がデスマ進行になってしまい（ところでマーチ＋進行って頭痛が痛い？）大変なことに。9月までずっと繁忙期でした。まぁこの時見つけたネタをいま色々と料理している状況なので、悪いことばかりではありません。繁忙期と言いつつ6月には休暇を取って東京に行きICFP contestに参加。チームのメンバーが凄すぎて生きているのが辛い(TM)状況に。優勝を勝ち取ったものの、ぶっちゃけ僕が居なくてもこのチームは取れたと今でも思ってます！　7月8月は繁忙期継続。9月-10月には優勝したおかげでICFPの本会議に出席してくることが出来ました。twitterでも書きましたが、英語が聞けて関数型言語に興味ある人はぜひ一度は学会に出てみると良いと思います（宿泊費も参加費も旅費も高いですけどそれでも！　しかも今年は東京ですよみなさん！）。濃密な実現可能な妄想が飛び交う空間というのは素晴らしいです。出張途中に寄った大学でも新しいネタをもらって来ました。11月はちょっと休息モード。流石に5月からの進行のツケが回ってきたので一旦休憩したり。あと3ヶ月ぐらい真面目に考えていたネタが潰れて凹んだりしていました。あと長年苦しんだ論文が出版されました。なんかカバーペーパーになったらしく非常に嬉しいです。この論文は難産でしたし、結果も何かを証明するには微妙に不足しているのですが、モデルは非常に気に入っているのでこれからも頑張って育てていきたいと思います。12月は溜まりに溜まったタスクを潰したりしていました。あとFO3:NVやったりとか。近接戦闘のシステムがあんまり進化していないのでES5が心配です。

皆様2011年もよろしくお願いします。