Entropía de Shannon: Midiendo la Información

Cuando pensamos en algún científico que gracias a sus aportaciones permitió a la humanidad el desarrollo de tecnologías actuales y necesarias en nuestro día a día como las computadoras, celulares y demás aparatos electrónicos se nos viene a la mente el nombre de Alan Turing, padre de las ciencias de la computación y de la inteligencia artificial. Entre los grandes logros de Turing se encuentra la solución al problema de la decisión, la idealización de la maquina de Turing, el inicio de la inteligencia artificial y por supuesto su papel protagónico en el descifrado de la máquina Enigma que ayudó a los aliados a ganar la Segunda Guerra Mundial. Después de repasar estos increíbles logros queda claro que si las comunicaciones y la información fueran un campo de investigación tan mediático como la ciencia computacional y la inteligencia artificial Claude Shannon sería tan conocido como Alan Turing. De hecho, Shannon llegó a ser cuestionado sobre si uno de sus grandes aportes a la teoría de la información como lo es la Entropía de Shannon es realmente suya o si fue idea de Turing. Esta controversia surgió de que I. J. Good, compañero de Turing en Bletchley Park donde descifraron el código Enigma, aseguró que Turing introdujo el concepto de entropía de la información en 1940, debido a esto surgió la duda de si Turing le habría compartido sus ideas sobre entropía a Shannon cuando coincidieron en 1942 en los Laboratorios Bell y cuando se supo que sostenían reuniones frecuentes en su estadía ahí, sin embargo, Shannon al ser cuestionado sobre si Turing le había compartido sus ideas sobre entropía de la información Shannon respondió que en sus reuniones hablaban casi en su totalidad del cerebro humano y su relación con las máquinas computables, es más, Shannon dijo al final de la entrevista que un día le compartió sus ideas a Turing sobre la teoría de la información pero que recibió \textit{feedback} negativo ya que Turing creía que sus ideas no estaban bien encaminadas o que estaban equivocadas.

Estas declaraciones de Shannon parecen ser las mas aceptadas ya que en sus artículos sobre criptografía, teoría de la información y circuitos, Turing nunca es mencionado ni citado, pero en sus trabajos sobre las computadores de ajedrez o inteligencia artificial si que lo es. De la misma manera, el hecho de que Turing nunca haya publicado sobre la Entropía de la información descalifica las afirmaciones de Good pero las sigue dejando en el aire debido a que durante la guerra los trabajos sobre criptografía estaban clasificados y para cuando se quitaron las restricciones Alan Turing ya había perdido la vida a la corta edad de 41 años.

A pesar de tales controversias Shannon es ampliamente aceptado por la comunidad científica como el Padre de la Era de la Información, repasemos los conceptos mas importantes de su teoría.

Información y La Entropía de Shannon

La entropía de Shannon es una medida de la incertidumbre de una distribución de probabilidad.

La entropía de Shannon es fácilmente explicada en base al siguiente ejemplo:

Dos máquinas escriben las primeras 4 letras del abecedario, la máquina uno que denotamos por $M_1$ genera las letras A,B,C y D aleatoriamente, de manera que cada letra tiene un $25\%$ de probabilidad de ser escrita mientras que la máquina dos $M_2$ genera las mismas letras siguiendo la siguiente distribución: $A \rightarrow 50\%$ , $B \rightarrow 12.50\%$ , $c \rightarrow 12.5\%$ y $D \rightarrow 25\%$ .

Shannon planteó lo siguiente: ¿Cuántas preguntas de ¿sí o no? necesito hacer para predecir el símbolo que escribirá cada una de las máquinas?

Veamos, para $M_1$ primero haríamos la pregunta:

1. ¿Es A o B?

dependiendo de la respuesta ya hemos eliminado la mitad de las probabilidades y quedaremos con dos letras igualemente probables. En caso de la respuesta sea sí, lo siguiente sería preguntar:

2. ¿Es A?

Si la respuesta es negativa sabríamos que es B. Si la respuesta a ¿Es A o B? es no, la pregunta dos sería:

2. ¿Es C?

Por lo que la incertidumbre de $M_1$ es de 2 preguntas por símbolo.

Ahora , para $M_2$ seguiríamos el siguiente orden, como A tiene una probabilidad del $50\%$ primero preguntamos:

1. ¿Es A?

En caso de una respuesta negativa preguntaríamos:

2. ¿Es D?

Ya que D tiene una probabilidad mas alta. En caso de que la respuesta sea no, finalmente preguntaríamos:

3. ¿Es C?

Y aquí ya tendríamos todos los resultados posibles contenidos en estas 3 preguntas. Ahora, a diferencia de $M_1$ para cualquier símbolo necesitas obligatoriamente hacer 2 preguntas, sin embargo, para $M_2$ puedes acabar el ejercicio con 1, 2 o 3 preguntas, por lo que nos interesa saber el promedio de preguntas que se deben hacer. Para conocer este valor hacemos una analogía con las maquinas tragamonedas de pinball. $M_1$ sería construida como se observa en la Figura 1.

La pelota rebota 2 veces antes de llegar a un símbolo y así las probabilidades de cada letra son de $25\%$ .

Para $M_2$ se tendría la disposición de la Figura 2.

Para escribir A se necesita un rebote, para D dos y para B o C se necesitan 3, entonces podemos encontrar el número promedio de rebotes multiplicando el número de estos por su probabilidad, es decir, sea N el número esperado de rebotes:

$N = p_A + p_B(3) + p_C(3) + p_D(2)$

$N = 0.50 + 0.125(3) + 0.125(3) + 0.25(2)$

$N = 1.75$

Aquí hemos encontrado que hay una relación entre el número esperado de preguntas y el número de rebotes en la máquina de pinball, deben ser iguales!

En base a esto podemos decir que la máquina dos está produciendo menos información porque hay menos incertidumbre o sorpresa en sus resultados. A esto es a lo que Shannon llamó entropía y la unidad para esta medidad la llamó bit. Entonces la entropía de nuestra máquina de pinball quedó como:

$H= \sum_{i=1}^{N}p_i(#rebotes)$

Ahora, podemos expresar el número de rebotes de una manera más general:

$N = \log_2(\frac{1}{p})$

Por ejemplo, observando la Figura 2, para que la máquina escriba la letra C hay una probabilidad de 0.125 y se necesitan 3 rebotes, comprobando con nuestra fórmula:

$N = \log_2(0.125) = 3$

Así la entropía H nos queda:

$H= \sum_{i=1}^{N}p_i\log_2(\frac{1}{p_i}) = -\sum_{i=1}^{N}p_i\log_2(p)$

La entropía de Shannon nos da un valor de incertidumbre para conocer el resultado de un experimento que sigue una distribución de probabilidad.

La probabilidad es máxima cuando todos los eventos son igualmente probables como lo vimos con la máquina $M_1$ y cada vez que nos desviemos de la equiprobabilidad la entropía debe disminuir. Así el bit se convirtió en la unidad de medida de la información.