Good-Turing frequency estimation

From Wikipedia, the free encyclopedia

Good–Turing frequency estimation is a statistical technique for predicting the probability of occurrence of objects belonging to an unknown number of species, given past observations of such objects and their species. (In drawing balls from an urn, the 'objects' would be balls and the 'species' would be the distinct colors of the balls (finite but unknown in number). After drawing $R r e d$ red balls, $R b l a c k$ black balls and $R g r e e n$ green balls, we would ask what is the probability of drawing a red ball, a black ball, a green ball or one of a previously unseen color.)

1 Historical background
2 The method
3 References
4 See also

[edit] Historical background

GTFE was developed by Alan Turing and his assistant I.J. Good during World War II. (It was part of their efforts at Bletchley Park to crack German ciphers for the Enigma machine during the war). Turing at first modeled the frequencies as a binomial distribution, but found it inaccurate. Good developed smoothing algorithms to improve the estimator's accuracy.

The discovery was recognized as significant when published by Good in 1953, but the calculations were difficult so it was not used as widely as it might have been.^[1]

The method even gained some literary fame due to the Robert Harris novel Enigma.

In the 1990s, Geoffrey Sampson worked with William A. Gale of AT&T, to create and implement a simplified and easier to use variant of the Good-Turing method ^[2] described below.

[edit] The method

Let us define some data structures and notation.

Assume we have observed X distinct species, numbered x = 1, ... , X

The frequency vector $R x$ gives the number of objects we have observed for species x

The frequency of frequencies vector $N r$ shows how many times the frequency r occurs in the vector $R x$ . For example $N 1$ is the number of species for which only 1 object was observed.

Note that the total number of objects observed, N, can be found from $N = \sum r N_r$ .

The first step in the calculation is to find an estimate of the total probability of unseen objects. This estimate is $p 0 = N 1 / N$

The next step is to find an estimate of probability for objects which were seen r times, this estimate is $p_r = \frac{(r+1) S(N_{r+1})}{N S(N_r)}$

The notation $S ()$ means the smoothed or adjusted value of the frequency shown in parenthesis. An overview of how to perform this smoothing will now be given.

We would like to make a plot of $log N r$ versus $log r$ but this is problematic because for large r many $N r$ will be zero. Instead we plot $log Z r$ versus $log r$ where Z is defined as

$Z_r = \frac{N_r}{0.5(t-q)}$ where q, r and t are consecutive subscripts having

N q, N r, N t

non zero.

A linear regression is then fit to the log-log plot. For small values of r we take $S (N r) = N r$ (that is, no smoothing is performed), while for large values on r $S (N r)$ is read off the regression line. An automatic procedure (not described here) specifies at what point the switch from no smoothing to linear smoothing should take place.

Code for the method is available in the public domain.