大規模データで単語の数を数える

研究

大規模データから one-pass で item（n-gram など）の頻度を数える手法に関するメモ．ここ数年，毎年のように超大規模な n-gram の統計情報を空間／時間効率良く利用するための手法が提案されている．最近だと，

とか．この論文では，最小完全ハッシュ関数や power-law を考慮した頻度表現の圧縮など，細かい技術を丁寧に組み上げており，これぐらい工夫が細かくなってくるとlog-frequency Bloom filter (ACL 2007) ぐらいからから始まった n-gram 頻度情報の圧縮の研究もそろそろ収束したかという印象（ちょうど論文を読む直前に，この論文の7節の可変長 fingerprint 辺りの内容を考えていた．手をつけないで良かった）．

これらの研究は，既に数え終わった静的な n-gram の頻度情報を，コンパクトに保持するためのデータ構造を提案しているが，そもそも数える方も時間・空間効率良くやらないと片手落ちだろう．そこで，最近出たサーベイ論文を読んでみた．

この論文自体は，VLDB 2008に出たものの改訂のさらに改訂バージョンなので，内容的にはそれほど目新しくはないのだけど，基礎的なアルゴリズムの簡潔な説明と網羅的な実験による比較，今後の展開など非常にバランスよくまとまっている．折角なので，基礎的なアルゴリズムについて簡単にメモしておく（以下，数を数える対象を，item と呼ぶことにする）．
メモリに載らないほどの種類の item の数を効率的に数えるには（分散計算するとか力任せでやらない限り）どこかで手を抜く必要があって，大まかにはメモリで扱えるサイズの種類の item に対して直接的にカウンタを保持する counter-based (deterministic) な手法と，全 item に対して近似的なカウンタを保持する sketch-based (probabilistic) な手法がある（サーベイにはもう少し一般的な問題を扱うための Quantile アルゴリズムや，sketch-based な手法の拡張なども紹介されているがここでは省略）．どのアルゴリズムも，擬似コードで10行前後と一目で理解できるほどにシンプルで美しい．以下，擬似コードが載っている5つのアルゴリズムの紹介．

Counter-based Algorithm のべ N 回の item の出現に対して，counter-based な手法は（高頻度の）item の頻度を最大 Nε (ε<1) の誤差で保持する．counter-based な手法の基礎的なアルゴリズムとしては，以下の三つがある（実際に実用的なのは下の二つ）．

どの研究も，近似誤差 Nε の保証は古典的な Majority アルゴリズムのアイデアに基づいている．即ち，少なくとも Nε 回より多く出現している高頻度の item（とその近似頻度）を得るためには，高々 1/ε - 1 の item についてカウンタを保持すれば十分，というもの．frequent ではこれを直接的に利用して，k = 1/ε - 1 個のカウンタを保持して，頻度が Nε 以上の全要素の頻度を，近似誤差 Nε で獲得する（得られる頻度は常に underestimate する; ε=0.5 (k=1) の場合が Majority アルゴリズム）．
Frequent で得られる頻度は，理論的な誤差は保証されるものの実際にはかなりいい加減な値になってしまい，実用上はあまり役に立たない（出力から実際に頻度 Nε 以上の top-k' (k' ≤ k) item を求めるのが困難）．一方，lossy counting や space saving では，高頻度の item の近似誤差を，（power-law に則るような実データでは）経験的に Nε より（大きく）抑えることができる. 例えば lossy counting では，データを 1/ε 単位で bucket に分割して順に処理し，i (≥0) 番目の bucket の処理後に（その時点まで処理したのべ n = i/ε の item で）頻度（の誤差を考慮した上限値）が Δ = i (= nε = i/ε * ε) 未満の item のカウンタを削除する（この Δ は i+1 番目の bucket で新しく追加される item の誤差の見積り（i 番目までの bucket での頻度の最大見積り）にも使われる）．一方，space saving では，常に k (= 1/ε) 個のカウンタのみを保持し，新しく観測された item と最低頻度の item を入れ替えるだけのシンプルなアルゴリズム．これらのアルゴリズムでは，最初に item を追加した時点の誤差が，その item がカウンタから削除されない限り保持されるので，高頻度でまんべんなく出現する item であるほど，頻度の正確な見積りが可能となっている．
サーベイ論文では，counter-based な手法では space saving が総合的に一番良いという結論になっている．空間計算量という点では，カウンタが固定長の space saving が使いやすいのは間違いないが*1，更新速度では自分で実装して試した限り大差はないという印象*2．lossy counting と space saving の本質的な差は，top-k' を取り出す際の質 (false positive の数の差) と思えば良さそう．
なお，lossy counting はもはや教科書レベルの基礎アルゴリズムで，例えば

などで使われている．
頻度順の出力を得たい場合，space saving ではカウンタの実装に用いるデータ構造（stream summary）が頻度順の出力もサポートするので悩むところはないが，lossy counting の方はカウンタの実装によっては別途出力時にソートする必要があったりと注意が必要（その他，各 bucket の処理後に削除する item の割合が全体に対して極端に少ない場合には，空間・時間効率が良いハッシュベースのカウンタより，stream summary のようなデータ構造の方を使うほうが良いかも知れない）．
Sketch-based Algorithm 一方，sketch-based なアルゴリズムは，キーを直接的に保持しないで，全 item に対して重複を許したサイズ w のカウンタを d 個保持する（各 item が各カウンタのどのスロットを使うかは，カウンタごとに pairwise independent なハッシュ関数を用意して利用*3; top-k' を出したい場合は，近似カウンタを利用しつつ，キーを別途保存）．counter-based との違いは，確率δで頻度の誤差範囲 Nε を外れるという点（カウンタのサイズや数は，与えられた (ε, δ) に対して最適化される; CountMin Sketch ではサイズ w = e/ε のカウンタが d = ln 1/δ 個必要）．基本的なアルゴリズムは以下の二つ（CGT: Combinatorial Group Testing は実装していないので，ここでは略）．

CountSketch はカウンタ更新時に更新の符号を別のハッシュ関数を使って決める分，更新速度が CountMin sketch に比べて倍程度遅くなる（また，近似頻度として，各カウンタに保存された値の median を用いるので，（実用的には問題ないが）時間計算量に拘ると実装が少し面倒）．また，CountMin Sketch は CountSketch より空間計算量の点でも理論的に優れており，誤差範囲から外れるとき overestimate しかしないなど，使い勝手は良い感じ．どちらの手法も誤差範囲を外れる確率 δ はかなり小さくできるので*4，実用性は高いと思う．
高頻度の item に対して Nε より小さい誤差が必要な場合や，キーを陽に保持する必要がある場合には counter-based の手法を，そうでない場合は sketch-based な手法を用いると良いのではないかな．

その他，両方の利点を組み合わせた手法も幾つか報告されている．例えばこれ．

前者は space-saving の前段に sketch-based のフィルタを入れたもの．space saving では，最終的にカウンタに含まれないような低頻度の item が，カウンタから頻繁に出たり入ったりすることになる．そこで各 item について頻度を更新する際に，item がカウンタに含まれていなかった累積の回数を sketch-based なカウンタで近似的に記録しておき，更新時にいつもカウンタへの新規登録が必要な低頻度の item については更新をサボるようにする（以上，斜め読み以下なので詳細は略）．後者は lossy counting で，データの偏り（power-law）を考慮して誤差 Δ の見積りをより小さく抑える手法（ただし，所与の確率 δ (<< 1) で見積り以上の誤差が生じることを許す）．結果として，各 bucket 処理後により多くの item を削除するようになり，空間使用率が改善される．データの skewness（要するに power-law のパラメタ）が所与であることを前提としていたりと，使い勝手はやや落ちているが，理論的には綺麗にまとまっている．

ここまで述べたアルゴリズムは，近似誤差が各 item ごとの頻度に対しては bound されないので，低頻度の item について相対的な誤差が大きくなる．item ごとに相対誤差を保証して計測する手法としては，上記の log-frequency Bloom filter （あるいはその変種）に，Morris の古典的な Approximate Counting を組み合わせた手法が提案されている（前者の方は斜め読み程度だけど，内容的には後者とほとんど同じ）．

どちらの研究でも言及されているが，Bloom filter（カウンタ）の適切なサイズ（item の種類数，平均対数頻度などに依存）を事前に決めることができない（また，キーを保持していない関係で動的に変更することもできない）ので，完全に one-pass で数えるというわけにはいかなさそうだ．また，log-frequency bloom filter では，頻度 f を量子化 log_(1+ε)(f) して保存する（εが相対誤差）のだけど，カウンタを更新・取得する item の頻度が大きくなるほど，また相対誤差を小さくしようとすればするほど，カウンタを確認する回数が増えて処理速度が落ちてしまう．
その他，CountMin Sketch で相対誤差を減らすヒューリスティクス

なども試されている（観測された item に対して各カウンタの対応するスロットを更新するときに，その時点での近似頻度から大きく外れるスロットは更新しない; 手元の実装で試したところ，更新は20%ほど遅くなるものの，近似頻度の誤差を減らすのにかなり効果がある感じ．+10 行ほどで実装できるし，オススメ）．

ここまで色々な手法をみてきたけど，これらのアルゴリズムは，基本的に非常に似通っていて，論文のタイトルも似たようなのばかりなので紛らわしい．CountMin Sketch と spectral Bloom filter (SIGMOD 2003) とか（前者はハッシュ関数ごとに独立したカウンタを用いるが，後者は共通のカウンタを一つだけ用いる），名前が全然違っていても，似たものがあるので注意が必要だ．

論文によって，しっかり読み込んだものと，斜め読み程度のが混ざっているので，説明の粒度がばらばらで無駄に長くなってしまった．今後は分散計算と親和性が高いアルゴリズムが増えていくと思われるけど，その辺りは個人的にあまり興味がないところもあって割愛．
[追記] 適当に書いていたところを少しずつ直しておこう．
[追記; 11/19] counter-based なカウンタ，sketch-based なカウンタで有望そうな space saving と CountMin sketch (+ conservative update) を，それぞれ c++ で実装してみた．

スループットは，Intel core2 3.2Ghz で，キーを陽に保存しない CountMin sketch (δ=0.001, ε=0.01-0.0001)が 58-65MiB/sec (10-11M words/sec)，陽に保存する space saving (ε=0.01-0.00001) が 37-52MiB/sec (6-9M words/sec) というところ．動的ダブル配列を使って Wikipedia のテキスト処理を高速化 - ny23の日記 で使った日本語 Wikipedia 全文 (テキストのみで1.5GiB) なら，30秒ぐらいで処理できる．手元のデータでどんな出力が得られるか試すぐらいなら使えるかも．

*1:lossy counting では，カウンタのサイズが最悪 O(1/ε log Nε) なのに対し，space saving では O(1/ε)．ただし，lossy couting の空間使用量が頻度分布の偏りに強い影響を受けることや，lossy counting では space saving より 1 item 辺りの空間使用率が良いデータ構造を使えることを考慮すると，実データセットでは大きな差は出ない感じ．

*2:このサーベイ論文の更新速度に関する実験結果は，参考程度にとどめておいた方が良さそう．例えば，space saving は lossy counting よりかなりスループットが出ているけど，別のサーベイ論文（Frequent items in streaming data: An experimental evaluation of the state-of-the-art (Data & Knowledge engineering 68, 2009)）では，（space saving を除いて，VLDB Journal のサーベイ論文の実験とほぼ同じ実装を用いているようだけど）全く逆の結果が出ている（ように見える）．また，著者らによる lossy counting の実装を眺めてみると，最適化の余地がまだあるように見える．item の型が uint32_t で，かつデータ全体を予めメモリ上に載せて実験しているのにも注意が必要で，自分で実装して実験した限り，item の型が可変長文字列 (char *) の場合などで動的なメモリ確保が必要となる場合は（1 行 1 item のデータを読み込むだけでも）入力を用意するところの方がボトルネックで，上記のどの手法でも動的ダブル配列を使って Wikipedia のテキスト処理を高速化 - ny23の日記のとき実装した富豪的なカウンタの2倍以内の速度に収まった．

*3:例えば，既約多項式に基づくハッシュ関数族など (cf. Recursive n-gram hashing is pairwise independent, at best (Computer Speech & Language 24 (4), 2010))．この論文では，文字列からから部分文字列 (character n-gram) をキーとして取り出す際に（巡回多項式に基づくハッシュ関数族を用いることで）そのハッシュ値を（最大n倍）高速に計算する手法が提案されてる．

*4:カウンタの数が O(ln 1/δ) であるため．例えば CountMin Sketch で δ を 0.01→0.0001 にしても，空間使用量で2倍，頻度の更新・取得速度で1/2倍程度の性能低下で済む．