Lo que he aprendido: entropía de Shannon

Hoy me han explicado la entropía de Shannon de una manera muy intuitiva que no conocía. Paso a compartirla con vosotros, pero primero haré una pequeña introducción. Claude Shannon era este señor con cara de pilluelo:

Claude Shannon de aquí

Claude Shannon de Tekniska museet. Licencia CC BY

Es conocido por ser el padre de la teoría de la información y por tener ocurrencias molonas ya desde crío, de las cuales mi favorita es el sistema de telégrafo que desarrolló para comunicarse con un amigo a distancia. Parece ser que en aquella época no había tarros de yogur o que la casa del amigo estaba muy lejos.

El señor definió una forma de medir la cantidad de información que contiene una variable aleatoria, es lo que se conoce como Entropía de Shannon y tiene esta pinta:

H(X)=-\sum P_i \log_{2}(x_i)

Hoy me han dicho cómo interpretar esa fórmula intuitivamente: la entropía de Shannon es el número de preguntas sí/no que se necesitan para llegar a la respuesta correcta. Es decir, imaginamos que hay un oráculo que siempre acierta y tenemos que hacerle preguntas hasta que lleguemos al valor de la variable. Esto lo podemos hacer de varias maneras: podemos ir dándole opciones una a una empezando en un valor y subiendo, dándole números al azar… O podemos hacer lo que yo llamo un Bolzano y que en realidad se llama búsqueda binaria. Si los valores límite de la variable son a y b y el punto medio entre ellos es c, hacemos lo siguiente:

  1. Preguntamos si el valor está entre a y c
  2. Si nos dice que sí descartamos el trozo entre c y b. En caso contrario el a – c
  3. Calculamos el punto medio del trozo y repetimos la operación hasta llegar al valor.

El coste de este sistema es de log2(N), donde N es el número de puntos entre a y b.

Veamos, imaginemos que queremos saber cuál es la entropía de Shannon de tirar un dado. Los estados posibles son {1,2,3,4,5,6} y la probabilidad de todos es la misma. Si le preguntamos al oráculo por los números de uno en uno siguiendo el orden de mayor a menor en el mejor de los casos necesitaremos una única pregunta y en el peor 6 preguntas. Para saber cuántas preguntas necesitamos de media debemos tener en cuenta todos los casos posibles y cómo de probables son. Esto es más rápido si usamos el truco, se ve fácilmente que siempre necesitamos 2 o 3 preguntas (haced la prueba en casa 🙂 ). Si repetimos este proceso para muchas tiradas de dados, de media necesitaremos log2(6)= 2.58 preguntas. Esto coincide con la entropía de Shannon que para este caso es:

H(X)=6*\frac{1}{6}\log_{2}(6) = 2.58

Esto es un caso muy simple, la fórmula tiene en cuenta procesos en los que la probabilidad de los diferentes estados es diferente, pero a mí por lo menos me ha servido para ver el concepto desde otro punto de vista. Espero que a vosotros también.

Más:

El artículo de Shannon en el que expone la entropía de la información en el IEEE

Shannon en Yorokobu

Un vídeo de Computerphile sobre la entropía en la compresión

Anuncios

Un pensamiento en “Lo que he aprendido: entropía de Shannon

  1. Pingback: Compilación: greatest hits del 2016 | Onda Hostil

¡Opina sin miedo! (Puedes usar Markdown)

Introduce tus datos o haz clic en un icono para iniciar sesión:

Logo de WordPress.com

Estás comentando usando tu cuenta de WordPress.com. Cerrar sesión / Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Cerrar sesión / Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Cerrar sesión / Cambiar )

Google+ photo

Estás comentando usando tu cuenta de Google+. Cerrar sesión / Cambiar )

Conectando a %s