How Is Compression Prediction? | Luca Lombardo

Over the past few weeks, I have repeatedly encountered the same claim on Hacker News: compression is prediction. The recent discussion has approached it from both directions. Two 3Blue1Brown videos, Reinventing Entropy and But what is cross-entropy?, derive entropy and cross-entropy from the limits of source coding. An ngrok article follows the same mathematics through arithmetic coding and language models. Salvatore Sanfilippo asks how far the resulting identification between prediction and compression should be taken. These explanations meet at one fact. A probabilistic model assigns a conditional probability to every possible continuation, and an entropy coder converts the probability assigned to the observed continuation into bits. For a sequence x1:nx_{1:n} and a model QQ, the resulting ideal payload length is −log2Q(x1:n)=∑i=1n−log2Q(xi∣x<i)-\log_2 Q(x_{1:n}) = \sum_{i=1}^n -\log_2 Q(x_i\mid x_{<i}) up to the overhead introduced by the coding procedure. The quantity on the right is also the model’s cumulative logarithmic loss. In this setting, improving prediction under log-loss and reducing the encoded payload are the same optimization problem. None of the underlying correspondence is new. Its foundations belong to classical information theory: Shannon connected probability to optimal code length, adaptive statistical compressors turned conditional estimates into codes long before modern language models, and the relation between learning and compression has been developed through minimum description length, MacKay’s treatment of information theory and inference, and work such as the Hutter Prize. Recent language-model results just instantiate this older correspondence at a new scale. I have spent the last few years working on compression, information theory, and compressed data structures and wanted to give my two cents. I agree with the equivalence. What interests me is where it begins and where it ends. It describes the cost of encoding data under an agreed model, but a compression problem starts before that model can be applied and does not always end when the shortest bitstream has been produced. The encoder and decoder must agree on what kind of object is being represented, which alternatives remain possible, how the probability model is made available, and what the decoder must be able to do with the representation. Throughout this article, compression means lossless compression unless stated otherwise. Even within that scope, compression can be defined before introducing a sequential model. A finite family of admissible objects gives a counting lower bound without identifying a next symbol. A fixed or data-dependent code can later be interpreted probabilistically, and a distribution over serialized objects can be factored into next-symbol conditionals. That reinterpretation does not choose the family of objects, pay for information unavailable to the decoder, or enforce operations such as random access. The question is therefore not whether prediction and compression can be made mathematically equivalent. They can. The question is what must be fixed before the equivalence applies, which part of a complete representation its bit count measures, and what remains outside that measurement. A note on level. This article is a bit technical, it assumes familiarity with undergraduate mathematics and elementary proof-style arguments, but no prior background in information theory is really required, although it may help. Table of Contents Open Table of Contents Compression Before Probability Possibilities Have Different Probabilities When Compression Becomes Prediction The Source Is Unknown Fitting a Zero-Order Model Counting Sequences Instead Adding Context The Model Is Part of the Message The Shortest Bitstream May Be the Wrong Representation So, Is Compression Prediction? Compression Before Probability The ngrok article begins by distinguishing minification from what it calls “true” compression. A minifier removes comments, whitespace, and other parts of a source file that do not affect its execution. The resulting program is shorter, but the original source file cannot be reconstructed from it. Whether this operation is lossless depends on what the representation is required to preserve. If the object is the original sequence of source bytes, minification is lossy. If the object is the program’s behaviour and the decoder may return any behaviourally equivalent program, a semantics-preserving minifier is lossless relative to that different contract. The transformation has not changed. The object being represented has. This distinction precedes any probability model. Before asking how likely an object is, the encoder and decoder must agree on what counts as that object and when two decoded outputs count as equivalent. Only then does the length of a description become meaningful. Once an individual object xx has been fixed, the most permissive effective descriptions are programs that produce it. After choosing a universal machine UU, the Kolmogorov complexity of a binary string xx is KU(x)=min{∣p∣:U(p)=x}K_U(x) = \min \left\{ |p| : U(p)=x \right\} Thus, KU(x)K_U(x) is the length of the shortest program that outputs xx. Any regularity that can be expressed algorithmically may shorten this description. A string containing a billion zeros has a long literal representation but a short program that prints one billion zeros. The definition does not require the string to have been sampled from a source, and it does not require one symbol to be predicted from the symbols preceding it. The machine UU is part of the description language. Choosing a different universal machine changes which programs are available and therefore changes the exact value of the complexity. The invariance theorem bounds this dependence. For two fixed universal machines UU and VV, there is a constant cU,Vc_{U,V} such that ∣KU(x)−KV(x)∣≤cU,V\left| K_U(x)-K_V(x) \right| \leq c_{U,V} for every string xx. The constant may depend on the two machines, but not on xx. It accounts for the fixed program needed to simulate one description language in the other. The choice of machine is therefore part of the description language shared by whoever produces and interprets the program. This is the first instance of a recurring theme: the length of an object is meaningful only relative to information already fixed outside its description. Kolmogorov complexity gives a limit on the effective description of an individual object, but it does not provide a general compression algorithm. The function KUK_U is not computable. No procedure can determine the length of the shortest program for every string, much less construct that program. A practical compressor must restrict the descriptions it is willing and able to consider. One such restriction is that the object belongs to a finite family F\mathcal{F}. Once F\mathcal{F} has been fixed, a lossless representation must distinguish every member of that family from every other member. Consider a fixed-length encoding C:F⟶{0,1}ℓC : \mathcal{F} \longrightarrow \{0,1\}^{\ell} Lossless decoding requires CC to be injective. Since only 2ℓ2^\ell binary strings of length ℓ\ell exist, injectivity implies 2ℓ≥∣F∣2^\ell \geq |\mathcal{F}| and therefore ℓ≥⌈log2∣F∣⌉\ell \geq \left\lceil \log_2|\mathcal{F}| \right\rceil An agreed enumeration of F\mathcal{F} attains this bound by assigning each object an index and representing that index in binary. The quantity log2∣F∣\log_2|\mathcal{F}| is the counting bound of the family. In the literature on succinct data structures, which studies representations whose space approaches information-theoretic lower bounds, the quantity log2∣F∣\log_2|\mathcal{F}| is sometimes called the worst-case entropy of the family. I will use counting bound because its derivation assumes neither a uniform distribution nor any sampling process. It only counts the alternatives that the representation must distinguish. The family F\mathcal{F} is part of the information shared by the encoder and decoder. If the decoder knows only that the object belongs to a larger family G\mathcal{G}, then the representation must distinguish among the members of G\mathcal{G} instead. The lower bound becomes log2∣G∣\log_2|\mathcal{G}| A restriction from G\mathcal{G} to F\mathcal{F} saves bits only if the decoder already knows that restriction or if the representation communicates it. What counts as redundancy therefore depends on which alternatives have already been excluded. Kolmogorov complexity and the counting bound answer different versions of the same preliminary question. The first considers the shortest effective description of one object. The second considers the number of bits needed to distinguish every object in a fixed finite family. Neither requires a probability distribution or a next-symbol predictor. Possibilities Have Different Probabilities The counting bound treats every admissible object symmetrically. To assign shorter descriptions to some objects, we need a rule that determines which objects receive them and which objects pay with longer descriptions. A probability distribution supplies that rule. Let X\mathcal{X} be a finite set of possible objects. For each x∈Xx\in\mathcal{X}, a source specifies a probability P(x)=Pr(X=x)P(x)=\Pr(X=x) where P(x)>0P(x)>0 and ∑x∈XP(x)=1\sum_{x\in\mathcal{X}}P(x)=1 A probability must be translated into a quantity measured in bits. If two independent outcomes occur with probabilities P(x)P(x) and P(y)P(y), their joint probability is the product P(x)P(y)P(x)P(y), while their bit costs should add. The logarithm performs this conversion. The information content of an outcome xx is IP(x)=−log2P(x)I_P(x) = -\log_2P(x) An event with probability 2−b2^{-b} has information content bb bits. More probable outcomes receive smaller values because fewer bits should be allocated to events that occur more often. Before the source produces an outcome, its information content is not