Ejemplo sencillo sobre representación de bits y entropía

Question

He leído que debemos pensar en la entropía como los bits esperados que se requieren para almacenar la información proporcionada sobre una variable.

Por ejemplo:

Si el resultado de una variable es A: 0,5 y B: 0,5, entonces

podemos almacenar esta información como:

[0] <- A # Store 0 for A
[1] <- B # Store 1 for B

En cada caso se requiere 1 bit, por lo que la entropía es:

entropy = prob of A * 1 + prob of B * 1 = 1

Si el resultado de una variable es A: 1,0 y B: 0,0, entonces

[] <- We know it is A not matter what

No almacenamos ningún bit, y la entropía es 0.

Estoy más o menos de acuerdo con los ejemplos anteriores, pero ¿qué pasa con

¿Si el resultado de una variable es A: 0,9 y B: 0,1?

Si almaceno ambas variables como en el ejemplo anterior:

[0] <- A # Store 0 for A
[1] <- B # Store 1 for B

Entonces se toma 1 bit sin importar qué y termino con entropía = 1, lo cual no es correcto.

Si intento no almacenar la variable A en absoluto,

[] <- A # Store 0 for A
[1] <- B # Store 1 for B

Lo entiendo:

entropy = prob of A * 0.0 + prob of B * 1 = 0.1

Lo cual no es correcto.

La respuesta correcta es:

In [20]: from scipy.stats import entropy

In [21]: entropy([0.9, 0.1], base=2)
Out[21]: 0.46899559358928117

¿Cómo debo almacenar los bits para representar las salidas en mi último ejemplo?

Answer 1

He leído que debemos pensar en la entropía como los bits esperados que se requieren para almacenar la información proporcionada sobre una variable.

Tal vez se pueda modificar un poco (¡un juego de palabras!). Intuitivamente, la entropía es la promedio por bit número de bits necesarios para almacenar la información, para una secuencia suficientemente larga de longitud conocida. Es decir, si se tiene una secuencia suficientemente larga de longitud $n$ con entropía $H$ entonces podrá codificarla en aproximadamente $nH$ bits (y no mucho menos), por lo que cada bit requiere de media , sobre $H$ bits.

¿Si el resultado de una variable es A: 0,9 y B: 0,1?

En este caso, un argumento combinatorio muestra que una secuencia suficientemente larga de longitud $n$ generada con estas probabilidades (o una secuencia lo suficientemente larga que tenga estas probabilidades empíricas) es una de las aproximadamente $2^{n H(0.9)}$ tales secuencias, y así sobre $n H(0.9)$ bits, por bit es una longitud de codificación necesaria y suficiente.

Answer 2

Desde un punto de vista práctico, codificación aritmética y Codificación ANS son dos enfoques alternativos, cada uno de los cuales permite codificar y descodificar eficazmente secuencias de datos utilizando un número esperado de bits esencialmente igual al límite teórico dado por la entropía.

Si sólo se trata de codificar una única variable aleatoria Bernoulli, está claro que no se puede representar con menos de 1 bit. Como se explica con más detalle en la otra respuesta, la entropía adquiere relevancia cuando se codifica no sólo una variable, sino toda una secuencia de ellas. En general, el número esperado de bits necesarios por variable no puede alcanzar el límite de entropía, porque la salida sólo puede utilizar un número entero de bits (o, en la práctica, normalmente un número entero de bytes o palabras del sistema), pero a medida que la secuencia se hace más larga la diferencia se vuelve insignificante.