Entropía y Teoría de la Información

entropiaEl concepto de entropía es común en termodinámica, mecánica estadística y teoría de la información. En todos los casos la entropía se concibe como una “medida del desorden”, o la “peculiaridad de ciertas combinaciones”. La entropía puede ser considerada como una medida de de la información necesaria para, en cualquier proceso, poder acotar, reducir o eliminar la incertidumbre.

El concepto básico de entropía en teoría de la información tiene mucho que ver con la incertidumbre que existe en cualquier experimento o señal aleatoria. Es también la cantidad de “ruido” o “desorden” que contiene o libera un sistema. De esta forma, podremos hablar de la cantidad de información que lleva una señal.

Cantidad de información

La entropía se mide según la cantidad de información que nos llega, con las ópticas de precisión y dificultad de obtenerla (su calidad).  Veamos dos ejemplos por separado y luego los uniremos en el concepto de entropía.

  • la cantidad de información es una medida de la disminución de incertidumbre acerca de un suceso:

ej.: si se nos dice que el número que ha salido en un dado es menor que dos, se nos da más precisión que si se nos dice que el número que ha salido es par.

  • la cantidad de información que se obtiene al conocer un hecho es directamente proporcional al número posible de estados que este tenía a priori:

Ahora bien, no es lo mismo analizar esta precisión en un universo de diez posibilidades, que si inicialmente se tuvieran dos.

ej.: supone mayor información conocer los números ganadores del próximo sorteo de la lotería, que saber si una moneda lanzada al aire va a caer con la cara o la cruz hacia arriba. En el caso extremo de tener un sólo valor posible con probabilidad 1 (un valor constante), el sistema no aportaría información alguna (0). Por otro lado, si existen infinitas posibilidades dando que la probabilidad de un suceso en dicho sistema es cercana a cero, cualquier indicio de certeza tendría mucho valor y la cantidad de información aportada sería enorme (tendiendo a infinito).

Por lo tanto, concluimos que la cantidad i de información contenida en un mensaje, es un valor matemático medible proporcional a la complejidad del sistema que lo emite, siendo de más (menos) valor si el suceso tiene una probabilidad p baja (alta) de haberlo emitido.

Es así que conocer el resultado de arrojar una moneda con probabilidades p iguales para cada cara nos brinda menos información que para una moneda sesgada, y también menos que conocer el lado de un dado equiprobable.

Entropía:

Definición Formal:

Supongamos que un evento (variable aleatoria) tiene un grado de indeterminación inicial igual a k (i.e. existen k estados posibles) y supongamos todos los estados equiprobables. Entonces la probabilidad de que se dé una de esas combinaciones será p=1/k. Luego podemos representar la expresión:

c_i= \log_2(k)= \log_2[1/(1/k)]= \log_2(1/p) = \underbrace{\log_2(1)}_{= 0}-\log_2(p) =- \log_2(p)

Siendo -log2(p) una función que brinda menos información a los sucesos más probables. Si ahora cada uno de los estados tiene una probabilidad , la cantidad de información es proporcional a suma de los p conocidos. Entonces la entropía vendrá dada por la suma ponderada de la cantidad de información:

Por lo tanto, la entropía de un mensaje X, denotado por H(X), es el valor medio ponderado de la cantidad de información de los diversos estados del mensaje:

Que representa una medida de la incertidumbre media acerca de una variable aleatoria y por tanto de la cantidad de información.

Ejemplos:

Se arroja una moneda al aire; se debe calcular la cantidad de información contenida en los mensajes cara o cruz separadamente:

i = log2 [(1/(1/2)] = log2 2 = 1.

i manifiesta la cantidad de símbolos posibles que representan el mensaje.

Si se lanzara una moneda tres veces seguidas, los ocho resultados (o mensajes) equiprobables pueden ser:

000, 001, 010, 011, 100, 101, 110, 111.

La p de cada mensaje es de 1/8, y su cantidad de información es:

i = log2 [1/(1/8)] = 3.

Entropía de la variable aleatoria asociada a lanzar una moneda al aire:

H(m) = -(0,5 log2 (0,5) + 0,5 log2 (0,5)) = 1.

El suceso aporta exactamente una unidad de información.

Si la moneda está trucada (60% de probabilidades para cara, 40% para cruz), se tiene:

H(m) = -(0,6 log2 (0,6) + 0,4 log2 (0,4)) = 0,970.

La cantidad de información asociada al suceso más simple:

Consta únicamente de dos posibilidades equiprobables (caso de la moneda sin trucar).

Será la unidad a la hora de medir esta magnitud, y se denominará bit.

Una Aplicación: Algoritmo ID3

La elección del mejor atributo para segmentar una base de datos se establece midiendo su entropía. La función elegida puede variar, pero en su forma más sencilla es como esta:

Donde p es el conjunto de los ejemplos positivos, n el de los negativos y d el total de ellos. Se debe establecer si el logaritmo es positivo o negativo.

Como conclusión se puede decir que el concepto de entropía tiene múltiples aplicaciones, y hemos intentado en forma simple mostrar una aplicación de este concepto en la teoría de la información.