Hispanopedia Wiki
Articulo de referencia

Estimación de la 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 hasta ahora desconocida , dada una serie...

Hispanopedia WikiContenido en espanolLectura gratuita

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 desconocida , dada una serie de observaciones pasadas de objetos de diferentes especies. Al extraer bolas de una urna, los "objetos" serían las bolas y las "especies" serían los distintos colores de las bolas (finitos pero desconocidos en número). Después de extraerRrojo{\displaystyle R_{\text{rojo}}}bolas rojas,Rnegro{\displaystyle R_{\text{negro}}}bolas negras yRverde{\displaystyle R_{\text{verde}}}Si sacamos 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.

Antecedentes históricos

La estimación de frecuencias de Good-Turing fue desarrollada por Alan Turing y su asistente I.J. Good como parte de los métodos que utilizaron en Bletchley Park para descifrar códigos alemanes para la máquina Enigma durante la Segunda Guerra Mundial . Inicialmente, Turing modeló las frecuencias como una distribución multinomial , pero descubrió que era 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 haberlo hecho. [ 2 ] El método incluso alcanzó cierta fama literaria gracias a la novela Enigma de Robert Harris .

En la década de 1990, Geoffrey Sampson colaboró ​​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 diversas 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

Supongamos queincógnita{\displaystyle X}Se han observado y enumerado distintas especies.1,…,incógnita{\displaystyle 1,\dots ,X}. Entonces el vector de frecuencia,R¯{\displaystyle {\bar {R}}}, tiene elementosRincógnita{\displaystyle R_{x}}que indican el número de individuos que se han observado para cada especie.incógnita{\displaystyle x}. El vector de frecuencias,(norter)r=0,1,…{\displaystyle (N_{r})_{r=0,1,\ldots }}muestra cuántas veces la frecuenciar{\displaystyle r}ocurre en el vectorR¯{\displaystyle {\bar {R}}}(es decir, entre los elementosRincógnita{\displaystyle R_{x}}):

norter=|{incógnita∣Rincógnita=r}|.{\displaystyle N_{r}={\Bigl |}\left\{x\mid R_{x}=r\right\}{\Bigr |}.}

Por ejemplo,norte1{\displaystyle N_{1}}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,norte{\displaystyle N}, se puede encontrar en

norte=∑r=1∞rnorter=∑incógnita=1incógnitaRincógnita.{\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 hasta ahora no vista. Esta estimación es [ 8 ].

pag0=norte1norte.{\displaystyle p_{0}={\frac {N_{1}}{N}}.}

El siguiente paso es estimar la probabilidad de que el siguiente individuo observado sea de una especie que se haya vistor{\displaystyle r}veces. Para una sola especie, esta estimación es pagr=(r+1)S(norter+1)norteS(norter).{\displaystyle p_{r}={\frac {(r+1)S(N_{r+1})}{NS(N_{r})}}.} Aquí, la notaciónS(⋅){\displaystyle S(\cdot )}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 (véase también el método bayesiano empírico ).

Para estimar la probabilidad de que el siguiente individuo observado sea de alguna especie de este grupo (es decir, el grupo de especies observadas).r{\displaystyle r}veces) se puede utilizar la siguiente fórmula: (r+1)S(norter+1)norte.{\displaystyle {\frac {(r+1)S(N_{r+1})}{N}}.}

Suavizado

Para suavizar los valores erráticos ennorter{\displaystyle N_{r}}para grandesr{\displaystyle r}, nos gustaría hacer un plano deregistro⁡norter{\displaystyle \log N_{r}}versusregistro⁡r{\displaystyle \log r}pero esto es problemático porque para grandesr{\displaystyle r}muchosnorter{\displaystyle N_{r}}será cero. En su lugar, una cantidad revisada,registro⁡Zr{\displaystyle \log Z_{r}}, se grafica versusregistro⁡r{\displaystyle \log r}, dóndeZr{\displaystyle Z_{r}}se define como

Zr=norter(t−q)/2,{\displaystyle Z_{r}={\frac {N_{r}}{(tq)/2}},}

y dóndeq{\displaystyle q},r{\displaystyle r}, yt{\displaystyle t}son tres subíndices consecutivos con recuentos distintos de ceronorteq{\displaystyle N_{q}},norter{\displaystyle N_{r}},nortet{\displaystyle N_{t}}. Para el caso especial cuandor{\displaystyle r}es 1, tomaq{\displaystyle q}ser 0. En el caso especial opuesto, cuandor=rúltimo{\displaystyle r=r_{\text{último}}}es el índice del último conteo distinto de cero, reemplace el divisor(t−q)/2{\displaystyle (tq)/2}conrúltimo−q{\displaystyle r_{\text{último}}-q}, entoncesZrúltimo=norterúltimo/(rúltimo−q){\displaystyle Z_{r_{\text{último}}}=N_{r_{\text{último}}}/(r_{\text{último}}-q)}.

Luego se ajusta una regresión lineal simple al gráfico log-log .

Para valores pequeños der{\displaystyle r}es razonable establecerS(norter)=norter{\displaystyle S(N_{r})=N_{r}}– es decir, no se realiza ningún suavizado.

Para valores grandes der{\displaystyle r}, valores deS(norter){\displaystyle S(N_{r})}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 no suavizado a suavizado lineal. [ 9 ] El código del método está disponible en el dominio público. [ 10 ]

Derivación

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

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 cierta frecuencia, elementos vistos una vez con cierta frecuencia, elementos vistos dos veces con cierta frecuencia, y así sucesivamente. Nuestro objetivo es estimar cuán probable es 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 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 cuál fue ese elemento: 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. Específicamente, la probabilidad de que hayamos visto un elemento para el(r+1){\displaystyle (r+1)}La vez es simplemente la posibilidad de que fuera uno de los elementos que ahora hemos visto.r+1{\displaystyle r+1}tiempos, a saber(r+1)norter+1norte{\displaystyle {\frac {(r+1)N_{r+1}}{N}}}En otras palabras, nuestra probabilidad de ver un artículo que había sido visto r veces antes era(r+1)norter+1norte{\displaystyle {\frac {(r+1)N_{r+1}}{N}}}. Así que ahora simplemente asumimos que esta probabilidad será aproximadamente la misma para el siguiente elemento que veamos. Esto nos da inmediatamente la fórmula anterior parapag0{\displaystyle p_{0}}, estableciendor=0{\displaystyle r=0}. Y parar>0{\displaystyle r>0}, para obtener la probabilidad de que uno en particular de losnorter{\displaystyle N_{r}}El elemento va a ser el siguiente que se vea, necesitamos dividir esta probabilidad (de ver algún elemento que se ha visto r veces) entre elnorter{\displaystyle N_{r}}posibilidades de qué artículo en particular podría ser. Esto nos da la fórmulapagr=(r+1)norter+1nortenorter{\displaystyle \;p_{r}={\frac {(r+1)N_{r+1}}{NN_{r}}}}Por supuesto, es probable que sus datos reales presenten cierto ruido, por lo que conviene suavizar los valores primero para obtener una mejor estimación de la rapidez con la que aumentan los recuentos de las categorías. Esto da como resultado la fórmula mostrada anteriormente. Este enfoque es similar al de derivar el estimador de Bernoulli estándar , simplemente preguntando cuáles fueron las dos probabilidades del lanzamiento de moneda anterior (tras mezclar los ensayos vistos hasta el momento), considerando únicamente los recuentos de resultados actuales y sin asumir nada sobre la distribución subyacente.

Véase también

Referencias

  1. 1 2 Good, IJ (1953). "Las frecuencias poblacionales de las 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 . MR 0061330 .  
  2. ↑ Newsise: Los científicos explican y mejoran la fórmula de probabilidad 'enigmática' , una reseña 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 lágrimas" . 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é Good-Turing es bueno?" (PDF) . Neural Information Processing Systems : 1–9 . Recuperado 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. 1 2 Hutter, Marcus (2014). "Conversión de Offline a Online". Actas de la 25.ª Conferencia Internacional sobre Teoría del Aprendizaje Algorítmico (ALT'14) . LNAI. Vol. 8776. Bled, Eslovenia: Springer. pp. 230–244 . arXiv : 1407.3334 . doi : 10.1007 /978-3-319-11662-4_17 .  
  7. ↑ Good, I. J. (1953). "Las frecuencias poblacionales de las 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). "Suavizado de Good-Turing sin lágrimas". 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}}: Para citar una revista se requiere |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: 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" . 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

  • 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 faltante y para el error de la regla del histograma , Journal of Machine Learning Research, págs.  895–911