N-gram 言語モデルを圧縮するには

はじめに

今回の記事は，以下の論文に関するものです．他にも紹介記事（ACL2011論文「Faster and Smaller N-Gram Language Models」を読んだ - EchizenBlog-Zwei）があるので，そちらでは特に触れられていない部分を（独断と偏見により）解説しています．

概要

この論文では，機械翻訳への応用を目的として，大規模な N-gram 言語モデルをオンメモリで効率的に扱うためのデータ構造を提案しています．言語モデルの用途としては，機械翻訳によって出力される文候補の尤もらしさを求めるところ，つまり最後の仕上げを想定しているようです．

そのため，言語モデルの仕様は，入力した n-gram の出現確率，あるいは (n-1)-gram が決定した段階での n-gram の出現確率（back-off）を取得できることです．(n-1)-gram を入力として n-gram の候補を列挙するような使い方は想定されていません．不可能ではありませんが，効率は極端に悪くなります．

Token をラベルとするトライ

N-gram 言語モデルには，共通の prefix を持つ n-gram がたくさん含まれます．たとえば，"言語 処理" という 2-gram で始まる 3-gram（http://s-yata.jp/apps/ssgnc/word?q=%E8%A8%80%E8%AA%9E+%E5%87%A6%E7%90%86+*&o=fixed&f=1&t=0-0&r=100&i=262144&c=html）は，以下に示すように，たくさんあります．

言語 処理 の 3800
言語 処理 系 3420
言語 処理 学会 1710
言語 処理 技術 1690
言語 処理 研究 1200
言語 処理 を 1030
...

トライは文字列の収納に便利なデータ構造として知られていますが，共通の prefix をマージできるという特長は，N-gram 言語モデルに対しても効果的です．もちろん，各 n-gram を文字列として格納することもできますが，token（1-gram）を整数の ID に変換して，ID をラベルとするトライにする方がコンパクトになります．

連想配列によるトライ

N-gram 言語モデルにおいて，あらゆる n-gram に対して ID を割り当てると（1-gram には token ID を用いる），トライを連想配列として表現することができます．すなわち，(n-1)-gram と次の token を入力すると，n-gram と出現確率が出てくるという構成です．論文中では，n-gram に対する (n-1)-gram のことを context と表現しています．

LM[context, token] => n-gram, value

トライの実装と考えると複雑に思うかもしれませんが，連想配列にしてしまえば，後はなんとでもなります．整列して二分探索したり，ハッシュ表で表現したり，B 木にしたりと，選択肢はいくらでもあります．論文中では，オンメモリを想定していることもあり，速度面ではハッシュ表が優れているという結果が示されています．

逆転の発想

トライを連想配列に置き換えたところで，ちょっとした，それでいて画期的な工夫があります．

LM[token, context] => n-gram, value

単純に token と context を交換しただけですが，この工夫により，連想配列の実装として「整列して二分探索」を選択したとき，N-gram 言語モデルを大幅に圧縮できるようになります．

ずばり，token に対して別々に配列を用意し，その配列には context を昇順に格納するという構成にします．実際には差分にして圧縮するわけですが，二分探索のためにブロック単位で圧縮する必要があります．

token と context を交換した理由をあらためて考えると，context 基準では短い単調増加な配列がたくさんという構成になるのに対し，token 基準では長い単調増加な配列が少しという構成になることがわかります．たとえば，Web1T では，token の種類が 1000 万程度なのに対して，context の種類は 10 億を超えます．つまり，差分にしたときに圧縮しやすくなるわけです．

おわりに

個人的にポイントだと思ったところに絞って，自分なりに解説してみました．ひょっとしたら，そんなこと書いてないかもしれませんが，そんな風に読めたということです．