La paradoja de la información y la teoría de Shannon

  • Categoría de la entrada:Vídeos

El robo de un banco en 1907, un ladrón que huye a Londres y un problema gordo para atraparlo. Estos son los ingredientes para introducir animadamente la teoría de la información de Shannon y su fórmula de la entropía.


Información adicional

La teoría de la información es una rama compleja y extensa. Nació hace setenta años y ha madurado desde entonces, modificando y matizando algunas de sus fórmulas originales. Por eso, al crear este vídeo tenía dos objetivos en mente: explicar qué significa la fórmula de la entropía —de forma más o menos explícita— y ser bastante fiel al enfoque que hace Shannon en su artículo original. Siempre es interesantísimo leer escritos originales: suelen explicar el tema de forma intuitiva, algo que se pierde cuando sus sucesores reorganizan y sintetizan las ideas para publicarlas en el ámbito académico.

Fórmula de la sorpresa

En ningún momento defino qué es la información de forma explícita, pero parece razonable medirla con la fórmula del logaritmo, es decir, como el número de preguntas que necesitas para encontrar a un candidato concreto dividiendo el grupo por la mitad:

I = \log_2(x)

El logaritmo en base dos es una elección arbitraria. Podríamos diseñar un sistema que midiera la información haciendo preguntas con tres posibles respuestas. La información, en vez de medirse en bits, se mediría en trits. Pero estarás conmigo en que es más cómodo usar preguntas binarias, de sí o no.

¿Cuánta información tiene una respuesta concreta? Lo intuitivo es medir cuántas preguntas te ahorra el conocer esa respuesta. Es decir, imagina que antes de hacer una pregunta dudaras entre A candidatos, y después de oír la respuesta dudaras entre B candidatos. Antes de preguntar necesitabas \log_2(A) preguntas para averiguar al candidato, y después de oír la respuesta necesitarás \log_2(B). En resumen, las preguntas que te has ahorrado son:

\log_2(A)-\log_2(B)

Si conoces las propiedades de los logaritmos, podrás concluir que la información que te da una respuesta concreta es de:

I_\text{respuesta}= \log_2 (A)-\log _2(B) = \log_2\left( \frac{A}{B} \right)

Acertijos y teoría de la información

Se puede utilizar la teoría de la información para resolver acertijos o juegos. Un ejemplo sencillo puede encontrarse en este artículo que escribí hace poco, sobre cuál es la mejor manera de jugar en el concurso Alta Tensión. En él estudio qué juagadas te dan más información y, en principio, te hacen ganar en menos pasos.

Otro enfoque harto interesante es el que proponen en este artículo, en inglés, sobre el acertijo de las 12 bolas y la balanza.

Curiosidades

En el vídeo aparece, en un momento determinado, un boleto de lotería con el número 08128. Este es uno de los cuatro números perfectos de menos de seis cifras.

En 2011, el quinto premio de la lotería de Navidad fue el 08128. Me gusta pensar que algún matemático apostó por él y se llevó una alegría.

Vídeo con ADNTRO

Aquí un vídeo resumen sobre qué hemos hecho en la web de ADNTRO. En esencia, hemos calculado la sorpresa que tiene cada cromosoma, hemos aplicado el proceso a toda la base de datos que tienen y hemos sacado la media y la desviación típica, que son las que se representan en el gráfico de barras.

Bibliografía y referencias

[1] New York Times, 1907.
https://en.wikisource.org/wiki/The_New_York_Times/1907/02/24/Sending_Photographs_by_Telegraph

[2] Me refiero a A Mathematical Theory of Communication, C. E. Shannon (1948).
https://ieeexplore.ieee.org/document/6773024?arnumber=6773024
He cambiado el título por cuestiones estéticas.

[3] Definición de bit.
https://en.wikipedia.org/wiki/Bit
Deberíamos añadir que el bit es la respuesta ante una pregunta de sí/no solo cuando ambas opciones son equiprobables. Lo malo es que aún no hemos introducido la probabilidad en la teoría.

[4] Plutón no es planeta (según la IAU, ejem, ejem):
https://www.iau.org/news/pressreleases/detail/iau0603/#1

[5] El logaritmo te dice el número de preguntas si la cantidad de opciones es una potencia de dos. En el resto de casos devuelve un valor con decimales. Es una generalización derivada de la potenciación en el caso continuo (pero si has entendido esta frase, entonces no creo que te resulte raro pensar en preguntas irracionales).

[6] Sobre la cantidad de caracteres de un tuit,
https://developer.twitter.com/en/docs/counting-characters

[7] No hago diferencias entre preguntas y respuestas, y quizá debería. Entiéndase que lo que da información es la respuesta, pero esta proviene de una pregunta contestada.

[8] Telegraphing Pictures, T. Thorne Baker (1909).
https://www.jstor.org/stable/41338909

[9] Shannon no “detecta” esta paradoja directamente en su trabajo original: deduce una fórmula que la evita, sin más circunloquios.

[10] No es la fórmula de Shannon. Se deduce de su teoría, pero él no la menciona en su trabajo original. Es una intepretación posterior, y un recurso pedagógico.

[11] Las tres preguntas del ejemplo inicial.

[12] En este vídeo, la interpretación de la probabilidad es de tipo frecuencial.

[13] Esta debería ser la definición de bit, ahora que hemos introducido la interpretación probabilística.

[14] The security of customer-chosen banking PINs.
https://www.ifca.ai/pub/fc12/73970024.pdf

[15] Sobre la frecuencia de las letras del español:
https://www.worldcat.org/es/title/795065
https://www.sttmedia.com/characterfrequency-spanish

[16] Se considera que 0\times\log_2(1/0)=0. La sorpresa de encontrar algo con probabilidad 0 es infinita, PERO nunca te encontrarás algo así. Y, si lo encuentras, que Dios te pille confesado. Fuera de bromas, cero es el valor que devuelve el límite de la función x \log_2(1/x) cuando x\to 0.

[17] Este es un caso especial, donde p=1 y la información puede considerarse nula.

[18] Este “mínima” es peligroso: podrías adivinar el mensaje por casualidad con una sola pregunta. Si el código se crea en función de un mensaje particular, la fórmula de Shannon te da la cantidad mínima de preguntas con una seguridad del 100% (es decir, sin recurrir a la suerte o al azar). Si quieres usar un código genérico (por ej., el códgo morse) para una familia de mensajes (telegramas en español), el “mínima” pierde sentido y la interpretación debe ser estadística, atendiendo a los teoremas de Shannon.

[19] Se consigue la igualdad si y solo si todas las probabilidades son iguales, p=1/n.

[20] Un análisis interesante sobre la información de cada letra en español (lo que se conoce como entropía del español).
On the Entropy of Written Spanish, F. G. Guerrero (2012).
http://www.scielo.org.co/pdf/rce/v35n3/v35n3a06.pdf

[21] Tomado de Wheel Of Fortune (1997). Es obvio, pero Internet nunca deja de sorprenderme, así que lo aclaro: he adulterado las imágenes. NO es el panel original.

[22] Lecture 6: Entropy.
https://scholar.harvard.edu/files/schwartz/files/6-entropy.pdf

[23] Un resumen general y recomendable es el de Establishing the Triplet Nature of the Genetic Code, C. Yanofsky (2007)
https://doi.org/10.1016/j.cell.2007.02.029