たまたま 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のように専門家が集まっている環境ではないので, 敵う訳がないよなあ.. と思ったり。

---