📋 Changes in this PR: Channel capacity, Entropy and mutual information, Error-correcting codes, Information Theory for Data Science, Source coding
💡 Tip: If change highlighting is glitchy, add the no-preview-highlights label to this PR to disable it.

📋 Other Formats: 📝 MS Word (tracked changes) | 🎞️ Slides

📝 Preview Changes: This page has been modified in this pull request (~4% of content changed).
🎨 Highlighting Legend: Modified text (yellow) shows changed words/phrases, added text (green) shows new content, and new sections (blue) highlight entirely new paragraphs.

Source coding

1 Codes

Definition 1 (Binary code) Let \(X\) be a discrete random variable. A binary code for \(X\) assigns each value \(x\) a codeword, a finite string of binary digits, of length \(\ell(x)\).

Definition 2 (Uniquely decodable code) A binary code is uniquely decodable if every finite sequence of codewords, written one after another, can be split back into codewords in only one way.

Definition 3 (Expected length) The expected length of a binary code for \(X\), where \(X\) has probability mass function \(p(x) \stackrel{\text{def}}{=}\mathbb{P}(X=x)\), is

\[L \stackrel{\text{def}}{=}{\mathbb{E}\mathopen{}\left[\ell(X)\right]\mathclose{}} = \sum_{x} p(x) \, \ell(x).\]

Remark 1 (Short codewords for common values). A code with a small expected length gives frequent values short codewords and rare values long ones, since each value’s length counts in \(L\) in proportion to its probability.

2 The source coding theorem

Theorem 1 (Source coding theorem) Let \(X\) be a discrete random variable that takes finitely many values, at least two of them with positive probability, and let \({\mathbb{H}\mathopen{}\left(X\right)\mathclose{}}\) be its entropy with base-2 logarithms.

1. Every uniquely decodable binary code for \(X\) has expected length \(L \ge {\mathbb{H}\mathopen{}\left(X\right)\mathclose{}}\).

2. Some uniquely decodable binary code for \(X\) has expected length \(L < {\mathbb{H}\mathopen{}\left(X\right)\mathclose{}} + 1\).

3. Coding blocks of \(n\) independent copies of \(X\) at a time, some uniquely decodable binary code spends, on average, fewer than \({\mathbb{H}\mathopen{}\left(X\right)\mathclose{}} + 1/n\) binary digits per copy.

Remark 2 (Where the theorem comes from). Shannon (1948) proved that entropy is the limit on how far the output of a source can be compressed. Cover and Thomas (2006, sec. 5.3 to 5.5) prove each part of Theorem 1. For part 2, they give each value \(x\) with \(p(x) > 0\) the length \(\ell(x) = \lceil -\log_2 p(x) \rceil\), its surprisal in bits rounded up; the Kraft inequality (Cover and Thomas 2006, sec. 5.2) guarantees that a code with these lengths exists.

3 Coding with the wrong distribution

Theorem 2 (The cost of coding with the wrong distribution) Let \(X\) take finitely many values, with probability mass function \(p\), and let \(q\) be a probability mass function, possibly different from \(p\), with \(q(x) > 0\) wherever \(p(x) > 0\). Suppose a code gives each value \(x\) with \(p(x) > 0\) the length \(\ell(x) = \lceil -\log_2 q(x) \rceil\). Then its expected length \(L\) under \(p\) satisfies

\[{\mathbb{H}\mathopen{}\left(p, q\right)\mathclose{}} \le L < {\mathbb{H}\mathopen{}\left(p, q\right)\mathclose{}} + 1,\]

where \({\mathbb{H}\mathopen{}\left(p, q\right)\mathclose{}}\) is the cross-entropy of \(q\) relative to \(p\), with base-2 logarithms.

ProofProof

Proof. Every sum here runs over the values \(x\) with \(p(x) > 0\). Rounding up adds less than one binary digit, so for each such \(x\)

\[-\log_2 q(x) \le \ell(x) < -\log_2 q(x) + 1.\]

Multiply each part by \(p(x) > 0\) and sum. Since \(\sum_{x} p(x) = 1\),

\[ -\sum_{x} p(x) \log_2 q(x) \le \sum_{x} p(x) \, \ell(x) < -\sum_{x} p(x) \log_2 q(x) + 1. \]

The middle sum is \(L\), and the outer sums are \({\mathbb{H}\mathopen{}\left(p, q\right)\mathclose{}}\).

Theorem 3 (Cross-entropy is entropy plus divergence) Let \(p\) and \(q\) be probability mass functions on the values \(x_1, \ldots, x_n\), with \(q(x) > 0\) wherever \(p(x) > 0\). Write \({\mathbb{H}\mathopen{}\left(p\right)\mathclose{}}\) for the entropy of \(p\), \({\mathbb{H}\mathopen{}\left(p, q\right)\mathclose{}}\) for the cross-entropy of \(q\) relative to \(p\), and \({{D_{\mathrm{KL}}}\mathopen{}\left(p \,\Vert\, q\right)\mathclose{}}\) for the Kullback–Leibler divergence of \(q\) from \(p\), all with base-2 logarithms. Then

\[{\mathbb{H}\mathopen{}\left(p, q\right)\mathclose{}} = {\mathbb{H}\mathopen{}\left(p\right)\mathclose{}} + {{D_{\mathrm{KL}}}\mathopen{}\left(p \,\Vert\, q\right)\mathclose{}}.\]

ProofProof

Proof. Every sum here runs over the values \(x\) with \(p(x) > 0\). For every such \(x\),

\[ -\log_2 q(x) = -\log_2 p(x) + \log_2 \frac{p(x)}{q(x)}. \]

Multiply by \(p(x)\) and add over \(x\):

\[ -\sum_x p(x) \log_2 q(x) = -\sum_x p(x) \log_2 p(x) + \sum_x p(x) \log_2 \frac{p(x)}{q(x)}. \]

Reading left to right, these are \({\mathbb{H}\mathopen{}\left(p, q\right)\mathclose{}}\), \({\mathbb{H}\mathopen{}\left(p\right)\mathclose{}}\) and \({{D_{\mathrm{KL}}}\mathopen{}\left(p \,\Vert\, q\right)\mathclose{}}\).

Example 1 (Cross-entropy, entropy and divergence for a uniform code)  

Let \(p = (1/2, 1/4, 1/4)\) be the probability mass function of a three-valued random variable, and let \(q = (1/3, 1/3, 1/3)\) assign \(1/3\) to each of the three values. The code below computes the cross-entropy, the entropy and the divergence in bits.

p <- c(1 / 2, 1 / 4, 1 / 4)
q <- rep(1 / 3, 3)
cross_entropy <- -sum(p * log2(q))
shannon_entropy <- -sum(p * log2(p))
divergence <- sum(p * log2(p / q))
c(
  cross_entropy = cross_entropy,
  shannon_entropy = shannon_entropy,
  divergence = divergence
)
#>   cross_entropy shannon_entropy      divergence 
#>       1.5849625       1.5000000       0.0849625

The cross-entropy is \({\mathbb{H}\mathopen{}\left(p, q\right)\mathclose{}} = 1.585\) bits. The entropy is \({\mathbb{H}\mathopen{}\left(p\right)\mathclose{}} = 1.5\) bits, and the divergence is \({{D_{\mathrm{KL}}}\mathopen{}\left(p \,\Vert\, q\right)\mathclose{}} = 0.085\) bits. They satisfy Theorem 3: 1.5 + 0.085 = 1.585.

Remark 3 (Cross-entropy is the cost of the wrong code). Theorem 3 splits the cross-entropy into the entropy and the divergence. By Theorem 1, no uniquely decodable code averages fewer than \({\mathbb{H}\mathopen{}\left(p\right)\mathclose{}}\) bits. By Theorem 2, a code built for \(q\) costs about \({{D_{\mathrm{KL}}}\mathopen{}\left(p \,\Vert\, q\right)\mathclose{}}\) bits per value more than that. By the divergence theorem, the excess vanishes only when the code was built for \(p\) (Cover and Thomas 2006, sec. 2.6; Yeung 2008, sec. 2.5). Cover and Thomas (2006, sec. 5.4) state Theorem 2 in this form, with \({\mathbb{H}\mathopen{}\left(p\right)\mathclose{}} + {{D_{\mathrm{KL}}}\mathopen{}\left(p \,\Vert\, q\right)\mathclose{}}\) in place of \({\mathbb{H}\mathopen{}\left(p, q\right)\mathclose{}}\).

Remark 4 (Why models are fit by minimizing cross-entropy). Fitting a classifier by minimizing cross-entropy chooses the model’s distribution \(q\) so that a code built for \(q\) would spend as few bits as possible on the observed labels. By Remark 3, that pushes \(q\) toward the distribution the labels came from.

For a single labeled example, let \(e\) be the distribution that puts all its mass on the observed label. Then \({\mathbb{H}\mathopen{}\left(e\right)\mathclose{}} = 0\) (as for a coin that always lands heads), so the example’s cross-entropy loss \({\mathbb{H}\mathopen{}\left(e, q\right)\mathclose{}}\) equals \({{D_{\mathrm{KL}}}\mathopen{}\left(e \,\Vert\, q\right)\mathclose{}}\): every bit the loss reports is a wasted one.

References

Cover, Thomas M., and Joy A. Thomas. 2006. Elements of Information Theory. 2nd ed. Wiley-Interscience. https://doi.org/10.1002/047174882X.

Shannon, C. E. 1948. “A Mathematical Theory of Communication.” Bell System Technical Journal 27 (3): 379–423. https://doi.org/10.1002/j.1538-7305.1948.tb01338.x.

Yeung, Raymond W. 2008. Information Theory and Network Coding. Springer. https://doi.org/10.1007/978-0-387-79234-7.