ACL/EMNLP 2009が終わって, シンガポールから日本に帰ってきました。
自分の発表は前の Percy Liang の時に部屋に入れないほどの満員で, それから流石に 少し減ったものの, だいたい満員で100-200人くらい(多分)いたような気が します。緊張していたせいか喉が渇いていたのに水を飲んでおかなかったので, 口が回らなかったというのが残念なところ。 論文のページ にスライドのPDFを置いておきました。
もっとも, 綿密な論文の鈴木さんの発表は朝一だったせいか20人くらいだった(多分) ので, 論文のレベルはあまり関係ないというか, 口頭発表は基本的におまけという気も します。

ホテルは Suntec の隣にある Marina Mandarin Singapore に泊まったのですが (各室にベランダがある), 幸いなことにマリーナ側で, しかも16Fという高層階だったので, もうそれだけで充分という感じ。
それほど観光する気はなかったのですが, 8/1から8/7まで1週間もいたので, シンガポールフライヤーに行ったり, フィッシュヘッドカレー, マーライオン, 最後の日(飛行機は夜中発なので, 時間があった)にラッフルズホテル散歩と結構 いつの間にか見所を押さえていたような気がします。
マーライオンを見に行ったところ, 実は部屋からも見えて, というかEMNLP2009の トップページのこれ(下図)がそうだということを知りました。

たまたま Van Gael (CambridgeのGhahramaniのグループ)のブログ "Undirected Grad" を開けたら, もろに僕のACLの話が紹介してあって驚いた。

今日, CS研内部の談話会で, ACL/EMNLP 2009の論文紹介と一緒に, 少し前に出た ICML 2009の "A Stochastic Memoizer for Sequence Data" の話をしました。 前にやった僕の話とまた違う形で∞-gramを実現するという話。 Yee Whyeと香港のLancelot James先生がやっている, という話を聞いていたので, ACLが終わって少し余裕ができたので読んでみました。
これは簡単に言うと, 以前書いたPPM-*をベイズ的に行うものと言ってよく, "Stochastic Memoizer" という名前はミスリーディングで, "All Memoizer" というのが近いと思う。(僕のIMMの方が本当に"Stochastic Memoizer"になっている。)

nグラムを実装するデータ構造としてトライ(Suffix Tree)を使うことができますが, nグラムのオーダーnが増えると, 木構造のサイズが非常に大きくなります。
ただし, 実際はよく見ると, 子供が一つしかないノードが多く, トライの代わりに パトリシア木を使えば, 余分なノードを圧縮して, 木のサイズをデータ長Nと同じに することができます。

ただしこのとき, ノードを圧縮する, つまり統計的に言うと中間ノードを周辺化した時 の分布がどうなるかという理論が必要です。バイグラム分布G_2がユニグラム分布G_1 を基底測度として, G_2 ~ PY(d_1,0,G_1) のように生成され, トライグラム分布G_3が バイグラムG_2を基底測度として G_3 ~ PY(d_2,0,G_2) のように生成されている時, さて

G₃|G₁ = ∫G₃|G₂・G₂|G₁ d(G₂)

は何? ということ。

この論文では, 上の式は, Pitman-Yor過程の集中度パラメータθが0ならば *1 (normalized stable processというらしい), G_2を消去して

G₃|G₁ = PY(d₁d₂,0,G₁)

になる, という確率論の結果を使っている。 この結果は, 離散分布のCoagulation(凝集)-Fragmentationという考え方から導かれる。
真面目に説明すると大変なので具体的に言うと, 自然言語処理の場合, ユニグラム分布 は比較的「なだらか」な分布なのに対し, バイグラム, トライグラムと進むに従って 分布が偏って急峻になってくる。これは, GEM分布(Stick-breaking)に coagulation operatorを適用したと考えることができる。本質的には, nグラムから i.i.d.に無限回サンプルを取って(n+1)-グラムを作ると, 必ず同じ単語が複数回引かれ るため, 重なりが生じて確率分布がそこに凝集する, ということ。 親の分布に偏りがあるほど, 子供の coagulation の度合いがどんどん強くなる。
逆に, ある単語に対する確率をそれ自体 Stick-breaking で無限に細かく分割して, size-biased permutationで並べ換えて戻すという逆の操作(fragmentation)を施すと, 元に戻すことができる。

この結果を使うと, 上の簡単な式だけでなく, 逆にユニグラムとトライグラムだけが 分かっている時に, 消去した中間のバイグラムを復元することができるようになる。 *2 式は複雑で, 理由を理解するには Annals of Probability の論文を読まないといけない ようなので省略。

内部で出たコメントを含めた感想は, データをとにかく全部使うこの方法は, モデル化 というよりアルゴリズム的な方に今後の意義があるのではないか, ということ。 PPM-*も同じようにデータを全部覚えて最長一致のn-gramを使う方法ですが, この∞-gramは階層ベイズなので, PPM-*のように情報が落ちることがなく (途中のノードを復元する必要があるので, 推定は重そうですが), 理論的上限を与える ことができます。

とりあえず, IMMが不要になるという話ではないようなので少し安心。
Coagulation-Fragmentationという話が重要らしい, ということ自体には去年あたりに 自分で辿り着いていたのですが, Gatsbyのように専門家が集まっている環境ではないので, 敵う訳がないよなあ.. と思ったり。

---

ラテン語版ハリーポッター 賢者の石 (Harrius Potter et Philosophi Lapis) というのがあるらしい。
予想通り, レビューの中に

***** facile et iucundum est hunc librum legere!, September 5, 2007  
quis aliquid magis quam hunc librum Latine legere vult? bene scriptum est et 
bonum non solum alicui legere sed etiam ad discipulos docendos. eme, tolle et
lege hunc librum et laetus esto!

Help other customers find the most helpful reviews  
Was this review helpful to you? [Yes] [No]

とかいうレビューが。イカス。何となく意味はわかりますが, つい[No]をクリックしたくなるというか.. (笑)。

今年も SVM 2009 が終了。発表も面白かったし, その後で普段話せない人と色々話すことができて, 楽しかったです。
僕は Gaussian Process とGPLVM, GPDMの話をしました。スライドがまだ荒削りなのと, 本来書きたくて時間切れになってしまったものもあるのでまだ公開は控えますが, Gaussian process と Dirichlet process の関係は知りたい人が他にもいるかも 知れないので, そこだけ1ページのPDFにして公開しておきます。

• gp-dp.pdf

ご興味のある方はどうぞ。
Poisson processなんかも考えてみると同じ構造を持っているので, 本当はそれらを 含めて統一的に説明すべきなのだと思いますが, そこまで僕の準備が整っていない ので, 今後ということで..。
M1が結構多かったようなので, M1あたりから見るとポカーン, なのかなあ, と 思ったり。 *1

---