« October 2008 | Main | December 2008 »

2008.11.24

海外のブログのお勧め

海外のブログでお勧めはどういうのありますかとよく聞かれるのでかいてみます。
といってもそんなないけど。

Terence Tao
非常に幅広い分野の第一線で活躍している数学者のテレンスタオ[jawiki]のブログ.ブログで毎回新しい定理を証明しちゃったり、突然、相対性理論の分かりやすい証明をしたりとすごい.コメントでの議論も丁寧.
ブログで書いたのをまとめたが出るそうですが、目次を読むとブログ本の範疇をこえてる・・

natural language processing blog
自然言語処理ではたぶん一番有名なブログ. による.いろいろな手法の解説から現在ある問題(自然言語処理以外にもアカデミック的な問題とかも含め).守備範囲が大体私と似ていて読んでいて楽しい.ちなみにHal Daumeはハスケラーで、そこそこ有名なhaskel tutorialかいてたりする

Google Research Blog
いわずもがなグーグルの研究部門のブログ.いろいろな分野の人がちょこちょこ書いてくれるので面白い

Machine Learning (Theory)
機械学習のいろいろなトピック,特に理論系を扱っている. 現在はYahoo! ResearchにいるJohn Langfordによる.

その他にもこのリンクのあたり
はよく読んでます.

実装系はあまり読んでいないのですが、有名どころの中では
Developing for Developersとかは気休めによんでます。

なにかいいのあったら教えてください

| | Comments (322) | TrackBack (0)

2008.11.08

左傾赤黒木

漢字で書くと仰々しいが、赤黒木 (wikipedia) red-black tree (english wikipedia)という平衡二分木で最も多くつかわれているデータ構造の、改善版が出てたそうだ。

left-leaning red-black tree (pdf)
日本語に訳すと左傾赤黒木かな。簡単な漢字を並べている感じがしてしまう

赤黒木の詳細については、wikipediaなどをよんでもらうとして、これは更新時間が定数で更新箇所が局所的(これはマルチスレッドとかでロックする箇所をかなり細かい単位で、できるという強い利点もある)のだが、実装が結構面倒くさい。例えばC++ stl のmapとかの赤黒木の実装のstl_tree.h(google code search)は大変なことになっている(特にRb_tree_rebalance_for_eraseとか)

赤黒木というのは動的データ構造の設計のときにもかなりの頻度で道具として使われていて(たとえばシーケンシャルなデータ構造でinsert deleteしたい場合とか)、論文的には、赤黒木をここで使うことでO(logn)保障とか書くんだけど実装はしたくないので、skip listとかをたいていつかってしまう

で、このleft-leaning red-black treeだと、赤黒木の実装がすごいシンプルになって、挿入で30行強、削除で80行ぐらいで書ける。なぜシンプルになったかというと、今までの赤黒木は対応する2-3-4木が必ずあるといっても3-nodeに対応するのが、左側の節点が赤になる場合と右側の節点が赤になる場合の自由度があって、これを左側の節点が赤になるように一種の正規化をかけることで、2-3-4木と必ず一対一対応がとれて、
場合分けをすごく減らすことができたからだそうだ。

既にある赤黒木より性能は同じだが、自分で組み込みやすくなったということで、いろいろなところで使いやすくなった。自分でも研究の実装であきらめていたところで使うようになりました。

枯れたと思ってても少しの工夫でよくなるのですね

| | Comments (845) | TrackBack (0)

IBIS2008

今更書きますが、仙台で開催されたIBIS2008に先週行ってきました。

福島出身ですが、仙台にちゃんといったのは初めてかもしれない。東北新幹線に乗ったのもおそらく初めて。各講演内容、ポスター発表内容、夜の飲み会とも濃い内容で楽しめました。自分もポスター発表して奨励賞ももらえました。ありがたや。

各講演内容のスライドのいくつかはダウンロードできますので、興味のある方はぜひご覧ください。

例えば、自然言語処理の松本先生のは機械学習による自然言語処理、特に係り受け解析についてどのあたりが難しいのか(局所情報と大域情報のトレードオフなど)を解説しています。

持橋さんのノンパラベイズ、栗原さんのグラフマイニング+ノンパラ、杉山先生の密度比推定などもダウンロード可能。岡本先生によるtree decomposition (= junction tree)の話もとても面白かった。世の中に存在するグラフ構造の話はほとんど木の問題に帰着できることが多いそうだ。

ポスター発表は午後4時間ぐらいぶっ通しであって、いろいろな人と深くディスカッションできたのでよかった。知らない分野は本とかで読むのもいいが、よく知っている人に説明してもらうのが圧倒的に早い。

牛タンがやはりうまかった。

| | Comments (1) | TrackBack (0)

« October 2008 | Main | December 2008 »