Estimativa de frequência de Good – Turing - Good–Turing frequency estimation

A estimativa de frequência de Good – Turing é uma técnica estatística para estimar a probabilidade de encontrar um objeto de uma espécie até então invisível, dado um conjunto de observações anteriores de objetos de diferentes espécies. Ao tirar 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, perguntaríamos qual é a probabilidade de tirar uma bola vermelha, uma bola preta, uma bola verde ou uma de uma cor nunca antes vista.

Contexto histórico

A estimativa de frequência Good – Turing foi desenvolvida por Alan Turing e seu assistente IJ Good como parte de seus métodos usados ​​em Bletchley Park para quebrar cifras alemãs para a máquina Enigma durante a Segunda Guerra Mundial . Turing a princípio modelou as frequências como uma distribuição multinomial , mas achou imprecisa. Algoritmos de suavização bem desenvolvidos para melhorar a precisão do estimador.

A descoberta foi reconhecida como significativa quando publicada por Good em 1953, mas os cálculos eram difíceis, por isso não foi usada tão amplamente como poderia ter sido. O método até ganhou alguma fama literária devido ao romance Enigma de Robert Harris .

Na década de 1990, Geoffrey Sampson trabalhou com William A. Gale da AT&T para criar e implementar uma variante simplificada e mais fácil de usar do método Good – Turing descrito abaixo. Várias justificativas heurísticas e uma derivação combinatória simples foram fornecidas.

O método

Notação

  • Assumindo que espécies distintas foram observadas, enumeradas .
  • Então, o vetor de frequência,, tem elementos que fornecem o número de indivíduos que foram observados para as espécies .
  • O vetor de frequência de frequências , mostra quantas vezes a frequência r ocorre no vetor (ou seja, entre os elementos ):

Por exemplo, é o número de espécies para as quais apenas um indivíduo foi observado. Observe que o número total de objetos observados,, pode ser encontrado a partir de

A primeira etapa do cálculo é estimar a probabilidade de que um indivíduo futuro observado (ou o próximo indivíduo observado) seja membro de uma espécie até então não vista. Esta estimativa é:

O próximo passo é estimar a probabilidade de que o próximo indivíduo observado seja de uma espécie que já foi vista várias vezes. Para uma única espécie, esta estimativa é:

Para estimar a probabilidade de que o próximo indivíduo observado seja de qualquer espécie deste grupo (ou seja, o grupo de espécies vistas vezes), pode-se usar a seguinte fórmula:

Aqui, a notação significa o valor suavizado ou ajustado da frequência mostrada entre parênteses (consulte também o método empírico de Bayes ). Segue uma visão geral de como realizar essa suavização.

Gostaríamos de fazer um gráfico de versus, mas isso é problemático porque, para grande, muitos serão zero. Em vez disso, uma quantidade revisada,, é plotada versus , onde Z r é definido como

e onde q , r e t são subscritos consecutivos não nulos. Quando r é 1, considere q igual a 0. Quando r é a última freqüência diferente de zero, considere ser .

A suposição da estimativa de Good-Turing é que o número de ocorrências para cada espécie segue uma distribuição binomial.

Uma regressão linear simples é então ajustada ao gráfico log – log. Para valores pequenos de é razoável definir (ou seja, nenhuma suavização é executada), enquanto para valores grandes de r , os valores de são lidos na linha de regressão. Um procedimento automático (não descrito aqui) pode ser usado para especificar em que ponto a mudança de sem suavização para suavização linear deve ocorrer. O código do método está disponível no domínio público.

Derivação

Muitas derivações diferentes da fórmula acima para foram fornecidas.

Uma das maneiras mais simples de motivar a fórmula é presumir que o próximo item se comportará de maneira semelhante ao anterior. A ideia geral do estimador é que atualmente estamos vendo itens nunca vistos em uma certa frequência, itens vistos uma vez em uma certa frequência, itens vistos duas vezes em uma certa frequência e assim por diante. Nosso objetivo é estimar a probabilidade de cada uma dessas categorias, para o próximo item que veremos. Dito de outra forma, queremos saber a taxa atual em que itens vistos duas vezes estão se tornando itens vistos três vezes e assim por diante. Uma vez que não assumimos nada sobre a distribuição de probabilidade subjacente, parece um pouco misterioso à primeira vista. Mas é extremamente fácil calcular essas probabilidades empiricamente para o item anterior que vimos, mesmo assumindo que não nos lembramos exatamente de qual item era: Pegue todos os itens que vimos até agora (incluindo multiplicidades) - o último item que vimos foi um aleatório desses, todos igualmente prováveis. Especificamente, a chance de termos visto um item pela enésima vez é simplesmente a chance de ser um dos itens que vimos agora , a saber . Em outras palavras, a nossa chance de ver um item que tinha sido visto r vezes antes foi . Portanto, agora simplesmente assumimos que essa chance será quase a mesma para o próximo item que veremos. Isso nos dá imediatamente a fórmula acima para , por definição . E para , para obter a probabilidade de que um particular dos itens vai ser o próximo visto, precisamos dividir essa probabilidade (de ver algum item que foi visto r vezes) entre as possibilidades para que determinado item que poderia ser. Isso nos dá a fórmula . Claro, seus dados reais provavelmente serão um pouco barulhentos, então você desejará suavizar os valores primeiro para obter uma estimativa melhor de quão rápido as contagens de categorias estão crescendo, e isso dá a fórmula conforme mostrado acima. Esta abordagem está no mesmo espírito que derivar o estimador Bernoulli padrão simplesmente perguntando quais eram as duas probabilidades para o lançamento da moeda anterior (depois de embaralhar as tentativas vistas até agora), dadas apenas as contagens de resultados atuais, embora não pressuponha nada sobre a distribuição subjacente .

Veja também

Referências

Bibliografia