Estimación de la entropía a partir de un conjunto de mediciones

Question

Dado un conjunto de medidas, como $528, 412, 281, 66, 338, 249$ ¿es posible calcular una estimación de la cantidad de entropía que proporciona cada medición?

Sólo para aclarar: busco una estimación de la cantidad de imprevisibilidad que cabe esperar de una medición, medida en bits (shannons).

Estoy experimentando con formas de cosechar entropía (para sembrar un generador de números pseudoaleatorios criptográficamente seguro), y una de mis fuentes de entropía proporciona medidas imprecisas del tiempo que tarda un proceso en completarse.

El proceso es el mismo cada vez, la medición debería ser aproximadamente la misma cada vez, por lo que la variación debería (por diseño) deberse principalmente al error de medición. La medición más pequeña teóricamente posible es $0$ El mayor es desconocido.

Mi formación matemática es limitada, por lo que agradecería explicaciones claras y comprensibles.

Answer 1

Como se indica correctamente en la respuesta de msm, la solución de este interesante problema podría ser considerablemente más fácil si pudiéramos tratar con un gran número de muestras. Independientemente del uso de una función de distribución empírica o de una distribución obtenida directamente por los datos de la fila, cuando tenemos un gran número de muestras y se puede definir una función de distribución empírica, podemos calcular rápidamente la entropía utilizando la fórmula estándar de la entropía de Shannon.

Sin embargo, hay dos cuestiones importantes que hay que tener en cuenta en esta cuestión. La primera es que el problema parece pedir claramente un análisis de la entropía sobre un único y relativamente pequeño conjunto de observaciones tomadas de un conjunto muy amplio de posibilidades (en este sentido, conocer el rango dentro del cual se generan los números podría ser útil). Por tanto, estamos trabajando en un contexto de régimen de "submuestreo". Por otro lado, la entropía de Shannon convencional es una medida adecuada para distribuciones de probabilidad claramente definidas. Aunque a veces podemos hacer suposiciones sobre la distribución subyacente para relacionar nuestro conjunto de datos de la muestra con alguna medida de entropía, estimar la entropía a partir de un único conjunto de observaciones submuestreadas no es fácil. En la práctica, tenemos una distribución discreta desconocida compuesta por $k $ observaciones sobre $N $ diferentes resultados posibles, definidos por un vector de probabilidades $p=(p_1,p_2,…,p_N) \,\,\,$ con $p_i \geq 0$ y $\sum p_i=1$ . Como en la mayoría de los casos el vector de probabilidad es desconocido, la entropía clásica de Shannon $$H (p)=-\sum_{i=1}^{N} p_i \log p_i $$ no se puede utilizar directamente. Así que tenemos que obtener una estimación de $H(p)$ de nuestro conjunto de datos de tamaño $k $ .

Por ello, el enfoque típico de la entropía en conjuntos de observaciones submuestreadas se basa en estimadores de entropía. Se trata de medidas sustitutas de la entropía que, en cierto modo, pretenden superar los inconvenientes que dependen del pequeño tamaño de nuestro conjunto de datos. Por ejemplo, un estimador muy básico (y poco utilizado) es el llamado estimador de complemento ingenuo (NP), que utiliza las estimaciones de frecuencia de las probabilidades discretas para calcular el siguiente sustituto de la entropía:

$$\hat {H} (p)=-\sum_{i=1}^{k} \hat {p}_i \log \hat {p}_i $$

donde $\hat {p}_i$ es la estimación de máxima verosimilitud de cada probabilidad $p_i $ calculado como la relación entre la frecuencia del resultado $i $ (es decir, el histograma de los resultados) y el número total de observaciones $k$ . Se puede demostrar que dicho estimador subestima en gran medida $H (p) $ .

Se han propuesto otros estimadores para mejorar el rendimiento del estimador NP $\hat {H}(p) $ . Por ejemplo, un enfoque bastante antiguo es el ajuste de Miller, en el que se obtiene un ligero aumento de la precisión del estimador del PN añadiendo a $\hat {H}(p) $ un desplazamiento constante igual a $(k-1)/(2N)\,\, \,$ . Evidentemente, esta corrección sigue siendo aproximada, ya que sólo tenía en cuenta el tamaño de la muestra, y no su distribución. Se puede obtener una modificación más robusta del estimador NP utilizando el enfoque clásico de remuestreo jackknife, comúnmente utilizado para evaluar el sesgo y la varianza de varios tipos de estimadores. La versión corregida por jackknife del PN para un conjunto de datos de $k $ observaciones es

$$\hat {H}_{J}(p)= k \hat {H}(p) - (k-1) \tilde {H}(p) $$

donde $\tilde {H}(p) $ es la media de $k $ Estimaciones NP, cada una de ellas obtenida excluyendo una única observación diferente. Otras variantes robustas del estimador NP, más complejas, pueden obtenerse utilizando procedimientos basados en la continuación analítica. Puede encontrar más detalles sobre este tema aquí .

Recientemente, se han propuesto otros estimadores basados en diferentes argumentos. Entre ellos, los más utilizados para distribuciones discretas son el Nemenman-Shafee-Bialek (NSB), la mezcla Dirichlet centrada, la mezcla Pitman-Yor y la mezcla del proceso Dirichlet. Se trata de estimadores bayesianos, que se basan en supuestos probabilísticos definidos explícitamente. Asimismo, se han sugerido medidas no bayesianas, como el estimador ajustado a la cobertura, el mejor límite superior o el estimador de James Stein. Hay que destacar que no existe un estimador insesgado en este contexto, y que la tasa de convergencia de los distintos estimadores puede variar de forma considerable, siendo en algunos casos arbitrariamente lenta. Sin embargo, para la cuestión específica del PO, que se basa en una distribución discreta con rango finito, una elección razonable podría ser el estimador NSB, que utiliza una distribución a priori aproximadamente plana sobre los valores de la entropía, construida como una mezcla de distribuciones Dirichlet simétricas. Este estimador muestra una rápida convergencia a la entropía y buenas prestaciones en términos de robustez y sesgo. Puede encontrar más detalles sobre la teoría subyacente aquí . Se pueden encontrar aplicaciones y herramientas en línea muy útiles para el cálculo de la entropía del INN aquí .

La segunda cuestión en esta pregunta es que el problema -si lo he entendido bien- parece centrarse en la cantidad de entropía relacionada con cada observación individual, en lugar de en la entropía del conjunto de datos. Mientras que la contribución de cada observación es fácil de determinar en los cálculos convencionales de entropía de Shannon, esto es más difícil para otros estimadores. Un enfoque típico para simplificar este problema, comúnmente utilizado en muchos otros campos estadísticos, podría ser calcular el estimador de entropía para todo el conjunto de datos después de eliminar las observaciones de interés, y luego compararlo con el estimador de entropía para todo el conjunto de datos. La diferencia puede utilizarse como una medida de la contribución de entropía relacionada con esa observación específica. La aplicación de este enfoque para el estimador del INN, o alternativamente para un estimador relativamente robusto relacionado con el PN (por ejemplo, el corregido por jackknife) podría ser una buena opción para responder a la pregunta específica planteada en el PO.

Answer 2

A partir de los comentarios, el problema se formula como:

Se nos da $n$ muestras de un proceso estocástico $X(t)$ donde las variables aleatorias $X_i=X(t=t_i)$ tienen idéntica distribución y son independientes y la entropía de las variables aleatorias $X_i$ se desea.

El problema se hace fácil asumiendo que todos $X_i$ tienen la misma distribución. Se reduce a estimar la distribución desconocida. Esto se debe a que se puede pensar que todas las muestras se extraen de la misma distribución.

Unas pocas muestras, sin ningún conocimiento previo del tipo de fuente, no ayudarán mucho. Si pudiéramos asumir una distribución que sigue la fuente, entonces usando las muestras se podrían estimar los parámetros.

En este caso particular, el enfoque estándar creo que es la construcción de un función de distribución empírica . Para que eso funcione, necesitamos un gran número de muestras. Supongamos que tenemos $n$ muestras de una variable aleatoria $X$ cuya fdc es desconocida y se denota por $F(x)$ . La idea es estimar $F(x)$ como $\hat{F}_n(x)$ sólo con mirar a $n$ muestras disponibles:

$$\hat{F}_n(x)=\frac{1}{n}(\text{number of samples that are less than }x )$$

Como resultado de la LLN, tenemos $\hat{F}_n(x)\to F(x)$ casi seguramente, como $n$ tiende al infinito.

A partir de la fdc empírica, podemos derivar una fdp empírica $p(x)$ y calcular la entropía

$$H=-\sum_x{p(x)\log(p(x))}$$

Pero esto es en realidad la entropía de todas las variables aleatorias $X_i$ ya que todos comparten el mismo pmf.