ACL2011論文「Faster and Smaller N-Gram Language Models」を読んだ

計算機科学

ACL2011の論文で「Faster and Smaller N-Gram Language Models」というのが気になったので読んでみた。

ACL Anthology » P11
Faster and Smaller N-Gram Language Models Adam Pauls, Dan Klein; 2011

本論文はこれまで提案されている言語モデルの圧縮・高速化の手法を実装して比較したよ、というもの。各種法が丁寧に解説されており、性能比較もよく知られているツールであるSRILMをベースラインとして行っているので参考になる。サーベイ論文として優れていると感じた。


本論文で紹介されている手法はモデルのサイズ圧縮と高速化の2点に関するもの。
まずはサイズ圧縮について。これはTRIEを使うことで各Nグラムの共通したプレフィクスを圧縮するのが基本らしい。でTRIEについてはノードの持たせ方がポイントになるがこれには辞書順ソートしておいて検索時は2分探索する手法(SORTED)とハッシュで実現する方法(HASH)がある。SORTEDはデータサイズが小さいが検索は2分探索を使うのでO(logN)。HASHはデータサイズが大きくなるが検索はO(1)というトレードオフ。
また上記2つの実装にプラスしてノードのIDをVariable Length Codeで圧縮する方法が提案されているらしい(COMPRESSED)。詳しくは後述するがCOMPRESSEDは高い圧縮性能の代償として検索がとても遅い様子。


ここからは高速化の話。まずは単純な話としてクエリとして投げられる単語には偏りがあるので頻出する語をキャッシュすればいいよねという話が書いてある。また別の手法としてSCROLLというのが紹介されている。これはどういうものかというと例えば「the cat fell down」というクエリがあったときに3グラムモデルだとすると、まず「the cat fell」のスコアを得る。この時点で「cat fell XXXX」のスコアを次に計算することは分かっているので、事前に「the cat fell」のノードに「cat fell」の位置情報を持たせておくよ、という話。余分なデータ領域を必要とするが高速化が実現できる。


で評価結果は論文のTable 4にある。詳しい実験の条件などは論文を参照されたい。

[Table 4より抜粋]

              No Cache    Cache     Size
===========================================
COMPRESSED    9264±73ns  565±7ns   3.7G
SORTED        1405±50ns  243±4ns   5.5G
HASH           495±10ns  179±6ns   7.5G
SRILM-H        428±5ns   159±4ns  26.6G
HASH+SCROLL    323±5ns   139±6ns  10.5G

この結果を見るとCOMPRESSEDはデータサイズが小さいが速度面でSRILMの20倍以上かかっていて実用性がないんじゃないかという印象。キャッシュのおかげで平均速度はマシになっているが、キャッシュにないデータのことを考えると即時性の求められるタスクでは使えなさそう。バッチ処理のタスクでどうしてもサイズが気になる場合向けかも。最近は簡潔データ構造とか色々あるのでVariable Length Codeのかわりにそれらを使ったらもっと良くなるんじゃないかという気もしている。ちゃんと調べてないけどそういう研究あるんだろうか。そもそもTRIEもDoubleArrayとかLOUDSとかあるわけで、そういうの使えるのでは、などと思った。
他を見るとHASHがSRILMとほぼ同じ速度でサイズはSRILMの1/4程度なので、これで充分なんじゃないのという気がした。逆にSRILMはなんでこんなに大きいのかが気になる。(SRILM使ったことないのでどういう構造なのか知らないです。すみません。)


以上、ざっと読んでみたが綺麗にまとまっていて良い論文だと思った。私は言語モデルの圧縮、高速化については特に詳しくないのだが、圧縮データ構造には興味があるので言語モデルに対して色々やってみるのも面白そうな気がしてきた。