mots quotidiens. | |
Daichi Mochihashi (持橋大地) daichi <at> ism.ac.jp | by hns, version 2.10-pl1. |
|
||||||||||||||||||||||||||||||||||||||||||||||||||||
今日, 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) のように生成されている時, さて
G3|G1 = ∫G3|G2・G2|G1 d(G2)は何? ということ。
この論文では, 上の式は, Pitman-Yor過程の集中度パラメータθが0ならば *1 (normalized stable processというらしい), G_2を消去して
G3|G1 = PY(d1d2,0,G1)になる, という確率論の結果を使っている。 この結果は, 離散分布のCoagulation(凝集)-Fragmentationという考え方から導かれる。
この結果を使うと, 上の簡単な式だけでなく, 逆にユニグラムとトライグラムだけが 分かっている時に, 消去した中間のバイグラムを復元することができるようになる。 *2 式は複雑で, 理由を理解するには Annals of Probability の論文を読まないといけない ようなので省略。
内部で出たコメントを含めた感想は, データをとにかく全部使うこの方法は, モデル化 というよりアルゴリズム的な方に今後の意義があるのではないか, ということ。 PPM-*も同じようにデータを全部覚えて最長一致のn-gramを使う方法ですが, この∞-gramは階層ベイズなので, PPM-*のように情報が落ちることがなく (途中のノードを復元する必要があるので, 推定は重そうですが), 理論的上限を与える ことができます。
とりあえず, IMMが不要になるという話ではないようなので少し安心。
Coagulation-Fragmentationという話が重要らしい, ということ自体には去年あたりに
自分で辿り着いていたのですが,
Gatsbyのように専門家が集まっている環境ではないので, 敵う訳がないよなあ..
と思ったり。
タイトル一覧 |