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 nunca antes vista, 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 (finito pero desconocido en número). Después de dibujar bolas rojas, bolas negras y bolas verdes, 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.
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 cifrados alemanes para la máquina Enigma durante la Segunda Guerra Mundial . Turing al principio 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 fue publicado por Good en 1953, [1] pero los cálculos fueron difíciles por lo que no se usó 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
Notación
- Asumiendo que Se han observado distintas especies, enumeradas .
- Entonces el vector de frecuencia, , tiene elementos que dan el número de individuos que se han observado para las especies .
- El vector de frecuencia de frecuencias, , muestra cuántas veces ocurre la frecuencia r en el vector; es decir, entre los elementos.
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
El primer paso en el cálculo es estimar la probabilidad de que un individuo observado en el futuro (o el próximo individuo observado) sea miembro de una especie hasta ahora no vista. Esta estimación es: [7]
El siguiente paso es estimar la probabilidad de que el siguiente individuo observado sea de una especie que se ha visto veces. Para una sola especie, esta estimación es:
Para estimar la probabilidad de que el siguiente individuo observado sea de cualquier especie de este grupo (es decir, el grupo de especies visto veces) se puede utilizar la siguiente fórmula:
Aquí, la notación significa el valor suavizado o ajustado de la frecuencia que se muestra entre paréntesis (ver también el método empírico de Bayes ). A continuación, se ofrece una descripción general de cómo realizar este suavizado.
Nos gustaría hacer una trama de versus pero esto es problemático porque para grandes muchos será cero. En lugar de una cantidad revisada,, se representa frente a , donde Z r se define como
y donde q , r y t son subíndices consecutivos que tienendistinto de cero. Cuando r es 1, tome q como 0. Cuando r es la última frecuencia distinta de cero, tome ser - estar .
El supuesto de la estimación de Good-Turing es que el número de ocurrencias de cada especie sigue una distribución binomial. [8]
Una regresión lineal simple es luego montado en el gráfico log-log. Para pequeños valores de es razonable establecer (es decir, no se realiza ningún suavizado), mientras que para valores grandes de r , los valores dese 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] El código para el método está disponible en el dominio público. [10]
Derivación
Muchas derivaciones diferentes de la fórmula anterior para ha sido dado. [1] [6] [8] [11]
Una de las formas más sencillas de motivar la fórmula es asumiendo que el siguiente elemento se comportará de manera similar al elemento anterior. La idea general del estimador es que actualmente estamos viendo 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 la probabilidad de cada una de estas categorías para el siguiente elemento que veremos. Dicho de otra manera, queremos saber la velocidad actual a la que los elementos vistos dos veces se convierten en elementos vistos tres veces, y así sucesivamente. Dado que no asumimos nada sobre la distribución de probabilidad subyacente, suena un poco misterioso al principio. Pero es extremadamente fácil calcular estas probabilidades empíricamente para el elemento anterior que vimos, incluso asumiendo que no recordamos exactamente qué elemento era: Tome todos los elementos que hemos visto hasta ahora (incluidas las multiplicidades): el último elemento que vimos fue uno al azar de estos, todos igualmente probables. Específicamente, la posibilidad de que viéramos un artículo para elEl tiempo es simplemente la posibilidad de que fuera uno de los elementos que ahora hemos visto tiempos, a saber . En otras palabras, nuestra posibilidad de ver un elemento que se había visto r veces antes era. Así que ahora simplemente asumimos que esta posibilidad será aproximadamente la misma para el siguiente elemento que veamos. Esto nos da inmediatamente la fórmula anterior para, configurando . Y para, para obtener la probabilidad de que una de laselementos va a ser el siguiente visto, necesitamos dividir esta probabilidad (de ver algún elemento que se ha visto r veces) entre losposibilidades para qué artículo en particular podría ser. Esto nos da la formula. 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 le 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 eran las dos probabilidades para el lanzamiento de la 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. .
Ver también
Referencias
- ^ a b 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 .
- ^ Noticia: 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). "Siempre bueno Turing: estimación de probabilidad asintóticamente óptima". Ciencia . 302 (5644): 427–31. Código Bibliográfico : 2003Sci ... 302..427O . doi : 10.1126 / science.1088284 . PMID 14564004 .
- ^ Sampson, Geoffrey y Gale, William A. (1995) Estimación de frecuencia de Good-turing sin lágrimas
- ^ Orlitsky, Alon; Suresh, Ananda (2015). "Estimación de la 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 .
- ^ Nadas, A. (1991). "Bueno, Jelinek, Mercer y Robbins en la estimación de probabilidades de Turing". Revista Estadounidense de Ciencias Matemáticas y de Gestión . American Sciences Press Syracuse, NY, EE. UU. 11 (3-4): 299-308. doi : 10.1080 / 01966324.1991.10737313 .
- ^ a b Hutter, Marcus (2014). "Conversión offline a online". Proc. 25a Conf. Internacional sobre teoría algorítmica del aprendizaje (ALT'14) . LNAI. 8776 . Bled, Eslovenia: Springer. págs. 230–244. arXiv : 1407.3334 . doi : 10.1007 / 978-3-319-11662-4_17 .
- ^ Gale, William A. (1995). "Good – Turing alisado sin lágrimas". Revista de Lingüística Cuantitativa . 2 (3): 3. CiteSeerX 10.1.1.110.8518 . doi : 10.1080 / 09296179508590051 .
- ^ a b Conferencia 11: La estimación de Good-Turing. CS 6740, Universidad de Cornell, 2010 [1]
- ^ Church, K; Gale, W. (1991). "Una comparación de los métodos de estimación eliminados y mejorados de Good-Turing para estimar probabilidades de bigramas ingleses". Cite journal requiere
|journal=
( ayuda ) - ^ Sampson, Geoffrey (2005) Estimador de frecuencia simple Good-Turing (código en C)
- ^ Favaro, Stefano; Nipoti, Bernardo; Teh, Yee Whye (2016). "Redescubrimiento de estimadores de Good-Turing a través de no paramétricos bayesianos" . Biometría . Biblioteca en línea de Wiley. 72 (1): 136-145. arXiv : 1401.0303 . doi : 10.1111 / biom.12366 . PMID 26224325 .
Bibliografía
- David A. McAllester, Robert Schapire (2000) Sobre la tasa de convergencia de los estimadores de Good-Turing , Actas de la decimotercera conferencia anual sobre teoría del aprendizaje computacional, págs. 1-6
- David A. McAllester, Ortiz, Luis (2003) Desigualdades de concentración para la masa que falta y para el error de regla de histograma , Journal of Machine Learning Research, págs. 895–911