Information theory

November 29, 2023

Information theory #

This is my note for reading a book Elements of information theory.

Entropy #

The measure of uncertainty of probablity distribution.

\[E = E(\frac{1}{\log(p(x))}) \]

If you have 2 side coins, your uncertainty is \( \frac{1}{2} \log(\frac{1}{2}) * 2 = 1\)

If you have 4 side coins, your uncertainty is \( \frac{1}{4} \log(\frac{1}{4}) * 4 = 2\)

And your uncertainty is measured by how many bits (the base can be changed) you need to represent the probability distribution on average.

Conditional expectation #

Ex. Y: weight, x: height

For a given \( X = x \), find the expected value of \( Y \). \[E(Y|X=x) = \sum p(Y|X=x) y = g(x)\]

For example, when height is 150, what’s the expected weight? The answer depends on \( x \). So it is a function of \( x \) (possibly a constant function)

If we let \( x \) be a random, \[E(Y|X) = \sum p(Y|X) y = g(X)\]

The answer depends on \( X \) and it is a random variable which depends on \(X\) : \( g(X) \)

You purposefully leave the \( X \) as random variable, and if you want to consider all possibility of \( X \) by \( E( E(Y|X)) \) you get \( E(Y) \)

Conditional Entropy #

Conditional entropy measures the remaining length you need after knowing something. For all cases, you look at the length of \( P(Y|X) \).

I.e. if I know \(X\) how uncertain am I about \( Y \)?

\[H(Y|X) = -E(\log(P(Y|X)) = \sum P(x, y) \log(P(y|x)) \]

This is different from conditional expectation in that

• we use the probability of \( p(X, Y) \) not \( p(Y|X) \) as a pdf.
• X, Y is summed over the possibilities

Compare with conditional expectation #

\(H(Y|X=x) = - \sum_{y\in Y} P(y|X=x) \log P(y|X=x)\)

\( H(Y|X) = - \sum_{x \in X} P(x) \sum_{y\in Y} P(y|X=x) \log P(y|X=x) \)

Joint Entropy #

Look at two event as single event, and measure the length of the probability.

\[H(X, Y) = -E(\log(P(X, Y)) \]

Chain rule of entropy #

The length I need to know for both is the length I need for single and the remaining.

\[H(X, Y) = H(X) + H(Y|X) = H(Y) + H(X|Y) \]

Relation to probability #

\( H(X) \) have similar property as the \( P(X) \).

Multiplication becomes addition under log #

\[\frac{P(X, Y)}{P(X)} = P(Y|X) \]

If we take log, \[ \log(P(X, Y)) = \log(P(X)) + \log(P(Y|X)) \]

If we take \( \mathbf{E} \) on both sides: \[ H(X, Y) = H(X) + H(Y|X) \]

We can take Conditional on both sides (tautology) #

If we can do \( \frac{P(X, Y|Z)}{P(X|Z)} = P(Y|X, Z) \)

it becomes:

\[ H(X, Y|Z) = H(X|Z) + H(Y|X, Z) \]

Relative Entropy #

Suppose there’s a distribution \( p(x) \), \( H(X) \) is the minimum average length we can achieve to send \(X\).

If we use length (coding scheme) based on \( q(x) \), it will be less efficient, the average length will be longer, and relative entropy measures that extra length.

\[D(p||q) = \text{ ineffcient length} - \text{ optimal length} = -\sum p(x) (\log(q(x)) - \log(p(x))) \]

Chain rule for relative entropy #

Mutual Information #

It is the information (length) of the other random variable provides me.

If I know \( X \), how much does I know about \( Y \) because of the knowledge of \( X \)

\[I(X;Y) = H(X) - H(X|Y) = H(Y) - H(Y|X) = \sum p(x,y) \frac{p(x,y)}{p(x)p(y)} \]

QUESTION Another interpretation? #

The sum expression seems to sugges another interpretation is possible.

By deconstructing \(\frac{p(x,y)}{p(x)p(y)} \)

Chain rule for information #

Self Information #

\( I(X; X) = H(X) \) what?

\( I(X; X) \): How much info you can get by knowing about yourself \( H(X) \): How much you are uncertain about yourself

The amount you gain by knowing yourself is the same as the amount you need to know about yourself.

Jenson’s inequality #

Convex function #

The line over two points are above the function.

\[f(cx_1 +(1-c)x_2) \le cf(x_1) + (1-c)f(x_2) \]

Convexity #

If a 2nd derivative is non negative over an interval, the function is convex over that interval.

Proof uses the Taylor series expansion.

QUESTION Taylor series? #

Taylor series is an approximation for the function. Why are we using it to prove a function has a property with the approximation?

Are we assuming the approximation is good enough over the region?

Jensen’s inequality #

If f is a convex function,

\[ Ef(X) \ge f(EX) \]

QUESTION What does it mean? #

Could it mean something like the following? I haven’t proved it.

If we find the mean of the \(X\) and draw the tangent line on \(f(EX) \)

\( E(f(X)) \): the area below the curved line \( f(E(X)) \): the area below the tangent line