Information Theory

Question 1

log(A) + log(B)

Answer 1

log(AB)

Question 2

Entropy for N equiprobable events

Answer 2

Entropy = E[-log p(x)] = - sum_{over classes} p(x_c) log p (x_c)

For equiprobable events, p(x_c) = 1/C, so
entropy = log(C)

Question 3

Is entropy ever negative?

Answer 3

No

Question 4

When is entropy additive?

Answer 4

For independent events

Question 5

Interpretation of -log p_i

Answer 5

of Bits required to represent ith symbol efficiently

Question 6

Shannon bit

Answer 6

0 or 1, but not both simultaneously (as opposed to qubit)
1 bit = amount of info gained
if we have apriori info about which event is more probable, then amount of info gain < 1 bit

Question 7

Shanon Coding

Answer 7

Minimize the bits required to represent message
Done by assigning shorter codes to symbols with higher probabilities
Mean Length = sum(p_x log_k (p_x)), where k = arity of code e.g., 2 for binary and p_x is probability for symbol x
Coding must be efficient but also decodable (unique symbols)
Here, log_k(p_x) is the bits of information and p_x is the proba of x happening

Question 7

Convert base of log

Answer 7

log_c(a) = log_b(a)/log_b(c)

Question 8

Interpretation of cross-entropy

Answer 8

• sum_x p_x log(q_x) where p is the true distribution and q is the predicted distribution
  Avg bits required to transmit p if q is used instead

Question 9

Interpretation of KL divergence

Answer 9

KLD(P||Q) = H(P, Q) - H(P)
i.e., cross-entropy - entropy (not symmetric)
i.e., additional bits required to transmit p since we are using the predicted distribution q instead of true distribution p

Question 10

Is KLD a distance measure? Why/Why not?

Answer 10

No, since it is not symmetric

Question 11

Mutual Information

Answer 11

I(X, Y) = H(X) + H(Y) - H(X, Y)
I(X, Y) = H(Y) - H(Y|X)