¿Quién acuñó el término "entropía empírica"?

9

Sé del trabajo de Shannon con la entropía, pero últimamente he trabajado en estructuras de datos sucintas en las que la entropía empírica se usa a menudo como parte del análisis de almacenamiento.

Shannon definió la entropía de la información producida por una fuente de información discreta como , donde es la probabilidad de que ocurra el evento , por ejemplo, un carácter específico generado, y hay posibles eventos. p i i ki=1kpilogpipiik

Como señaló MCH en los comentarios, la entropía empírica es la entropía de la distribución empírica de estos eventos y, por lo tanto, está dada por donde es el número de ocurrencias observadas del evento y es el número total de eventos observados. Esto se llama entropía empírica de orden cero . La noción de Shannon de entropía condicional tiene una versión empírica de orden superior similar . niini=1kninlogninniin

Shannon no usó el término entropía empírica, aunque seguramente merece algo del crédito por este concepto. ¿Quién utilizó por primera vez esta idea y quién utilizó por primera vez el nombre (muy lógico) entropía empírica para describirla?

usuario eliminado 42
fuente
"puntiagudo definido para cada cadena" suena como la complejidad de Kolmogorov: ¿a eso se refiere? Si no es así, ¿puede señalar un enlace que lo defina o, mejor aún, proporcionar una definición en la pregunta misma?
Suresh Venkat
1
Se llama así porque la entropía empírica es la entropía de la distribución empírica de una secuencia.
Mahdi Cheraghchi
@SureshVenkat He intentado elaborar la pregunta.
Usuario eliminado 42
1
Eche un vistazo a Kosaraju S. Rao, Manzini G., "Compresión de cadenas de baja entropía con algoritmos Lempel-Ziv" (1998), también. Analizan el rendimiento de los algoritmos Lempel-Ziv utilizando la llamada " entropía empírica ".
Marzio De Biasi
2
Tenga en cuenta que la "distribución empírica" ​​es realmente la distribución ML para un conjunto dado de conteos de frecuencia. Así que me pregunto si esto se remonta a Bayes. Incluso Laplace había reflexionado sobre el problema de definir una distribución a partir de recuentos empíricos.
Suresh Venkat

Respuestas:

3

Estoy interesado en la "entropía empírica" ​​como tú y el primer artículo que encontré fue que desde Kosaraju como el usuario "Marzio De Biasi" dijo en su comentario.

Pero en mi opinión, las definiciones reales de "entropía empírica" ​​se hacen más adelante al generalizar los conceptos anteriores:

  1. "Alfabetos grandes e incompatibilidad" por Travis Gagie (2008)
  2. "Entropía empírica" ​​por Paul MB Vitányi (2011)

Gagie reformula la definición de entropía empírica de orden para: k

  • Hk(w)=1|w|minQ{log1P(Q=w)}

donde es un proceso de Markov de orden . También mostró que esta definición es equivalente a la anterior. El siguiente paso de Vitányi fue una generalización a clases arbitrarias de procesos (no solo procesos de Markov):Qk

  • H(w|X)=minX{K(X)+H(X):|H(X)log1P(X=w)|isminimal!}

donde es la clase de procesos permitidos y es la complejidad de Kolmogorov. Si elegimos para ser la clase de orden , los procesos de Markov producen una secuencia devariables aleatorias e ignorando la complejidad de Kolmogorov, esto también lleva a la definición de Gagie (multiplicada por ).XK(X)
Xk|w||w|

Danny
fuente