Estimación de frecuencia de Good-Turing

Técnica estadística inventada por Alan Turing y su asistente IJ Good.

La estimación de frecuencia de Good-Turing es una técnica estadística para estimar la probabilidad de encontrar un objeto de una especie hasta ahora invisible, dado un conjunto de observaciones pasadas de objetos de diferentes especies. Al sacar bolas de una urna, los "objetos" serían bolas y las "especies" serían los distintos colores de las bolas (finitos pero desconocidos en número). Después de sacar bolas rojas, bolas negras y bolas verdes, nos preguntaríamos cuál es la probabilidad de sacar una bola roja, una bola negra, una bola verde o una de un color nunca antes visto. ${\displaystyle R_{\text{red}}}$ ${\displaystyle R_{\text{black}}}$ ${\displaystyle R_{\text{green}}}$

Antecedentes históricos

La estimación de frecuencia de Good-Turing fue desarrollada por Alan Turing y su asistente IJ Good como parte de sus métodos utilizados en Bletchley Park para descifrar cifras alemanas para la máquina Enigma durante la Segunda Guerra Mundial . Al principio, Turing modeló las frecuencias como una distribución multinomial , pero la encontró inexacta. Algoritmos de suavizado bien desarrollados para mejorar la precisión del estimador.

El descubrimiento fue reconocido como significativo cuando Good lo publicó en 1953, ^[1] pero los cálculos fueron difíciles, por lo que no se utilizó tan ampliamente como podría haber sido. ^[2] El método incluso ganó cierta fama literaria gracias a la novela Enigma de Robert Harris .

En la década de 1990, Geoffrey Sampson trabajó con William A. Gale de AT&T para crear e implementar una variante simplificada y más fácil de usar del método Good-Turing ^{[3] [4]} que se describe a continuación. Se han proporcionado varias justificaciones heurísticas ^{[5] y una derivación combinatoria simple. [6]}

El método

El estimador de Good-Turing es en gran medida independiente de la distribución de frecuencias de especies. ^[7]

Notación

• Suponiendo que se hayan observado especies distintas, enumeradas ${\displaystyle X}$ ${\displaystyle \;1,\dots ,X~.}$
• Luego el vector de frecuencia, tiene elementos que dan el número de individuos que se han observado por especie. ${\displaystyle \,{\bar {R}}\;,}$ ${\displaystyle \,R_{x}\,}$ ${\displaystyle \,x\;.}$
• El vector de frecuencia de frecuencias muestra cuántas veces la frecuencia r ocurre en el vector (es decir, entre los elementos ): ${\displaystyle \,(N_{r})_{r=0,1,\ldots }\;,}$ ${\displaystyle {\bar {R}}}$ ${\displaystyle R_{x}}$

${\displaystyle N_{r}={\Bigl |}\left\{x\mid R_{x}=r\right\}{\Bigr |}~.}$

Por ejemplo, es el número de especies para las que solo se observó un individuo. Tenga en cuenta que el número total de objetos observados se puede encontrar en ${\displaystyle N_{1}}$ ${\displaystyle \,N\,,}$

${\displaystyle N=\sum _{r=1}^{\infty }rN_{r}=\sum _{x=1}^{X}R_{x}~.}$

Cálculo

El primer paso en el cálculo es estimar la probabilidad de que un individuo observado en el futuro (o el siguiente individuo observado) sea miembro de una especie no vista hasta ahora. Esta estimación es: ^[8]

${\displaystyle p_{0}={\frac {N_{1}}{N}}~.}$

El siguiente paso es estimar la probabilidad de que el siguiente individuo observado pertenezca a una especie que ha sido vista varias veces. Para una sola especie esta estimación es: ${\displaystyle r}$

${\displaystyle p_{r}={\frac {\;(r+1)\;S(N_{r+1})\;}{N\,S(N_{r})}}~.}$

Aquí, la notación significa el valor suavizado o ajustado de la frecuencia que se muestra entre paréntesis. En la siguiente sección se ofrece una descripción general de cómo realizar este suavizado (consulte también el método empírico de Bayes ). ${\displaystyle S(\cdot )}$

Para estimar la probabilidad de que el próximo individuo observado sea de cualquier especie de este grupo (es decir, el grupo de especies vistas veces) se puede utilizar la siguiente fórmula: ${\displaystyle \,r\,}$

${\displaystyle {\frac {\;(r+1)\,S(N_{r+1})\;}{N}}~.}$

Suavizado

Para suavizar los valores erráticos para r grandes , nos gustaría hacer una gráfica de versus , pero esto es problemático porque para muchos grandes será cero. En lugar de ello, se traza una cantidad revisada versus donde se define como ${\displaystyle \,N_{r}\,}$ ${\displaystyle \;\log N_{r}\;}$ ${\displaystyle \;\log r\;}$ ${\displaystyle \,r\,}$ ${\displaystyle \,N_{r}\,}$ ${\displaystyle \;\log Z_{r}\;,}$ ${\displaystyle \;\log r~,}$ ${\displaystyle \,Z_{r}\,}$

${\displaystyle Z_{r}={\frac {N_{r}}{\;{\tfrac {1}{2}}\,(t-q)\;}}~,}$

y donde q , r y t son tres subíndices consecutivos con recuentos distintos de cero . Para el caso especial cuando r es 1, tome q como 0. En el caso especial opuesto, cuando sea el índice del último recuento distinto de cero, reemplace el divisor con así ${\displaystyle \;N_{q},N_{r},N_{t}\;}$ ${\displaystyle \,r=r_{\mathsf {last}}\;}$ ${\displaystyle \,{\tfrac {1}{2}}\,(t-q)\,}$ ${\displaystyle \,r_{\mathsf {last}}-q\;,}$ ${\displaystyle \;Z_{r_{\mathsf {last}}}={\frac {N_{r_{\mathsf {last}}}}{\;r_{\mathsf {last}}-q\;}}~.}$

Luego se ajusta una regresión lineal simple a la gráfica log-log.

Para valores pequeños es razonable establecerlo , es decir, no se realiza ningún suavizado. ${\displaystyle \,r\,}$ ${\displaystyle \;S(N_{r})=N_{r}\;}$

Para valores grandes de r , los valores de se leen en la línea de regresión. Se puede utilizar un procedimiento automático (no descrito aquí) para especificar en qué punto debe tener lugar el cambio de sin suavizado a suavizado lineal. ^{[9] [ cita completa necesaria ]} El código del método está disponible en el dominio público. ^[10] ${\displaystyle \;S(N_{r})\;}$

Derivación

Se han dado muchas derivaciones diferentes de la fórmula anterior . ^{[1] [6] [11] [12]} ${\displaystyle p_{r}}$

Una de las formas más sencillas de motivar la fórmula es asumir que el siguiente elemento se comportará de manera similar al anterior. La idea general del estimador es que actualmente vemos elementos nunca vistos con una frecuencia determinada, elementos vistos una vez con una frecuencia determinada, elementos vistos dos veces con una frecuencia determinada, etc. Nuestro objetivo es estimar qué tan probable es cada una de estas categorías, para el siguiente elemento que veremos. Dicho de otra manera, queremos saber el ritmo actual al que los elementos vistos dos veces se convierten en elementos vistos tres veces, y así sucesivamente. Como no asumimos nada sobre la distribución de probabilidad subyacente, al principio suena un poco misterioso. Pero es extremadamente fácil calcular estas probabilidades empíricamente para el elemento anterior que vimos, incluso suponiendo que no recordemos exactamente qué elemento era: tome todos los elementos que hemos visto hasta ahora (incluidas las multiplicidades): el último elemento que vimos fue uno aleatorio de estos, todos igualmente probables. Específicamente, la posibilidad de que hayamos visto un elemento por enésima vez es simplemente la posibilidad de que sea uno de los elementos que hemos visto varias veces, es decir . En otras palabras, nuestra probabilidad de ver un objeto que había sido visto r veces antes era . Así que ahora simplemente asumimos que esta probabilidad será más o menos la misma para el próximo elemento que veamos. Esto nos da inmediatamente la fórmula anterior para , configurando . Y para obtener la probabilidad de que uno de los elementos en particular sea el siguiente que se vea, necesitamos dividir esta probabilidad (de ver algún elemento que se ha visto r veces) entre las posibilidades de qué elemento en particular podría ser. Esto nos da la fórmula . Por supuesto, sus datos reales probablemente serán un poco ruidosos, por lo que primero querrá suavizar los valores para obtener una mejor estimación de qué tan rápido están creciendo los recuentos de categorías, y esto da la fórmula como se muestra arriba. Este enfoque tiene el mismo espíritu que derivar el estimador estándar de Bernoulli simplemente preguntando cuáles eran las dos probabilidades para el lanzamiento de moneda anterior (después de mezclar las pruebas vistas hasta ahora), dado que solo cuenta el resultado actual, sin asumir nada sobre la distribución subyacente. . ${\displaystyle (r+1)}$ ${\displaystyle r+1}$ ${\displaystyle {\frac {(r+1)N_{r+1}}{N}}}$ ${\displaystyle {\frac {(r+1)N_{r+1}}{N}}}$ ${\displaystyle p_{0}}$ ${\displaystyle r=0}$ ${\displaystyle r>0}$ ${\displaystyle N_{r}}$ ${\displaystyle N_{r}}$ ${\displaystyle \;p_{r}={\frac {(r+1)N_{r+1}}{NN_{r}}}}$

Ver también

• Fórmula de muestreo de Ewens
• pseudocuenta

Referencias

1. Bueno, IJ (1953). "Las frecuencias poblacionales de especies y la estimación de parámetros poblacionales". Biometrika . 40 (3–4): 237–264. doi :10.1093/biomet/40.3-4.237. JSTOR  2333344. SEÑOR  0061330.
2. Newsise: Los científicos explican y mejoran la fórmula de probabilidad 'enigmática', una revisión popular de Orlitsky A, Santhanam NP, Zhang J (2003). "Always Good Turing: estimación de probabilidad asintóticamente óptima". Ciencia . 302 (5644): 427–31. Código bibliográfico : 2003 Ciencia... 302..427O. doi : 10.1126/ciencia.1088284. PMID  14564004.
3. Gale, William A.; Sampson, Geoffrey (1995). "Estimación de frecuencia de Good-Turing sin lágrimas". Revista de Lingüística Cuantitativa . 2 (3): 217–237. doi :10.1080/09296179508590051. ISSN  0929-6174.
4. Orlitsky, Alon; Suresh, Ananda (2015). "Estimación de distribución competitiva: ¿Por qué Good-Turing es bueno?" (PDF) . Sistemas de procesamiento de información neuronal (NIPS) : 1–9 . Consultado el 28 de marzo de 2016 .
5. Nadas, A. (1991). "Good, Jelinek, Mercer y Robbins sobre la estimación de probabilidades de Turing". Revista Estadounidense de Ciencias Matemáticas y de Gestión . 11 (3–4). American Sciences Press Syracuse, Nueva York, EE. UU.: 299–308. doi :10.1080/01966324.1991.10737313.
6. Hutter, Marcus (2014). "Conversión fuera de línea a en línea". Proc. 25ª Conferencia Internacional. sobre Teoría del Aprendizaje Algorítmico (ALT'14) . LNAI. vol. 8776. Bled, Eslovenia: Springer. págs. 230–244. arXiv : 1407.3334 . doi :10.1007/978-3-319-11662-4_17.
7. BUENO, IJ (1953). "Las frecuencias poblacionales de especies y la estimación de parámetros poblacionales". Biometrika . 40 (3–4): 237–264. doi : 10.1093/biomet/40.3-4.237 . Consultado el 14 de septiembre de 2022 .
8. Gale, William A. (1995). "Buen alisado de Turing sin lágrimas". Revista de Lingüística Cuantitativa . 2 (3): 3. CiteSeerX 10.1.1.110.8518 . doi :10.1080/09296179508590051. 
9. Iglesia, K.; Gale, W. (1991). "Una comparación de los métodos de estimación mejorados de Good-Turing y eliminados para estimar probabilidades de bigramas en inglés". {{cite journal}}: Citar diario requiere |journal=( ayuda )
10. Sansón, Geoffrey (2005). "Estimador de frecuencia simple de Good-Turing". grsampson.net (código fuente en C ).
11. "La estimación de Good-Turing" (PDF) . Informática (guía docente). CS 6740. Ithaca, Nueva York: Universidad de Cornell . 2010.
12. Favaro, Stefano; Nipoti, Bernardo; Teh, Yee Whye (2016). "Redescubrimiento de estimadores de Good-Turing mediante métodos no paramétricos bayesianos". Biometría . 72 (1). Biblioteca en línea Wiley: 136–145. arXiv : 1401.0303 . doi :10.1111/biom.12366. hdl :2318/1591184. PMID  26224325. S2CID  5704019.

Bibliografía

• David A. McAllester, Robert Schapire (2000) Sobre la tasa de convergencia de los estimadores Good-Turing, Actas de la decimotercera conferencia anual sobre teoría del aprendizaje computacional, págs.
• David A. McAllester, Ortiz, Luis (2003) Desigualdades de concentración para la masa faltante y el error de la regla del histograma, Journal of Machine Learning Research, págs. 895–911