# Information theory

Going through lecture series: Information Theory, Pattern Recognition, and Neural Networks by David MacKay. The textbook is available for free online.

## Lecture 1: Introduction to Information Theory

### Sending information over noisy channels (formulation)

• We’re using systems to send information over imperfect channels:
• Source message $$s$$.
• Encoded into a transmission message $$t$$.
• Sent across an imperfect channel which adds noise $$n$$.
• Received on the other side as message $$r$$.
• Decoded into a guess of $$s$$, $$\hat{s}$$.
• The encoder adds redundancy.
• The decoder infers $$n$$ and $$s$$.

#### Binary symmetric channel (BSC)

• $$s = t \in \{0, 1\}^+$$
• Noise is added by flipping each token in $$s$$ with probability $$f$$.

## Lectures 2-5: Entropy and Data Compression

### Ensembles

• An “Ensemble” $$X$$ is $$(x, A_x, P_x)$$
• $$x$$ is a random variable.
• $$A_x$$ is an alphabet $$\{a_1, a_2, ...\}$$.
• $$P_x$$ is a probability distribution over $$A_x$$ $$\{p_1, p_2, ...\}$$.
• $$\sum{P_x} = 1$$

### Shannon information content

• The Shannon information content of an outcome $$x = a_i$$ is:
• $$h(x = a_i) = log_2(\frac{1}{P(x=a_i)})$$
• Measured in bits.

#### Likely vs. unlikely events

• Unlikely events have a lot of information content, likely events have little.

#### Relationship to compressed file length

• $$h(x=a_i)$$ is the best possible compressed file length.

• $$h(x=a_i)$$ is additive for independent random variables.
• $$h(x,y) = log_2(\frac{1}{P(x,y)})$$
• $$h(x,y) = log_2(\frac{1}{P(x)}) + log_2(\frac{1}{P(y)})$$
• $$h(x,y) = h(x) + h(y)$$

### Entropy

• The entropy of an ensemble is the average Shannon information content.
• $$H(X) = \sum_a{P(x=a) h(x=a)}$$
• $$H(X) = \sum_a{P(x=a) \log_2(\frac{1}{P(x=a)})}$$
• Measured in bits.

#### Binary entropy

$H_2(x) = x log \frac{1}{x}$

### Source coding theorem

• $$N$$ outcomes from a source $$X$$ can be compressed into $$~NH(X)$$ bits.

### Typical outcomes

• Source $$X$$ produces $$N$$ independent outcomes $$\textbf{x}=x_1,x_2,...$$.
• Assume $$P_x$$ has a long tail, i.e. some outcomes are much more likely than others.
• $$x_i$$ is likely to be one of $$~2^{NH(X)}$$ typical outcomes.

### Symbol codes

• Map from symbol $$x$$ to codes $$c(x)$$.
• Concatenate codes without punctuation.
• $$[x_1,x_2,x_3] \to c(x_1)c(x_2)c(x_3)$$

#### Expected length

$$L(C, X) = \sum_x{P(x)len(C(x))}$$

### Kraft inequality

• If a code is uniquely decodable…
• $$\sum_j{2^{-l_i}} \leq 1$$
• When $$\sum_j{2^{-l_i}} = 1$$, the code is complete.

### Prove the length a message can’t be greater than its entropy

Proving $$L(C, X) \geq H(X)$$.

• Alphabet $$x_i$$, codes $$c_i$$, code lengths $$l_i$$, probabilities $$p_i$$.
• Say that the ideal code lengths are $$l_i^{*} = h(x_i) = log_2(\frac{1}{p_i})$$
• Given we already have $$l_i$$, we can say what the “implicit” probability $$q_i$$ of each $$x_i$$ is:
• $$q_i = 2^{-l_i}$$
• But we need to make sure $$\sum{q_i} = 1$$, so we normalize by $$z$$.
• $$z = \sum{2^{-l_i}}$$
• $$z \leq 1$$ for any uniquely decodable code (see Kraft inequality).
• $$z = 1$$ for any complete code.
• $$q_i = \frac{2^{-l_i}}{z} = \frac{2^{-l_i}}{\sum{2^{-l_i}}}$$
• So, $$l_i = log(\frac{1}{q_i}) - log(z)$$
• $$L(C, X) = \sum_i{p_i l_i}$$
• $$L(C, X) = \sum_i{p_i (log(\frac{1}{q_i}) - log(z))}$$
• $$L(C, X) = \sum_i{p_i log(\frac{1}{q_i})} - log(z)$$
• $$L(C, X) = \sum_i{p_i log(\frac{1}{p_i})} + \sum_i{p_i log(\frac{p_i}{q_i})} - log(z)$$
• $$L(C, X) = H(X) + \sum_i{p_i log(\frac{p_i}{q_i})} - log(z)$$
• $$L(C, X) = H(X) + D_{KL}(p || q) - log(z)$$
• $$D_{KL}(p || q) = \sum_i{p_i log(\frac{p_i}{q_i})}$$
• $$D_{KL}(p || q) \geq 0$$
• $$-log(z) \geq 0$$
• So, $$L(C, X) \geq H(X)$$
• And $$L(C, X) = H(X)$$ if:
• There’s no difference between $$p$$ and $$q$$: $$D_{KL}(p || q) = 0$$.
• You have a complete code: $$z = 1$$.
• If ideal lengths $$l_i = log(\frac{1}{p_i})$$ are not integers:
• $$H \leq L < H + 1$$

### Huffman algorithm

• Making a binary tree.
• Given unconnected leaf nodes with values $$p_1, p_2, ...$$.
• Take two smallest leaf nodes, and make a split node.
• Add the leaf node to the list of nodes.
• Repeat until there’s only one node in the list, the root node.

#### Main issue

• Symbol codes require $$\geq 1$$ bit per character, even if $$H \ll 1$$.
• For example:
• $$p = [0.01, 0.99]$$
• $$c = [0, 1]$$
• $$L = 1$$
• $$H = 0.01 log(1 / 0.01) + 0.99 log(1 / 0.99) = 0.08$$
• So, $$H \leq L < H + 1 \to 0.08 \leq 1 < 1.08$$ holds, but this isn’t efficient!

### Arithmetic coding

• Given a string in the alphabet $$\textbf{x} = x_1, x_2, ...$$
• Given an oracle $$P(x_t | x_1, x_2, ..., x_{t-1})$$.
• Picture $$\textbf{x}$$ dividing the interval $$[0, 1]$$ repeatedly. For example:
• Alphabet $${a, b, c}$$.
• $$P(x_1) = {0.5, 0.25, 0.25}$$
• Interval of $$x_1 = a$$ is $$[0, 0.5]$$.
• Interval of $$x_1 = b$$ is $$[0.5, 0.75]$$.
• Interval of $$x_1 = c$$ is $$[0.75, 1]$$.
• Further elements $$x_2, x_3, ...$$ further subdivide the space.
• Take the interval $$[i_{lower}, i_{higher}]$$ described by $$\textbf{x}$$.
• Find a binary string $$\textbf{y}$$ with $$P(y_n=1) = 0.5$$ that subdivides to the same interval.
• $$\textbf{y}$$ is now the encoded version of $$\textbf{x}$$!

#### Length of encoding

• $$L(\textbf{x}) \leq log \frac{1}{P(\textbf{x})} + 2$$
• $$L(\textbf{x}) \leq H(\textbf{x}) + 2$$

#### Computation

You only need to compute $$NI$$ conditional probabilities, where $$N$$ is the length of the string and $$I$$ is the size of the alphabet.

#### Main advantage over Huffman algorithm

• Huffman codes use at least 1 bit per token.
• $$L(x) \leq H(x) < L(x) + 1$$ where $$x$$ is a single token.
• Arithmetic coding can use less than 1 bit per token.
• $$L(X) \leq H(X) + 2$$ where $$X$$ is the whole string.

#### Building simple predictor

• Take $$[0, 6]$$-gram statistics.
• Use these to predict the next token.

## Lectures 6-8: Noisy channel coding

### Entropy of joint distributions

• $$H(X, Y) = \sum_{x \in X} \sum_{y \in Y} P(x, y) h(x, y)$$
• where $$h(x, y) = log \frac{1}{P(x, y)}$$
• $$H(X | Y=y) = \sum_{x \in X} P(x | Y=y) h(x | y)$$
• where $$h(x | Y=y) = log \frac{1}{P(x | Y=y)}$$
• $$H(X | Y) = \sum_{y \in Y} P(Y=y) H(X | Y=y)$$
• $$H(X) + H(Y) \geq H(X, Y)$$
• $$H(X) + H(Y) = H(X, Y)$$ if $$X$$ and $$Y$$ are independent.
• $$H(X | Y) \leq H(X)$$
• $$H(X, Y) = H(X) + H(Y | X) = H(Y) + H(X | Y)$$

### Mutual information

• $$I(X ; Y) = H(X) - H(X | Y)$$
• $$I(X ; Y) = H(Y) - H(Y | X)$$
• $$I(X ; Y) = 1 - H(X | Y) - H(Y | X)$$

### Formalizing channels as matrices

• We formalize channels as a matrix $$Q$$, where:
• $$Q_{i, j} = P(Y = b_j | X = a_i)$$
• $$a$$ is the input alphabet of length $$i$$.
• $$b$$ is the output alphabet of length $$j$$.
• We can find $$P(X | Y)$$ using Bayes.

### Capacity of a channel

• $$C(Q) = \max_{P_x} I(X ; Y)$$
• i.e. the maximum mutual information given we can choose the input probability distribution.

#### Optimal input distribution

• $$P_x$$ chosen in $$C(Q) = \max_{P_x} I(X ; Y)$$
##### For BSC
• Optimal input distribution is $$P(x_i = 1) = 0.5$$
• Proof:
• $$p_1 = P(x_i = 1)$$
• $$I(X ; Y) = H(Y) - H(Y | X)$$
• $$I(X ; Y) = H_2(p_1 (1 - f) + (1 - p_1) f) - H_2(f)$$
• $$max_{p_1} I(X ; Y) =$$
• $$max_{p_1} H_2(p_1 (1 - f) + (1 - p_1) f) - H_2(f)$$
• $$max_{p_1} H_2(p_1 (1 - f) + (1 - p_1) f)$$
• Maximum value $$H_2$$ can have is $$H_2(0.5) = 1$$
• $$0.5 = p_1 (1 - f) + (1 - p_1) f$$
• $$0.5 = p_1 - p_1 f + f - p_1 f$$
• $$0.5 = p_1 - f - 2 p_1 f$$
• $$0.5 = p_1 (1 - 2 f) - f$$
• $$p_1 = \frac{0.5 + f}{1 - 2 f} = 0.5$$

### Shannon’s noisy-channel coding theorem

• For any $$\epsilon > 0$$, $$R < C$$, and large enough $$N$$
• There exists a code with length $$N$$ and rate $$R$$
• Such that the probability of a block error is $$< \epsilon$$.

#### Parity check matrix

##### Matrix definition
• We transfer 4 bits, $$t_1, t_2, t_3, t_4$$.
• We append 3 parity bits:
• $$t_5 = t_1 + t_2 + t_3$$
• $$t_6 = t_2 + t_3 + t_4$$
• $$t_7 = t_1 + t_3 + t_4$$
• We encode the relationships within $$\textbf{t}$$ as a matrix $$H$$, where $$H_{i, j}$$ represents whether bit $$i$$ was included in $$t_{3+j}$$’s parity calculation. $H = \begin{pmatrix} 1 & 1 & 1 & 0 & 1 & 0 & 0\\ 0 & 1 & 1 & 1 & 0 & 1 & 0\\ 1 & 0 & 1 & 1 & 0 & 0 & 1\\ \end{pmatrix}$
• Note that the last three columns make up an identity matrix.
##### Encoding & decoding
• $$t$$ is encoded such that $$Ht = [0, 0, 0]^T = \textbf{0}$$
• Noise is added to the received signal $$r = t + n$$
• Syndrome $$z = Hr = H(t + n) = Hr + Hn = Hn$$
• The column in $$H$$ that is equal to $$z$$ identifies which bit was flipped.
##### Generalizing >4
• Above, $$H$$ is a $$(7 \times 3)$$ matrix where $$4$$ source bits are transmitted for every $$7$$ transmission bits.
• Generally, $$H$$ is a $$N \times M$$ matrix where $$T = N - M$$ bits are transmitted for every $$N$$ bits.
• Thus, the rate is $$\frac{N - M}{N}$$ or $$1 - \frac{M}{N}$$.

#### Proving the theorem for BSC

• Say we have:
• A BSC with probability $$f$$ of flipping, with a capacity of $$1 - H_2(f)$$
• A parity check matrix $$H \in \mathbb{R}^{N \times M}$$ where $$N > M$$.
• A source and noise that have $$N - M$$ bits.
• A transmission that has $$N$$ bits.
• A syndrome that has $$M$$ bits.
• A “typical set syndrome decoder” $$M \in \mathbb{R}^M \times \mathbb{R}^{N}$$ that recovers the transmission from the syndrome.
• This has $$2^{NH_2(f) + ...}$$ entries.
• Transmissions have a rate $$R = 1 - \frac{M}{N}$$.
• We want to prove $$R < C$$ i.e. $$1 - \frac{M}{N} < 1 - H_2(f)$$.
• $$P(error) = P_1 + P_2$$ where:
• $$P_1$$ is the probability of $$n$$ not being in $$M$$.
• This is arbitrarily small as $$M$$ contains the typical set.
• $$P_2$$ is the probability of there being a $$\hat{n} \neq n$$ that has the same syndrome $$z$$.
• $$Hn = H\hat{n}$$
• $$H(n - \hat{n}) = 0$$
• We’ll focus on the constraints for $$P_2$$.
• $$P_2 = \sum_n P(n) 1(\exists \hat{n}. \hat{n} \neq n, H(n - \hat{n}) = 0)$$
• (there exists at least one is less than the number of existences)
• $$P_2 \leq \sum_n P(n) \sum_{\hat{n} \neq n} 1(H(n - \hat{n}) = 0)$$
• (we take the average $$H$$ as it is simpler to not assume a specific $$H$$)
• $$P_2 \leq \sum_n P(n) \sum_{\hat{n} \neq n} \sum_{H} P(H) 1(H(n - \hat{n}) = 0)$$
• Aside: $$P(H(n - \hat{n}) = 0 | n - \hat{n} \neq 0) = 2^{-M}$$
• $$P_2 \leq \sum_n P(n) \sum_{\hat{n} \neq n} 2^{-M}$$
• $$P_2 \leq \sum_{\hat{n} \neq n} 2^{-M}$$
• $$P_2 \leq 2^{NH_2(f)} \cdot 2^{-M}$$
• $$P_2 \leq 2^{NH_2(f)- M}$$
• So, $$P_2$$ vanishes as:
• $$M \gg NH_2(f)$$
• $$\frac{M}{N} > H_2(f)$$
• $$1 - \frac{M}{N} < 1 - H_2(f)$$
• $$R < C$$!!!

### Entropy when probabilities are certain

$H_2(0) = P(0) \log(\frac{1}{0}) = 0$

$H_2(1) = P(1) \log(\frac{1}{1}) = 0$

### Feedback gem

The encoder knowing what noise is added doesn’t improve the rate.

## Lectures 9-10: Introduction to Bayesian inference

No notes, covers the basics.

## Lectures 11-14: Approximating Probability Distributions

### K-means

Clustering algorithm. Given $$\{x_n\}$$ data points to put into $$K$$ clusters:

1. Assign cluster means $$\{\mu_k\}$$ randomly.
2. Assign each data point to the closest cluster: $$r^n_k = \arg\min_{k} (x_n - \mu_n)^2 = k$$
3. Update cluster means to the mean of its data points: $$\mu_k = \sum_n{r^n_k x_n} / \sum{r^n_k}$$
4. Go to 2.

#### Bayesian interpretation

K-means is a Maximum A Posteriori (MAP) algorithm which assumes:

• There are $$K$$ clusters.
• The probability of being in each cluster is equivalent.
• Each cluster has the same variance.

These assumptions might not be necessary. Additionally, MAP can result in incorrect cluster centers due to a hard boundary pushing clusters apart.

#### Soft K-means

Cluster responsibilities are no longer binary. Introduces an additional $$\beta$$ hyperparameter. Update rule is the same.

$r^n_k = \frac{\exp(-\beta d(x_n, \mu_k))}{\sum_{k'} \exp(-\beta d(x_n, \mu_{k'}))}$

### Monte Carlo methods

#### The problem

We’re given: - $$P(x) = \frac{P^*(x)}{Z}$$, some probability distribution that we can’t sample from. - $$Q(x)$$, some simple probability distribution (e.g. uniform, gaussian) that we can sample from. - $$\phi(x)$$, some function of interest that we want to run over $$P$$.

We want to either be able to draw samples from $$P$$, or to calculate the value of $$\phi$$.

#### Importance sampling

$\Phi = \frac{\sum_n \frac{P^*(x_n)}{Q(x_n)} \phi(x_n)}{\sum_n \frac{P^*(x_n)}{Q(x_n)}}$

where $$\{x_n\}_N$$ are $$N$$ samples drawn from $$Q$$.

##### Choice of Q

If $$Q$$ has little overlap with $$P$$, we’ll be sampling from the wrong part of the distribution. Although we’ll still eventually converge, this can take a while and its impossible to tell that we’re converging.

#### Rejection sampling

Given a $$Q$$ and constant $$c$$ such that: $\forall x. cQ(x) \ge P^*(x)$

1. Sample $$x \sim Q$$.
2. Sample $$u \sim \text{Uniform}(0, cQ(x))$$.
3. Store $$x$$ if $$u < P^*(x)$$, reject otherwise.

This provides $$\{x\}$$ that are sampled from $$P$$.

### Markov Chain Monte Carlo (MCMC) methods

Different to Monte Carlo methods our samples are no longer independent. We draw from $$Q(x; x')$$ rather than $$Q(x)$$.

This works well when $$Q$$ and $$P$$ are very different.

#### Metropolis sampling

1. Sample $$x \sim Q(x; x_t)$$.
2. Calculate $$a = \frac{P^*(x) Q(x_t; x)}{P^*(x_t) Q(x; x_t)}$$.
3. If $$a>1$$, accept, otherwise accept with probability $$a$$.
• Accept means $$x_{t+1} = x$$.
• Reject means $$x_{t+1} = x_t$$.

Asymptotically, $$\{x\}$$ is sampled from $$P$$, but they won’t be independent.

##### Gaussian Q

$$Q(x; x_t) = \mathcal{N}(x_t, \sigma)$$. By symmetry, the $$Q$$s in $$a$$ cancel out.

#### Gibbs sampling

Assume we can sample from $$P^*(x_n | x_{!n})$$, where $$x_{!n}$$ is all elements of the hypothesis apart from $$x_n$$.

We do Metropolis sampling, but while cycling through the variables in the hypothesis.

• $$x_t \sim Q(x_{1, t}; x_{!1, t-1})$$
• $$x_{t+1} \sim Q(x_{2, t+1}; x_{!2, t})$$