Mostrar código-fonte de 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 <math>R_\text{red}</math> bolas vermelhas, <math>R_\text{black}</math> bolas pretas e <math>R_\text{green}</math> 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,<ref>{{citar periódico
 |último =Good |primeiro =I.J. |autorlink =I.J. Good
 |ano=1953
 |título=The population frequencies of species and the estimation of population parameters
 |periódico=[[Biometrika]]
 |volume=40 |número=3–4 |páginas=237–264
 |doi=10.1093/biomet/40.3-4.237 |jstor=2333344 | mr = 61330
}}</ref> but the calculations were difficult so it was not used as widely as it might have been.<ref>[http://www.newswise.com/articles/view/501440/ Newsise: Scientists Explain and Improve Upon 'Enigmatic' Probability Formula], a popular review of {{citar periódico|periódico=Science (New York, N.Y.). | volume=302 |número=5644 |páginas=427–31 |ano=2003  |autor =Orlitsky A, Santhanam NP, Zhang J. |título=Always Good Turing: asymptotically optimal probability estimation. | pmid= | doi = 10.1126/science.1088284 }}
</ref> O método ganhou até alguma fama literária devido ao romance ''[[Enigma (novel)|Enigma]]'' de [[Robert Harris (novelist)|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<ref>Sampson, Geoffrey and Gale, William A. (1995) [http://dx.doi.org/10.1080/09296179508590051 Good‐turing frequency estimation without tears]</ref> 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,  ''<math>\bar{R}</math>'', tem elementos <math>R_x</math> que dão o número de indivíduos que foram observados para a espécie ''x''.
* A frequência do vetor frequência, <math>(N_r)_{r=0,1,\ldots}</math>, mostra quantas vezes a frequência ''r'' ocorre em um vetor ''R'', i.e. entre os elementos <math>R_x</math>.

:<math>N_r = |\{ x | R_x = r \}|</math>

Por exemplo <math>N_1</math> é o número de espécies para o qual apenas 1 indivíduo foi observado. Perceba que o número total de objetos observados''N'', não pode ser encontrado a partir de

:<math>N = \sum_{r=1}^\infty r N_r.</math>

O primeiro passo no cálculo é achar uma estimativa para a probabilidade total de espécies não vistas. Essa estimativa é <ref>{{citar periódico
 |último =Gale |primeiro =William A. |autorlink =William A. Gale
 |ano=1995
 |título=Good–Turing smoothing without tears
 |periódico=[[Journal of Quantitative Linguistics]]
 |url=http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.110.8518
 |volume=2 |página=3  |doi=10.1080/09296179508590051
}}</ref>

:<math>p_0 = \frac{N_1}{N}. </math>

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 é:
:<math>p_r = \frac{(r+1) S(N_{r+1})}{N S(N_r)}.</math>

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:
:<math>\frac{(r+1) S(N_{r+1})}{N}.</math>

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

Nós gostaríamos de fazer um gráfico de <math>\log N_r</math> versus <math>\log r</math> mas isso é problemático porque para ''r'' grandes muitas <math>N_r</math> serão zero. Em vez disso, uma quantidade revisada, <math>\log Z_r</math>, é colocada contra <math>\log r</math>, onde ''Z''<sub>''r''</sub> é definida como

:<math>Z_r = \frac{N_r}{0.5(t-q)},</math>

e onde ''q'', ''r'' e ''t'' são subscripts consecutivos tendo <math>N_q, N_r, N_t</math> não zero. Quando ''r'' é 1, tome ''q'' sendo 0. Quando ''r'' é a última frequência não-zero, tome ''t'' como 2''r''&nbsp;&minus;&nbsp;''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.<ref>Lecture 11: The Good-Turing Estimate. CS 6740, Cornell University, 2010 [http://www.cs.cornell.edu/courses/cs6740/2010sp/guides/lec11.pdf]</ref>

Uma [[regressão linear simples]] é então encaixada ao log-log do gráfico. Para pequenos valores de ''r'' é razoável para definir <math>S(N_r) = N_r</math>

(isto é, nenhuma suavização é realizada), enquanto para grandes valores de ''r'', valores de <math>S(N_r)</math> 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|data=dezembro de 2010}}

O código para o método é avaliado em domínio público.<ref>Sampson, Geoffrey (2005) [http://www.grsampson.net/D_SGT.c Simple Good–Turing Frequency Estimator]  (code in C)</ref>{{carece de fontes|reason=addition sources?|data=dezembro de 2010}}

==Veja também==

* [[Ewens sampling formula]]
* [[Pseudocount]]

==Referências==
<div class="references-small">
<!--See http://en.wikipedia.org/wiki/Wikipedia:Footnotes for an explanation of how to generate footnotes using the <ref(erences/)> tags-->
<references/>
* David A. McAllester, Robert Schapire (2000) [http://people.csail.mit.edu/mcollins/6864/slides/goodturing.pdf ''On the Convergence Rate of Good–Turing Estimators']', ''Proceedings of the Thirteenth Annual Conference on Computational Learning Theory''  pp.&nbsp;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.&nbsp;895–911

</div>

{{DEFAULTSORT:Estimativa de Frequencia de Good-Turing}}
[[Categoria:Probabilidade]]