Download Unidad 5 - Ingenieria Cognitiva

Unidad 5: Entropía y Fuente del
Teorema de Codificación de
Shannon
En ésta unidad empezamos a ver la teoría de la información, al cual nos permitirá aprender
mas sobre las propiedades fundamentales de códigos generales sin tener que diseñarlos.
La teoría de la información es una parte de la física que trata de describir qué es la
información y cómo podemos trabajar con ella. Como todas las teorías en la física, es un
modelo del mundo real el cual es aceptado como verdadero siempre mientras que éste
pueda predecir con suficiente precisión cómo actúa la naturaleza.
Motivación
Empezamos éste subtema preguntándonos sobre lo que es la información. A partir de éste
punto, podemos reforzar varios puntos, tales como:
 El número de posibles respuestas r a algún problema o pregunta debería de estar
relacionada con la “información.”
 La información debería de ser aditiva de alguna forma (o sea, se acumula a medida que
se obtiene más información).
 Una medida de la información correcta necesita tomar en consideración las
probabilidades de los varios posibles eventos
Podemos calcular cualquier medida deseada información con la fórmula
𝐼 𝑈
≜ 𝑙𝑜𝑔𝑏 𝑟
Donde r es el número de todos los resultados posibles de un mensaje aleatorio U.
Podemos utilizar ésta fórmula para confirmar la propiedad antes mencionada de la adición:
𝐼 𝑈1 , 𝑈2 , … , 𝑈𝑛
= 𝑙𝑜𝑔𝑏 𝑟 𝑛 = 𝑛 ∗ 𝑙𝑜𝑔𝑏 𝑟 = 𝑛 ∗ 𝐼 (𝑈)
La medida de la información de Shannon es una “información de Hartley promedio,” la cual
es representada de la siguiente manera:
𝑟
𝑖=1
𝑝𝑖 𝑙𝑜𝑔2 1
= −
𝑝𝑖
𝑟
𝑝𝑖 𝑙𝑜𝑔2 𝑝𝑖
𝑖=1
Donde pi denota la probabilidad del resultado posible en la i vez
Incertidumbre o entropía
Debido a su relación con un concepto que corresponde a diferentes áreas de la física,
Shannon denominó a su medida como entropía; sin embargo, incertidumbre es una
definición más precisa.
Dicho esto, la entropía o incertidumbre de un mensaje aleatorio U que toma diferentes
valores r con probabilidad pi, i=1, …, r, es definida como:
𝑟
𝐻 𝑈
≜ −
𝑝𝑖 𝑙𝑜𝑔𝑏 𝑝𝑖
𝑖=1
Es importante señalar que cada vez que sumamos sobre 𝑝𝑖 𝑙𝑜𝑔𝑏 𝑝𝑖 , podemos asumir que
implícitamente se excluyen todos los índices i con pi = 0
También es importante señalar que en el caso que todos los eventos r son igualmente
probables, la definición de entropía de Shannon se reduce a la medición de Hartley:
1
𝑝𝑖 = ,
𝑟
𝑟
∀𝑖:
𝐻 𝑈
= −
𝑖=1
1
1
𝑙𝑜𝑔𝑏
𝑟
𝑟
1
= 𝑙𝑜𝑔𝑏 𝑟 ∗
𝑟
𝑟
1 = 𝑙𝑜𝑔𝑏 𝑟
𝑖=1
Función de entropía binaria
En éste caso, si U es binaria con dos posibles valores 𝑢1 y 𝑢2 de dicha manera que Pr[U=u1] =
p y Pr[U=u2] = 1 – p, entonces:
𝐻 𝑈
= 𝐻𝑏 (𝑝),
Donde 𝐻𝑏 (∙) es llamada la función de entropía binaria, y ésta es definida como:
𝐻𝑏 𝑝
≜ −𝑝𝑙𝑜𝑔2 𝑝 −
1 − 𝑝 𝑙𝑜𝑔2 1 − 𝑝 ,
𝑝 ∈ [0,1]
La Teoría de la Información Desigualdad
Ésta desigualdad no tiene un nombre exacto, pero ya que es muy importante en la teoría de
la información se le conoce como la Teoría de la Información Desigualdad o la Desigualdad
TI, la cual estipula que para cualquier base b > 0 y cualquier ξ > 0:
1
1−
𝑙𝑜𝑔𝑏 𝑒 ≤ 𝑙𝑜𝑔𝑏 ξ ≤ (ξ − 1) − 𝑙𝑜𝑔𝑏 𝑒
ξ
Con desigualdades en ambos lados si, y únicamente si, ξ = 1
Límites de la entropía
Si U tiene r posibles valores, entonces:
0 ≤ 𝐻 𝑈 ≤ 𝑙𝑜𝑔2 𝑟 𝑏𝑖𝑡𝑠
En donde:
 𝐻 𝑈 =0
si, y únicamente si, 𝑝𝑖 = 1 para alguna i
 𝐻 𝑈 ≤ 𝑙𝑜𝑔2 𝑟 𝑏𝑖𝑡𝑠
si, y únicamente si, 𝑝𝑖 = 𝑟 ∀𝑖
1
Árboles revisitado
 Considera un árbol binario con probabilidades. Recuerda que:
 n denota el número total de hojas
 pi, i=1, …, n, denota las probabilidades de las hojas
 N denota el número de nodos (incluyendo la raíz pero excluyendo las hojas)
 Pl, l=1, …, N, denota las probabilidades de los nodos, en donde por definición p1 = 1 es la
probabilidad de la raíz.
Además se utilizará ql,j para denotar la probabilidad del nodo/hoja j que está un paso
delante de l (el hijo j del nodo l) donde j = 0,1.
La entropía de hojas es definida como
𝑛
𝐻ℎ𝑜𝑗𝑎 ≜ −
𝑝𝑖 𝑙𝑜𝑔2 𝑝𝑖
𝑖=1
Denotando que P1, P2, …, Pn son las probabilidades de todos los nodos (incluyendo la raíz) y que
por qj,l la probabilidad de los nodos y hojas un paso adelante del nodo l, podemos definir a la
entropía derivativa hj del nodo l como:
𝐻𝑙 ≜ −
𝑞𝑙,0
𝑞𝑙,0
𝑙𝑜𝑔2
𝑃𝑙
𝑃𝑙
−
𝑞𝑙,1
𝑞𝑙,1
𝑙𝑜𝑔2
𝑃𝑙
𝑃𝑙
Teorema de Entropía de Hojas: En cualquier árbol con posibilidades tenemos que:
𝑁
𝐻ℎ𝑜𝑗𝑎 =
𝑃𝑙 𝐻𝑙
𝑙=1
Codificación de una fuente de Información
Una fuente discreta sin memoria r-aria (DMS) es un dispositivo cuya salida es una secuencia
de mensajes aleatorios U1, U2, U3,…, donde:
 Cada Ul puede aceptar diferentes valores r con probabilidades p1, …, pr y
 Los diferentes mensajes Ul son independientes el uno del otro
El teorema de Codificación de Código de Shannon/Teorema de codificación para un DMS:
Existe un código binario libre de prefijos de un mensaje bloque-v de una fuente discreta sin
memoria (DMS) de tal manera que el número promedio lav/v de dígitos de código binario por
cada letra fuente satisface lo siguiente:
𝐿𝑎𝑣
𝑣
<𝐻 𝑈 +
1
𝑣
𝑏𝑖𝑡𝑠,
En donde H(U) es la entropía de una sola letra medida en bits y v es un vector de mensajes
aleatorios. Inversamente, por cada código binario de un mensaje bloque-v:
𝐿𝑎𝑣
≥ 𝐻 𝑈 𝑏𝑖𝑡𝑠
𝑣
Note que siempre necesitamos escoger las unidades de la entropía para que se
encuentren en bits. Esto se debe a que, al escoger un v suficientemente grande,
podemos acercarnos arbitrariamente cerca al límite definitivo de compresión H(U)
cuando usamos códigos de Huffman o Fano.
En otras palabras, podemos comprimir cualquier DMS a bits D(U) en promedio, pero no
menos.
Mientras más cerca nos queremos acercar al límite definitivo de la entropía, más grande
es nuestro retraso potencial en el sistema.
Un sistema verdaderamente práctico debería de trabajar independientemente de la fuente
asociada; en otras palabras, debería de estimar las probabilidades de los símbolos fuente al
instante para poder adaptarse a éstos automáticamente. Tal sistema es denominado un
esquema de compresión universal.
Dichos sistemas existen y son utilizados en algoritmos de compresión; un ejemplo de un sistema
que implementa dichos sistemas es el ZIP.