Introduccion a La Teoria de La Informacion

7/29/2019 Introduccion a La Teoria de La Informacion

1/76

Introduccin a la Teora de la

Informacin

Toms V. Arredondo

8/4/2011


2/76

Introduccin a la a la Teora de la Informacin y

Aplicaciones

Contenidos:

Introduccin a algunos aspectos de la teora de lainformacin (T.I.): informacin y probabilidades

Entropa

Resea de algunas aplicaciones en diferentes reasincluyendo: Comunicaciones, Encripcin yBioinformtica.


3/76


Aplicaciones: Introduccin

Que es la informacin?

La informacin como es conocida comnmente 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 teora de la informacin?

Serie de las leyes para relacionardeterminado orden de

fenmenos relacionados con la comunicacin de la

informacin entre su origen y su destino a travs de un

canal.


4/76



Sistema de Comunicaciones Bsico

Origen Canal Destino

Mensaje M Mensaje M


5/76



Cul es el rol de las probabilidades en lascomunicaciones?

Las probabilidades nos dan una manera de determinar

cuantitativamente las caractersticas que queremos

estudiar en los sistemas (ej. la distribucin de lainformacin de un origen, la confiabilidad de un canal, la

relacin entre el origen y el destino de la informacin

entre otras)

Las probabilidades estn basadas en las frecuenciasobservables de la ocurrencia de eventos


6/76



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), AB (ninguno de los dos).

A BABAB


7/76



Las frecuencias y las probabilidades (cont)

Permutaciones: Las permutaciones son elreordenamiento de objetos o smbolos en secuenciasdistinguibles:

El numero de permutaciones de n objetos es n!

n(n-1)(n-2)...3210! = 1

La formula para el numero de permutaciones de

r objetos seleccionados de un conjunto de n objetos:

Cada uno de los objetos es distinguible de los otros

Pn , r=n !

nr!


8/76




Ejemplo:Si tengo 6 tarros de pintura de color y una flota de 4 autos

(Ferrari, Jaguar, Corvette, Citroen), el numero de

permutacin posibles para pintar los autos es

6543 o usando la formula:

Si alguien eligiera una permutacin de colores para su flota

al azar la probabilidad de ella seria = 1/360

Pn , r=P6, 4=6 !

64!=360


9/76




En otras situaciones no nos importa la posicin de seleccinde los objetos en cuestin.

En ese caso se quieren determinar el numero de lascombinaciones de elegir r objetos de un set de n objetos:

Estas cantidades se llaman coeficientes binomiales porquefueron estudiados en relacin con la expansion de binomialesen los cuales las maneras de seleccionar el numero de lasvariables es dado por la relacin descrita anteriormente

(a + b)3 = a3 + 3a2b + 3ab2 + b3

(a + b)3 =

Cn , r=nr=

n n1n2...nr1

r ! = n !nr! r !

30a331a

2b32ab

233b

3


10/76




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

combinacin que {Suizo, Gruyere, Cabra})

Si nos importara el orden el resultado seria unapermutacion:

P(12,3) = 121110 = 1320

C12,3=12

3

=12 !

9! 3 !=220


11/76




Probabilidad condicionalMuchas veces es importante saber la probabilidad de un

evento (A) basado en informacin 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 laprobabilidad

La probabilidad de A dado S se escribe: P(A | S}


12/76


Aplicaciones: IntroduccinLas 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 (AB): n4

A o B o ambos ocurren (A + B): n1 + n2 + n3El 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 BAB AB

AB BA


13/76




Cuando N tiende a estas frecuencias tienden a probabilidades:

P{A+B} = P{AB} = P{A} + P{B} - P{AB} P{A} + P{B}

P{AB} = P{AB} = P{A} P{B|A}

P{AB} = P{AB} = 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


14/76




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/26Prob{A + B} = Prob{A} + Prob{B} Prob{AB}

= 1/2 +1/13 1/26 = 7/13


15/76




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.


16/76




Si el evento A y B son independientesP{A|B} = P{A}

P{B|A} = P{B}

P{A+B} = P{AB} = P{A} + P{B}

P{AB} = P{AB} = P{A} P{B}

A BAB

AB BA


17/76




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


18/76




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

f


19/76


Aplicaciones: IntroduccinFuncin Discreta de Probabilidad (PDF) y Funcin

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 funcin

discreta de probabilidadf(x) se define como:

{p1,p

2, p

3,...,p

k} en el cual f(x

k) = Prob{X = x

k} = x

k

La funcin cumulativa de probabilidadse define como:

Fx =xjx

fx j

I t d i l l T d l I f i


20/76



Funcin Discreta de Probabilidad (PDF) y Funcin

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 kX = {1, 2, 3,...,k}

PDF: f = {1/2, 1/4, 1/8, ..., 2-k}

CDF: F(x) = 2-1 + 2-2 + ... + 2-x

x

f(x)

1 2 3 4 50

.125

.25

.375

.5

F(x)

1 2 3 4 50

.125

.5

.625

1

x



21/76



Funciones Discretas de Multiples Variables

En la mayora de los problemas en ingeniera es importante saber la

distribucin 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 distribucin

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:

Se denominanprobabilidades marginales cuando solo se considera solo

una de las dos variables sin consideracin por la otra.

Fx , y = xjx y

ky

fx j , yk



22/76



Funciones Discretas de Multiples Variables (cont)

Distribucin (probabilidad) marginal

La distribucin marginal de una matrix (n x m) de probabilidades se calculan

segn:

P( X = i)

= j(pij) = pi1 + pi2 + ... + pin,

P( Y = j) = i(p

ij) = p

1j+ p

2j+ ... + p

mj

Ejemplo:

P( X = 1)= p11

+p12

+p13

+p14

= 4/16 = 1/4

P( Y = 2)= p12

+p22

+p32

+p42

= 5/16 [2

16

1

16

1

16

0

16

116

216

116

036

0

16

1

16

2

16

1

16

0

16

1

16

1

16

2

16

]X=1

2

3

4

1 2 3 4

Y=

4/16

4/16

4/16

4/16

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



23/76




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?

Probabilidad de cada punto en la muestra:

P{X=i, Y=j} = 1/36

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

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)

[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

]X=1

2

3

4

5

6

1 2 3 4 5 6

Y=

1/6

1/6

1/6

1/6

1/6

1/6

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

I t d i l T d l I f i


24/76

Introduccin a la Teora de la Informacin y

Aplicaciones: n v/s log n

Como se usan las probabilidades en lascomunicaciones?

Si se quieren comparar fuentes y canales de datos, sepueden usarmedidas 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 YSistema decomunicaciones

I t d i l T d l I f i


25/76




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 especficamente:

P{0|0} = P{1|1} = p, P{1|0} = P{0|1} = qX Y

0

1 1

0p

p

q

q

Introd ccin a la Teora de la Informacin


26/76




Ejemplo: Binary Erasure Channel (BEC)

Para el BEC P{0|0} = P{1|1} = p, P{z|0} = P{z|1} = q

X

z

0 0

1 1

p

p

qq

Y



27/76




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 } ?

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)

Ejemplo:

P( X = 1| Y = 2) = p(x1, y

2) /

i(p

i2) = (1/16) / (5/16) = 1/5

P( Y = 3| X = 3) = p(x3, y

3) /

j(p

3j) = (2/16) / (4/16) = 1/2

[2

16

1

16

1

16

0

16

1

16

2

16

1

16

0

360

16

1

16

2

16

1

16

0

16

1

16

1

16

2

16

]X=1

2

3

4

1 2 3 4

Y=

4/16

4/16

4/16

4/16

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



28/76


Aplicaciones

Contenidos: Introduccin a algunos aspectos de la teora de la

informacin (T.I.): informacin y probabilidades

Entropa




29/76


Aplicaciones: log n v/s Entropa

La entropa H(X)H(X) es una medida de la incertidumbre o de la informacin

promedio que nos provee una variable aleatoria (o grupo de

variables aleatorias)

La seleccin de un evento de dos posibles eventos de igual

probabilidad requiere 1 bit de informacin

La seleccin de un evento de cuatro posibles eventos de

igual probabilidad requiere 2 bits de informacin

...etc...



30/76



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 informacin (en bits) proveida por el evento Ek

es:

N

N===

2log)log(p)I(E kk



31/76



La entropia H(X) (cont)

La informacin promedio dada por una variable aleatoria X

que representa un sistema finito de probabilidades entonces

es:

H(X) cumple con varios requisitos:

Continuidad

Simetra

Extrema: cuando todos los eventos son equiprobablesH(X) tiene que ser mximo, cuando uno es el unico

probable H(X) tiene que ser mnimo

Aditiva

)(plogp)I(EH(X)k2

1

kk =

==n

k



32/76



La entropia H(X): porque nlogn como medida?

Si se tiene un sistema con por ejemplo n diferentesopciones de transmisin

Y si se quiere tener una medida basada en esasopciones para poder diferenciar un sistema de otro opara disear sistemas en el cuales el origen, el canal yel destino estuvieran bien dimensionados.

Podra usarse por ejemplo el numero de estados n

como medida de las opciones disponibles?



33/76



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 dosposibles estados (raya y punto).



34/76




probabilistico

Ejemplo (cont):

Asumiendo que todos los estados son equiprobables lasprobabilidades 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 ochoposibles estados (raya-raya-raya, raya-raya-punto,, punto-punto-punto, 23=8) pero las tres claves como componentesdel sistema nos da seis posibles estados (2+2+2=6).



35/76



...8

-..7.-.6

--.5

..-4-.-3

.--2

---1

Clave 3Clave 2Clave 1Estado



36/76




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 nmeros a sumas es usando el logaritmo.



37/76



La entropia H(X): log n, otra posible medida de sistemaprobabilistico

log2n tiene la capacidad requerida de nuestra medida yaque: 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 cadaclave log2(nc1)=log2(nc2)=log2(nc3) = log2(2)

Esta nueva medida si tiene esta cualidad deseada

(propiedad aditiva) mc1 +mc2 +mc3 = ms Tpicamente se usa la base 2 para el logaritmo

especialmente en sistemas binarios. En este caso launidad de informacin de sistemas binarios se llama bitque es una contraccin de binary unit.



38/76



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 nuestramedida (log2(n)).

Esta medida se llama entropa se usa el smbolo H para

designarla.



39/76




No se pueden sumar las contribuciones de los diferentescomponentes de manera igual ya que en sistemas reales

los componentes de los mensajes tienen diferentesfrecuencias y probabilidades.

Incluir esas probabilidades es esencial para que nuestramedida mida las contribuciones de las diferentes opcionesen nuestro mensajes de manera mas realista.



40/76




Ejemplo: Sistema morse

Si {P(raya) = .1 y P(punto) = .9} se puede decir que la

informacin promedio contribuida por una raya es

Prayalog(Praya)

y la informacin promedio contribuida por un punto es

Ppuntolog(Ppunto).



41/76




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 habercerteza no hay incertidumbre (una pista: -P(x

n)logP(x

n)

tiende a cero cuando P(xn

) es cero o uno).

El valor mximo de H(X) es cuando P(xn) = 1/N =

indicando mayor incertidumbre en el mensaje y msinformacin transmitida sobre el sistema (propiedaextrema).



42/76




Si el numero de posibles resultados equiprobables se

incrementa entonces la entropa tambin se incrementa.

Tambin nos interesa que esta funcin H(X) tengasimetra 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 entropa sedefine de la siguiente forma:

=i

ii )log(ppH(X)



43/76



Medidas

-8

-6

-4

-2

0

2

4

6

8

0

0.

07

0.

14

0.

21

0.

28

0.

35

0.

42

0.

49

0.

56

0.

63

0.

7

0.

77

0.

84

0.

91

0.

98

Probabilidad P

Valores log(P)

-log(P)

-Plog(P)



44/76



Medidas

0

0.1

0.2

0.3

0.4

0.5

0.6

00.04

0.08

0.12

0.16 0.

20.24

0.28

0.32

0.36 0.

40.

440.

480.52

0.56 0.

60.64

0.68

0.72

0.76 0.

80.84

0.88

0.92

0.96 1

Probabilidad P1

Valores

-P1log(P1)



45/76

y


Medidas

0

0.1

0.2

0.3

0.4

0.5

0.6

10.96

0.92

0.88

0.84 0.

80.76

0.72

0.68

0.64 0.

60.56

0.52

0.48

0.44 0.

40.36

0.32

0.28

0.24 0.

20.

160.

120.08

0.04 0

Probabilidad P2

Valores

-P2log(P2)



46/76

y


Medidas

0

0.2

0.4

0.6

0.8

1

1.2

0

0.0

4

0.0

8

0.1

2

0.1

60

.2

0.2

4

0.2

8

0.3

2

0.3

60

.4

0.4

4

0.4

8

0.5

2

0.5

60

.6

0.6

4

0.6

8

0.7

2

0.7

60

.8

0.8

4

0.8

8

0.9

2

0.9

6 1

Probabilidad P1

(P2 = 1 - P1)

ValoresH(x

)

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



47/76

y

Aplicaciones: Entropa

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 {simetra}

Si P(raya) =.5 y P(punto)=.5:

H(X) = -(.5log2.5 + .5log2.5) = 1.0 bits {P=(1/N) H(x)Mx}

Si P(raya) =0 y P(punto)=1:

H(x) = -(0log20 + 1log21) = 0 bits {P=(1) H(x)Min=0}



48/76

y


Conclusion:Que es la entropa?

La entropa H(X) mide la informacin o incertidumbrepromedio de una variable aleatoria X (o sistemarepresentado por X).



49/76

y


Entropas 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 entropas para medir relaciones entre las variables:

H(X) : Informacin o entropia por carcter en el transmisor(en bits)H(Y) : Informacin o entropia por carcter en el receptor(en bits)

H(X,Y) : Informacin o entropia por par de caracteres transmitidos y

recibidos (en bits)

H(Y| X) : Informacin o entropia condicional sobre el receptor Y sabiendo

que X = ifue transmitido (en bits)

H(X| Y) : Informacin o entropia condicional sobre el transmisor sabiendo

que Y = jfue recibido, tambin conocido como equivocacin (en bits)



50/76

y


Ejemplo: Entropas 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

p(Y=1)=0.35, p(Y=2)=0.35, p(Y=3)=0.20, p(Y=4)=0.1

p( x1| y

1) = p(x

1, y

1) /

i(p

i1)

=0.25/0.35 = .714

p( y1

| x1

) = 0.25/0.25 = 1

p( y2| x

3) = 0.05/0.15 = .333

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 0 0

0.1 0.3 0 0

0 0.05 0.1 00 0 0.05 0.1

0 0 0.05 0 ]X=

1

2

34

5

1 2 3 4

Y=

0.25

0.4

0.150.15

0.050.35 0.35 0.20 0.1

H Xi j

p x , y log p X ii

p X i log p X i



51/76

y


Ejemplo: Entropas a considerar en un sistema

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

0.05 log 0.20 0.1 log 0.1 = 1.856 bits

Equivalentemente:

H(Y) = -0.35 log 0.35 0.35 log 0.35 0.2 log 0.2

0.1 log 0.1 = 1.856 bits

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

[0.25 0 0 0

0.1 0.3 0 0

0 0.05 0.1 0

0 0 0.05 0.1

0 0 0.05 0 ]X=

1

2

3

4

5

1 2 3 4

Y=

0.25

0.4

0.15

0.15

0.050.35 0.35 0.20 0.1

H X , Yi j

p x , y log p x , y

H Yi j

p x , y log p Y jj

p Y j log p Y j



52/76


Ejemplo: Entropas a considerar en un sistema (cont)

H(X | Y) = -p(x1,y

1) log p(x

1|y

1) - p(x

2,y

1) log p(x

2|y

1) - p(x

2,y

2) log p(x

2|y

2)

- p(x3,y

2) log p(x

3|y

2) - p(x

4,y

3) log p(x

4|y

3) - p(x

4,y

4) log p(x

4|y

4)

- p(x5,y

3) log p(x

5|y

3) - p(x

5,y

4) log p(x

5|y

4)

= 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 [0.25 0 0 0

0.1 0.3 0 00 0.05 0.1 0

0 0 0.05 0.1

0 0 0.05 0 ]X=

1

23

4

5

1 2 3 4

Y=

0.25

0.40.15

0.15

0.050.35 0.35 0.20 0.1

H X Yi j

p X i ,Y j log p xyj

p Y j H X Y j



53/76



H(Y | X) = - p(y1,x

1) log p(y

1|x

1) - p(y

1,x

2) log p(y

1|x

2) p(y

2,x

2) log p(y

2|x

2)

- p(y2,x

3) log p(y

2|x

3) - p(y

3,x

3) log p(y

3|x

3) - f(y

3,x

4) log p(y

3|x

4)

- f(y3,x

4) log p(y

3|x

4) - p(y

3,x

5) log p(y

3|x

5)

= 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)

+ 0.15 H(0.05/0.15, 0.1/0.15)+ 0.05 H(0.05/0.05)

= 0.6 bits [0.25 0 0 0

0.1 0.3 0 0

0 0.05 0.1 0

0 0 0.05 0.1

0 0 0.05 0 ]X=

1

23

4

5

1 2 3 4

Y=

0.25

0.4

0.15

0.15

0.050.35 0.35 0.20 0.1

H Y Xi j

p X i ,Y j log p y xi

p X i H Y X i



54/76



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)



55/76


Informacin Mutua

La informacin mutua I(X;Y) es una medida de la informacin proveidapor los pares de smbolos (x,y), la relacin 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 informacin

transmitida por el canal, es positiva y simtrica en X y Y.

H(X, Y)

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

H(X) H(Y)



56/76


Informacin 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(X, Y)

H(X) H(Y | X) = H(Y)

H(X, Y)

H(Y | X) maxima H(Y | X) grande

H(X, Y) H(X, Y)

H(X) = H(Y) =

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

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

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



57/76


Informacin Mutua (cont)

Para un canal libre de ruido (canal perfecto):

p( x1| y

1) = 0.25/0.25 = 1 , p( x

2| y

2) = 0.25/0.25 = 1

p( x3| y3) = 0.25/0.25 = 1 , p( x4| y4) = 0.25/0.25 = 1

p( y1| x

1) = 0.25/0.25 = 1 , p( y

2| x

2) = 0.25/0.25 = 1

p( y3| x

3) = 0.25/0.25 = 1 , p( y

4| x

4) = 0.25/0.25 = 1

todos los otros f(x | y) y f(y | x) son zero

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 0 00 0.25 0 0

0 0 0.25 0

0 0 0 0.25]X=12

3

4

1 2 3 4

Y=

0.250.25

0.25

0.25

0.25 0.25 0.25 0.25

H X , Yx y

p x , y log p x , y



58/76



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

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 0 0

0 0.25 0 0

0 0 0.25 0

0 0 0 0.25]X=

1

2

3

4

1 2 3 4

Y=

0.25

0.25

0.25

0.25

0.25 0.25 0.25 0.25



59/76



Para un canal con inputs y output independientes:

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

Para un canal libre de ruido (canal perfecto):

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(Y) H(Y|X) = 1 0 = 1 bit

H(X, Y)

H(X) = H (X | Y) H(Y | X) = H(Y)

H(Y | X) = H(Y) (maxima)

I(X;Y)=0

[0.50 00 0.50 ]X=121 2

Y=

0.5

0.5

0.5 0.5

[0.25 0.25

0.25 0.25

]X=

1

2

1 2Y=

0.5

0.50.5 0.5

H(X, Y)

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

H(Y | X) = 0



60/76

Aplicaciones: Entropa Relativa

Que es la entropa relativa ? La entropa relativa es una medida de la distancia o divergenciaentre dos funciones de probabilidad p(x) y q(x). Tambin esconocida como distancia Kullback Leibler (KL1 y KL2).

La medida Jensen/Jeffreys (simtrica) es la suma de KL1 y KL2 :

J = KL1 + KL2.

Hay muchas otras medidas de divergencia aparte de KL1, KL2 y J.

==i

iii )p/log(qqq)|D(pKL2

==i

iii )q/log(ppq)|D(pKL1



61/76


Ejemplos de H(x), KL1, KL2 y J:

Hay dos dados (los dos estn 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}

Y

f(y)

1 2 3 4 5 60

1/12

2/12

4/12

3/12

X

f(x)

1 2 3 4 5 60

1/12

2/12

4/12

3/12


A li i E R l i


62/76


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.333KL2 = D(X | Y) = 0.833

J = KL1 + KL2 = 2.16666

KL1 y KL2 no son simtricas pero J si lo es.



63/76

Aplicaciones

Contenidos: Introduccin a algunos aspectos de la teora de la

informacin (T.I.): informacin y probabilidades

Entropa



A li i A li i


64/76

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 entropa H(x) mide la incertidumbre de una variable

aleatoria (X).

Para medir la incertidumbre de un canal de

comunicaciones se usa una medida llamada lainformacin mutual I(X;Y) = H (X) H(X|Y).

Introduccin a la a la Teora de la Informacin yA li i I t d i


65/76


Sistema de Comunicacin

Codificador CanalDe-

codificador

Mensaje M Mensaje M

DestinoOrigen


A li i A li i


66/76


Comunicaciones I(X;Y) mide la dependencia entre el input X y el output Y

es positiva y simtrica 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).


A li i A li i


67/76


Comunicaciones Claude Shannon demostr que la informacin puede

ser transmitida con fiabilidad hasta el ritmo permitido por

la capacidad del canal C. Esta fiabilidad era

independiente del ritmo de la transmisin siempre quefuera menor que C.

El teorema de codificacin de canales de Shannon

prometi la existencia de cdigos que permitiran la

transmisin de informacin a velocidades mas rapidas.

Algunos codigos que usaron estas ideas son los codigos

de Hamming y Reed-Solomon.


A li i A li i


68/76


Criptografa La teora de la informacin tambin es usada en otras

reas como la encriptacin.

Usando M como el mensaje, C como el cypher texto, K

como la llave para la encriptacin. La situacin corresponde al sistema de comunicaciones

pero con agregando seguridad a la informacion

transmitida.

Introduccin a la a la Teora de la Informacin yA li i I t d i


69/76


Sistema de Encriptacin

Encriptor CanalDecriptor

Mensaje M Mensaje M

DestinoOrigen

Generador

de llaves

K K

Interceptor

(e, K, C)

C=e(M,K)




70/76


Criptografa Shannon describi la equivocacin 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 teora de la informacin han sido usadoen procesos y algoritmos como PGP, RSA, DES y otros.

Gracias a estos algoritmos existe el internet como se

conoce hoy.




71/76


Bioinformtica Los conceptos de divergencia (Kullback Leibler) entre

distribuciones ha sido usado en la Bioinformtica para ladeteccin de patrones en secuencias de ADN.

Estas secuencias son un patrn estocstico que puedeser considerado como un generador ergodico decaracteres.

Los caracteres usados en el ADN son elA, T, C, y G.

Usando mtodos basados en la Teora de la Informacin

es posible mejorar el anlisis de codones (tripletes deADN que generan protenas), motifs (grupos decaracteres que tienen una significancia biolgica) y otrosrelieves de inters.




72/76


Ejemplo: Usando la diferencia en sus estadsticas se hancreado medidas para medir la divergencia entre de

codones y nocodones.

Usando un indicador (pointer) se calculan lasfrecuencias de los doce diferentes nucletidos (A0, T0,C0, G0, A1, T1, C1, G1, A2, T2, C2, G2) a la izquierda yderecha 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 calcularD(p | q) y detectar codones y no codones.

Hay muchas (mas de treinta) diferentes medidas quepueden ser usadas con estos propsitos.




73/76


Bioinformatica

Medida Kullback Leibler 1 (KL1) y KL2

)p/plog(PIKL 2112,12,1 ==

)p/plog(PIKL 1221,21,2 ==

1,22,1 KLKLJ +=

Medida Jensen Jeffreys (J)




74/76


Bioinformatica

(1)

0

0.02

0.04

0.06

KL1

I II

III

(2)

0

0.02

0.04

0.06

KL1

Pointer

position

300

1900 3500 5100

KL

1

0

0.1

0.2

0.3

(3)

Pointer

position

300 1900 3500 5100

KL

1

0

0.1

0.2

0.3

(4)

I II

III

Medida Kullback Leibler 1 para detectar codones

(1) human ; (2) ecoli; (3) jannaschii; and (4) rprowazekii)


Aplicaciones: Conclusin


75/76

Aplicaciones: Conclusin

En general estas medidas y la Teora de la Informacin

pueden ser usadas para detectar patrones estadsticos

en muchos tipos de secuencias, imagenes u otras

formas de informacin. La Teora de la Informacin nos da una base terica

para la investigacin de muchas reas diferentes

aparentemente no relacionadas.


Aplicaciones


76/76

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

Documents

Introduccion a La Teoria de La Informacion