論文紹介「階層 Pitman-Yor 過程に基づく可変長 n-gram 言語モデル」
既存の方法だと8-gramの言語モデルとか現実的に無理なんだけども、この方法だと可変長だから必要なところだけ長いgramにできるよ、という論文。
Pitman-Yor過程と等価な中華料理店過程でツリーを作る。she willの後にsingが来たとするとルートノードからwillをたどってsheをたどったところにsingに対応する客を追加する。上位のノードにも代理客を追加する。
既存手法(HPYLM)だと、客を追加する高さが固定。しかし決まった高さに追加するのではなく「客がルートから進んできて、テーブルを通過する確率」を各ノードごとに考える。この確率qiは未知、どうやって推定するか？
qiの事前分布がベータ分布であるとし、まず配置する。そこからランダムな単語wtを取り除いて、残りの客の分布からベータ分布のパラメータを更新、そのベータ分布からサンプリングして新しい深さに客を追加。この「取って、入れる」を繰り返すことで正しい分布に収束する（ギブスサンプリング）
サンプリングの際に深さの最大値を決めておくか、確率が十分小さくなるまでやるか、の2通りがある。後者の場合は完全にn-gramのnに相当するパラメータが消えてなくなるので∞-gramと呼べるだろう。
実装にはスプレー木を使う。各ノードは(intもptrも64bitとして)64バイトのサイズがある。10000Kノードでmax 8-gramの言語モデルを作ることができているので、つまり640MBくらい。現実的サイズ。既存手法では30000種類の語彙の8乗のオーダーで記憶領域が必要なので現実的ではないが、提案手法では必要なところだけ長いgram数を使うので実現できている。実際5-gramの文脈と推定される箇所は3-gramと推定される箇所の半分くらいで、3-gramの記憶の9億倍を5-gramにつぎ込む既存手法は合理的でない。
既存手法で可能な3-gram、5-gramについては若干既存手法よりパープレキシティが高いが、英語コーパスに関しては7-gram，8-gramは既存手法5-gramより低い。日本語コーパスは…低くない。∞-gramも低くない。このへんは若干残念な感じだけども、とにかくノード数の削減効果が大きい！というのが長所だろうか。
感想: Googleさん、max 8-gramで作った言語モデルをください
追記: 実装してみてわからなかったところを追記。「thwはwがp(w|h)からではなく、親ノードp(w|h')から生成されたと推定された回数」このsum_wであるthを保存するフィールドがノードの定義にあるけど、これはどのタイミングでどんな値を入れたらいいのか。またthしか保存されてないけどthwはどうやって復元するのか。dとθの推定方法は書いていなかったけども元のHPYLMの論文の最後におまけみたいに付いているdmとθmのサンプリングの式を使って推定するのか？
実装
https://github.com/nishio/VPYLM/blob/master/t.py
注: 新しいテーブルが作られる確率を無視しているのでまだ正しく動きません。通して動かすことはできるので雰囲気を知るぐらいで。
さいごに
この記事はDeep Learningに興味を持った著者が、関連論文を読んで勉強しながら書いているものです。そのため間違いなどが含まれている可能性があります。もしなにか気になる点がありましたらご指摘いただけるとありがたいです。
