Heapsの法則によるコーパス中の語彙数予測と評価実験

さて先日あることがきっかけでヒープスの法則 (Heaps' law) のことを思い出した．最初はヒープの法則と記憶していたのだけれど，'がHeapsの後ろにあるので，ヒープスの法則とかヒープス則と呼ぶのが正しいのだろう．ここではHeapsの法則と呼ぶことにする．

Heapsの法則とはN語数から成るコーパスにおいて，総語彙数Dは以下の等式で表現できるというもの*1

$D = k N^\beta$

ここで，kとβはコーパスによって定められた定数とする．英文コーパスではβは大体0.4-0.6になるらしい*2

この法則が示唆することは，コーパスサイズの増加に対して語彙は増え続けるというもの．まぁlogスケールにおいては直線なので，徐々にサチっていくのは確かであるが．

Wikipediaでヒープスの法則の出展を調べてみると，どうやら1978年出版のHeaps著"Information Retrieval"[1]内で提案されたものらしい．その後，Zipfの法則との関連を示した論文[2]や，Zipfの法則を一般化したMandelbrot分布からHeapsの法則の導出を示した論文[3]があるのだけれど，~~全く理解していない~~横道に逸れてしまうので本記事からは割愛．

検索エンジンにおいては検索対象であるコーパスにおける総語彙数の予測は大切な問題であるため，その後の情報検索の教科書でも必ずと言ってもいいほど紹介されるようになったのだろう*3

情報検索が専門ですとかほざいている人間がHeaps本を読まないわけにはいかないとあわてて図書館にかけこみHeaps本をGET．

出版年は1978年．自分が生まれる前に書かれた本に，現代の検索エンジンの基礎が書かれていると思うとゾクゾクした．改めて検索エンジンはウェブの出現によって改めて注目されるようになったという背景を感じることができる．

しかし，そんなワクテカ気分でHeapsの法則について書かれた部分を読んでみたところ，Heaps本ではたったの3ページで紹介されて，ハイおしまい，というものであった．まさか著者もその後情報検索では必ずといっていいほど引用されるようになるとは思わなかっただろう．

簡単なスクリプトですぐに計算できることなので実データに対してHeapsの法則が成り立っているかどうかを検証してみる．

また教科書的には現象を説明できるよね，すごいよね，ハイおしまい，でいいのかもしれないけれど，やはり工学的手法たるもの「役に立ってナンボ」というのが本来あるべき姿だと思う．というわけで，データセットの一部が与えられた際にHeapsの法則に従って予測モデルを構築し，ある総語数における総語彙数を予測する精度を評価しようと考えた．

というわけで以下の2つを検証してみる．

検証1: 実データにおける単語数-語彙数曲線を描いて眺めてみる
検証2: コーパスの一部を用いてHeapsの法則に基づく予測モデルを作成して予測曲線を描いて眺めてみる

検証のために，以下の2つの公開データセットを利用した．

Reuters-21578 (Reuters)
- http://www.daviddlewis.com/resources/testcollections/reuters21578/
- SGMLタグは全て除去し，スペース区切りで単語を抽出
- 不要語の除去，ステミングは行わない
AOL query log (AOL)
- http://www.gregsadetsky.com/aol-data/
- クエリに含まれるキーワードをスペースで区切って単語を抽出
- 不要語の除去，ステミングは行わない
- 総単語数が多いため，100000語までは1単語ずつカウント，それ以降は100単語毎に語彙数をカウント

Reutersはテキスト分類で用いられているニュース記事データセットで，AOLは，検索エンジンに対するクエリログのデータセット．Reutersでもいくつかのトピックに分けられているが，クエリログの場合はニュース記事に比べてトピックの偏りや多様性が大きく，Heapsの法則から外れた結果になるのではないかと期待して検証対象としてみた．なお，いずれのコーパスもデータセットのシャッフルは行っていないため，IDや日付の小さい方からカウントをしている．

検証1: 実データにおける単語数-語彙数曲線を描いて眺めてみる

まずは2つのコーパスにおける単語数-語彙数曲線を描いてみる．実数グラフと両対数グラフも描いてみる．

Reuters (実数スケール)

きれいな曲線を描いているが，x=2.5e+6あたりで一度語彙数増加のペースが上がっているように見える．具体的な原因はわからないが，Reutersコーパスを眺めてみると，21個に分割されているうち，最初の16個のファイルが1987年3月-4月の記事で構成されているのに対し，残りの5ファイルでは1987年4月-10月の記事で構成されているため，コーパスにおける記事サンプリング数に偏りがあることがわかった．これが原因だと思って，2.5e+6語数あたりがちょうど5月あたりになっているといいなぁと思って調べてみたが，そういうわけでもなさそう．おそらく，断続的に新しい話題が生まれたのだろうか．

Reuters (両対数スケール)

両対数グラフを描いてみると何回かギザギザしている部分が見て取れる．最初の曲線とは少し違う印象を受ける．最終的にはほぼ直線になっている．

AOL (実数スケール)

Reutersに比べて曲線の傾きがゆるやか (Heapsの法則で言うところのβが大きい) ように見える．AOLデータは約2ヶ月間のクエリログだが，日常的に新しい話題が発生し，ユーザは日々似た話題を追いかける傾向があるため語彙の増加が波打っているのだろうか．

AOL (両対数スケール)

両対数にすると微妙にゆがんでいる部分もあるが，基本的には直線近似ができそうな形をしている．というわけでクエリログだとHeapsの法則から外れるかな，という予想を外してしまった．Heapsの法則すげぇ．

検証2: コーパスの一部を用いてHeapsの法則に基づく予測モデルを作成して予測曲線を描いて眺めてみる

どうやら2つのデータセットでHeapsの法則が成り立ちそうなことがわかったので次は予測モデルを作ってみる．

さてHeapsの法則は一見するとNの肩の上に $\beta$ が乗っているので推定が難しそうに見えるけれど，左辺右辺でlogを取ると

$\log D = \beta \log N + \log k$

といういわゆるy = a x + bの線形回帰モデルと解釈することができる．大学で然るべき講義をまじめに受けていた学生には対数->対数の単回帰モデルだということがわかる (僕はわからなかった)．

ここでは特に凝ったことをするつもりはないので，最小二乗法でフィッティングすることにする．最小二乗法の場合にはデータが与えられた際に閉じた解で求めることができるので，行列のかけ算と逆行列計算ができればよい．

~~そんな簡単なプログラムも書くことがでｋ~~今回はデータ数が多いのでナイーブな実装では苦労すると思い，Rのlm関数で最小二乗法に基づくフィッティングを行った．

以下のようにlmを用いて両対数の線形回帰モデルを推定する．

# データの読み込み
> x <- read.table("reuters-21578_per_token.dat")

# 最小二乗法による線形回帰モデルの推定 (logを付けることを忘れずに)
> lm(log(x$V2) ~ log(x$V1))

Call:
lm(formula = log(x$V2) ~ log(x$V1))

Coefficients:
(Intercept)    log(x$V1)
     1.8359       0.6784

# ここで切片はlog kなので，expを取ってkを計算する
> exp(1.8359)
[1] 6.270775

上記の例では最小二乗近似曲線は $D = 6.270775 N^{0.6784}$ となる．

2つのデータセットについて以下の2つを加えたグラフを描いてみる

全データを用いた最小二乗近似曲線
一部のデータを用いた最小二乗近似曲線

Reuters

全単語を用いた場合と，10,000語 (0.2%)，370,000語 (10%) における最小二乗近似曲線を加えたグラフを以下に示す．

10,000語を用いた予測は最終的には大きく外れており，370,000語を用いてもまだ外れている．全データを用いれば綺麗に $k N^\beta$ という指数モデルで綺麗にフィッティングできていることがわかる．

なお，対数スケールの場合は以下の通りになる．

AOL

こちらもReuters同様に全単語を用いた場合と，10,000単語 (0.5%)，250,000単語 (10%) における最小二乗近似曲線を加えたグラフを以下に示す．

10,000単語の近似曲線では予想を大きく外しているが，全体の10%である250,000単語で推定したパラメータでかなり近い曲線を描けていることがわかる．AOLの方がReutersに比べて少ないデータ比率で近い曲線を描けていることが興味深い．

なお，対数スケールの場合は以下の通りになる．

まとめ

本記事ではHeapsの法則を紹介し，公開データセットを用いてHeapsの法則が成立するか，また最小二乗近似によるモデル予測がどのようになるかということを検証してみた．

コーパスがあるデータソースからサンプリングされたものだとすると，このままコーパスサイズを大きくした場合の総語彙数の変化を予測することが可能になるのだけれど，今回の検証結果からはコーパスによって正確な予測に必要な比率はまちまちということがわかった．

Future work
- 日本語コーパスでの検証．特にTwitterあたり
- 予測モデルの高精度化
  - 最小二乗法以外のフィッティング方法などを検討
  - 新たなヒューリスティクスの導入

なんだか書いているうちに堅い文章になってしまったなぁ．実験は30分程度で終わったのにブログ記事書くのに変に気合い入れすぎて2-3時間もかけてしまった．次回はもっとゆるふわな実験記事にしたい．

References

[1] H. S. Heaps, "Information Retrieval: Computational and Theoretical Aspects", Academic Press, 1978.
[2] L. Lu, Z.-K. Zhang and T. Zhou, "Zipf's Law Leads to Heaps' Law: Analyzing Their Relation in Finite-Size Systems", arXiv:1002.3861v2, 2010.
- http://arxiv.org/abs/1002.3861
[3] D.C. van Leijenhorst, Th.P. van der Weide, "A formal derivation of Heaps' Law", Information Sciences, Vol.170, pp.263--272, 2005.

付録A

単語カウントに用いたPerl ソースコードは以下のとおり

reuters

# reuter-count.pl
use strict;
use warnings;

my $doc_count   = 0;
my $token_count = 0;
my %count_of;

while (my $line = <>) {
  chomp $line;

  foreach my $contents (split /<[^>]+>/, $line) {
    next unless ($contents =~ /\S+/);
    foreach my $word (split /\s/, $contents) {
      $count_of{ $word }++;
      $token_count++;
      print $token_count, "\t", scalar keys %count_of, "\n";
    }
  }
}

use strict;
use warnings;

my $token_count = 0;
my %count_of;

while (my $line = <>) {
  chomp $line;
  foreach my $word (split /\s/, $line) {
    $count_of{ $word }++;
    $token_count++;
    if ($token_count < 100000 ||
        $token_count % 100 == 0) {
      print $token_count, "\t", scalar keys %count_of, "\n";
    }
  }
}

*1:ここで語数とはいわゆるトークン数のことを表し，語彙と呼ぶ際にはユニークなものを表す

*2:ただしこれはWikipedia情報で，Heapsによる記述[1]では前述の値の範囲は記されておらず，図書館の目録タイトル，化学の蔵書タイトルにおけるデータを元に近似値を求め，β= 0.5, 0.6という値を示している．

*3:IIR, Croft本，モダインでは確認済．それぞれの教科書の解説は情報検索ことはじめ〜教科書編その2 (2011年決定版) 〜を参照