Introducción a la Teoría de la Información - Inicio

Introducción a la Teoría de la Información Tomás V. Arredondo 8/4/2011

Introducción a la a la Teoría de la Información y Aplicaciones Contenidos: • Introducción a algunos aspectos de la teoría de la información (T.I.): información y probabilidades • Entropía • Reseña de algunas aplicaciones en diferentes áreas incluyendo: Comunicaciones, Encripción y Bioinformática.

Introducción a la a la Teoría de la Información y Aplicaciones: Introducción

¿Que es la información? • La información como es conocida comúnmente es una amalgama de muchas nociones vagas e imprecisas que generalmente es medida basada en la cantidad de noticia (o sorpresa) que provee. ¿Que es la teoría de la información? • Serie de las leyes para relacionar determinado orden de fenómenos relacionados con la comunicación de la información entre su origen y su destino a través de un canal.

Introducción a la a la Teoría de la Información y Aplicaciones: Introducción Sistema de Comunicaciones Básico

Origen

Mensaje M

Canal

Destino

Mensaje M’

Introducción a la a la Teoría de la Información y Aplicaciones: Introducción ¿Cuál es el rol de las probabilidades en las comunicaciones? • Las probabilidades nos dan una manera de determinar cuantitativamente las características que queremos estudiar en los sistemas (ej. la distribución de la información de un origen, la confiabilidad de un canal, la relación entre el origen y el destino de la información entre otras) • Las probabilidades están basadas en las frecuencias observables de la ocurrencia de eventos

Introducción a la a la Teoría de la Información y Aplicaciones: Introducción Las frecuencias y las probabilidades • Si repetimos un experimento N veces que tiene M diferentes resultados posibles y contamos el numero de veces que se observan las diferentes posibilidades n1, n2,..., nM entonces podemos determinar la frecuencia de estas observaciones (f1, f2, ..., fM) al dividir n1, n2,..., nM por N. Si N → ∞ estas frecuencias son la probabilidad (p1, p2, ..., pM) de ocurrencia del evento y sus valores posibles son entre 0 y 1. • El siguiente es el caso de tener los eventos A, B, AB (A y B, ambos eventos ocurriendo), A’B’ (ninguno de los dos). •

A’B’

A

AB

B

Introducción a la a la Teoría de la Información y Aplicaciones: Introducción Las frecuencias y las probabilidades (cont) Permutaciones: Las permutaciones son el • reordenamiento de objetos o símbolos en secuencias distinguibles: El numero de permutaciones de n objetos es n! n(n-1)(n-2)...·3·2·1 0! = 1 La formula para el numero de permutaciones de r objetos seleccionados de un conjunto de n objetos: P n , r =

n! n−r !

Cada uno de los objetos es distinguible de los otros

Introducción a la a la Teoría de la Información y Aplicaciones: Introducción Las frecuencias y las probabilidades (cont) Ejemplo: • Si tengo 6 tarros de pintura de color y una flota de 4 autos (Ferrari, Jaguar, Corvette, Citroen), el numero de permutación posibles para pintar los autos es 6·5·4·3 o usando la formula: P n , r = P 6, 4=

6! =360 6−4!

Si alguien eligiera una permutación de colores para su flota al azar la probabilidad de ella seria = 1/360

Introducción a la a la Teoría de la Información y Aplicaciones: Introducción Las frecuencias y las probabilidades (cont) En otras situaciones no nos importa la posición de selección • de los objetos en cuestión. En ese caso se quieren determinar el numero de las • combinaciones de elegir r objetos de un set de n objetos: n n−1 n−2...n−r 1 n! C n , r = n = = r! n−r ! r ! r



•

Estas cantidades se llaman coeficientes binomiales porque fueron estudiados en relación con la expansion de binomiales en los cuales las maneras de seleccionar el numero de las variables es dado por la relación descrita anteriormente – (a + b)3 = a3 + 3a2b + 3ab2 + b3

0 1  2 3

– (a + b)3 = 3 a 3 3 a 2b 3 ab 2 3 b3

Introducción a la a la Teoría de la Información y Aplicaciones: Introducción Las frecuencias y las probabilidades (cont) •

Ejemplo: Si alguien compra 3 tipos de quesos del supermercado de 12 posibles tipos ¿Cual es el numero de combinaciones de compra? No nos importa el orden en que los compramos (e.g. {Gruyere, Suizo, Cabra} se considera la misma combinación que {Suizo, Gruyere, Cabra})

12 ! C 12,3= 12 = =220 9! 3 ! 3

 

Si nos importara el orden el resultado seria una permutacion: P(12,3) = 12·11·10 = 1320

Introducción a la a la Teoría de la Información y Aplicaciones: Introducción Las frecuencias y las probabilidades (cont) Probabilidad condicional • Muchas veces es importante saber la probabilidad de un evento (A) basado en información previa sobre otro evento o variable, este otro evento o variable determina el espacio de muestreo (S) que se esta usando y por ende el valor de la probabilidad La probabilidad de A dado S se escribe: P(A | S}

Introducción a la a la Teoría de la Información y Aplicaciones: Introducción Las frecuencias y las probabilidades (cont) Si se observan el siguiente numero de eventos: • A ocurre, B no ocurre (AB’):

n1

B ocurre, A no ocurre (BA’):

n2

A y B ocurren (AB):

n3

Ni A ni B ocurren (A’B’):

n4

A o B o ambos ocurren (A + B):

n1 + n2 + n3

El total de los eventos son N:

N = n1 + n2 + n3 + n4

Las frecuencias son: f {A} = (n1 + n3)/N, f {B} = (n2 + n3)/N, f {AB} = n3/N, f {A+B} = (n1 + n2 + n3)/N = f {A} + f {B} – f {AB}, La frecuencia que A ocurre si sabemos que B ya ocurrió f {A|B} = n3/(n2 + n3), La frecuencia que B ocurre si sabemos que A ya ocurrió f {B|A} = n3/(n1 + n3), A’B’ AB A B AB’

BA’


Cuando N tiende a ∞ estas frecuencias tienden a probabilidades: P{A+B} = P{A∪B} = P{A} + P{B} - P{AB} ≤ P{A} + P{B} P{AB} = P{A∩B} = P{A} P{B|A} P{AB} = P{A∩B} = P{B} P{A|B} P{A|B} = P{AB}/P{B}, P{B}≠0 P{B|A} = P{AB}/P{A}, P{A}≠0

•

Para eventos A y A’ (inversos) P{A+A’} = 1 P{AA’} = 0


Las frecuencias y las probabilidades (cont) Ejemplo: • Se saca una carta de un mazo de cartas: A = Sale una carta roja, B = sale un rey, AB = sale un rey rojo, A + B = sale un rey o sale una carta roja Prob{A} = 1/2, Prob{B} = 1/13, Prob{AB} = (1/13)(1/2)= 1/26 Prob{A + B} = Prob{A} + Prob{B} – Prob{AB} = 1/2 +1/13 – 1/26 = 7/13


Las frecuencias y las probabilidades (cont) Ejemplo: • Si estamos tirando dos dados y tenemos los siguientes eventos: A = Dado 1 sale 3, B = dado 2 sale 1, C = la suma de ambos da 8. •

Probs. apriori (antes de tener mas datos): P{A} = P{B} = 1/6, P{C} = 5/36

•

Probs. conjuntas: P{A ∩ Β} = 1/36, P{A ∩ C} = 1/36, P{B ∩ C} = 0/36

•

Probs. condicional: P{C | Β} = 0, P{C | A} = 1/ 6, P{B | A } = P{B} dado que A y B son independientes.


Si el evento A y B son independientes P{A|B} = P{A} P{B|A} = P{B} P{A+B} = P{A∪B} = P{A} + P{B} P{AB} = P{A∩B} = P{A} P{B}

A’B’ A

B

AB’

BA’

Introducción a la a la Teoría de la Información y Aplicaciones: Introducción Las frecuencias y las probabilidades (cont) Ejemplo: • Se tiran dos dados, uno rojo y uno blanco: A = Dado rojo sale uno, B = Dado blanco sale seis AB = dado rojo sale uno y dado blanco sale seis A + B = dado rojo sale uno o dado blanco sale seis Prob{A} = P{A|B} = 1/6, Prob{B} = P{B|A} = 1/6, Prob{AB} = (1/6)(1/6)= 1/36 Prob(A + B) = 1/6 + 1/6 = 1/3

Introducción a la a la Teoría de la Información y Aplicaciones: Introducción Las frecuencias y las probabilidades (cont) Si el evento A y B son excluyentes: • P{AB} = {∅} Ejemplo: Se tira un dado: • A = el dado sale 1, B = el dado sale 2 AB = el dado sale 1 y el dado sale 2 A+B = el dado sale 1 o el dado sale 2 Prob{A} = 1/6, Prob{B} = 1/6, Prob{AB} = {∅} Prob{A+B} = 1/6 + 1/6 = 1/3

Introducción a la a la Teoría de la Información y Aplicaciones: Introducción Función Discreta de Probabilidad (PDF) y Función Cumulativa de Probabilidad (CDF) Si se tiene un experimento aleatorio y los resultados se pueden poner en correspondencia con un numero de enteros positivos entonces ese numero de enteros se denomina un espacio de muestreo discreto. En un espacio discreto de muestreo, cuando la variable aleatoria X asume valores {x1, x2, x3,...,xk} la función discreta de probabilidad f(x) se define como: {p1,p2, p3,...,pk} en el cual f(xk) = Prob{X = xk} = xk La función cumulativa de probabilidad se define como: F  x = ∑ f  x j  x j x

Introducción a la a la Teoría de la Información y Aplicaciones: Introducción Función Discreta de Probabilidad (PDF) y Función Cumulativa de Probabilidad (CDF) (cont) Ejemplo: • Se tira una moneda repetidamente hasta que sale una cara X = La moneda sala cara por primera vez en el tiro k X = {1, 2, 3,...,k} PDF: f = {1/2, 1/4, 1/8, ..., 2-k} CDF: F(x) = 2-1 + 2-2 + ... + 2-x .5 f(x)

1

.375

F(x)

.25 .125 0

1

2

x

3

4

5

.625 .5 .125 0

1

2

3 x

4

5

Introducción a la a la Teoría de la Información y Aplicaciones: Introducción Funciones Discretas de Multiples Variables En la mayoría de los problemas en ingeniería es importante saber la distribución entre multiples variables aleatorias. Esto puede ser para por ejemplo saber el comportamiento de un sistema con inputs (X) y outputs (Y). Para estudiar esto se formaliza la idea de una distribución discreta multivariable. Si se tienen dos variables aleatorias X e Y entonces la PDF y CDF se definen de esta forma: PDF: f(x, y) = Prob{X = x, Y= y} CDF: F  x , y =

∑

x j x y k  y

f  x j , yk 

Se denominan probabilidades marginales cuando solo se considera solo una de las dos variables sin consideración por la otra.

Introducción a la a la Teoría de la Información y Aplicaciones: Introducción Funciones Discretas de Multiples Variables (cont) Distribución (probabilidad) marginal La distribución marginal de una matrix (n x m) de probabilidades se calculan según: •

P( X = i) = Σj(pij) = pi1 + pi2 + ... + pin,

•

P( Y = j) = Σi(pij) = p1j + p2j + ... + pmj

Y= 1

Ejemplo: P( X = 1) = p11+p12+p13+p14= 4/16 = 1/4 P( Y = 2) = p12+p22+p32+p42= 5/16

1

X=

2 3 4

2

3

4

[ ] 2 16 1 16 0 16 0 16

1 16 2 16 1 16 1 16

1 16 1 16 2 16 1 16

0 16 0 36 1 16 2 16

3/16 5/16 5/16 3/16

4/16 4/16 4/16 4/16

Introducción a la a la Teoría de la Información y Aplicaciones: Introducción Funciones Discretas de Multiples Variables (cont) Ejemplo: Un sistema con input (X) y output (Y). ¿Cual es la Prob{ 3 ≤ X ≤ 5, 2 ≤ Y ≤ 3 } y las probabilidades marginales de X e Y? Y= 1

Probabilidad de cada punto en la muestra: P{X=i, Y=j} = 1/36

1 2

P{ 3 ≤ X ≤ 5, 2 ≤ Y ≤ 3 } = 6/36 = 1/6

3

Probabilidades marginales: P{ 3 ≤ X ≤ 5} = 18/36 = 1/2 P{ 2 ≤ Y ≤ 3} = 12/36 = 1/3 X e Y son independientes, ya que todos los valores del arreglo 1/36 = (1/6)(1/6)

X=

4 5 6

2

3

4

5

6

[ ] 1 36 1 36 1 36 1 36 1 36 1 36

1 36 1 36 1 36 1 36 1 36 1 36

1 36 1 36 1 36 1 36 1 36 1 36

1 36 1 36 1 36 1 36 1 36 1 36

1 36 1 36 1 36 1 36 1 36 1 36

1 36 1 36 1 36 1 36 1 36 1 36

1/6 1/6 1/6 1/6 1/6 1/6

1/6 1/6 1/6 1/6 1/6 1/6

Introducción a la Teoría de la Información y Aplicaciones: n v/s log n ¿Como se usan comunicaciones?

las

probabilidades

en

las

• Si se quieren comparar fuentes y canales de datos, se pueden usar medidas de las diferencias entre ellos • Estas medidas nos pueden dar un reflejo del tipo de fuente y del tipo de canal que se esta estudiando

X

Sistema de comunicaciones

Y


las

probabilidades

en

las

Ejemplo: Binary Symmetric Channel (BSC), un modelo de un canal simple pero que incluye gran parte de la complejidad del problema de comunicaciones en general. Nos interesa P{Y|X}, mas específicamente: P{0|0} = P{1|1} = p, P{1|0} = P{0|1} = q X 0

p q

Y 0

q 1

p

1


las

probabilidades

Ejemplo: Binary Erasure Channel (BEC) Para el BEC P{0|0} = P{1|1} = p, P{z|0} = P{z|1} = q

X 0

1

p q q p

Y 0 z 1

en

las

Introducción a la a la Teoría de la Información y Aplicaciones: Introducción Funciones Discretas de Multiples Variables (cont) Probabilidades Condicionales Considere una matrix de probabilidades para dos variables aleatorias X, Y representando un transmisor y un receptor: ¿Como se calcula la probabilidad de X dado Y: P( X | Y } o Y dado X: P( Y | X } ? Y=

•

P{ X = i | Y = j ) = p(xi | yj) = p(xi , yj) / Σi(pij)

•

P{ Y = j | X = i )= p(yj | xi) = p(xi , yj) / Σj(pij)

1 1 2

Ejemplo: X= P( X = 1| Y = 2) = p(x1 , y2) / Σi(pi2) = (1/16) / (5/16) = 1/5 3 P( Y = 3| X = 3) = p(x3 , y3) / Σj(p3j) = (2/16) / (4/16) = 1/2

4

2

3

4

[ ] 2 16 1 16 0 16 0 16

1 16 2 16 1 16 1 16

1 16 1 16 2 16 1 16

0 16 0 36 1 16 2 16

3/16 5/16 5/16 3/16

4/16 4/16 4/16 4/16


Introducción a la Teoría de la Información y Aplicaciones: log n v/s Entropía La entropía H(X) H(X) es una medida de la incertidumbre o de la información promedio que nos provee una variable aleatoria (o grupo de variables aleatorias) • La selección de un evento de dos posibles eventos de igual probabilidad requiere 1 bit de información • La selección de un evento de cuatro posibles eventos de igual probabilidad requiere 2 bits de información • ...etc...

Introducción a la Teoría de la Información y Aplicaciones: log n v/s Entropía La entropia H(X) (cont) • Si tenemos un espacio de muestreo dividido en 2N eventos que son igualmente probables Ek (k = 1, 2, ..., 2N) entonces la información (en bits) proveida por el evento Ek es:

−N

I(Ek ) = − log(pk ) = − log 2 = N

Introducción a la Teoría de la Información y Aplicaciones: log n v/s Entropía La entropia H(X) (cont) • La información promedio dada por una variable aleatoria X que representa un sistema finito de probabilidades entonces n es:

H(X) = I(E k ) = −

∑

k= 1

p k log 2 (p k )

H(X) cumple con varios requisitos: – Continuidad – Simetría – Extrema: cuando todos los eventos son equiprobables H(X) tiene que ser máximo, cuando uno es el unico probable H(X) tiene que ser mínimo – Aditiva

Introducción a la Teoría de la Información y Aplicaciones: n v/s log n La entropia H(X): ¿porque nlogn como medida? • Si se tiene un sistema con por ejemplo n diferentes opciones de transmisión • Y si se quiere tener una medida basada en esas opciones para poder diferenciar un sistema de otro o para diseñar sistemas en el cuales el origen, el canal y el destino estuvieran bien dimensionados. • ¿Podría usarse por ejemplo el numero de estados n como medida de las opciones disponibles?

Introducción a la Teoría de la Información y Aplicaciones: n v/s log n La entropia H(X): n, una posible medida de un sistema probabilistico Ejemplo: Un sistema de comunicaciones Morse en el cual se pueden mandar tres diferentes combinaciones de claves. • En nuestro ejemplo cada una de las tres claves tiene dos posibles estados (raya y punto).

Introducción a la Teoría de la Información y Aplicaciones: n v/s log n La entropia H(X): n, una posible medida de un sistema probabilistico • Ejemplo (cont): • Asumiendo que todos los estados son equiprobables las probabilidades son: P{cl1=raya} = P{cl1=punto} = P{cl2=raya} = P{cl2=punto} = P{cl3=raya} = P{cl3=punto} = ½ • En nuestro ejemplo el sistema visto como conjunto tiene ocho posibles estados (raya-raya-raya, raya-raya-punto,…, puntopunto-punto, 23=8) pero las tres claves como componentes del sistema nos da seis posibles estados (2+2+2=6).

Introducción a la Teoría de la Información y Aplicaciones: n v/s log n Estado

Clave 1

Clave 2

Clave 3

1

-

-

-

2

-

-

.

3

-

.

-

4

-

.

.

5

.

-

-

6

.

-

.

7

.

.

-

8

.

.

.

Introducción a la Teoría de la Información y Aplicaciones: n v/s log n La entropia H(X): n, una posible medida de un sistema probabilistico • El numero de estados (n) para el sistema es ms = 8, para cada clave mc1=mc2=mc3= 2 • Una cualidad deseable en cualquier medida es que se puedan sumar los estados de los componentes del sistema y que esta suma sea igual a los estados del sistema completo → mc1 + mc2 + mc3 = ms • Pero 2 + 2 + 2 ≠ 8 Entonces simplemente usar n no funciona… ¿Qué hacer? • Afortunadamente una manera de transformar productos de números a sumas es usando el logaritmo.

Introducción a la Teoría de la Información y Aplicaciones: n v/s log n La entropia H(X): log n, otra posible medida de sistema probabilistico • log2n tiene la capacidad requerida de nuestra medida ya que: log2(2) + log2(2) + log2(2) = log2(8) • Entonces usando nuestra nueva medida m = log2(n) • Para el sistema entero log2(ns) = log2(8) y para cada clave log2(nc1)= log2( nc2) = log2( nc3) = log2(2) • Esta nueva medida si tiene esta cualidad deseada (propiedad aditiva) → mc1 + mc2 + mc3 = ms • Típicamente se usa la base 2 para el logaritmo especialmente en sistemas binarios. En este caso la unidad de información de sistemas binarios se llama bit que es una contracción de “binary unit”.

Introducción a la Teoría de la Información y Aplicaciones: log n v/s Entropía La entropia H(X): Sistemas con probabilidades distintas • En sistemas en los cuales las probabilidades de los componentes transmitidos en mensajes no son equiprobables, entonces es necesario ampliar nuestra medida (log2(n)). • Esta medida se llama entropía se usa el símbolo H para designarla.

Introducción a la Teoría de la Información y Aplicaciones: log n v/s Entropía La entropia H(X): Sistemas con probabilidades distintas • No se pueden sumar las contribuciones de los diferentes componentes de manera igual ya que en sistemas reales los componentes de los mensajes tienen diferentes frecuencias y probabilidades. • Incluir esas probabilidades es esencial para que nuestra medida mida las contribuciones de las diferentes opciones en nuestro mensajes de manera mas realista.

Introducción a la Teoría de la Información y Aplicaciones: log n v/s Entropía La entropia H(X): Sistemas con probabilidades distintas • Ejemplo: Sistema morse Si {P(raya) = .1 y P(punto) = .9} se puede decir que la información promedio contribuida por una raya es Prayalog(Praya) y la información promedio contribuida por un punto es Ppuntolog(Ppunto).

Introducción a la Teoría de la Información y Aplicaciones: log n v/s Entropía La entropia H(X): Sistemas con probabilidades distintas • Asumiendo que X = {raya, punto}, P(raya)=.1, P(punto)=.9, x es una variable aleatoria del espacio X, N es la cantidad de opciones igual a 2 (raya o punto). • H(X) deberia tender a 0 cuando P(xn) tiende a cero o a 1 ya que eso indica certeza en el mensaje y al haber certeza no hay incertidumbre (una pista: -P(xn)logP(xn) tiende a cero cuando P(xn) es cero o uno). • El valor máximo de H(X) es cuando P(xn) = 1/N = ½ indicando mayor incertidumbre en el mensaje y más información transmitida sobre el sistema (propiedad extrema).

Introducción a la Teoría de la Información y Aplicaciones: log n v/s Entropía La entropia H(X): Sistemas con probabilidades distintas • Si el numero de posibles resultados equiprobables se incrementa entonces la entropía también se incrementa. • También nos interesa que esta función H(X) tenga simetría con respecto a la probabilidades de izquierda a derecha • H(X) debiera ser concava hacia abajo (limitada) y continua • Para que cumpla con estos requerimientos, la entropía se define de la siguiente forma:

H(X) = −

∑ i

p i log(pi )

Introducción a la Teoría de la Información y Aplicaciones: log n v/s Entropía Medidas 8 6 4 log(P)

0

-log(P) -Plog(P)

-2 -4 -6

Probabilidad P

0.98

0.91

0.84

0.77

0.7

0.63

0.56

0.49

0.42

0.35

0.28

0.21

0.14

0.07

-8 0

Valores

2

Introducción a la Teoría de la Información y Aplicaciones: log n v/s Entropía

Medidas 0.6 0.5

0.3

-P1log(P1)

0.2 0.1

Probabilidad P1

1

0 0 0. 04 0. 08 0. 12 0. 16 0. 2 0. 24 0. 28 0. 32 0. 36 0. 4 0. 44 0. 48 0. 52 0. 56 0. 6 0. 64 0. 68 0. 72 0. 76 0. 8 0. 84 0. 88 0. 92 0. 96

Valores

0.4


Medidas 0.6 0.5

0.3

-P2log(P2)

0.2 0.1

Probabilidad P2

0

0 1 0. 96 0. 92 0. 88 0. 84 0. 8 0. 76 0. 72 0. 68 0. 64 0. 6 0. 56 0. 52 0. 48 0. 44 0. 4 0. 36 0. 32 0. 28 0. 24 0. 2 0. 16 0. 12 0. 08 0. 04

Valores

0.4


Medidas 1.2

0.8 0.6

H(x)=-P1log(P1)-P2log(P2)

0.4 0.2

Probabilidad P1 (P2 = 1 - P1)

1

0.96

0.92

0.88

0.84

0.8

0.76

0.72

0.68

0.64

0.6

0.56

0.52

0.48

0.44

0.4

0.36

0.32

0.28

0.24

0.2

0.16

0.12

0.08

0.04

0 0

Valores H(x)

1

Introducción a la Teoría de la Información y Aplicaciones: Entropía Ejemplos H(X): • Si P(raya) = .1, P(punto) = .9: H(X) = -(.1log20.1 + .9log2.9) = 0.476 bits • Si P(raya) = .9, P(punto) = 0.1: H(X) = -(.9log2.9 + .1log2.1) = 0.476 bits {simetría} • Si P(raya) =.5 y P(punto)=.5: H(X) = -(.5log2.5 + .5log2.5) = 1.0 bits {P=(1/N) → H(x)Máx} • Si P(raya) =0 y P(punto)=1: H(x) = -(0log20 + 1log21) = 0 bits {P=(1) → H(x)Min=0}

Introducción a la Teoría de la Información y Aplicaciones: Entropía Conclusion:¿Que es la entropía?

• La entropía H(X) mide la información o incertidumbre promedio de una variable aleatoria X (o sistema representado por X).

Introducción a la Teoría de la Información y Aplicaciones: Entropía Entropías a considerar en un sistema Igual que cuando se estudio las probabilidades en el caso de tener dos variables aleatorias (Ej: transmisor X y receptor Y) se consideran las siguientes entropías para medir relaciones entre las variables: H(X) : Información o entropia por carácter en el transmisor (en bits) H(Y) : Información o entropia por carácter en el receptor (en bits) H(X,Y) : Información o entropia por par de caracteres transmitidos y recibidos (en bits) H(Y| X) : Información o entropia condicional sobre el receptor Y sabiendo que X = i fue transmitido (en bits) H(X| Y) : Información o entropia condicional sobre el transmisor sabiendo que Y = j fue recibido, también conocido como equivocación (en bits)

Introducción a la Teoría de la Información y Aplicaciones: Entropía Ejemplo: Entropías a considerar en un sistema p(X=1)=0.25, p(X=2)=0.4, p(X=3)=0.15, p(X=4)=0.15, p(X=5)=0.05 Y= p(Y=1)=0.35, p(Y=2)=0.35, p(Y=3)=0.20, p(Y=4)=0.1 1

p( x1| y1) = p(x1, y1) / Σi(pi1) =0.25/0.35 = .714 p( y1| x1) = 0.25/0.25 = 1 p( y2| x3) = 0.05/0.15 = .333

1 2 X= 3 4 5

[

2

3

0.25 0 0 0.1 0.3 0 0 0.05 0.1 0 0 0.05 0 0 0.05 0.35

0.35 0.20

4

0 0 0 0.1 0

]

0.1

H  X =−∑ ∑ p  x , y log p X =i=−∑ p X =i log p  X =i i

j

i

H(X) = -0.25 log 0.25 – 0.1 log 0.4 – 0.3 log 0.4 – 0.05 log 0.15 - 0.1log 0.15 – 0.05 log 0.15 – 0.1 log 0.15 – 0.05 log 0.05 = 2.066 bits Equivalentemente: H(X) = -0.25 log 0.25 – 0.4 log 0.4 – 0.15 log 0.15 – 0.15 log 0.15 – 0.05 log 0.05 = 2.066 bits

0.25 0.4 0.15 0.15 0.05

Introducción a la Teoría de la Información y Aplicaciones: Entropía Ejemplo: Entropías a considerar en un sistema

H Y =−∑ ∑ p x , y log p Y = j=−∑ pY = j log pY = j i

j

j

H(Y) = -0.25 log 0.35 – 0.1 log 0.35 – 0.3 log 0.35 – 0.05 log 0.35 – 0.1log 0.2 – 0.05 log 0.2 1 – 0.05 log 0.20 – 0.1 log 0.1 = 1.856 bits 2 X= 3 Equivalentemente: 4 H(Y) = -0.35 log 0.35 – 0.35 log 0.35 – 0.2 log 0.2 5 – 0.1 log 0.1 = 1.856 bits

H  X , Y =−∑ ∑ p x , y log p  x , y i

j

H(X, Y) = -0.25 log 0.25 – 0.1 log 0.1 – 0.3 log 0.3 – 0.05 log 0.05 – 0.1log 0.1 – 0.05 log 0.05 – 0.1 log 0.1 – 0.5 log 0.5 = 2.665 bits

Y= 1

[

2

3

0.25 0 0 0.1 0.3 0 0 0.05 0.1 0 0 0.05 0 0 0.05 0.35

0.35 0.20

4

0 0 0 0.1 0 0.1

]

0.25 0.4 0.15 0.15 0.05

Introducción a la Teoría de la Información y Aplicaciones: Entropía Ejemplo: Entropías a considerar en un sistema (cont)

H  X∣Y =−∑ ∑ p  X =i ,Y = jlog p x∣y=∑ p Y = j H  X∣Y = j  i

j

j

H(X | Y) = -p(x1,y1) log p(x1|y1) - p(x2,y1) log p(x2|y1) - p(x2,y2) log p(x2|y2) - p(x3,y2) log p(x3|y2) - p(x4,y3) log p(x4|y3) - p(x4,y4) log p(x4|y4) - p(x5,y3) log p(x5|y3) - p(x5,y4) log p(x5|y4) = 0.809 bits Equivalentemente: H(X | Y) = 0.35 H(0.25/0.35, 0.1/0.35) + 0.35 H(0.3/0.35, 0.05/0.35) + 0.2 H(0.1/0.2, 0.05/0.2, 0.05/0.2) + 0.1 H(0.1/0.1) = 0.809 bits

Y= 1

1 2 X= 3 4 5

[

2

3

0.25 0 0 0.1 0.3 0 0 0.05 0.1 0 0 0.05 0 0 0.05 0.35

0.35 0.20

4

0 0 0 0.1 0 0.1

]

0.25 0.4 0.15 0.15 0.05

Introducción a la Teoría de la Información y Aplicaciones: Entropía Ejemplo: Entropías a considerar en un sistema (cont)

H Y∣X =−∑ ∑ p  X =i ,Y = jlog p y∣x =∑ p  X =i H Y∣X =i i

j

i

H(Y | X) = - p(y1,x1) log p(y1|x1) - p(y1,x2) log p(y1|x2) – p(y2,x2) log p(y2|x2) - p(y2,x3) log p(y2|x3) - p(y3,x3) log p(y3|x3) - f(y3,x4) log p(y3|x4) - f(y3,x4) log p(y3|x4) - p(y3,x5) log p(y3|x5) = 0.6 bits Equivalentemente: H(Y | X) = 0.25 H(0.25/0.25) + 0.4 H(0.1/0.4,0.3/0.4) + 0.15 H(0.05/0.15, 0.1/0.15) 1 + 0.15 H(0.05/0.15, 0.1/0.15) 2 + 0.05 H(0.05/0.05) X= 3 = 0.6 bits

4 5

Y= 1

[

2

3

0.25 0 0 0.1 0.3 0 0 0.05 0.1 0 0 0.05 0 0 0.05 0.35

0.35 0.20

4

0 0 0 0.1 0 0.1

]

0.25 0.4 0.15 0.15 0.05

Introducción a la Teoría de la Información y Aplicaciones: Entropía Ejemplo: Entropías a considerar en un sistema (cont) Hay que notar que H(x,y) < H(X) + H(Y) 2.665 < 2.066 + 1.856 y que: H(X,Y) = H(Y) + H(X|Y) = H(X) + H(Y|X) 2.665 = 1.856 + 0.809 = 2.066 + 0.600

H(X, Y)

H(X)

H(Y | X)

H(X, Y)

H(X | Y)

H(Y)

Introducción a la Teoría de la Información y Aplicaciones: Entropía Información Mutua La información mutua I(X;Y) es una medida de la información proveida por los pares de símbolos (x,y), la relación entre I(X;Y) y la entropia es: H(X,Y) = H(X) + H(Y | X) = H(Y) + H(X | Y) H(X,Y) = H(X) + H(Y) - I(X;Y) I(X;Y) = H(X) – H(X | Y) I(X;Y) = H(Y) – H(Y | X) I(X;Y) mide la dependencia entre el input X y el output Y, o la información transmitida por el canal, es positiva y simétrica en X y Y. H(X, Y)

H(X)

H(Y) H(X | Y) I(X;Y)

H(Y | X)

Introducción a la Teoría de la Información y Aplicaciones: Entropía Información Mutua La capacidad de un canal definida por Shannon es C = max I(X;Y), max I(X;Y) es cuando la incertidumbre de lo que se transmitió (X) dado Y es zero o cuando la incertidumbre de recibir Y dado X es zero: Si I(X;Y) = H(X) – H(X | Y), cuando H(X | Y) = 0 → max I(X;Y) = C Si I(X;Y) = H(Y) – H(Y | X), cuando H(Y | X) = 0 → max I(X;Y) = C H(Y | X) maxima

H(Y | X) “grande”

H(X, Y)

H(X, Y)

H(X)

H(Y | X) “chica” H(X, Y)

H(Y | X) = H(Y) I(X;Y)=0

I(X;Y)

I(X;Y)

H(Y | X) = 0 H(X, Y)

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

Introducción a la Teoría de la Información y Aplicaciones: Entropía Información Mutua (cont)

Y= 1

Para un canal libre de ruido (canal perfecto):

p( x1| y1) = 0.25/0.25 = 1 , p( x2| y2) = 0.25/0.25 = 1

1 2 X= 3 4

[

2

3

0.25 0 0 0 0.25 0 0 0 0.25 0 0 0

0.25

4

0 0 0 0.25

0.25 0.25

p( x3| y3) = 0.25/0.25 = 1 , p( x4| y4) = 0.25/0.25 = 1 p( y1| x1) = 0.25/0.25 = 1 , p( y2| x2) = 0.25/0.25 = 1 p( y3| x3) = 0.25/0.25 = 1 , p( y4| x4) = 0.25/0.25 = 1 todos los otros f(x | y) y f(y | x) son zero

H  X , Y =−∑ ∑ p x , y log p  x , y x

y

H(X, Y) = –0.25 log 0.25 –0.25 log 0.25 –0.25 log 0.25 –0.25 log 0.25 = 2 bits

]

0.25

0.25 0.25 0.25 0.25

Introducción a la Teoría de la Información y Aplicaciones: Entropía Información Mutua (cont)

Y= 1

H(X) = –0.25 log 0.25 –0.25 log 0.25 –0.25 log 0.25 –0.25 log 0.25 = 2 bits H(Y) = –0.25 log 0.25 –0.25 log 0.25 –0.25 log 0.25 –0.25 log 0.25 = 2 bits

1 2 X= 3 4

[

2

3

0.25 0 0 0 0.25 0 0 0 0.25 0 0 0

0.25

0.25 0.25

4

0 0 0 0.25

]

0.25

H(Y | X) = - 0.25log1 – 0.25log1 -0.25log1 -0.25log1 = 0 similarmente H(X | Y) = 0

Para este canal libre de ruido : I(X;Y) = H(X) = H(Y) = H(X,Y) = 2 bits

0.25 0.25 0.25 0.25

Introducción a la Teoría de la Información y Aplicaciones: Entropía Y= 1

Información Mutua (cont) Para un canal con inputs y output independientes: H(Y | X) = H(Y) (maxima)

2

[

1 0.25 X= 2 0.25 0.5

H(X, Y)

0.25 0.25

]

0.5 0.5

0.5

H(X) = H(X|Y) = 1, H(Y) = H(Y|X) = 1, H(X,Y) = 2 I(X;Y)= H(X) – H(X|Y) = 1 – 1 = 0 bits = H(Y) – H(Y|X) = 1 – 1 = 0 bits H(X) = H (X | Y) H(Y | X) = H(Y) I(X;Y)=0

Para un canal libre de ruido (canal perfecto): H(Y | X) = 0 H(X, Y)

1

Y=

2

[

1 0.50 0 X= 0 0.50 2

H(X) = 1, H(Y) = 1, H(X,Y) = 1, H(X|Y) = 0, H(X|Y) = 0

I(X;Y)= H(X) – H(X|Y) = 1 – 0 = 1 bit H(X) = H(Y) = H(X, Y)=I(X;Y) = H(Y) – H(Y|X) = 1 – 0 = 1 bit

0.5

0.5

]

0.5 0.5

Introducción a la Teoría de la Información y Aplicaciones: Entropía Relativa ¿Que es la entropía relativa ? • La entropía relativa es una medida de la distancia o divergencia entre dos funciones de probabilidad p(x) y q(x). También es conocida como distancia Kullback Leibler (KL1 y KL2). • La medida Jensen/Jeffreys (simétrica) es la suma de KL1 y KL2 : J = KL1 + KL2. • Hay muchas otras medidas de divergencia aparte de KL1, KL2 y J.

∑ p log(p / q ) D(p | q) = ∑ q log(q / p )

KL1 = D(p | q) =

i

i

i

i

KL2 =

i

i

i

i

Introducción a la Teoría de la Información y Aplicaciones: Entropía Relativa Ejemplos de H(x), KL1, KL2 y J: Hay dos dados (los dos están arreglados!) y por consecuencia dos variables aleatoria X e Y con los siguientes valores y probabilidades. Posibles eventos : X = [1, 2, 3, 4, 5, 6], Y = [1, 2, 3, 4, 5, 6] Ejemplo 1: Funciones de probabilidades discreta: f(x) = {px1, px2, px3, px4, px5, px6} = {1/3,1/3,1/12,1/12,1/12,1/12}, f(y) = {py1, py2, py3, py4, py5, py6} = {1/12,1/12,1/6,1/6,1/6,1/3}

f(x)

4/12

4/12

3/12

3/12

f(y)

2/12

2/12

1/12

1/12

0

0

1

2

3

X

4

5

6

1

2

3

Y

4

5

6

Introducción a la Teoría de la Información y Aplicaciones: Entropía Relativa Ejemplo de H(x), KL1, KL2 y JS (cont): H(X) = -(1/3log21/3+1/3log21/3+...+1/12log21/12) = 2.2516 H(Y) = -(1/12log21/12+1/6log21/6+...+1/3log21/3) = 2.5157 KL1 = D(X | Y) = 0.833 KL2 = D(X | Y) = 1.333 J = KL1 + KL2 = 2.16666 Ejemplo 2: f(x) = {1/12,1/12,1/6,1/6,1/6,1/3} f(y) = {1/3,1/3,1/12,1/12,1/12,1/12} , KL1 = D(X | Y) = 1.333 KL2 = D(X | Y) = 0.833 J = KL1 + KL2 = 2.16666 KL1 y KL2 no son simétricas pero J si lo es.


Introducción a la Teoría de la Información y Aplicaciones: Aplicaciones Comunicaciones • La T.I. es muy importante en el continuo desarrollo de las comunicaciones. • Un canal de comunicaciones es un sistema en el cual el output (M’) depende probabilisticamente del input (M). • La entropía H(x) mide la incertidumbre de una variable aleatoria (X). • Para medir la incertidumbre de un canal de comunicaciones se usa una medida llamada la información mutual I(X;Y) = H (X) – H(X|Y).

Introducción a la a la Teoría de la Información y Aplicaciones: Introducción Sistema de Comunicación

Origen

Codificador

Mensaje M

Canal

Decodificador

Destino

Mensaje M’

Introducción a la Teoría de la Información y Aplicaciones: Aplicaciones Comunicaciones • I(X;Y) mide la dependencia entre el input X y el output Y es positiva y simétrica en X y Y. • La capacidad de un canal es C=max I(X;Y); max I(X;Y) es cuando la incertidumbre de lo que se transmitió (X) dado Y es zero : H(X|Y) = 0 → C=max I(X;Y).

Introducción a la Teoría de la Información y Aplicaciones: Aplicaciones Comunicaciones • Claude Shannon demostró que la información puede ser transmitida con fiabilidad hasta el ritmo permitido por la capacidad del canal C. Esta fiabilidad era independiente del ritmo de la transmisión siempre que fuera menor que C. • El teorema de codificación de canales de Shannon prometió la existencia de códigos que permitirían la transmisión de información a velocidades mas rapidas. Algunos codigos que usaron estas ideas son los codigos de Hamming y Reed-Solomon.

Introducción a la Teoría de la Información y Aplicaciones: Aplicaciones Criptografía • La teoría de la información también es usada en otras áreas como la encriptación. • Usando M como el mensaje, C como el cypher texto, K como la llave para la encriptación. • La situación corresponde al sistema de comunicaciones pero con agregando seguridad a la informacion transmitida.

Introducción a la a la Teoría de la Información y Aplicaciones: Introducción Sistema de Encriptación K

Origen

Generador de llaves

Encriptor

Canal

Interceptor (e, K, C)

Mensaje M

C=e(M,K)

K

Decriptor

Destino

Mensaje M’

Introducción a la Teoría de la Información y Aplicaciones: Aplicaciones Criptografía • Shannon describió la equivocación de la llave H(K | C) el cual mide la incertidumbre promedio de una llave K cuado un criptograma C ha sido interceptado. • Conceptos de la teoría de la información han sido usado en procesos y algoritmos como PGP, RSA, DES y otros. • Gracias a estos algoritmos existe el internet como se conoce hoy.

Introducción a la Teoría de la Información y Aplicaciones: Aplicaciones Bioinformática • Los conceptos de divergencia (Kullback Leibler) entre distribuciones ha sido usado en la Bioinformática para la detección de patrones en secuencias de ADN. • Estas secuencias son un patrón estocástico que puede ser considerado como un generador ergodico de caracteres. • Los caracteres usados en el ADN son el A, T, C, y G. • Usando métodos basados en la Teoría de la Información es posible mejorar el análisis de codones (tripletes de ADN que generan proteínas), motifs (grupos de caracteres que tienen una significancia biológica) y otros relieves de interés.

Introducción a la Teoría de la Información y Aplicaciones: Aplicaciones Ejemplo: Usando la diferencia en sus estadísticas se han creado medidas para medir la divergencia entre de codones y nocodones. • Usando un indicador (pointer) se calculan las frecuencias de los doce diferentes nucleótidos (A0, T0, C0, G0, A1, T1, C1, G1, A2, T2, C2, G2) a la izquierda y derecha del indicador • Se usan las doce frecuencias a la izquierda como p: (fiA0,...fiG2) y las otras doce como q: (fdA0,...,fdG2) • Se usan diferentes medidas (KL1, KL2, ...) para calcular D(p | q) y detectar codones y no codones. • Hay muchas (mas de treinta) diferentes medidas que pueden ser usadas con estos propósitos.

Introducción a la Teoría de la Información y Aplicaciones: Aplicaciones

Bioinformatica Medida Kullback Leibler 1 (KL1) y KL2

KL1, 2 = I1, 2 = − ∑ P1 log(p1 / p 2 )

KL 2,1 = I 2,1 = − ∑ P2 log(p 2 / p1 ) Medida Jensen Jeffreys (J)

J = KL1, 2 + KL2,1

Introducción a la Teoría de la Información y Aplicaciones: Aplicaciones Bioinformatica Medida Kullback Leibler 1 para detectar codones (1) human ; (2) ecoli; (3) jannaschii; and (4) rprowazekii) I

I

II III

0.06

0.06

(1)

(2)

0.04

KL 1

II III

0.04

KL 1

0.02

0

0.02

0

0.3

0.3

(3)

(4)

0.2

KL 1

0.2

KL 1

0.1

0

0.1

0

30 0

1900

3500 Pointer position

5100

300

1900

3500 Pointer position

5100

Introducción a la Teoría de la Información y Aplicaciones: Conclusión

• En general estas medidas y la Teoría de la Información pueden ser usadas para detectar patrones estadísticos en muchos tipos de secuencias, imagenes u otras formas de información. • La Teoría de la Información nos da una base teórica para la investigación de muchas áreas diferentes aparentemente no relacionadas.

Introducción a la Teoría de la Información y Aplicaciones Referencias: [1] Reza, F., An Introduction to Information Theory, Dover Publications, 1994 [2] Cover, T., Elements of Information Theory, Wiley, 1991 [3] Galvan, P.B. et al, “Finding Borders between Coding and Noncoding DNA Regions by an Entropic Segmentation Method”, Physical Review Letters, 85 (2000) [4] en.wikipedia.org

Introducción a la Teoría de la Información - Inicio

Recommend Documents