introduccion a la teoria de la informacion 2015

Introduccin a la Teora de la Informacin

2015 - EPIE - 1

Introduccin a la a la Teora de la Informacin y Aplicaciones

Contenidos: Introduccin a algunos aspectos de la teora de la

informacin (T.I.): informacin y probabilidades Entropa Resea de algunas aplicaciones en diferentes reas

incluyendo: Comunicaciones, Encripcin y Bioinformtica.

2015 - EPIE - 2

Introduccin a la a la Teora de la Informacin y 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 relacionar determinado orden de

fenmenos relacionados con la comunicacin de la informacin entre su origen y su destino a travs de un canal.

2015 - EPIE - 3


Sistema de Comunicaciones Bsico

Origen Canal Destino

Mensaje M Mensaje M

2015 - EPIE - 4


Cul es el rol de las probabilidades en las comunicaciones?

Las probabilidades nos dan una manera de determinar cuantitativamente las caractersticas que queremos estudiar en los sistemas (ej. la distribucin de la informacin 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 frecuencias observables de la ocurrencia de eventos

2015 - EPIE - 5


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

2015 - EPIE - 6


Las frecuencias y las probabilidades (cont) Permutaciones: Las permutaciones son el

reordenamiento de objetos o smbolos en secuencias distinguibles:

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

P n , r = n!nr !

2015 - EPIE - 7


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

P n , r =P 6, 4= 6 !64!

=360

2015 - EPIE - 8


Las frecuencias y las probabilidades (cont) En otras situaciones no nos importa la posicin de seleccin

de los objetos en cuestin. En ese caso se quieren determinar el numero de las

combinaciones de elegir r objetos de un set de n objetos:

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

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

(a + b)3 =

C n , r =nr=n n1n2...nr1r ! = n !nr ! r !

30a331a2b32ab233b32015 - EPIE - 9


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 combinacin que {Suizo, Gruyere, Cabra})

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

C 12,3=123 = 12 !9! 3 !=220

2015 - EPIE - 10


Las frecuencias y las probabilidades (cont) Probabilidad condicional Muchas 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 la probabilidad

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

2015 - EPIE - 11


Las frecuencias y las probabilidades (cont) Si se observan el siguiente numero de eventos:

A ocurre, B no ocurre (AB): n1B ocurre, A no ocurre (BA): n2A y B ocurren (AB): n3Ni A ni B ocurren (AB): n4A 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

2015 - EPIE - 12


Las frecuencias y las probabilidades (cont) 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}= 1P{AA} = 0

2015 - EPIE - 13



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

2015 - EPIE - 14



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.

2015 - EPIE - 15


Las frecuencias y las probabilidades (cont) Si el evento A y B son independientes

P{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

2015 - EPIE - 16


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 seisAB = dado rojo sale uno y dado blanco sale seisA + 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/36Prob(A + B) = 1/6 + 1/6 = 1/3

2015 - EPIE - 17


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 2AB = el dado sale 1 y el dado sale 2A+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

2015 - EPIE - 18


Funcin 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 deenteros 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 {x

1, x

2, x

3,...,x

k} la funcin

discreta de probabilidad f(x) se define como: {p

1,p

2, p

3,...,p

k} en el cual f(x

k) = Prob{X = x

k} = x

k

La funcin cumulativa de probabilidad se define como:F x =

x jxf x j 2015 - EPIE - 19


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

x2015 - EPIE - 20


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 denominan probabilidades marginales cuando solo se considera solo una de las dos variables sin consideracin por la otra.

F x , y = x jx yk y

f x j , yk

2015 - EPIE - 21


Funciones Discretas de Multiples Variables (cont)

Distribucin (probabilidad) marginalLa distribucin marginal de una matrix (n x m) de probabilidades se calculansegn:

P( X = i) = j(pij) = pi1 + pi2 + ... + pin, P( Y = j) = i(pij) = p1j + p2j + ... + pmj

Ejemplo:

P( X = 1) = p11

+p12

+p13

+p14

= 4/16 = 1/4

P( Y = 2) = p12

+p22

+p32

+p42

= 5/16 [216

116

116

016

116

216

116

036

016

116

216

116

016

116

116

216]X= 123

4

1 2 3 4 Y=

4/16

4/16

4/16

4/16

3/16 5/16 5/16 3/16 2015 - EPIE - 22



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/2P{ 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)

[136

136

136

136

136

136

136

136

136

136

136

136

136

136

136

136

136

136

136

136

136

136

136

136

136

136

136

136

136

136

136

136

136

136

136

136

]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 2015 - EPIE - 23

Introduccin a la Teora de la Informacin y Aplicaciones: n v/s log n

Como se usan las probabilidades en las comunicaciones?

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 YSistema de

comunicaciones

2015 - EPIE - 24



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

qq

2015 - EPIE - 25



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

pqq

Y

2015 - EPIE - 26



Probabilidades Condicionales

Considere una matrix de probabilidades para dos variables aleatorias X, Yrepresentando 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(x

1 , 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

[216

116

116

016

116

216

116

036

016

116

216

116

016

116

116

216]X= 123

4

1 2 3 4 Y=

4/16

4/16

4/16

4/16

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

2015 - EPIE - 27

Introduccin a la a la Teora de la Informacin y Aplicaciones

Contenidos: Introduccin a algunos aspectos de la teora de la

informacin (T.I.): informacin y probabilidades Entropa Resea de algunas aplicaciones en diferentes reas

incluyendo: Comunicaciones, Encripcin y Bioinformtica.

2015 - EPIE - 28

Introduccin a la Teora de la Informacin y 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 devariables 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...

2015 - EPIE - 29


La entropia H(X) (cont)

Si tenemos un espacio de muestreo dividido en 2N eventos que son igualmente probables E

k (k = 1, 2, ..., 2N) entonces

la informacin (en bits) proveida por el evento Ek

es:

NN === 2log)log(p )I(E kk

2015 - EPIE - 30


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 equiprobables

H(X) tiene que ser mximo, cuando uno es el unico probable H(X) tiene que ser mnimo

Aditiva

)(plog p )I(E H(X) k21

kk =

==

n

k

2015 - EPIE - 31


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

Si se tiene un sistema con por ejemplo n diferentes opciones de transmisin

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

Podra usarse por ejemplo el numero de estados ncomo medida de las opciones disponibles?

2015 - EPIE - 32


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

2015 - EPIE - 33



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,, punto-punto-punto, 23=8) pero las tres claves como componentes del sistema nos da seis posibles estados (2+2+2=6).

2015 - EPIE - 34


...8-..7.-.6--.5..-4-.-3.--2---1Clave 3Clave 2Clave 1Estado

2015 - EPIE - 35



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.

2015 - EPIE - 36


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 Tpicamente se usa la base 2 para el logaritmo

especialmente en sistemas binarios. En este caso la unidad de informacin de sistemas binarios se llama bit que es una contraccin de binary unit.

2015 - EPIE - 37


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 entropa se usa el smbolo H para designarla.

2015 - EPIE - 38



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.

2015 - EPIE - 39



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

2015 - EPIE - 40



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(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 ms informacin transmitida sobre el sistema (propiedad extrema).

2015 - EPIE - 41



Si el numero de posibles resultados equiprobables se incrementa entonces la entropa tambin se incrementa.

Tambin nos interesa que esta funcin H(X) tenga simetra 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 se

define de la siguiente forma:

=i

ii )log(pp H(X)2015 - EPIE - 42

Introduccin a la Teora de la InformacinIntroduccin a la a la Teora de la Informacin y Aplicaciones Introduccin a la a la Teora de la Informacin y Aplicaciones: Introduccin Introduccin a la a la Teora de la Informacin y Aplicaciones: Introduccin Sistema de Comunicaciones BsicoIntroduccin a la a la Teora de la Informacin y Aplicaciones: Introduccin Pgina 6Pgina 7Pgina 8Pgina 9Pgina 10Pgina 11Pgina 12Pgina 13Pgina 14Pgina 15Pgina 16Pgina 17Pgina 18Pgina 19Pgina 20Pgina 21Pgina 22Pgina 23Introduccin a la Teora de la Informacin y Aplicaciones: n v/s log n Pgina 25Pgina 26Pgina 27Pgina 28Pgina 29Pgina 30Pgina 31Pgina 32Pgina 33Pgina 34Pgina 35Pgina 36Pgina 37Introduccin a la Teora de la Informacin y Aplicaciones: log n v/s Entropa Pgina 39Pgina 40Pgina 41Pgina 42

introduccion a la teoria de la informacion 2015

Documents