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

機械学習 NLP

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


今回はノンパラメトリックベイズ特集ということでか、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 を使った圧縮を下記のデモサイトで試すことができる。


bzip2 と上のサイトで不思議の国のアリスを圧縮してファイルサイズを比べてみた。

オリジナル 145,283
bzip2-9 40,777
deplump 36,506


うーん、全然うまく説明できてないなー。難しい。
もちろんいつものように突っ込み歓迎。

参照論文

  • [Teh 2006] A Hierarchical Bayesian Language Model based on Pitman-Yor Processes
  • [Teh 2006] A Bayesian Interpretation of Interpolated Kneser-Ney
  • [Wood+ 2009] A Stochastic Memoizer for Sequence Data
  • [Gasthaus+ 2010] Lossless Compression based on Sequence Memoizer
  • [Gasthaus+ 2010] Improvements to the Sequence Memoizer