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
7/29/2019 Introduccion a La Teoria de La Informacion
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.
7/29/2019 Introduccion a La Teoria de La Informacion
3/76
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 relacionardeterminado orden de
fenmenos relacionados con la comunicacin de la
informacin entre su origen y su destino a travs de un
canal.
7/29/2019 Introduccion a La Teoria de La Informacion
4/76
Introduccin a la a la Teora de la Informacin y
Aplicaciones: Introduccin
Sistema de Comunicaciones Bsico
Origen Canal Destino
Mensaje M Mensaje M
7/29/2019 Introduccion a La Teoria de La Informacion
5/76
Introduccin a la a la Teora de la Informacin y
Aplicaciones: Introduccin
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
7/29/2019 Introduccion a La Teoria de La Informacion
6/76
Introduccin a la a la Teora de la Informacin y
Aplicaciones: Introduccin
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/29/2019 Introduccion a La Teoria de La Informacion
7/76
Introduccin a la a la Teora de la Informacin y
Aplicaciones: Introduccin
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!
7/29/2019 Introduccion a La Teoria de La Informacion
8/76
Introduccin a la a la Teora de la Informacin y
Aplicaciones: Introduccin
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
Pn , r=P6, 4=6 !
64!=360
7/29/2019 Introduccion a La Teoria de La Informacion
9/76
Introduccin a la a la Teora de la Informacin y
Aplicaciones: Introduccin
Las frecuencias y las probabilidades (cont)
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
7/29/2019 Introduccion a La Teoria de La Informacion
10/76
Introduccin a la a la Teora de la Informacin y
Aplicaciones: Introduccin
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 unapermutacion:
P(12,3) = 121110 = 1320
C12,3=12
3
=12 !
9! 3 !=220
7/29/2019 Introduccion a La Teoria de La Informacion
11/76
Introduccin a la a la Teora de la Informacin y
Aplicaciones: Introduccin
Las frecuencias y las probabilidades (cont)
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}
7/29/2019 Introduccion a La Teoria de La Informacion
12/76
Introduccin a la a la Teora de la Informacin y
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
7/29/2019 Introduccion a La Teoria de La Informacion
13/76
Introduccin a la a la Teora de la Informacin y
Aplicaciones: Introduccin
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}= 1
P{AA} = 0
7/29/2019 Introduccion a La Teoria de La Informacion
14/76
Introduccin a la a la Teora de la Informacin y
Aplicaciones: Introduccin
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/26Prob{A + B} = Prob{A} + Prob{B} Prob{AB}
= 1/2 +1/13 1/26 = 7/13
7/29/2019 Introduccion a La Teoria de La Informacion
15/76
Introduccin a la a la Teora de la Informacin y
Aplicaciones: Introduccin
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.
7/29/2019 Introduccion a La Teoria de La Informacion
16/76
Introduccin a la a la Teora de la Informacin y
Aplicaciones: Introduccin
Las frecuencias y las probabilidades (cont)
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
7/29/2019 Introduccion a La Teoria de La Informacion
17/76
Introduccin a la a la Teora de la Informacin y
Aplicaciones: Introduccin
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
7/29/2019 Introduccion a La Teoria de La Informacion
18/76
Introduccin a la a la Teora de la Informacin y
Aplicaciones: Introduccin
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
f
7/29/2019 Introduccion a La Teoria de La Informacion
19/76
Introduccin a la a la Teora de la Informacin y
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
7/29/2019 Introduccion a La Teoria de La Informacion
20/76
Introduccin a la a la Teora de la Informacin y
Aplicaciones: Introduccin
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
I t d i l l T d l I f i
7/29/2019 Introduccion a La Teoria de La Informacion
21/76
Introduccin a la a la Teora de la Informacin y
Aplicaciones: Introduccin
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
I t d i l l T d l I f i
7/29/2019 Introduccion a La Teoria de La Informacion
22/76
Introduccin a la a la Teora de la Informacin y
Aplicaciones: Introduccin
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
I t d i l l T d l I f i
7/29/2019 Introduccion a La Teoria de La Informacion
23/76
Introduccin a la a la Teora de la Informacin y
Aplicaciones: Introduccin
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?
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
7/29/2019 Introduccion a La Teoria de La Informacion
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
7/29/2019 Introduccion a La Teoria de La Informacion
25/76
Introduccin a la Teora de la Informacin y
Aplicaciones: n v/s log n
Como se usan las probabilidades en lascomunicaciones?
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
7/29/2019 Introduccion a La Teoria de La Informacion
26/76
Introduccin a la Teora de la Informacin y
Aplicaciones: n v/s log n
Como se usan las probabilidades en lascomunicaciones?
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
Y
Introduccin a la a la Teora de la Informacin y
7/29/2019 Introduccion a La Teoria de La Informacion
27/76
Introduccin a la a la Teora de la Informacin y
Aplicaciones: Introduccin
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 } ?
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
I t d i l l T d l I f i
7/29/2019 Introduccion a La Teoria de La Informacion
28/76
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 reasincluyendo: Comunicaciones, Encripcin yBioinformtica.
Introduccin a la Teora de la Informacin y
7/29/2019 Introduccion a La Teoria de La Informacion
29/76
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 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...
Introduccin a la Teora de la Informacin y
7/29/2019 Introduccion a La Teoria de La Informacion
30/76
Introduccin a la Teora de la Informacin y
Aplicaciones: log n v/s Entropa
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
Introduccin a la Teora de la Informacin y
7/29/2019 Introduccion a La Teoria de La Informacion
31/76
Introduccin a la Teora de la Informacin y
Aplicaciones: log n v/s Entropa
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
Introduccin a la Teora de la Informacin y
7/29/2019 Introduccion a La Teoria de La Informacion
32/76
Introduccin a la Teora de la Informacin y
Aplicaciones: n v/s log n
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?
Introduccin a la Teora de la Informacin y
7/29/2019 Introduccion a La Teoria de La Informacion
33/76
Introduccin a la Teora de la Informacin 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 dosposibles estados (raya y punto).
Introduccin a la Teora de la Informacin y
7/29/2019 Introduccion a La Teoria de La Informacion
34/76
Introduccin a la Teora de la Informacin 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 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).
Introduccin a la Teora de la Informacin y
7/29/2019 Introduccion a La Teoria de La Informacion
35/76
Introduccin a la Teora de la Informacin y
Aplicaciones: n v/s log n
...8
-..7.-.6
--.5
..-4-.-3
.--2
---1
Clave 3Clave 2Clave 1Estado
Introduccin a la Teora de la Informacin y
7/29/2019 Introduccion a La Teoria de La Informacion
36/76
Introduccin a la Teora de la Informacin 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 nmeros a sumas es usando el logaritmo.
Introduccin a la Teora de la Informacin y
7/29/2019 Introduccion a La Teoria de La Informacion
37/76
Introduccin a la Teora de la Informacin y
Aplicaciones: n v/s log n
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.
Introduccin a la Teora de la Informacin y
7/29/2019 Introduccion a La Teoria de La Informacion
38/76
Introduccin a la Teora de la Informacin y
Aplicaciones: log n v/s Entropa
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.
Introduccin a la Teora de la Informacin y
7/29/2019 Introduccion a La Teoria de La Informacion
39/76
Introduccin a la Teora de la Informacin y
Aplicaciones: log n v/s Entropa
La entropia H(X): Sistemas con probabilidades distintas
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.
Introduccin a la Teora de la Informacin y
7/29/2019 Introduccion a La Teoria de La Informacion
40/76
Introduccin a la Teora de la Informacin y
Aplicaciones: log n v/s Entropa
La entropia H(X): Sistemas con probabilidades distintas
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).
Introduccin a la Teora de la Informacin y
7/29/2019 Introduccion a La Teoria de La Informacion
41/76
Introduccin a la Teora de la Informacin y
Aplicaciones: log n v/s Entropa
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 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).
Introduccin a la Teora de la Informacin y
7/29/2019 Introduccion a La Teoria de La Informacion
42/76
Introduccin a la Teora de la Informacin y
Aplicaciones: log n v/s Entropa
La entropia H(X): Sistemas con probabilidades distintas
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)
Introduccin a la Teora de la Informacin y
7/29/2019 Introduccion a La Teoria de La Informacion
43/76
Introduccin a la Teora de la Informacin y
Aplicaciones: log n v/s Entropa
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)
Introduccin a la Teora de la Informacin y
7/29/2019 Introduccion a La Teoria de La Informacion
44/76
Introduccin a la Teora de la Informacin y
Aplicaciones: log n v/s Entropa
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)
Introduccin a la Teora de la Informacin y
7/29/2019 Introduccion a La Teoria de La Informacion
45/76
y
Aplicaciones: log n v/s Entropa
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)
Introduccin a la Teora de la Informacin y
7/29/2019 Introduccion a La Teoria de La Informacion
46/76
y
Aplicaciones: log n v/s Entropa
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)
Introduccin a la Teora de la Informacin y
7/29/2019 Introduccion a La Teoria de La Informacion
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}
Introduccin a la Teora de la Informacin y
7/29/2019 Introduccion a La Teoria de La Informacion
48/76
y
Aplicaciones: Entropa
Conclusion:Que es la entropa?
La entropa H(X) mide la informacin o incertidumbrepromedio de una variable aleatoria X (o sistemarepresentado por X).
Introduccin a la Teora de la Informacin y
7/29/2019 Introduccion a La Teoria de La Informacion
49/76
y
Aplicaciones: Entropa
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)
Introduccin a la Teora de la Informacin y
7/29/2019 Introduccion a La Teoria de La Informacion
50/76
y
Aplicaciones: Entropa
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
Introduccin a la Teora de la Informacin y
7/29/2019 Introduccion a La Teoria de La Informacion
51/76
y
Aplicaciones: Entropa
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
Introduccin a la Teora de la Informacin y
7/29/2019 Introduccion a La Teoria de La Informacion
52/76
Aplicaciones: Entropa
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
Introduccin a la Teora de la Informacin y
7/29/2019 Introduccion a La Teoria de La Informacion
53/76
Aplicaciones: Entropa
Ejemplo: Entropas a considerar en un sistema (cont)
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
Introduccin a la Teora de la Informacin y
7/29/2019 Introduccion a La Teoria de La Informacion
54/76
Aplicaciones: Entropa
Ejemplo: Entropas 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)
Introduccin a la Teora de la Informacin y
7/29/2019 Introduccion a La Teoria de La Informacion
55/76
Aplicaciones: Entropa
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)
Introduccin a la Teora de la Informacin y
7/29/2019 Introduccion a La Teoria de La Informacion
56/76
Aplicaciones: Entropa
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)
Introduccin a la Teora de la Informacin y
7/29/2019 Introduccion a La Teoria de La Informacion
57/76
Aplicaciones: Entropa
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
Introduccin a la Teora de la Informacin y
7/29/2019 Introduccion a La Teoria de La Informacion
58/76
Aplicaciones: Entropa
Informacin Mutua (cont)
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
Introduccin a la Teora de la Informacin y
7/29/2019 Introduccion a La Teoria de La Informacion
59/76
Aplicaciones: Entropa
Informacin Mutua (cont)
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
Introduccin a la Teora de la Informacin y
7/29/2019 Introduccion a La Teoria de La Informacion
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
Introduccin a la Teora de la Informacin y
7/29/2019 Introduccion a La Teoria de La Informacion
61/76
Aplicaciones: Entropa Relativa
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
Introduccin a la Teora de la Informacin y
A li i E R l i
7/29/2019 Introduccion a La Teoria de La Informacion
62/76
Aplicaciones: Entropa 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.333KL2 = D(X | Y) = 0.833
J = KL1 + KL2 = 2.16666
KL1 y KL2 no son simtricas pero J si lo es.
Introduccin a la a la Teora de la Informacin y
7/29/2019 Introduccion a La Teoria de La Informacion
63/76
Aplicaciones
Contenidos: Introduccin a algunos aspectos de la teora de la
informacin (T.I.): informacin y probabilidades
Entropa
Resea de algunas aplicaciones en diferentes reasincluyendo: Comunicaciones, Encripcin yBioinformtica.
Introduccin a la Teora de la Informacin y
A li i A li i
7/29/2019 Introduccion a La Teoria de La Informacion
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
7/29/2019 Introduccion a La Teoria de La Informacion
65/76
Aplicaciones: Introduccin
Sistema de Comunicacin
Codificador CanalDe-
codificador
Mensaje M Mensaje M
DestinoOrigen
Introduccin a la Teora de la Informacin y
A li i A li i
7/29/2019 Introduccion a La Teoria de La Informacion
66/76
Aplicaciones: Aplicaciones
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).
Introduccin a la Teora de la Informacin y
A li i A li i
7/29/2019 Introduccion a La Teoria de La Informacion
67/76
Aplicaciones: Aplicaciones
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.
Introduccin a la Teora de la Informacin y
A li i A li i
7/29/2019 Introduccion a La Teoria de La Informacion
68/76
Aplicaciones: Aplicaciones
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
7/29/2019 Introduccion a La Teoria de La Informacion
69/76
Aplicaciones: Introduccin
Sistema de Encriptacin
Encriptor CanalDecriptor
Mensaje M Mensaje M
DestinoOrigen
Generador
de llaves
K K
Interceptor
(e, K, C)
C=e(M,K)
Introduccin a la Teora de la Informacin y
Aplicaciones: Aplicaciones
7/29/2019 Introduccion a La Teoria de La Informacion
70/76
Aplicaciones: Aplicaciones
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.
Introduccin a la Teora de la Informacin y
Aplicaciones: Aplicaciones
7/29/2019 Introduccion a La Teoria de La Informacion
71/76
Aplicaciones: Aplicaciones
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.
Introduccin a la Teora de la Informacin y
Aplicaciones: Aplicaciones
7/29/2019 Introduccion a La Teoria de La Informacion
72/76
Aplicaciones: Aplicaciones
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.
Introduccin a la Teora de la Informacin y
Aplicaciones: Aplicaciones
7/29/2019 Introduccion a La Teoria de La Informacion
73/76
Aplicaciones: Aplicaciones
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)
Introduccin a la Teora de la Informacin y
Aplicaciones: Aplicaciones
7/29/2019 Introduccion a La Teoria de La Informacion
74/76
Aplicaciones: Aplicaciones
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)
Introduccin a la Teora de la Informacin y
Aplicaciones: Conclusin
7/29/2019 Introduccion a La Teoria de La Informacion
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.
Introduccin a la Teora de la Informacin y
Aplicaciones
7/29/2019 Introduccion a La Teoria de La Informacion
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
Top Related