"Coding" Interpretation of Entropy
Cross Entropy
PA154 Jazykové modelování (2.1) Pavel Rychlý
pary@fi.muni.cz
March 2, 2017
The least (average) number of bits needed to encode a message (string, sequence, series, ...) (each element having being a result of a random process with some distribution p): — H(p) Remember various compressing algorithms?
► they do well on data with repeating (= easily predictable = = low entropy) patterns
► their results though have high entropy => compressing compressed data does nothing
Source: Introduction to Natural Language Processing (600.465) Jan Hajic, CS Dept., Johns Hopkins Univ. www.c5.jhu.edu/" hajic
Coding: Example
Entropy of Language
How many bits do we need for ISO Latin 1?
► the trivial answer: 8
Experience: some chars are more common, some (very) rare:
► ... so what if we use more bits for the rare, and less bits for the frequent? (be careful: want to decode (easily)!)
► suppose: p('a') = 0.3, p('b') = 0.3, p('c') = 0.3, the rest: p(x)^.0004
■ 01, 'c' ~ 10, rest: 11 b1b2b3b,b5b6b7bs
code: 'a' ~ 00, 'b' code 'acbbecbaac': 00    10   01 01 a     c     b     b é number of bits used: 28 (vs.
1100001111 10
01 b
00   00 10
I using "naive" coding)
code length ~ — log(probability)
Imagine that we produce the next letter using
p('n+i|'i, ■ ■ ■ 'n),
where /i,... /„ is the sequence of all the letters which had been uttered so far (i.e. n is really big!); let's call k,... /„ the history h(hn+i), and all histories H: Then compute its entropy:
► -£/,eH£/e,lp(','0i°g2P('l'0
Not very practical, isn't it?
Cross-Entropy
Cross Entropy: The Formula
estimate (sample): Vy g ft : p(y) =
Typical case: we've got series of observations
T = {ti, t2, f3, t4,..., f„} (numbers, words, ...; ti 6 ft);
cM
\T\ '
def. c(y) = \{t g T;t = y}\
... but the true p is unknown; every sample is too small! Natural question: how well do we do using p (instead of p)? Idea: simulate actual p by using a different T (or rather: by using different observation we simulate the insufficiency of T vs. some other data ("random" difference))
Hp,(~p) = H(p') + D(p'\\p)
hp'(P) = - Ex€S2 P'M |0S2 P(x)
p' is certainly not the true p, but we can consider it the "real world" distribution against which we test p
note on notation (confusing .
-op, also H-r(p)
(Cross)Perplexity: Gp,(p) = GT,(p) = 2řV(ř')
PA154 Jazykové modelováni (2.1)
Conditional Cross Entropy
Sample Space vs. Data
So far: "unconditional" distribution(s) p(x), p'(x)... In practice: virtually always conditioning on context Interested in: sample space V, r.v. Y, y g V; context: sample space Q., r.v.X, xeQ:
"our" distribution p(y|x), test against p'(y,x), which is taken from some independent data:
-       p'(y<x) los2P(ylx)
In practice, it is often inconvenient to sum over the space(s)
(especially for cross entropy!) Use the following formula: hp'(p) = -Eyev,xenP'(y.x) log2P(yM =
-VI ^'l E;=i...|T'i loS2 p(y;k;)
This is in fact the normalized log probability of the "test" data: H„{p) = -1/| T'\log2 p(y;|x;)
Computation Example
ft = {a, b, ..,z}, prob. distribution (assumed/estimated from data): p(a) = .25, p(b) = .5, p(a) = ^ for a £ {c.r}, = 0 for the rest: s,t,u,v,w,x,y,z
Data (test): barb p'(a) = p'(r) = .25, p'(b) = .5 Sum over ft:
a abcdefg...pqrst...z -p'(a)l°g2p(a)  -5+.5+0+0+0+0+0+0+0+0+0+1.5+0+0+0+0+0 = 2.5
Sum over data: i/sl 1/b -logics;) 1
2/a     3/r     4/b s---1/|T'|
+   2   +   6    +    1    =10    (1/4)  x 10 = 2.5
Cross Entropy: Some Observations
■ H(p) ??<,=,>?? Hp/(p) : ALL!
■ Previous example:
p(a) = .25, p(b) = .5, p(a)= ^ for a £ {c.r}, = 0 for the rest: s,t,u,v,w,x,y,z
H(p) = 2.5bits = H(p')(barb)
■ Other data: probable: (|)(6 + 6 + 6 + 1 + 2 + 1 + 6 + 6)= 4.25
H(p) < 4.25bits = H(p')(probable)
■ And finally: abba: (±)(2 + 1 + 1 + 2) = 1.5
H(p) > 1.5fa/ts = H(p')(abba)
■ But what about: baby -p'(y)log2p(y) = -.25log20 = oo (??)
Cross Entropy: Usage
Comparing data??
► NO! (we believe that we test on real data!) Rather: comparing distributions fvs. real data) Have (got) 2 distributions: p and q (on some ft,X)
► which is better?
► better: has lower cross-entropy (perplexity) on real data S "Real" data: S
Hs(p) = -l/|S|£,,
log2p(yi\xi) KU Hs{q) = -1/|S| E;=i..|s| loe^(yi\xi)
Comparing Distributions
■ p(.) from previous example:
\Hs(p) = 4.25
p(a) = .25, p(b) = .5, p(a) = ^ for a € {c.r}, = 0 for the rest: s,t,u,v,w,x,y,z
q{.\.) (conditional; defined by a table):
1	a b 0 .5	0 0	0	p * 125 0	0
b * 1	1 0 0 0 0 .5	0 0 0 1 0 c	i 0 0	125 D ,123 0 1 25    0 f	0 0
0	0 0	0 0	0	125 ľ	0
V	0 0 o o	0 0 0 c	0 0	125 0 125 <-e——	1
other	0 0	í 0	0	125 0	0
ex.: q(o|r) = 1 a(r|p)= 125
(l/8)(log(p|oth.)+log(r|p)+l»g(»|r)+log(b|o)+log(a|b)+log(b|a)+lc,gfl|b)+log(c|l)) (1/8) (    0      +3+0+0+1   +   0+1   +   0 )
|Hs(q) = .62S
PA154 Jazykové modelováni (2.1)