stringtranslate.com

Estimación de frecuencia de Good-Turing

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 no vista hasta ahora, dado un conjunto de observaciones anteriores de objetos de diferentes especies. Al extraer 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 extraer bolas rojas, bolas negras y bolas verdes, nos preguntaríamos cuál es la probabilidad de extraer una bola roja, una bola negra, una bola verde o una de un color nunca antes visto.

Antecedentes históricos

La estimación de frecuencia de Good-Turing fue desarrollada por Alan Turing y su asistente IJ Good como parte de los métodos utilizados en Bletchley Park para descifrar los códigos alemanes para la máquina Enigma durante la Segunda Guerra Mundial . Turing inicialmente modeló las frecuencias como una distribución multinomial , pero la encontró imprecisa. Good desarrolló algoritmos de suavizado para mejorar la precisión del estimador.

El descubrimiento fue reconocido como significativo cuando Good lo publicó en 1953, [1] pero los cálculos eran difíciles, por lo que no se utilizó tan ampliamente como podría haber sido. [2] El método incluso ganó cierta fama literaria debido 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

Por ejemplo, es el número de especies de las que se observó solo un individuo. Nótese que el número total de objetos observados se puede encontrar a partir de

Cálculo

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

El siguiente paso es estimar la probabilidad de que el próximo individuo observado pertenezca a una especie que ya ha sido vista varias veces. Para una sola especie, esta estimación es:

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 ).

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:

Suavizado

Para suavizar los valores erráticos en para valores grandes de r , nos gustaría hacer un gráfico de versus pero esto es problemático porque para valores grandes de r será cero. En cambio, se traza una cantidad revisada, versus donde se define como

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 es el índice del último recuento distinto de cero, reemplace el divisor con so

Luego se ajusta una regresión lineal simple al gráfico logarítmico-logarítmico.

Para valores pequeños es razonable establecerlo , es decir, no se realiza ningún suavizado.

Para valores grandes de r , los valores de se leen de la línea de regresión. Se puede utilizar un procedimiento automático (no descrito aquí) para especificar en qué punto debe producirse el cambio de la ausencia de suavizado al suavizado lineal. [9] [ cita completa necesaria ] El código para el método está disponible en el dominio público. [10]

Derivación

Se han dado muchas derivaciones diferentes de la fórmula anterior . [1] [6] [11] [12]

Una de las formas más sencillas de motivar la fórmula es suponer que el siguiente elemento se comportará de forma similar al elemento anterior. La idea general del estimador es que actualmente estamos viendo elementos nunca vistos con una determinada frecuencia, elementos vistos una vez con una determinada frecuencia, elementos vistos dos veces con una determinada frecuencia, y así sucesivamente. Nuestro objetivo es estimar la probabilidad de cada una de estas categorías para el siguiente elemento que veremos. Dicho de otro modo, queremos saber la tasa actual a la que los elementos vistos dos veces se convierten en elementos vistos tres veces, y así sucesivamente. Dado que no suponemos 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 recordamos exactamente cuál era: tomemos todos los elementos que hemos visto hasta ahora (incluidas las multiplicidades): el último elemento que vimos fue uno aleatorio de estos, todos igualmente probables. En concreto, la probabilidad de que hayamos visto un elemento por enésima vez es simplemente la probabilidad de que fuera uno de los elementos que ya hemos visto veces, es decir , . En otras palabras, nuestra probabilidad de ver un elemento que se había visto r veces antes era . Así que ahora simplemente suponemos que esta probabilidad será aproximadamente la misma para el próximo elemento que veamos. Esto nos da inmediatamente la fórmula anterior para , estableciendo . Y para , para obtener la probabilidad de que un elemento en particular sea el próximo que veamos, 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 serlo. Esto nos da la fórmula . Por supuesto, sus datos reales probablemente serán un poco ruidosos, por lo que querrá suavizar los valores primero 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 de Bernoulli estándar simplemente preguntando cuáles fueron las dos probabilidades para el lanzamiento de moneda anterior (después de mezclar los ensayos vistos hasta ahora), dado que solo cuenta el resultado actual, sin asumir nada sobre la distribución subyacente.

Véase también

Referencias

  1. ^ ab Good, IJ (1953). "Las frecuencias poblacionales de las especies y la estimación de los parámetros poblacionales". Biometrika . 40 (3–4): 237–264. doi :10.1093/biomet/40.3-4.237. JSTOR  2333344. MR  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". Science . 302 (5644): 427–31. Bibcode :2003Sci...302..427O. doi :10.1126/science.1088284. PMID  14564004.
  3. ^ Gale, William A.; Sampson, Geoffrey (1995). "Estimación de frecuencia de Good-Turing sin desgarros". Journal of Quantitative Linguistics . 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é es bueno el método de Good-Turing?" (PDF) . Neural Information Processing Systems (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". American Journal of Mathematical and Management Sciences . 11 (3–4). American Sciences Press Syracuse, NY, EE. UU.: 299–308. doi :10.1080/01966324.1991.10737313.
  6. ^ ab Hutter, Marcus (2014). "Conversión de offline a online". Proc. 25th International Conf. on Algorithmic Learning Theory (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 las especies y la estimación de los 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). "Suavizado de Good-Turing sin desgarros". Journal of Quantitative Linguistics . 2 (3): 3. CiteSeerX 10.1.1.110.8518 . doi :10.1080/09296179508590051. 
  9. ^ Church, K.; Gale, W. (1991). "Una comparación de los métodos de estimación Good-Turing mejorado y eliminado para estimar probabilidades de bigramas ingleses". {{cite journal}}: Requiere citar revista |journal=( ayuda )
  10. ^ Sampson, Geoffrey (2005). "Estimador de frecuencia simple de Good-Turing". grsampson.net (código fuente en C ).
  11. ^ "La estimación de Good-Turing" (PDF) . Ciencias de la Computación (guía del curso). CS 6740. Ithaca, NY: Cornell University . 2010.
  12. ^ Favaro, Stefano; Nipoti, Bernardo; Teh, Yee Whye (2016). "Redescubrimiento de los estimadores de Good-Turing mediante métodos no paramétricos bayesianos". Biometrics . 72 (1). Wiley Online Library: 136–145. arXiv : 1401.0303 . doi :10.1111/biom.12366. hdl :2318/1591184. PMID  26224325. S2CID  5704019.

Bibliografía