Reinventing Entropy | Compression & Intelligence Part 1

Scientific concepts / discoveries / nature phenomena

Limits of data compression

• Investigating whether there is a fundamental lower bound on how efficiently text (or any data) can be compressed.

Information theory foundations (Shannon)

• The historical basis for information and entropy in determining compressibility.
• The idea that modern learning objectives connect back to information theory.

Mathematical equivalence: prediction ↔ compression

• Prediction (e.g., next-token prediction) is mathematically equivalent to compression.
• Training large language models using cross-entropy loss can be reframed as training an efficient text compressor.

Noiseless coding theorem / Shannon entropy

• Shannon entropy gives a theoretical minimum average number of bits per symbol needed for optimal compression.
• No encoding can beat the entropy limit, but one can get arbitrarily close asymptotically.

Encoding as probability-weighted bit lengths

For an event with probability (p):

• Information content is linked to:
  • (-\log_2(p)) (the “negative log” formula).
• In ideal compression, the bit length allocated to an event equals its information content.

Prefix-free codes

• To decode a variable-length bitstream unambiguously, the set of code words must be prefix-free (no code word is a prefix of another).
• This leads to the intuition that more probable symbols get shorter codes.

Entropy as “randomness” for optimal compressed outputs

• “Perfect compression” yields an output bitstream that is indistinguishable from random noise (uniform over bitstrings of the same length).
• Incompressibility argument: if the compressed output looks random/uniform, no further compression should be possible.

Entropy rate / language modeling

• For language, symbol probabilities depend strongly on context, so a single-letter entropy isn’t enough.
• The relevant generalization is entropy rate: average information per symbol for a stochastic process with context dependence.
• Shannon estimated English entropy as about ~1 bit per character when using long context (e.g., ~100 letters).

Cross-entropy (as used in ML training)

• A related quantity to entropy that measures how well a probability model predicts data.
• Presented as central to understanding why cross-entropy loss is used to train language models.

Historical experiments on language compressibility

• n-gram statistics: early approach; limited for longer unseen sequences.
• Shannon’s “wife Betty” guessing-game experiments to estimate predictive uncertainty/information in English.

---

Methodology / procedure outlined (compression example + entropy reasoning)

Warm-up: variable-length encoding for a robot

Instructions: Up / Down / Left / Right with probabilities:

• Up: (1/2)
• Down: (1/4)
• Left: (1/8)
• Right: (1/8)

Compare encodings:

• Naive fixed-length: (2) bits per instruction (ASCII-like inefficiency in spirit)
• Clever variable-length prefix-free code:
  • Up → 0
  • Down → 10
  • Left → 110
  • Right → 111

Compute average bits per instruction (weighted sum): [ 0.5\cdot1 + 0.25\cdot2 + 0.125\cdot3 + 0.125\cdot3 = 1.75 \text{ bits/instruction} ]

Decode rule:

• Read bits until a complete code word is formed.
• Works because the code is prefix-free.

Perfect compression → random-noise argument

• Assume equally likely compressed bitstrings of length (n).
• Then underlying messages must have probability about (1/2^n).
• Leads to the information formula:
  • bits needed (\approx -\log_2(p))

From information to entropy

For a distribution over symbols with probabilities ({p}):

• Define entropy as: [ \sum p \,(-\log_2 p) ]

• Under i.i.d. assumptions, entropy becomes the compression limit per symbol.

Language requires entropy rate

• Replace i.i.d. symbol assumptions with context-dependent probabilities.
• Estimate entropy using experiments involving prediction from human guessers.

---

Researchers / sources featured

• Claude Shannon
  • Foundations of information theory; 1948 paper A Mathematical Theory of Communication
  • Discussion of Prediction and Entropy of Printed English
• John von Neumann
  • Attribution for naming “entropy” via a story suggesting advantage in arguments and similarity to statistical mechanics terminology
• Betty Shannon
  • Shannon’s wife; used in letter-guessing experiments to estimate information in English
• Mentions of GPT
  • Specifically “a GPT that I’m running locally” as a modern reference source for estimating character probabilities (no named researcher/model provider given in subtitles)
• Mentions of GZIP
  • As a practical compression example (no specific researchers named)