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, $\overline{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,\dots }$, 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}^{\mathrm{\infty }}r{N}_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.Predefinição:Carece de fontes

O código para o método é avaliado em domínio público.Predefinição: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