« December 2008 | Main | February 2009 »

2009.01.21

マイクロソフト戦記

本屋で、ふと目にとまり、買った本でしたが、とても面白く一気に読んでしまいました。

マイクロソフト戦記―世界標準の作られ方 (新潮新書 298)

MicrosoftがどのようにしてOSにおいてデファクトスタンダードをとっていったかの舞台裏が描かれており、
MS-DOS, MSXと進んでいく中でという流れは必然的な流れではなく、たくさんの要因に揺らされ、他にたくさん選択肢がある中で、なぜWindowsが勝ち残ったのか、その経過と考察が述べられてます。

現場にいる人しか知らないエピソードもいろいろあり、例えば、windows1.0の日本語版は2人で対応し大変厳しい状況だったとか(一人は有名な中島さん)、コンソーシアムの直前に演説内容をうまくとりまとめたりとか、周りの巻き込み方とか面白い。

私は、結果としてどうなったかより、実際にプレイヤーどのように考えて行動していて、うまくいかなかったのはどのようなことがあって(大抵うまくいったこと、結果に関係したことしか後に知られない)、他にどのような可能性があったのかとかを知りたいのですが、この本はまさにそのへんが書かれていて、いろいろ考えさせられます。

#そういうわけで、私は、歴史の勉強は苦手だったのですが(なぜ年号を覚える・・)、歴史書で好きで大人になってから読みあさってます。お勧めの本があったら教えてください。

どんな成功や栄光の前にも”冴えない”時期があって、その時に踏ん張れるかだなぁ。

| | Comments (177) | TrackBack (0)

2009.01.16

昨年の論文をふりかえる

新年すっかりあけてました。
今年もよろしくお願いします。

年末年始はドタバタして昨年を振り返られなかったのですが、せっかくなので2008年に読んだ論文で私個人のベスト5を以下に列挙してみます。

D. Sontag, et. al. "Tightening LP Relaxations for MAP using Message Passing", UAI 2008 [pdf]

Graphical ModelのMAP推定問題で従来解けなかった規模の複雑さの問題を高速にしかも最大であるという保障付きで解けるようにした。書いたメンバーはこの問題に関するオールスターのような感じ。解く問題は、n個の頂点からなるグラフで、各頂点には変数x1...xnがついていて、各頂点と各枝に対し関数gi(xi)、gij(xi,xj)が与えられた時、∑i gi(xi) + ∑ij gij(xi,xj)が最大となるような変数x1^*...xn^*を求めよという問題。このようなタスク設定はタンパク質の構造決定、写真が複数枚与えられての立体情報の復元など非常に広い問題で使われている。自然言語処理でも、普通現実的に使うCRFは一本鎖のグラフィカルモデルで、自由に枝を張ってしまう計算量が爆発してしまうというのが、枝を結構自由にはっても解けるようになったと思っていただければすごさがわかるかとおもう。
ずっと長い期間様々な方法が提案されてきたが、この論文では、非常に簡単なメッセージパッシングアルゴリズム、線形計画緩和、双対問題、制約の逐次追加などこれまでの技術の集大成でこの問題をきれいに解決している。UAIのbest paper。

G. Nong, et. al. Two Efficient Algorithms for Linear Suffix Array Construction, 2008, [pdf]
(上のconference version) Linear Suffix Array Construction by Almost Pure Induced-Sorting, DCC 2009 [pdf]
Moriさんにより実装・比較(sais)

線形時間で接尾辞配列を構築するコードがC++で100行弱で書けて、しかも結構速く(O(nlogn)の方がまだ速いがかなり縮まってきた)、無駄に使う作業領域量はほとんど無い。元東工大の伊藤さんから始まり、元群馬大の儘田さんや森さんなどが培ってきた二段階法の進化形。私も接尾辞配列の構築については10年以上付き合ってきているので、この進化は感慨深い。すごく単純に言うと、接尾辞配列を構築する際には接尾辞を全部ソートする必要はなく、ソートが必要なものと必要じゃないものに分けることができて、一部をソートしたら、残りの順序はそのソート結果から自動的に決定できる。で、このソートが必要な部分の結果を求めるには元のテキストの部分文字列を新しい文字に置き換えて、長さが半分以下になったテキストに対する接尾辞配列の結果を使えば求まる。長さが半々になっていく再帰問題で、他の部分が全部線形時間で求まるのならば全体も線形時間でできる。で、この新しい文字への置き換えの部分も先ほどの「ソート結果から自動的に決定できる」のと全く同じアルゴリズムを動かすと求まるよというのが上の論文。部分文字列をradix sortしているだけといえばそうだが、ここまできれいにまとまるのはすごい。

B. Zhao, et.al, "Efficient multiclass maximum margin clustering", ICML 2008 [pdf]

前回のエントリで書いたので詳細は書かないが、読めば読むほど面白い。ちなみに著者らが所属している清華大の研究グループはものすごい量の論文を国際会議に通していることで話題になっているとこlink

A. Haghighi, et. al. "Learning Bilingual Lexicons from Monolingual Corpora", ACL 2008 [pdf]

これも以前勉強会で紹介した[ppt]ものなので詳細は書きません。最近、自分でも学習データ作ったり、いろいろやってて思うのは、言語リソースを作るのには「教師無学習で得られた結果に対してアノテーションをする」というのが、かなり良いような気がしてきています(論文や研究としてはやりにくいけど、リソース作るコストとかにも注目した"Cheap and Fast But is it Good? ..."[pdf]とか論文も出てきてるし、何かできるかな)

Mihai Patrascu, "Succincter", FOCS 2008 [pdf]

圧縮したままアクセスするようなデータ構造でかなり基礎的な部分での上限を変えた。ブロックを符号化した場合、基本的にはブロックまとめて復元しないといけない。たとえば3通りある文字を符号化しようと思うと1bitでは保存できないので、なくなく2bit使うしかなく1文字あたり1bit近く損してしまう。そこで文字をk個まとめて符号化すると無駄は1文字あたり1/k bitと減るが、各文字の情報はブロック全体に広がってしまっているので、1文字にアクセスする場合もブロック全体を復元する必要があり、必要な作業領域と、必要な計算量は線形の関係があるように思われていた。
論文では、この直感は間違いで、溢れた情報を再帰的に管理していけば、ブロックあたり2bitの無駄を許すならば、ブロックサイズの対数時間でアクセスができるということを示してます。理論的にはすごいものだし(いろいろな簡潔構造の上限がだいぶ下がった)、実用的にももうちょい工夫すれば算術圧縮のランダム復元など面白いのができるだろうなぁ。student best paper

今年もいろいろ情報紹介していきます。よろしく

| | Comments (44) | TrackBack (1)

« December 2008 | Main | February 2009 »