CSE5313 Coding and information theory for data science (Lecture 15)

Information theory

Transmission, processing, extraction, and utilization of information.

• Information: “Resolution” of uncertainty.
• Question in the 1940’s: How to quantify the complexity of information?
  • Questions:
    • How many bits are required to describe an information source?
    • How many bits are required to transmit an information source?
    • How much information does one source reveal about another?
  • Applications:
    • Data Compression.
    • Channel Coding.
    • Privacy.
• Claude Shannon 1948: Information Entropy.

Entropy

The “information value” of a message depends on how surprising it is.

• The more unlikely the event, the more informative the message.

The Shannon information of an event $E$:

Entropy the the expected amount of information in a random trial.

• Rolling a die has more entropy than rolling a coin (6 states vs 2 states).

Information entropy

Let $X$ be a random variable with values in some finite set $\mathcal{X}$.

The entropy $H(X)$ of $X$ is defined as:

Idea: How many bits are required, on average, to describe $X$?

• The more unlikely the event, the more informative the message.
• Use “few” bits for common $x$ (i.e., $Pr(x)$ large).
• Use “many” bits for rare $x$ (i.e., $Pr(x)$ small).

Notes:

• $H(X)=\mathbb{E}_{x\sim X}[I(X=x)]$
• $H(X)\geq 0$
• $H(X)=0$ if and only if $Pr(X=x)=1$ for some $x\in \mathcal{X}$.
• Does not depend on $\mathcal{X}$ but on the probability distribution $Pr(X=x)$.
• Maximum entropy is achieved when the distribution is uniform. $H(Uniform(n))=\log_2 n$. Where $n$ is the number of events. ($a$ bits required to describe each event of size $2^a$).

Motivation

Optimal compression:

Consider the $X$ with distribution given belows:

The average length of the encoding is $1/8\times 3+1/4\times 3+1/4\times 2+1/2\times 1=7/4$.

And the entropy of $X$ is $H(X)=1/8\times \log_2 8+1/4\times \log_2 4+1/4\times \log_2 2+1/2\times \log_2 1=7/4$.

So the average length of the encoding is equal to the entropy of $X$.

This is the optimal compression.

This is the Huffman coding.

Few extra theorems that will not be proved in CS course

• Theorem: Avg. # of bits in any prefix-free compression of $X$ is ≥ $H(X)$.
• Theorem: Huffman coding is optimal.
  • I.e., Avg. # of bits equals $H(X)$.
• Disadvantage of Huffman coding: the distribution must be known.
  • Generally not the case.
• [Lempel-Ziv 1978]: Universal lossless data compression.

Conditional and joint entropy

How does the entropy of different random variables interact?

• As a function of their dependence.
• Needed in order to relate:
  • A variable and its compression.
  • A variable and its transmission over a noisy channel.
  • A variable and its encryption

Definition for joint entropy

Let $X$ and $Y$ be discrete random variables.

The joint entropy $H(X,Y)$ of $X$ and $Y$ is defined as:

Notes:

• $H(X,Y)\geq 0$
• $H(X,Y)=H(Y,X)$
• $H(X,Y)\geq \max\{H(X),H(Y)\}$
• $H(X,Y)\leq H(X)+H(Y)$ with equality if and only if $X$ and $Y$ are independent.

Conditional entropy

What is the average amount of information revealed by $Y$ given the distribution of $X$?

For each given $x\in \mathcal{X}$, the conditional entropy $H(Y|X=x)$ is defined as:

The conditional entropy $H(Y|X)$ is defined as:

Notes:

• $H(X|X)=0$
• $H(Y|X)=0$ when $Y$ is a function of $X$.
• Conditional entropy not necessarily symmetric. $H(X|Y)\neq H(Y|X)$.
• Conditioning will not increase entropy. $H(X|Y)\leq H(X)$.

Chain rules of entropy

Joint entropy: $H(X,Y)=\mathbb{E}_{x\sim X, y\sim Y}\log \frac{1}{Pr(X=x, Y=y)}$.

Conditional entropy: $H(Y|X)=\mathbb{E}_{x\sim X}\log \frac{1}{Pr(Y=y|X=x)}$.

Chain rule: $H(X,Y)=H(X)+H(Y|X)$.

Mutual information

Definition for mutual information

The mutual information $I(X;Y)$ of $X$ and $Y$ is defined as:

Properties of mutual information

• $I(X;Y)\geq 0$
  • Prove via Jensen’s inequality.
  • Conditioning will not increase entropy.
• $I(X;Y)=I(Y;X)$ symmetry.
• $I(X;X)=H(X)-H(X|X)=H(X)$
• $I(X;Y)=H(X)+H(Y)-H(X,Y)$

Applications

Channel capacity

Recall a channel is tuple of $(F,\Phi,\operatorname{Pr})$.

Definition of discrete channel

A discrete channel is a system consisting of a discrete input alphabet $\mathcal{X}$, a discrete output alphabet $\mathcal{Y}$, and a probability transition $\operatorname{Pr}(y|x)$.

The channel is memoryless if the output at any time depends only on the input at that time and not on the inputs and outputs at other times.

Definition of channel capacity

The channel capacity $C$ of a channel is defined as:

where $I(X;Y)$ is the mutual information between $X$ and $Y$.

Shannon’s noisy coding theorem

Recall the rate of the code is $R=\frac{\log_{|F|}|\mathcal{C}|}{n}$.

For a discrete memoryless channel with capacity $C$, every rate $R<C$ is achievable.

• There exists a sequence of codes of length $n$ and size $|F|^{nR}$ with vanishing probability of error as $n\to \infty$.
• In 1 channel use, it is impossible beat the noise.
• In $n$ channel uses as $n\to \infty$,it is possible to beat the all the noise.

Corollary for the binary symmetric channel

The capacity of the binary symmetric channel with crossover probability $p$ is $1-H(p)$.