Estimativa de frequência de Good-Turing

A estimativa de frequência Good-Turgin foi desenvolvida por Alan Turing e seu assistente I. J. Good como parte de seus esforços na Bletchley Park para quebrar a cifra Alemanha para o Enigma (máquina) durante a Segunda Guerra Mundial. Turing primeiramente modelou as frequências como uma distribuição multinominal, mas a achou inexata. O algoritmo de suavização de Good desenvolvido para melhorar a precisão da estimativa.

A descoberta foi reconhecida como significante quando publicada por Good in 1953,[1] but the calculations were difficult so it was not used as widely as it might have been.[2] O método ganhou até alguma fama literária devido ao romance Enigma de Robert Harris.

Nos anos de 1990, Geoffrey Sampson trabalho com William A. Gale of AT&T, parar criar e implementar um variante simplificado e fácil de usar do método Good-Turing[3] descrito abaixo.

A primeira notação e algumas estrutura de dados requeridas são definidas:

• Assumindo que X espécies distintas tenham sido observadas, numeradas x = 1, ..., X.
• Então o vetor frequência, ${\displaystyle {\bar {R}}}$, tem elementos ${\displaystyle R_{x}}$ que dão o número de indivíduos que foram observados para a espécie x.
• A frequência do vetor frequência, ${\displaystyle (N_{r})_{r=0,1,\ldots }}$, mostra quantas vezes a frequência r ocorre em um vetor R, i.e. entre os elementos ${\displaystyle R_{x}}$.

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

Por exemplo ${\displaystyle N_{1}}$ é o número de espécies para o qual apenas 1 indivíduo foi observado. Perceba que o número total de objetos observadosN, não pode ser encontrado a partir de

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

O primeiro passo no cálculo é achar uma estimativa para a probabilidade total de espécies não vistas. Essa estimativa é [4]

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

O próximo passo é achar uma estimativa de probabilidade para as espécies que foram vistas r vezes. Para uma 'única espécie esta estimativa é:

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

Para estimar a probabilidade de encontrar alguma espécie desse grupo (i.e., o grupo de espécies vistos r vezes) pode ser usada a seguinte fórmula:

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

Aqui, a notação ${\displaystyle S()}$ significa o valor suavizado ou ajustado da frequência mostrada em parênteses.

Nós gostaríamos de fazer um gráfico de ${\displaystyle \log N_{r}}$ versus ${\displaystyle \log r}$ mas isso é problemático porque para r grandes muitas ${\displaystyle N_{r}}$ serão zero. Em vez disso, uma quantidade revisada, ${\displaystyle \log Z_{r}}$, é colocada contra ${\displaystyle \log r}$, onde Z_r é definida como

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

e onde q, r e t são subscripts consecutivos tendo ${\displaystyle N_{q},N_{r},N_{t}}$ não zero. Quando r é 1, tome q sendo 0. Quando r é a última frequência não-zero, tome t como 2r − q.

A suposição da estimativa de Good-Turing é que o número de ocorrências para cada espécie segue uma distribuição binária.[5]

Uma regressão linear simples é então encaixada ao log-log do gráfico. Para pequenos valores de r é razoável para definir ${\displaystyle S(N_{r})=N_{r}}$

(isto é, nenhuma suavização é realizada), enquanto para grandes valores de r, valores de ${\displaystyle S(N_{r})}$ são lidos da linha de regressão. Um procedimento automático (não descrito aqui) pode ser usado para especificar em que ponto a troca de não-suavização para a suavização linear deve acontecer.^{[carece de fontes?]}

O código para o método é avaliado em domínio público.[6]^{[carece de fontes?]}

• Ewens sampling formula
• Pseudocount