Good-Turing推定

背景

以前の記事（データ生成工場の設計方法）で、タクソノミーのカバレッジ（網羅性）とデンシティ（密度）という考え方を扱った
そのとき、集めているデータが母集団に対してどれくらい網羅できているか、まだどれくらい未知の要素が残っていそうかを見積もるために、Good-Turing推定という手法を使った
名前と大まかな用途は知っていたが、中身をきちんと理解していなかったので整理する

Good-Turing推定とは

過去の観測データから、まだ観測されていない種類（species）に遭遇する確率を推定する統計的手法
例えるなら、壺の中に色のついた玉がたくさん入っていて、何色の玉がそれぞれ何個あるかは分からない状況。何個か玉を取り出して色を記録したとき、次に取り出す玉が「これまで見たことのない色」である確率はどれくらいか、という問題を扱う
単純に「観測回数 ÷ 全観測数」で確率を見積もる最尤推定（MLE）には欠陥がある。特に、まだ一度も観測されていない事象の確率を0と見積もってしまうが、実際にはまだ観測されていないだけで存在する可能性のある事象は多く残っている

歴史的背景

第二次世界大戦中、Alan TuringとI.J. Goodが、Bletchley ParkでのEnigma暗号解読の作業の中で考案した
Turingは最初、暗号鍵の出現頻度を多項分布としてモデル化しようとしたが、精度が不十分だった
そこでGoodが、それを改善する平滑化のアルゴリズムを開発した
Goodは1953年にこの手法を発表したが、計算が煩雑だったため、当時はあまり広く使われなかった
1990年代に、Geoffrey SampsonとWilliam Galeが、計算が簡単な簡略版（Simple Good-Turing）を発表し、実用的に使われるようになった

記法

ある要素（species）$x$が観測された回数を$R_x$とする
$N_r$を、ちょうど$r$回観測された要素の種類数と定義する

$$ N_r = |\{x \mid R_x = r\}| $$

例えば$N_1$は、ちょうど1回だけ観測された要素（種類）の数
全観測数$N$は、次のように表せる

$$ N = \sum_{r \geq 1} r \cdot N_r $$

未知の要素の確率質量

Good-Turing推定の最も有名な結果は、まだ一度も観測されていない要素全体の確率質量の推定式

$$ p_0 = \frac{N_1}{N} $$

直感的には「ちょうど1回だけ観測された要素の割合が高いほど、まだ見たことのない要素がたくさん残っていそうだ」という考え方
逆に、$N_1$が0に近ければ、未観測の要素はほとんど残っていないと推定できる

観測済みの要素の確率

$r$回観測された要素についても、単純な$r/N$ではなく、調整した頻度$r^*$を使う

$$ r^* = \frac{(r+1) \cdot N_{r+1}}{N_r} $$

この調整後の頻度を使うと、$r$回観測された1つの要素の確率は次のようになる

$$ p_r = \frac{r^*}{N} = \frac{(r+1) \cdot N_{r+1}}{N \cdot N_r} $$

これは、観測回数が少ない要素ほど、単純な頻度の比率よりも低く見積もり、その分の確率質量を未観測の要素に配分するという考え方
実際には$N_r$をそのまま使うのではなく、平滑化した値$S(N_r)$を使うのが一般的

$$ p_r = \frac{(r+1) \cdot S(N_{r+1})}{N \cdot S(N_r)} $$

なぜ平滑化が必要か

実際のデータでは、$r$が大きくなるにつれて$N_r$が0になる（その回数だけ観測された要素が1つもない）ことが頻繁に起こる
$N_r = 0$だと、上の式がそのまま使えなくなる
そこで、$\log N_r$を$\log r$に対してプロットし、そこに線形回帰を当てはめることで、$N_r$がなめらかに変化するように補正する
これが、GaleとSampsonによるSimple Good-Turingの中心的なアイデア。$r$が小さい領域ではそのままの$N_r$を使い、$r$が大きい領域では回帰直線から読み取った値を使う

具体例: Wikipediaの中の数字表現を網羅する

実際に使ったのは、Wikipediaの中にある「算用数字（アラビア数字、0〜9の半角・全角digit）を使った表現」のパターンを、できるだけ網羅的に集めたいという場面
「3つ」「３個」「100人」「1,000円」のように、算用数字と助数詞・区切り記号・全角半角の組み合わせには、さまざまなバリエーションがある
このバリエーションの種類は、理論上は無限に作文できるが、実際にWikipediaのような実在のコーパスに出現するパターンとしては、おそらく有限に収まるだろうという前提がある
そこで、記事を順番に読み進めながら、新しく登場した表現パターンを「種類（species）」として数えていく
- これまで見たことのないパターンに出会うたびに、$N_1$（1回だけ観測された種類の数）が増える
- 同じパターンに再度出会うと、そのパターンの観測回数が増える
この状態で、「次にWikipediaの別の記事を読んだとき、まだ見たことのないパターンに出会う確率」を、Good-Turing推定の$p_0 = N_1/N$でそのまま見積もれる
$N_1/N$が十分小さくなってくれば、それは「新しいパターンがほとんど出てこなくなってきた」ことを意味し、母集団（表現パターン全体）がほぼ網羅できた、あるいは有限であるという前提が妥当だったと判断する材料になる
逆に、観測数を増やしても$N_1/N$が一向に下がらなければ、パターンの種類が事実上無限に近い（あるいは想定より大きい）可能性があり、網羅するという前提自体を見直す必要がある

データ生成工場の文脈での使い方

以前の記事で、タクソノミーのカバレッジ（網羅性）とデンシティ（密度）という考え方を扱った
同じ考え方は、教師データ生成のカタログ・タクソノミーにも使える
生成したデータのうち、あるカテゴリ・パターンがちょうど1回しか出てきていないものの割合（$N_1/N$に相当）が高いままであれば、まだ見つけていないカテゴリ・パターンが多く残っていると推定できる
逆に、新しく生成するデータの多くが既存のカテゴリの再登場ばかりになってきたら（$N_1/N$が小さくなってきたら）、母集団をほぼ網羅できてきたと判断できる
つまりGood-Turing推定は、カタログやタクソノミーの網羅性の検査、言い換えると「母集団が有限であり、かつどれくらい網羅できているか」を定量的に見積もるための道具として使える

自然言語処理での利用

もともと暗号解読の文脈で考案された手法だが、自然言語処理でも広く使われてきた
n-gramの言語モデルでは、学習データに出現しなかった単語列（未知のn-gram）にも0ではない確率を割り当てる必要がある
Good-Turing推定による割引（discounting）は、Katzのback-off法など、スムージング手法の一部として使われてきた

まとめ

Good-Turing推定は、過去の観測から、まだ観測されていない事象の確率質量を見積もる統計的手法
第二次世界大戦中にAlan TuringとI.J. Goodが、暗号解読の文脈で考案した
未観測の確率質量は$N_1/N$という単純な式で推定できる。ちょうど1回だけ観測された要素の割合が、未知の要素がどれだけ残っているかの手がかりになる
観測回数が大きい領域では$N_r$が0になりがちなので、GaleとSampsonによるSimple Good-Turingのような平滑化が必要になる
カタログやタクソノミーの網羅性を検査する場面でも、同じ考え方を使って「まだ見つかっていない要素がどれくらい残っていそうか」を見積もることができる

参考文献

Good–Turing frequency estimation - Wikipedia
Gale, W. A., & Sampson, G. (1995). Good-Turing frequency estimation without tears. Journal of Quantitative Linguistics, 2(3), 217-237.
Good-Turing Frequency Estimation Without Tears - Geoffrey Sampson