La fórmula de entropía de Shannon. Ayuda mi confusión

Question

mi comprensión de la fórmula de entropía es que se usa para calcular la cantidad mínima de bits necesarios para representar algunos datos. Por lo general, está redactado de manera diferente cuando se define, pero la comprensión previa es en lo que confiaba hasta ahora.

Aquí está mi problema. Supongamos que tengo una secuencia de 100 '1' seguida de 100 '0' = 200 bits. El alfabeto es {0,1}, la base de la entropía es 2. Probabilidad del símbolo "0" es 0.5 y '' 1 '' es 0.5. Entonces la entropía es 1 o 1 bit para representar 1 bit.

Sin embargo, puede codificarlo en longitud de ejecución con algo así como 100/1/100/0, donde es el número de bits que se emitirá seguido del bit. Parece que tengo una representación más pequeña que los datos. Especialmente si aumenta el número de 100 a mucho mayor.

Estoy usando: http://en.wikipedia.org/wiki/Information_entropy como referencia en este momento. ¿Qué hice mal? ¿Es la probabilidad asignada a los símbolos? No creo que esté mal. ¿O me equivoqué de conexión entre la compresión y la entropía? ¿Algo más?

Gracias.

Editar

Siguiendo algunas de las respuestas, mi seguimiento es: ¿aplicaría la fórmula de entropía a una instancia particular de un mensaje para tratar de averiguar su contenido de información? ¿Sería válido tomar el mensaje "aaab"? y digamos que la entropía es ~ 0.811. En caso afirmativo, ¿cuál es la entropía de 1 ... 10 .... 0 donde 1s y 0s se repiten n veces usando la fórmula de entropía. ¿Es la respuesta 1?

Sí, entiendo que está creando una variable aleatoria de sus símbolos de entrada y adivinando la función de masa de probabilidad basada en su mensaje. Lo que intento confirmar es que la fórmula de entropía no tiene en cuenta la posición de los símbolos en el mensaje.

Answer 1

  

¿O me equivoqué en la conexión entre la compresión y la entropía?

Estás bastante cerca, pero esta última pregunta es dónde estuvo el error. Si puede comprimir algo en una forma que era más pequeña que su representación original, significa que la representación original tenía al menos algo de redundancia. Cada bit del mensaje realmente no transmitía 1 bit de información.

Debido a que los datos redundantes no contribuyen al contenido de información de un mensaje, tampoco aumenta su entropía. Imagine, por ejemplo, un "generador de bits aleatorio". que solo devuelve el valor " 0 " ;. ¡Esto no transmite ninguna información en absoluto! (En realidad, transmite una cantidad de información indefinida , porque cualquier mensaje binario que consista en un solo tipo de símbolo requiere una división por cero en la fórmula de entropía).

Por el contrario, si hubiera simulado un gran número de lanzamientos aleatorios de monedas, sería muy difícil reducir mucho el tamaño de este mensaje. Cada bit estaría contribuyendo cerca de 1 bit de entropía.

Cuando comprime datos, extrae esa redundancia. A cambio, usted paga un precio único de entropía al tener que idear un esquema que sepa cómo comprimir y descomprimir estos datos; eso en sí toma algo de información.

  

Sin embargo, puede codificarlo en longitud de ejecución con algo así como 100/1/100/0, donde es el número de bits que se emitirá seguido del bit. Parece que tengo una representación más pequeña que los datos. Especialmente si aumenta el número de 100 a mucho mayor.

Para resumir, el hecho de que pueda idear un esquema para hacer que la codificación de los datos sea más pequeña que los datos originales le dice algo importante. Es decir, dice que sus datos originales contenían muy poca información .

---

Lecturas adicionales

Para un tratamiento más completo de esto, incluyendo exactamente cómo calcularía la entropía para cualquier secuencia arbitraria de dígitos con algunos ejemplos, consulte este breve documento técnico .

Answer 2

Eche un vistazo a Complejidad de Kolmogorov

  

El número mínimo de bits en los que se puede comprimir una cadena sin perder información. Esto se define con respecto a un esquema de descompresión fijo, pero universal, dado por una máquina universal de Turing.

Y en su caso particular, no se limite al alfabeto {0,1}. Para su ejemplo, use {0 ... 0, 1 ... 1} (cientos de 0 y cientos de 1)

Answer 3

Su codificación funciona en este ejemplo, pero es posible concebir un caso igualmente válido: 010101010101 ... que se codificaría como 1/0/1/1 / ...

La entropía se mide en todos los mensajes posibles que se pueden construir en el alfabeto dado, ¡y no solo en ejemplos patológicos!

Answer 4

John Feminella acertó, pero creo que hay más que decir.

La entropía de Shannon se basa en la probabilidad, y la probabilidad siempre está en el ojo del espectador.

Dijiste que 1 y 0 eran igualmente probables (0.5). Si es así, entonces la cadena de 100 1s seguida de 100 0s tiene una probabilidad de 0.5 ^ 200, de los cuales -log (base 2) es de 200 bits, como es de esperar. Sin embargo, la entropía de esa cadena (en términos de Shannon) es su contenido de información multiplicado por su probabilidad, o 200 * 0.5 ^ 200, siendo un número realmente pequeño.

Esto es importante porque si realiza una codificación de longitud de ejecución para comprimir la cadena, en el caso de esta cadena obtendrá una longitud pequeña, pero promediada sobre las 2 ^ 200 cadenas, no funcionará bien. Con suerte, tendrá un promedio de alrededor de 200, pero no menos.

Por otro lado, si miras tu cadena original y dices que es tan sorprendente que cualquiera que la haya generado probablemente generará más, entonces realmente estás diciendo que su probabilidad es mayor que 0.5 ^ 200, por lo que estás haciendo una suposición diferente sobre la estructura de probabilidad original del generador de la cadena, a saber, que tiene una entropía menor que 200 bits.

Personalmente, este tema me parece realmente interesante, especialmente cuando analizas la información de Kolmogorov (Algorithmic). En ese caso, define el contenido de información de una cadena como la longitud del programa más pequeño que podría generarlo. Esto conduce a todo tipo de ideas sobre ingeniería de software y diseño de lenguaje.

Espero que ayude, y gracias por su pregunta.