How Is Compression Prediction?

压缩即预测吗？

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. 在过去的几周里，我在 Hacker News 上反复看到同一个观点：压缩即预测。最近的讨论从两个方向探讨了这一话题。

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. 3Blue1Brown 的两期视频《重构熵》（Reinventing Entropy）和《交叉熵究竟是什么？》（But what is cross-entropy?）从信源编码的极限推导出了熵和交叉熵。一篇 ngrok 的文章通过算术编码和语言模型遵循了同样的数学逻辑。Salvatore Sanfilippo 则提出了一个问题：将预测与压缩等同起来的这种做法，究竟应该推演到什么程度？

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 $x_{1:n}$ and a model $Q$, the resulting ideal payload length is $-\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. 这些解释都指向一个事实：概率模型为每一个可能的后续内容分配一个条件概率，而熵编码器将观察到的后续内容所对应的概率转换为比特。对于序列 $x_{1:n}$ 和模型 $Q$，理想的有效载荷长度为 $-\log_2 Q(x_{1:n}) = \sum_{i=1}^n -\log_2 Q(x_i\mid x_{<i})$（不计编码过程带来的额外开销）。等式右侧的量也是该模型的累积对数损失。在这种设定下，在对数损失下改进预测与减少编码载荷是同一个优化问题。

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. 这种内在的对应关系并非新事物。其基础属于经典信息论：香农将概率与最优码长联系起来；在现代语言模型出现很久之前，自适应统计压缩器就已经将条件估计转化为编码；而学习与压缩之间的关系也已通过最小描述长度（MDL）、MacKay 对信息论与推理的处理，以及 Hutter 奖等工作得到了发展。最近的语言模型成果只是在新的规模上印证了这种古老的对应关系。

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 / 目录

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. ngrok 的文章首先区分了“精简”（minification）与它所谓的“真正”压缩。精简器会删除注释、空格以及源文件中不影响执行的其他部分。生成的程序更短，但无法从中还原出原始源文件。这种操作是否无损，取决于表示形式需要保留什么。如果对象是原始的源字节序列，那么精简就是有损的。如果对象是程序的行为，且解码器可以返回任何行为等价的程序，那么对于这种不同的契约而言，保持语义的精简器就是无损的。转换过程没有变，但被表示的对象变了。

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 $x$ has been fixed, the most permissive effective descriptions are programs that produce it. After choosing a universal machine $U$, the Kolmogorov complexity of a binary string $x$ is $K_U(x) = \min { |p| : U(p)=x }$. 这种区分先于任何概率模型。在询问一个对象有多大概率出现之前，编码器和解码器必须就什么是该对象以及何时两个解码输出被视为等价达成一致。只有这样，描述的长度才有意义。一旦确定了单个对象 $x$，最宽松的有效描述就是生成该对象的程序。在选择了一个通用机器 $U$ 后，二进制字符串 $x$ 的柯尔莫哥洛夫复杂性（Kolmogorov complexity）为 $K_U(x) = \min { |p| : U(p)=x }$。

Thus, $K_U(x)$ is the length of the shortest program that outputs $x$. 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 $U$ 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 $U$ and $V$, there is a constant $c_{U,V}$ such that $|K_U(x) - K_V(x)| \le c_{U,V}$. 因此，$K_U(x)$ 是输出 $x$ 的最短程序的长度。任何可以通过算法表达的规律性都可以缩短这种描述。一个包含十亿个零的字符串有很长的字面表示，但却有一个打印十亿个零的短程序。该定义并不要求字符串是从某个信源采样得到的，也不要求根据前面的符号来预测下一个符号。机器 $U$ 是描述语言的一部分。选择不同的通用机器会改变可用的程序，从而改变复杂性的确切值。不变性定理限制了这种依赖性。对于两个固定的通用机器 $U$ 和 $V$，存在一个常数 $c_{U,V}$，使得 $|K_U(x) - K_V(x)| \le c_{U,V}$。