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 bolas vermelhas, bolas pretas e 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.Newsise: Scientists Explain and Improve Upon 'Enigmatic' Probability Formula, a popular review of 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-TuringSampson, Geoffrey and Gale, William A. (1995) Good‐turing frequency estimation without tears 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, , tem elementos que dão o número de indivíduos que foram observados para a espécie x. A frequência do vetor frequência, , mostra quantas vezes a frequência r ocorre em um vetor R, i.e. entre os elementos .
Por exemplo é 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
O primeiro passo no cálculo é achar uma estimativa para a probabilidade total de espécies não vistas. Essa estimativa é
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 é:
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:
Aqui, a notação significa o valor suavizado ou ajustado da frequência mostrada em parênteses.
Nós gostaríamos de fazer um gráfico de versus mas isso é problemático porque para r grandes muitas serão zero. Em vez disso, uma quantidade revisada, , é colocada contra , onde Zr é definida como
e onde q, r e t são subscripts consecutivos tendo 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.Lecture 11: The Good-Turing Estimate. CS 6740, Cornell University, 2010
Uma regressão linear simples é então encaixada ao log-log do gráfico. Para pequenos valores de r é razoável para definir
(isto é, nenhuma suavização é realizada), enquanto para grandes valores de r, valores de 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.
O código para o método é avaliado em domínio público.Sampson, Geoffrey (2005) Simple Good–Turing Frequency Estimator (code in C)
Ver 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) [http://jmlr.csail.mit.edu/papers/v4/mcallester03a.html Concentration Inequalities for the Missing Mass and for Histogram Rule Error'', Journal of Machine Learning Research pp. 895–911
Categoria:Probabilidade