Tema 1: Entropía e Información

1.1. Entropía:

La entropía es una medida de información.
Para poder entender el concepto que encierra vamos primero a ver un ejemplo:

Ejemplo 1: Tenemos una fuente de información, F, que nos va diciendo quien ha ganado un partido de fútbol, si el equipo A, con una probabilidad de 3/4, o el B, con probabilidad 1/4, de tal manera que la situación que tenemos es la siguiente:

Dibujo del ejemplo 1

A la hora de transmitir esta información a través del canal podemos hacerlo de muchas maneras. Supongamos que mandamos los resultados de tres partidos a la vez dando lugar a una codificación como la que sigue:

DATO PROB. CÓDIGO LONGITUD
AAA 27/64   0 1
ABA 9/64   100 3
BAA 9/64   101 3
AAB 9/64   110 3
BBA 3/64   11100 5
BAB 3/64   11101 5
ABB 3/64   11110 5
BBB 1/64   11111 5

Observando nuestro código vemos que mandamos una mayor cantidad de bits en aquellas cadenas que tienen menor probabilidad de ocurrir. La longitud media del código es:

L = 27/64·1 + 9/64·3 + 9/64·3 +9/64·3 + 3/64·5 + 3/64·5 + 3/64·5 +1/64 = 3.4688 bits

De acuerdo con este nuevo código ahora lo que tenemos es p(0) = 0.36 y p(1) = 0.63.

Vemos que tras la codificación binaria las probabilidades de 0 y 1 están más balanceadas que las A y B; lo perfecto sería que lo estuviesen totalmente.

Ya comprendido este ejemplo pasemos a definir entropía:

Definición 1: Dada una variable aleatoria discreta X que tiene una determinada distribución de probabilidades, p(x), entropía de X es:

Fórmula de la entropía

Así, la entropía es una medida de la información que recibimos cuando nos mandan un dato. La unidad en que se mide depende de la base del logaritmo utilizada. Si es dicha base es 2, entonces medimos en BITS o si es el número "e", en NATS, etc. (véase Unidades de la entropía H(X)).

Ejemplo 2: De acuerdo con el ejemplo anterior, la medida de la entropía de la fuente sería:

Fórmula del ejemplo 2

Nota: El resultado esperado más probable es el que, obviamente, menos contribuye al valor de la entropía; luego esta puede entenderse como una ponderación de las contribuciones de cada suceso.


1.1.1. Unidades de la Entropía H(X)

BASE DEL LOGARITMO    UNIDAD   
Decimal (10) Dits
Binario (2) Bits
Número e Nats

Nota: La forma de calcular los logaritmos que no son en base decimal es teniendo en cuenta que:

logbx = logba · logax = logax / logab



1.1.2. Propiedades de la Entropía H(x)

  1. H(X)0
    Demostración: 0p(x)1 implica que log(1/p(x)) >= 0
  2. H(X)=cte·H'(X)

Ejemplo 3: Si F es una fuente binaria tal que p(0)=p y p(1)=1-p=q:

H(p)

A esta H(X) podemos llamarla H(p) o también H(p,q). Su representación gráfica será:

Dibujo de H(p) del ejemplo 2

Observando la gráfica nos damos cuenta de algunas propiedades de la entropía. Vemos que H(X) es cero cuando p=0 ó p=1 porque entonces la variable deja de ser aleatoria, ya que no hay incertidumbre sobre el valor que tomará X. Por otra parte la incertidumbre es máxima cuando p=1/2, lo que consecuentemente coincide con el máximo de H(X).


1.1.3. Entropía con dos variables discretas X e Y

La entropía conjunta de dos variables aleatorias se calcula (en este caso, en bits) de la siguiente manera:

Entropía con dos variables aleatorias

Ejemplo 4: Sean X e Y dos variables aleatorias discretas con la siguiente función de distribución:

Y\X 1 2 3 4
1 1/8 1/16 1/32 1/32
2 1/16 1/8 1/32 1/32
3 1/16 1/16 1/16 1/16
4 1/4 0 0 0

H(X,Y)= 27/8 = 3.375 bits, donde H(X) = 7/4 = 1.75 bits y H(Y)= 2 bits.


1.1.4. Entropía Condicionada

Fórmula de la entropía condicionada



1.1.5. Regla de la Cadena

H(X,Y) = H(Y,X) = H(X) + H(Y/X) = H(Y) + H(X/Y)

Si X e Y son independientes, entonces: H(X,Y)=H(X)+H(Y)


Demostración:

H(X,Y) = –p(x,y)·log2p(x,y) = – E[log2p(x,y)] = – E[log2p(x) + log2p(y/x)] =
= – E[log2p(x)] – E[log2p(y/x)] = H(X) + H(Y/X)


Corolario: H(X,Y/Z)=H(X/Z)+H(Y/X,Z)

Ejemplo 5: Continuando con el ejemplo anterior:

H(Y/X=1) = 7/4 = 1.75 bits.
H(Y/X=2) = 3/2 = 1.5 bits.
H(Y/X=3) = 3/2 = 1.5 bits.
H(Y/X=4) = 3/2 = 1.5 bits.
H(X/Y) = H(X,Y) - H(Y) = 27/8-2 = 11/8 = 1.375 bits.


Nota: Por convenio se tiene:

Fórmulas de convenio






1.2. INFORMACIÓN MUTUA ENTRE X E Y: I(X;Y)

Veamos previamente otro concepto necesario para la explicación de este.


1.2.1. Entropía Relativa o Entropía Diferencial D(p||q)

(A veces también llamada Distancia de Kullback-Leibler).
Es una medida de la distancia entre dos distribuciones de probabilidades de una misma variable aleatoria.

Ejemplo 6: Si conocemos la distribución verdadera de una variable aleatoria, podríamos construir un código usando H(p); pero si construyéramos ese código basándonos en q(x), entonces su longitud sería de H(p) + D(p||q) [bits].

Definición 2: La entropía relativa o diferencial se define como:

Fórmula de la entropía relativa

Propiedades:

  1. D(p||q)0
  2. D(p||q) = 0 si y sólo si p(x) = q(x)
  3. D(p||q) D(q||p)

La tercera propiedad nos lleva a la posibilidad de equivocarnos si entendemos la entropía relativa como una distancia métrica. Es mejor que tengamos el siguiente concepto: D(p||q) es la medida de la ineficiencia de asumir que la distribución correcta es "q" cuando en realidad es "p". De esta forma comprendemos que efectivamente D(p||q) D(q||p).

Ejemplo 7: Dadas las distribuciones p y q

X 0 1
p(x) 1/2 1/2
q(x) 3/4 1/4

sus entropías relativas son:

Ejemplo de entropía relativa



1.2.2. Información Mutua entre X e Y: I(X;Y)

Definición 3: Es la medida de la cantidad de información que una variable aleatoria contiene sobre la otra. Aunque I(X;Y)=I(Y;X), en concreto I(X;Y) es la cantidad de información que X contiene sobre Y.

Fórmula de la información mutua



1.2.3. Relación entre Información Mutua y Entropía

Dado que: p(x,y) = p(y)·p(x/y), entonces:

Deducción de la relación entre I(X;Y) y H

luego:

I(X;Y) = I(Y;X) = H(X) - H(X/Y) = H(Y) - H(Y/X)

Por simetría hemos obtenido que: I(X;Y) = H(Y) - H(Y/X)


Ejemplo 8: Si H(Y) = 2 bits y H(Y/X) = 13/8, calcular I(X;Y).

I(X;Y) = H(Y)-H(Y/X) = 3/8 bits


Como H(X,Y) = H(X) + H(Y/X) entonces:

I(X;Y) = H(X) + H(Y) - H(X,Y)


Resumiendo, nos queda la siguiente tabla de relaciones:

I(X;Y) = H(X) - H(X/Y) = H(Y) - H(Y/X)
I(X;Y) = H(X) + H(Y) - H(X,Y)
I(X;X) = H(X)
I(Y;Y) = H(Y)


Representación con diagramas de Venn de la relación entre la entropía de dos variables aleatorias:

Diagrama de Venn


De los diagramas de Venn podemos concluir:






1.3. Entropía, Entropía Relativa e Información Mutua Condicionadas. Regla de la Cadena.

1.3.1. Entropía Condicionada

La entropía condicionada H(X/Y) ya se vio en el apartado 1.1.4.


1.3.2. Regla de al Cadena para la Entropía

La regla de la cadena para la entropía entre 2 variables aleatorias X e Y ya se vio en el apartado 1.1.5.

Para n variables aleatorias llegamos a:

Regla de la cadena para la entropía


Demostración: La demostración para n variables se realiza como para 2 variables aleatorias mediante la conocida regla de la cadena para probabilidades

Regla de la cadena para las probabilidades
y con ayuda de las reglas de los logaritmos.


Si tenemos n variables aleatorias condicionadas a otra variable aleatoria Y, la entropía de esta relación se podrá expresar como:

Regla de la cadena para la entropía condicionada



1.3.3. Entropía Relativa (o Diferencial) Condicional

Definición 4: La entropía relativa condicional se define a partir de la entropía relativa como:

Fórmula de entropía relativa condicional



1.3.4. Regla de la Cadena para la Entropía Relativa (o Diferencial)

Aplicando la regla de la cadena:

D(p(x,y)||q(x,y)) = D(p(x)||q(x)) + D(p(y/x)||q(y/x))



1.3.5. Informació´n Mutua Condicional

Definición 5: La información mutua condicional se relaciona con la entropía análogamente a la información mutua sin condicionar, de tal manera que:

I(X;Y/Z) = H(X/Z) - H(X/Y,Z) = H(Y/Z) - H(Y/X,Z)



1.3.6. Regla de la Cadena para la Información Mutua

Aplicando de igual manera que antes la regla de la cadena de las probabilidades:

Regla de la cadena para informacion mutua





1.4. Desigualdad de Jensen y sus Consecuencias

Vamos a probar alguna de las propiedades de las magnitudes definidas en el apartado anterior. Empezamos con las propiedades de las funciones cóncavas.

NOTA: En inglés, los términos cóncavo y convexo significan lo contrario que en español. Por esto, cuando en el libro de Cover el autor dice convex, en español decimos cóncavo, y cuando se dice en el libro concave, deberemos entender convexo.

1.4.1. Función Cóncava

Definición 6: Una función se dice que es cóncava en el intervalo (a,b) si se cumple que para todo x1, x2 del intervalo (a,b) y para todo 0K1:

f (K·x1+ (1-k)·x2) K·f (x1) + (1-K)·f (x2)

Se dice que una función es estrictamente cóncava si la igualdad se mantiene solamente para K=0 ó para K=1.

Gracias a la propiedad de concavidad se pueden demostrar otras muchas propiedades de las magnitudes fundamentales de la teoría de la información a través de la desigualdad de Jensen.


1.4.2. Desigualdad de Jensen

Sea f una función convexa y X una variable aleatoria con distribución de probabilidades p1, p2,...,pn (con pi = 1). Entonces:

pi · f(xi) f( pi · x i)   implica que...   E[f(X)] f(E[X])

De la misma manera y con las mismas condiciones, si f fuera una función cóncava:

E[f(X)] f(E[X])

Si f es estrictamente convexa o cóncava, entonces se cumple que X=E[X] con probabilidad 1, es decir, X es una constante. Y se tendría:

E[f(X)] = f(E[X])



1.4.3. PROPIEDADES

  1. D( p || q ) 0.
    D( p || q ) = 0 si y sólo si p( x ) = q( x ) para todo x.

    Demostración: Sea A = { x .. p(x)>0 }

    Demostración de la 1ª propiedad

  2. D( p( x / y ) || q( x / y )) 0.

    Demostración:

    Demostración de la 2ª propiedad

  3. I(X;Y) 0.
    I(X;Y) = 0 si y sólo si X e Y son independientes.

    Demostración:

    I(X;Y) = D( p(x,y) || p(x)·p(y) ) 0 y sólo vale cero si p(x,y) = p(x)·p(y).
    Esto último se cumple únicamente cuando X e Y son independientes.

    Corolario: I(X;Y/Z) 0.

    Demostración:

    I(X;Y/Z) = H(X/Z) - H(X/Y,Z) = D( p(x,y/z)|| p(x/z)·p(y/z) ) 0

    I(X;Y/Z) = 0 p(x,y/z) = p(x/z)·p(y/z)

    Por lo tanto, esta igualdad se dará cuando X e Y sean independientes entre ellas pero condicionadas a Z.

  4. H(X) H(X/Y).
    H(X) = H(X/Y) si y sólo si X e Y son independientes.

    Demostración:

    H(X) - H(X/Y) = I(X;Y) 0


    Ejemplo 9:

    Y\X 1 2
    1 0 3/4
    2 1/8 1/8

    Vamos a ir hallando los distintos valores de la entropía:

    Tabla de valores del ejemplo 9

    Con este ejemplo, lo que queremos es demostrar que la propiedad 4 sólo es verdadera en promedio. Lo vemos en, por ejemplo, H(X) = 0.544 H(X/Y=2), pero también vemos que efectivamente, en promedio sí se cumple que H(X) H(X/Y). Esto se produce porque hay condicionamientos que, de forma aislada, aumentan la incertidumbre (entropía) en vez de reducirla, confundiéndonos aún más. Pero en promedio, siempre los condicionamientos nos reducen o dejan igual la entropía (se sabe más de una variable aleatoria condicionada que sin condicionar).

  5. Fórmula del apartado 5

    Demostración: Por la regla de la cadena, sabemos que:

    Demostración del apartado 5

  6. E[log|X|] H(X)

    Demostración:

    Fórmula del apartado 6

    Notas:

    • |X| representa el cardinal de X.
    • La igualdad se dará cuando p(x) = q(x) = 1/|X| (i.e. X es uniforme, por lo que H(X) es máximo).


  7. Si tenemos una interpolación de dos probabilidades, la entropía aumenta.

    Fórmulas del apartado 7






1.5. Teorema de Procesado de la Información

Nos sirve para demostrar que nunca una manipulación más inteligente de los datos va a mejorar la información mutua entre las v.a. Es decir, dadas X e Y, podemos intentar mejorar I(X;Y) mediante un procesado y obtener Z, pero siempre se va a cumplir que:

I(X;Y) I(X;Z)



1.5.1. Procesos y Cadenas de Markov

Definición 6: Sea la secuencia x1,...,xn,...,xL; xi pertenece a... X; i pertenece a... {1,...,L}. Para que un proceso sea markoviano de orden n, se tiene que cumplir que:

P{xL+1 / xL,...,x1} = P{xL+1 / xL,...,xL-n+1}

Aunque el caso que nos ocupa es con índice "i" y variable aleatoria discretos, también hay procesos markovianos con índice y/o variable aleatoria continuos.


Con ayuda de la definición para el orden n, podemos definir en más detalle la cadena de Markov para orden 1:

Definición 7: Un proceso markoviano de orden 1 es un proceso estocástico de orden 1 en el cual su pasado no tiene ninguna influencia en el futuro si su presente está especificado. Es decir:

Si tn-1 < tn, entonces:

P{ X(tn) Xn/X(t) , t tn-1 } = P{ X(tn) Xn/X(tn-1) }

Luego, si t1 < t2 < ... < tn:

P{ X(tn) Xn / X(tn-1),...,X(t1) } = P{ X(tn) Xn / X(tn-1) }

En nuestro objeto de estudio, que son las cadenas markovianas, tenemos que en una cadena markoviana de primer orden se cumplirá:

P{xL+1 / xL,...,x1} = P{xL+1 / xL}


Ahora definimos un estado como:

sL = {xL, xL-1, ... , xL-n+1}

Por lo tanto:

P{xL+1 / xL, xL-1, ... , xL-n+1} = P{xL+1 / sL}

De la misma manera obtenemos:

sL+1 = {xL+1, ... , xL+2-n}
P{xL+1 / xL, xL-1, ... , xL-n+1} = P{sL+1 / sL}

Por lo tanto, según se ha deducido, mediante los estados podemos pasar de una cadena de orden n a otra de orden 1, ya que hemos formado con los estados la cadena

p(s1,...,sn) = p(s1)·p(s2 / s1)·p(s3 / s2)·...·p(sn / sn-1),
que es una cadena es de orden 1.


Aclaremos lo anterior con un pequeño ejemplo:

Ejemplo 10: Cadena markoviana de 2º orden.

p(x1,...,xn) = p(x1,x2)·p(x3/x1,x2)·p(x4/x2,x3)·...·p(xn/xn-2,xn-1)

Si por ejemplo la secuencia es del tipo abaabbaaab..., tendremos:

p(abaabbaaab...)=p(ab)·p(a/ab)·p(a/ba)·p(b/aa)·p(b/ab)·p(a/bb)·p(a/ba)·p(a/aa)·...

Por estados:

Estados del ejemplo 10


Cuando ocurre que:

P{xL+1=j / xL=i} = P{x2=j / x1=i}
se dice que estamos ante una cadena markoviana invariante en el tiempo u homogénea.


En el ejemplo anterior:

Cadena markoviana homogénea del ejemplo 10


Definición 8: Matriz de probabilidades de transición:

P = Matriz de probabilidades, siendo P{xn+1= j / xn= i} = pij

Propiedades de P:

  1. Es una matriz cuadrada.
  2. pij 0, i,j
  3. pij = 1


Ahora sean:

n = ( p(xn=1) , ... , p(xn=M) )
n+1 = ( p(xn+1=1) , ... , p(xn+1=M) )
p(xn+1= j) = p(xn= i, xn+1= j) = p(xn= i)·pij

Las probabilidades de transición del estado n+1 son:

n+1 = n·[P]

Por lo tanto, dado 1, se obtiene

n = 1·[P]n-1

Ejemplo 11:
Dado el diagrama de estados

Estados del ejemplo 11

una secuencia válida podría ser: abadcb...

Como cada estado depende del anterior (cadena markoviana), se observa como una característica de este ejemplo que, si el estado inicial es a, los estados a y c sólo pueden aparecer en posiciones impares de la cadena, y los estados b y d sólo en posiciones pares. Ocurriría lo mismo si el estado inicial fuera el c, y ocurriría lo contrario si el estado inicial fuera b ó d.


Periodicidad

La probabilidad de ir del estado i al estado j en n saltos se expresa como:

Pij(n) = P{xL+n= j / xL= i} = pih·phj(n-1)

La probabilidad de llegar al mismo símbolo (estado i) tras L saltos será Pii(L). Si Pii(L) , entonces diremos que el estado i es un estado periódico de periodo d=L. Si todos los estados tienen el mismo periodo, la cadena es periódica.


Cadenas de Markov reducibles e irreducibles

Para entenderlo mejor, veamos el siguiente ejemplo:

Ejemplo 12:

DIbujo del ejemplo 12

Se ve claramente que Pac(n) 0, pero Pca(n) = 0, n

Los estados conectados entre sí forman un cluster. En el dibujo hay dos, y están rodeados en rojo y azul.

Un estado es transitorio si, después de pasar por él una o varias veces, no se vuelve a pasar después por él ninguna vez más.

Si todos los estados están conectados entre sí y no son transitorios, se dice que la cadena es irreducible.

En el ejemplo anterior, hay una cadena reducible compuesta por dos cadenas irreducibles (los clusters antes mencionados). Cuando se pasa del estado b al c (transición en color verde), ya no hay manera de volver a los estados a y b. Por lo tanto, estos dos estados son transitorios en la cadena total.


Si la cadena es aperiódica, irreducible y homogénea, entonces

existe un tal que = ·[P]

Si en el instante n la distribución es n = , entonces en el instante n+1 será n+1 = . Por lo tanto, en una cadena de este tipo:

n+L = , L



Para demostrar el teorema de procesado de información, nos hace falta tener claros unos conceptos:

Una cadena de tres v.a. X, Y, Z es de Markov si cumplen:

p(x,y,z) = p(x)·p(y/x)·p(z/y)
Consecuencias: (para la cadena de Markov X -> Y -> Z)


Ejemplo 14::Figura de ejemplo 14


Ahora podemos probar un importante teorema demostrando que ningún proceso de la v.a. Y, ya sea aleatorio o determinista, va a aumentar la información que Y tiene de X.


1.5.2. Demostración del Teorema de Procesado de Información

Si X -> Y -> Z, entonces I(X;Y) I(X;Z)

Demostración: Usando la regla de la cadena:

I(X;Y,Z) = I(X;Z) + I(X;Y/Z) = I(X;Y) + I(X;Z/Y)
Como I(X;Y/Z)0, y I(X;Z/Y)=0:

I(X;Y) I(X,Z)

Nota: Si Z = f(Y) (proceso de Markov), podemos afirmar que I(X;Y) I(X;f(Y))

Corolario: Si X->Y->Z entonces

I(X;Y/Z)I(X;Y)

Luego la independencia entre X e Y disminuye o permanece igual introduciendo la v.a. Z.


Hay que tener cuidado, pues es posible que ocurra que I(X;Y/Z)I(X;Y) si resulta que X, Y, Z   NO forman una cadena de Markov.

Ejemplos:

  1. Dibujo del ejemplo 1
    Fórmulas del ejemplo 1
  2. Dibujo del ejemplo 2 Fórmulas del ejemplo 2





1.6. Límite de Fano

Supongamos que conocemos una v.a. Y y que queremos conocer el valor de una v.a. correlada X. Pues bien, la desigualdad o límite de Fano relaciona la probabilidad de error que tenemos en adivinar X a partir de H(X,Y). Ya sabemos que la entropía de una v.a. X dada otra Y es cero si X es función de Y; luego, según Fano, se podría estimar X sin probabilidad de error si ocurre que H(X/Y)=0. Obviamente, X es función de Y y X es lo que deseo hallar, por lo que nosotros esperamos estimar X con una pequeña probabilidad de error si H(X/Y) es pequeña.

Ahora supongamos que queremos estimar una v.a. X con una distribución p(x). Observamos una v.a. Y relacionada con X a través de la distribución condicional p(y/x). A partir de Y, podemos calcular una función f(Y)=X', que es una estimación de la v.a. X. Entonces, ¿cuál es la probabilidad de que XX'? Lo expresaremos como Pe=Pr{xx'}.

Entonces, la cadena X-> Y-> X' es una cadena de Markov. La desigualdad de Fano nos dice que:

Cadena de Markov
Fórmula del límite de Fano

Demostración: Definimos una variable E de error aleatorio:

E=1 si xx'; E=0 si x=x'. Si ahora hallo H(E,X/Y), entonces:

H(E,X/Y) = H(X/Y) + H(E/X,Y) = H(E/Y) + H(X/E,Y)

Como H(E/Y)H(E), y H(E,X/Y)=0:

H(X/E,Y) = H(X/Y) - H(E/Y) H(X/Y) - H(E)
H(X/E,Y) = P(E=0)·H(X/Y,E=0) + P(E=1)·H(X/Y,E=1) = Pe·H(X/Y,E=1) Pe·log2(|X|-1)

De las dos anteriores inecuaciones, y sabiendo que log2(|X|-1) < log2(|X|) y que H(E) 1, entonces:

Pe·log2(|X|-1) H(X/E,Y) H(X/Y) - H(< B>E) H(X/Y) - 1 Fórmula del límite de Fano


[Tema anterior] [Temario] [Tema siguiente]