Informação. Duas aplicações recreativas.
Codificação eficiente
L.J. Amoreira
UBI
Dezembro 2010
Tópicos do dia
Revisão dos conceitos de entropia condicional
Revisão dos conceitos de informação e de informação mútua
Um exemplo
Duas aplicações recreativas da teoria da informação
Jogo de adivinha
Mastermind
Codificação eficiente
Questionário
Entropias condicionais
Dadas duas variáveis aleatórias X e Y ,
x1 x2 . . . xN
y1
X =
Y =
p1 p2 . . . pN
q1
y2
q2
...
...
yM
qM
,
definimos
I As entropias marginais:
H(X ) = −
N
X
pi log pi
H(Y ) = −
i=1
I
M
X
A entropia condicional de Y sabendo que X = xi :
H(Y |X = xi ) = −
M
X
P(Y = yj |X = xi ) log P(Y = yj |X = xi )
j=1
I
qj log qj
j=1
A entropia condicional de Y conhecido X :
H(Y |X ) =
N
X
i=1
pi H(Y |X = xi )
Informação e informação mútua
I
Definimos também informação sobre Y veiculada pelo
conhecimento de que X = xi
I(Y ; X = xi ) = H(Y ) − H(Y |X = xi )
I
E informação mútua sobre Y trazida por X
I(Y ; X ) = H(Y ) − H(Y |X )
I
Propriedades fundamentais da entropia e da informação
H(X , Y ) ≤ H(X ) + H(Y )
H(Y |X ) ≤ H(Y )
I(Y ; X ) ≥ 0
I(X ; Y ) = H(X ) + H(Y ) − H(X , Y )
Um exemplo
I
I
I
I
Um grupo é constituı́do por 7 mulheres e 13 homens. 4 homens
e 5 mulheres têm menos de 30 anos.
Um elemento do grupo é escolhido ao acaso. Seja S o seu sexo
(f ou m) e V a sua idade (j ou a)
Probs. conjunta e marginal
Probs. condicional P(S|V )
@s
@s
f
m
P(V )
f
m
v@
v@
@
@
j
0,25 0,20
0,45
j
5/9
4/9
0,10 0,45
0,55
a
a
2/11 9/11
P(S) 0,35 0,65
Entropias marginais:
H(S) = 0, 9341 bits;
I
Entropias condicionais de S para cada V
H(S|V = j) = 0, 9911 bits;
I
H(V ) = 0, 9928 bits
H(S|V = a) = 0, 6840 bits;
Entropia condicional associada a S, conhecido V :
H(S|V ) = 0, 8220 bits.
Aplicação simples da Teoria da Informação
Jogo de adivinha
I Um dos participantes (jogador A) escolhe secretamente um
inteiro s num intervalo dado [a, b]
I O outro (jogador B) tenta adivinhá-lo por tentativa e erro. A cada
tentativa t de B, A responde “é alto de mais”(se t > s), “é baixo
demais”(se t < s) ou “está certo”(se t = s)
I Qual a estratégia para determinar s num número expectável
mı́nimo de tentativas?
I Intuitivamente, parece-nos que a melhor estratégia é a de
escolher h no centro do intervalo de possibilidades de s. Vamos
demonstrar que assim é usando a teoria da informação.
I
I
Note-se que no intervalo [a, b] há b − a + 1 valores possı́veis
para s
Se o jogador A escolher s de forma equiprovável, a
probabilidade de cada valor é então
p=
1
b−a+1
Aplicação simples da Teoria da Informação
I
Para o jogador B, o número secreto s é uma variável aleatória
que pode tomar qualquer dos b − a + 1 valores no intervalo [a, b]
I
A entropia inicial associada a esta variável é então
H0 (s) = −
b
X
pi log pi = log(b − a + 1)
i=a
I
Colocada uma hipótese h, a resposta dada pelo jogador A é
também uma variável aleatória R
“baixo demais” “certo” “alto demais”
R=
1
h−a
b−h
b−a+1
b−a+1
b−a+1
Aplicação simples da Teoria da Informação
Três possibilidades
1. R(h) = “alto demais”
I
O número de possibilidades reduz-se a h − a:
H11 = log(h − a)
p1 =
h−a
b−a+1
2. R(h) = “certo”
I
O número de possibilidades reduz-se a 1:
H12 = 0
p2 =
1
b−a+1
3. R(h) = “baixo demais”
I
O número de possibilidades reduz-se a b − h:
H13 = log(b − h)
p3 =
b−h
b−a+1
Aplicação simples da Teoria da Informação
I
Valor esperado da entropia final (entropia condicionada):
H1 (h) = p1 H11 + p2 H12 + p3 H13
1
=
(h − a) log(h − a) + (b − h) log(b − h)
b−a+1
I
A hipótese h óptima é a que minimiza H1 (maximiza a
informação I = H0 − H1 transmitida pela resposta)
I
Determinamos h com o método geral de anular a derivada de
H1 :
dH1
1
h−a
=
log
=0
dh
b−a+1
b−h
a+b
h=
2
Este é o resultado que já intuı́amos e que pretendı́amos
demonstrar!
Outro exemplo: mastermind
Algoritmo simples
Algoritmo melhorado
1. Gera uma lista com todas as
soluções
1. Gera uma lista com todas as
soluções
2. Repete
2. Repete
I
I
I
Sugere a primeira da lista
Se a resposta é (4, 0):
o jogo acabou, pára
Elimina da lista todas as
incompatı́veis
I
I
I
Sugere a chave que
minimiza o valor esperado
da entropia final
Se a resposta é (4, 0):
o jogo acabou, pára
Elimina da lista todas as
incompatı́veis
Número médio de jogadas até chegar à solução:
Algoritmo simples: 5,8
Algoritmo melhorado: 3,8
Outros mastermind
Ns=6; Nd=4
Ns=8; Nd=4
800
2,500
700
Alg. simples
Informação
Alg. simples
Informação
2,000
Número de jogos
Número de jogos
600
500
400
N. de jogos: 1296
áNt ñ = 5,2 / 3,8
Max: 8 / 6
300
1,500
N. de jogos: 4096
áNt ñ = 6,7 / 4,8
Max: 10 / 8
1,000
200
500
100
0
0
0
1
2
3
4
5
6
7
8
9 10 11
Número de tentativas
12 13
14
15 16
0
1
2
3
4
5
6 7
8
9 10 11
Número de tentativas
12 13
14 15 16
Ns=6; Nd=5
5,000
Alg. simples
Informação
Número de jogos
4,000
3,000
N. de jogos: 7776
áNt ñ = 5,7 / 4,3
Max: 10 / 7
2,000
1,000
0
0
1
2
3
4
5
6 7
8
9 10 11
Número de tentativas
12 13
14 15 16
Conclusão:
O algoritmo melhorado é claramente superior ao algoritmo simples
Códigos
QUESTIONÁRIO
Para os alunos de número par
Para os alunos de número ı́mpar
1. Qual das seguintes expressões é
falsa?
A H(X , Y ) ≤ H(X ) + H(Y )
1. Qual das seguintes expressões é
falsa?
A H(X , Y ) ≤ H(X ) + H(Y )
B H(Y |X ) > H(Y )
B H(Y |X ) ≤ H(Y )
C I(Y ; X ) = H(Y ) − H(Y |X )
C H(X |Y ) < 0
2. Num grupo com 4 homens e 3 mulheres, um dos homens é canhoto.
Um dos elementos do grupo é escohido, ao acaso. Quanta informação
relativamente ao sexo da pessoa escolhida recebemos, se nos disserem
se ela é canhota?
A -0,13 bits
2. Num grupo com 5 homens e 3 mulheres, um dos homens é canhoto.
Um dos elementos do grupo é escohido, ao acaso. Quanta informação
relativamente ao sexo da pessoa escolhida recebemos, se nos disserem
se ela é canhota?
A -0,09 bit
B 0,13 bit
B 1,20 bits
C 1,2 bits
C 0,09 bits