Estimativa de frequência de Good-Turing

Estimativa de frequência Good-Turing é uma técnica estatística para prever a probabilidade de ocorrência de objetos pertencentes a um número de espécies desconhecidos, dado observações passadas desses objetos e suas espécies. (Desenhando bolas de uma urna, os "objetos" seriam bolas e as "espécies" seriam as cores distintas das bolas (finitas mas desconhecidas em número). Depois de desenhar $R_{\text{red}}$ bolas vermelhas, $R_{\text{black}}$ bolas pretas e $R_{\text{green}}$ bolas verdes, nós perguntaríamos qual é a probabilidade de desenhar a bola vermelha, a bola preta, a bola verde ou uma de uma cor ainda nao vista.)

Acontecimentos históricos

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, but the calculations were difficult so it was not used as widely as it might have been. 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 descrito abaixo.

O método

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, ${\bar {R}}$, tem elementos $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, $(N_{r})_{r=0,1,\ldots }$, mostra quantas vezes a frequência r ocorre em um vetor R, i.e. entre os elementos $R_{x}$.

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

Por exemplo $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

$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 é

$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 é:

$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:

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

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

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

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

e onde q, r e t são subscripts consecutivos tendo $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.

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

(isto é, nenhuma suavização é realizada), enquanto para grandes valores de r, valores de $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.^{[carece de fontes]}

Veja também

• Ewens sampling formula
• Pseudocount

Referências

• David A. McAllester, Robert Schapire (2000) On the Convergence Rate of Good–Turing Estimators'', Proceedings of the Thirteenth Annual Conference on Computational Learning Theory pp. 1–6
• David A. McAllester, Ortiz, Luis (2003) Concentration Inequalities for the Missing Mass and for Histogram Rule Error'', Journal of Machine Learning Research pp. 895–911