冪乗則と一様分布と遷移キャッシュ

これまでキーの参照頻度が一様分布に従うという無茶な仮定の下で実験をすることが多かったのですが，遷移キャッシュを導入したということもあり，冪乗則だとどうなるのかを調べてみました．実験に用いたデータは，日本語ウェブコーパスにおける頻度 1000 以上の単語 N-gram です．

単語 N-gram コーパスの頻度情報を利用すれば，冪乗則が成立する状況を再現できます．すなわち，一部の高頻度な N-gram が全体に対して大きな割合を占め，ほとんどの N-gram は稀に出現するのみとなります．

遷移キャッシュの効果は高頻度の遷移を高速化することであり，参照頻度が冪乗則に従う状況であれば，より高い効果が期待できます．

実験結果において，1 つ目のシートがキャッシュあり，2 つ目のシートがキャッシュなしになっています．3 行目の Power law と Uniform は検索時の参照頻度を冪乗則と一様分布にした場合を示しています．5 行目の Uniform と Power law は重みを一様にした場合と冪乗則にした場合という意味です．

  • 3 行目
    • Power law: 検索するキーをランダムに選んだ場合です．
    • Uniform: 検索するキーを頻度に応じて選んだ場合です．
  • 5 行目
    • Uniform: すべてのキーの重みを 1 にした場合です．
    • Power law: キーの頻度を重みとした場合です．

注目すべき部分は F, G 列です．F 列は重みを一様にした場合，すなわち，あらかじめ参照頻度を求めることができない場合と考えてください．逆に，G 列の方は，あらかじめ参照頻度が分かっている場合です．

Cache On のシートを見ると，参照頻度を使えば検索時間を短縮できることが分かります．1-gram のみが対象のときは効果が大きく，1-gram から 7-gram まですべてを対象にすると効果がほとんどなくなっているのは，高頻度の N-gram には自然と派生する N-gram が多くなり，ノードの重みに反映されるからだと考えられます．

次に，Cache On/Off のシートで比較すると，参照頻度が Power law のときはキャッシュの効果が高くなっていることが確認できます．当初の予想通りです．

以上，参照頻度が推定できる状況では，検索をより高速化できることが確認できました．今まできちんと確認していなかったので，これで安心できます．

# なんだかとても眠たいので適当な考察になってしまいましたが，予想と大きく外れるような結果ではなかったこともあり，このくらいで…．

（追記 2011-05-08）もう一つ注目すべきことは，参照頻度を推定できなくても，それなりに効果があることです．これは，キー単位での頻度は一様でも，ノード単位で見ると一様ではなくなるからです．たとえば，"AB", "AC" というキーの推定頻度を両方とも 1 にしたとき，"A" に対応するノードの推定頻度は 2 になります．