統計的機械学習セミナー (1) sequence memoizer

統計数理研究所にて行われた第２回統計的機械学習セミナーにのこのこ参加してきました。

http://groups.google.com/group/ibisml/browse_thread/thread/092f5fb3d45a91ea/8cae858cb8bfc00c

今回はノンパラメトリックベイズ特集ということでか、Yee Whye Teh さんが sequence memoizer を、持橋さんが教師無し＆半教師分かち書きを話されたので、まずは sequence memoizer について自分のわかる範囲で書いてみよう。

まず、Pitman-Yor 過程については既知とする。ご存じない方は、「独断と偏見によるノンパラ入門」を読めばだいたいわか……んないか(苦笑)。
ええと、とりあえず今回必要な範囲で説明すると、G という単語の分布(ただし台は無限。つまり「独断と偏見〜」でいう「その他」の目があるサイコロ)に対して、G' 〜 PY(θ,d,G) とすると、G を元にベキ分布を考慮した新しい単語分布 G' を作ってくれる。そんな PY(θ,d,G) が Pitman-Yor 過程。θは concentration パラメータ、d は discount パラメータ、G は base measure。

例えば不思議の国アリスには "rabbit" が 51回登場する。"rabbit" の前には "the" や "white" が来る。"white rabbit" は 22回登場する。
ここで "white rabbit" の後ろに続く単語である "with" や "read" は、全て "rabbit" の後ろに続く単語の分布に出てくる。逆に "rabbit" の後ろに続く単語は必ずしも "white rabbit" の後ろに続くとは限らない。
そのとき "white rabbit" の後ろに続く単語の分布 G_{white rabbit} を "rabbit" の後ろに続く単語の分布 G_{rabbit} から G_{white rabbit} 〜 PY(θ,d,G_{rabbit}) として作ってあげると非常に精度の高い分布ができる。
同じように "the rabbit" や "the white rabbit" の分布も G_{the rabbit} 〜 PY(θ,d,G_{rabbit}) や G_{the white rabbit} 〜 PY(θ,d,G_{white rabbit}) として作る。じゃあ G_{rabbit} はというと、単語の事前分布 H から G_{rabbit} 〜 PY(θ,d,H) として作る。

G_{rabbit} は G_{white rabbit} の親、G_{white rabbit} は G_{the white rabbit} の親、……と見なしてあげると、H を根に持つツリー構造になる。このツリー構造を例えば深さ３まで作ったとき、4-gram の階層 Pitman-Yor 言語モデルになる。G_{3単語} はその次の４つ目の単語の分布を与えているため 4-gram になる。
学習データにないフレーズはサイコロの「その他」の面に対応する。これが出た場合には、親の単語分布から単語を引っ張ってくる。親の単語分布は子のそれより一般に少し広いので、これで学習データにないフレーズを生成することができる。
もちろん、親の単語分布にも「その他」面があるので、それが出たらさらに親の親にさかのぼっていく。最終的には単語の事前分布 H が控えているので、どこまでも戻る心配はないから大丈夫。
この挙動は 4-gram の smoothing で 3-gram/2-gram/1-gram の確率も傾斜を付けて加えることに相当し、ちょうど階層 Pitman-Yor 言語モデルは Kneser-Ney smoothing の Bayesian な表現になっている。

sequence memoizer はこの階層 Pitman-Yor 言語モデルの階層を無限の深さまで考える ∞-gram の言語モデル。
単純に作ると無限の深さの suffix "trie" を作ることになってしまうが、子を１つしか持たない G_{hoge} を全部周辺化することで suffix "tree" と同じ形になり、ノード数が文章長の2倍で抑えられることが言える。
周辺化とはつまり G_{white rabbit} 〜 PY(θ,d,G_{rabbit}) と G_{the white rabbit} 〜 PY(θ,d,G_{white rabbit}) があるとき、間の G_{white rabbit} をすっ飛ばして G_{rabbit} から直接 G_{the white rabbit} を作るということだが、これは「Pitman-Yor の Pitman-Yor」が計算できないといけない。
が、実はパラメータにある制約を入れておけば「Pitman-Yor の Pitman-Yor」も Pitman-Yor になることが言える。ここがキモ。

こうして作った sequence memoizer は言語モデルとして現時点で最高精度をたたき出す。
精度が高い言語モデルと言うことは、続く単語の確率を正確に予測できる→圧縮に使ったらすごいよ、ということで実際に sequence memoizer を使った圧縮を下記のデモサイトで試すことができる。