Good–Turing推定

Good–Turing推定 (英語: Good–Turing frequency estimation) は、これまでに観測されていない種の対象に遭遇する確率を、異なる種の対象 (有限個だが総数は不明) についての過去の観測情報から推定するための統計的手法である。壺から玉を取り出すことを考えると、「対象」はボールに対応し、「種」は玉の色に対応する。赤色の玉 $R_{\text{red}}$ 黒色の玉 $R_{\text{black}}$ 緑色の玉 $R_{\text{green}}$ を引いたあとに、次に赤色の玉、黒色の玉、緑色の玉、あるいはこれまでに観測していない色の玉が出る確率はいくつか、というのがここでの問題である。

歴史

Good–Turing推定はアラン・チューリング (Alan Turing) と彼の助手I. J. グッド (I. J. Good)により、第二次世界大戦中ブレッチリー・パーク (Bletchley Park)におけるドイツ軍のエニグマ暗号を解読する試みの中で提案された。チューリングははじめ頻度を多項分布でモデル化したが、そのモデルは不正確だとわかった。グッドはその推定法の精度を改善すべく、平滑化アルゴリズムを考案した。

その発見はグッドにより1953年に公開され、多大な注目をあつめることとなった 。しかしその計算は難しく、それほど広く使用されることはなかった 。ただ、グッドの手法はロバート・ハリス (Robert Harris) の小説『暗号機エニグマへの挑戦 (Enigma)』により文学的な名声をいくらか得ることとなった。

1990年代、Geoffrey SampsonはAT&TのWilliam A. Galeと共に、次に述べるシンプルで使いやすいGood–Turing推定の手法を考案、実現した。

方法

まず、表記と必要なデータ構造を以下のように定義する:

• 観測された種の総数を X とする。観測されたそれぞれの種を x = 1, ..., X と番号付けする。
• 頻度ベクトル R を、観測された種 x の個体数 R_x を要素に持つベクトルとして定義する。
• 頻度ベクトル中の頻度 $(N_{r})_{r=0,1,\ldots }$ を、ベクトル R 中の r の頻度、つまり r に一致する要素 R_x の個数により定義する。

$N_{r}=|\{x\mid R_{x}=r\}|$

例えば $N_{1}$ は1つしか個体が観測されなかった種の数を表す。ここで、対象の総個体数 N は次のように表される。

$N=\sum _{r=1}^{\infty }rN_{r}.$

計算の最初のステップは、未観測の種の総確率を推定することである。その推定値は次式である。

$p_{0}={\frac {N_{1}}{N}}.$

次のステップは、 r 回観測された種の確率の推定値を求めることである。それぞれの種に対する確率の推定値は次である:

$p_{r}={\frac {(r+1)S(N_{r+1})}{NS(N_{r})}}.$

このグループ (r 回観測された種のグループ) のいずれかの種と遭遇する確率を推定するためには、次の式を計算すればよい:

${\frac {(r+1)S(N_{r+1})}{N}}.$

ここで $S()$ はカッコ内の頻度が平滑化あるいは調整された値であることを意味する (empirical Bayes methodも参照)。この平滑化を行う方法について、概要を次に述べる。

$\log N_{r}$ と $\log r$ の関係をプロットしたいとする。しかしこれは r が大きくなれば多くの $N_{r}$ がゼロになってしまうため、問題がある。代わりに、修正された数 $\log Z_{r}$ を $\log r$ に対してプロットする。ここで Z_r は次で定義される。

$Z_{r}={\frac {N_{r}}{0.5(t-q)}},$

そしてここで q、 r そして t は非ゼロである $N_{q},N_{r},N_{t}$ を持つ三連続の添字である。r が1のとき、qは0とする。r が最後の非ゼロの頻度であるときは t を 2r − q とする。

Good–Turing推定はそれぞれの種の出現回数が二項分布に従うことを仮定している。

そして両対数グラフに対して線形単回帰 (simple linear regression) を行う。小さい r に対しては、$S(N_{r})=N_{r}$ (つまり、平滑化を行わない) としてよい。一方で大きい r に対しては、$S(N_{r})$ の値は回帰線から取る。(ここでは記述しないが) 自動的な手続きによってどの点でその平滑化無しから線形平滑化への切替が行われるべきかを特定することができる 。その手法のソースコードはパブリックドメインで使用可能である。

関連項目

• Ewens sampling formula
• Pseudocount