压缩与预测如何关联？

# 压缩即预测？| Luca Lombardo 来源：https://lukefleed.xyz/posts/compression/ 过去几周，我在 Hacker News 上反复看到相同的主张：**压缩即预测**。近期的讨论从两个方向探讨了这一观点。3Blue1Brown 的两个视频——《重新发明熵》(https://youtu.be/l6DKRf-fAAM) 和《但什么是交叉熵？》(https://youtu.be/GlYgs6v2YfU)——从信源编码的极限推导出熵和交叉熵。一篇 ngrok 文章 (https://ngrok.com/blog/compression-is-prediction) 通过算术编码和语言模型阐述了相同的数学原理。Salvatore Sanfilippo (https://www.youtube.com/watch?v=UgRiVUce9sY) 则追问：预测与压缩的这种等同性究竟可以推进到何种程度？ 这些解释汇聚于一个事实：概率模型为每一种可能的延续分配条件概率，而熵编码器将观测到延续所分配的概率转换为比特。对于序列 \(x_{1:n}\) 和模型 \(Q\)，理想负载长度为 \(-\log_2 Q(x_{1:n}) = \sum_{i=1}^n -\log_2 Q(x_i \mid x_{<i})\)。 **关于难度说明：** 本文略具技术性，假定读者熟悉本科数学和基础证明风格的论证，但无需信息论的先验背景知识（尽管相关知识可能有所帮助）。 ## 目录 打开目录 - [概率之前的压缩](#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) ## 概率之前的压缩 ngrok 文章 (https://ngrok.com/blog/compression-is-prediction) 首先区分了“代码压缩”(minification) 和它所谓的“真正压缩”。代码压缩会移除注释、空格以及源文件中不影响执行的其他部分。生成的程序更短，但无法从该程序重构出原始源文件。这种操作是否无损，取决于表示形式需要保留什么。如果目标是原始源字节序列，则代码压缩是有损的；如果目标是程序的行为，且解码器可返回任何行为等价的程序，那么语义保持的代码压缩相对于不同的契约就是无损的。转换本身未改变，改变的是被表示的对象。 这种区分先于任何概率模型。在询问一个对象的可能性之前，编码器和解码器必须就“什么算作该对象”以及“何时两个解码输出算作等价”达成一致。只有这样，描述的长度才有意义。 一旦固定了单个对象 \(x\)，最宽松的有效描述是能产生它的程序。选择通用图灵机 \(U\) 后，二进制串 \(x\) 的 Kolmogorov 复杂度 (https://en.wikipedia.org/wiki/Kolmogorov_complexity) 定义为 \(K_U(x) = \min \{ |p| : U(p) = x \}\)，即输出 \(x\) 的最短程序长度。任何可算法表达的规律性都可能缩短此描述。一个包含十亿个零的字符串有很长的字面表示，但打印十亿个零的程序却很短。该定义不要求字符串从某个信源采样，也不要求一个符号必须从其前面的符号预测得出。机器 \(U\) 是描述语言的一部分。选择不同的通用图灵机将改变可用的程序，从而改变复杂度的精确值。不变性定理限制了这种依赖性：对于两个固定的通用图灵机 \(U\) 和 \(V\)，存在常数 \(c_{U,V}\)，使得对所有字符串 \(x\)，\(|K_U(x) - K_V(x)| \leq c_{U,V}\)。该常数可能依赖于两个机器，但与 \(x\) 无关，它反映了在一种描述语言中模拟另一种所需的核心程序。因此，机器的选择是生产者和解释者共享的描述语言的一部分。 这是一个反复出现的主题的第一个实例：对象的长度仅相对于其描述之外已固定的信息才有意义。Kolmogorov 复杂度给出了单个对象有效描述的极限，但并未提供通用的压缩算法。函数 \(K_U\) 是不可计算的——没有过程能确定每个字符串的最短程序长度，更不用说构建该程序了。实用的压缩器必须限制其愿意且能够考虑的描述范围。一种限制是对象属于有限族 \(\mathcal{F}\)。一旦 \(\mathcal{F}\) 固定，无损表示必须区分该族中的每个成员。考虑定长编码 \(C : \mathcal{F} \to \{0,1\}^\ell\)，无损解码要求 \(C\) 是单射的。由于长度为 \(\ell\) 的二进制串只有 \(2^\ell\) 个，单射性意味着 \(2^\ell \geq |\mathcal{F}|\)，因此 \(\ell \geq \lceil \log_2 |\mathcal{F}| \rceil\)。通过为每个对象分配索引并用二进制表示该索引，一个约定的枚举可以达到此界限。量 \(\log_2 |\mathcal{F}|\) 是该族的**计数界限**。在研究空间接近信息论下限的表示法的**简洁数据结构** (https://en.wikipedia.org/wiki/Succinct_data_structure) 文献中，\(\log_2 |\mathcal{F}|\) 有时被称为该族的**最坏情况熵**。我将使用“计数界限”，因为其推导不假设均匀分布或任何采样过程，仅计算表示必须区分的选择数量。 族 \(\mathcal{F}\) 是编码器和解码器共享信息的一部分。如果解码器只知道对象属于更大的族 \(\mathcal{G}\)，则表示必须区分 \(\mathcal{G}\) 的成员。下界变为 \(\log_2 |\mathcal{G}|\)。只有当解码器已知晓从 \(\mathcal{G}\) 到 \(\mathcal{F}\) 的限制，或表示本身传达了该限制时，这种限制才能节省比特。因此，什么算作冗余取决于哪些选择已被排除。 Kolmogorov 复杂度和计数界限回答了同一初步问题的不同版本：前者考虑单个对象的最短有效描述，后者考虑区分固定有限族中每个对象所需的比特数。两者都无需概率分布或下一个符号的预测器。 ## 可能性具有不同的概率 计数界限将每个允许的对象视为对称的。要为某些对象分配更短的描述，我们需要一个规则来决定哪些对象获得短描述，哪些对象需要以更长的描述作为代价。概率分布提供了该规则。 设 \(\mathcal{X}\) 是可能对象的有限集合。对于每个 \(x \in \mathcal{X}\)，信源指定概率 \(P(x) = \Pr(X = x)\)，其中 \(P(x) > 0\) 且 \(\sum_{x \in \mathcal{X}} P(x) = 1\)。概率必须转换为以比特为单位的量度。如果两个独立事件以概率 \(P(x)\) 和 \(P(y)\) 发生，其联合概率为乘积 \(P(x)P(y)\)，而它们的比特开销应相加。对数实现了这种转换。事件 \(x\) 的**信息内容** (https://people.math.harvard.edu/~ctm/home/text/others/shannon/entropy/entropy.pdf) 定义为 \(I_P(x) = -\log_2 P(x)\)。概率为 \(2^{-b}\) 的事件具有 \(b\) 比特的信息内容。更可能的事件获得更小的值，因为更频繁发生的事件应分配更少的比特。 在信源产生结果之前，其信息内容未知。其期望值 \(H(P) = \sum_{x \in \mathcal{X}} P(x) I_P(x) = -\sum_{x \in \mathcal{X}} P(x) \log_2 P(x)\) 是信源的**香农熵** (https://people.math.harvard.edu/~ctm/home/text/others/shannon/entropy/entropy.pdf)。当 \(P\) 均匀时，每个对象的信息内容为 \(\log_2 |\mathcal{X}|\)，因此香农熵等于该族的计数界限。 值 \(I_P(x)\) 是从信源分布导出的理想比特开销。为了获得表示，我们需要一个二进制码 \(C : \mathcal{X} \to \{0,1\}^*\)，其码字长度 \(\ell_C(x) = |C(x)|\)。该码的期望比特数为 \(L_P(C) = \sum_{x \in \mathcal{X}} P(x) \ell_C(x)\)。信源建议的理想实数值长度为 \(-\log_2 P(x)\)，但实际的二进制码必须分配整数长度。在比较它们的平均值之前，我们需要回答两个问题：哪些整数长度集合可以构成可解码的码？一旦选择了这样的码，其长度本身能否被概率性地解释？ Kraft-McMillan 不等式回答了第一个问题，并使第二个问题成为可能。当每个码字单独呈现时，为每个对象分配不同的二进制字符串就足够了。但当码字连接时，这就不够了。连接后的比特流可能被分解为码字的两种方式，从而对应两种可能的信源序列。如果每个码字的连接只有一种分解，则该码是**唯一可解码**的 (https://en.wikipedia.org/wiki/Variable-length_code)。**前缀码** (https://en.wikipedia.org/wiki/Prefix_code) 通过要求没有码字是另一个码字的前缀来保证这一特性。其码字可放置在二叉树的叶子上。每条边贡献一个比特，叶子的深度等于其码字的长度。 设 \(m\) 至少与最长码字一样大。长度为 \(\ell_C(x)\) 的码字在深度 \(m\) 处有 \(2^{m - \ell_C(x)}\) 个后代。由于没有码字是另一个的前缀，不同码字的后代集合互不相交。完全二叉树在深度 \(m\) 处只有 \(2^m\) 个节点，因此 \(\sum_{x \in \mathcal{X}} 2^{m - \ell_C(x)} \leq 2^m\)。两边除以 \(2^m\) 得到 \(\sum_{x \in \mathcal{X}} 2^{-\ell_C(x)} \leq 1\)。这就是 **Kraft-McMillan 不等式** (https://en.wikipedia.org/wiki/Kraft%E2%80%93McMillan_inequality)。树论证对前缀码证明了这一点，而对任何唯一可解码码，即使其码字不构成前缀树的叶子，该不等式同样成立。反之，任何满足该不等式的非负整数长度集合都可以通过前缀码实现。视频《重新发明熵》(https://youtu.be/l6DKRf-fAAM?t=518) 中的图示可视化了该不等式的前缀码情况。长度为 \(\ell\) 的码字排除了其所有后代，因此占据了可用二进制编码空间的 \(2^{-\ell}\) 部分。该视频利用这一几何解释为何为一个符号分配较短的码字会为其他符号留下更少的空间；Kraft-McMillan 不等式将相同的约束精确化，并将其扩展到任何唯一可解码码。 信源概率满足一个相关的恒等式。根据信息内容的定义，\(2^{-I_P(x)} = P(x)\)，因此 \(\sum_{x \in \mathcal{X}} 2^{-I_P(x)} = \sum_{x \in \mathcal{X}} P(x) = 1\)。理想长度 \(I_P(x)\) 满足与码字长度相同的约束（且取等号）。但它们可能是分数，因此不一定能指定一个二进制码。 到目前为止，概率产生了理想的码长。对于我们论证而言，更重要的方向是其逆向：即使没有概率模型选择的码，其长度仍确定了概率权重。给定一个唯一可解码码 \(C\)，定义其 Kraft 和 \(S_C = \sum_{x \in \mathcal{X}} 2^{-\ell_C(x)}\)。Kraft-McMillan 不等式给出 \(S_C \leq 1\)。因此，量 \(2^{-\ell_C(x)}\) 的总和可能小于 1，但归一化将其转化为概率分布：\(Q_C(x) = \frac{2^{-\ell_C(x)}}{S_C}\)。求解码字长度得到 \(\ell_C(x) = -\log_2 Q_C(x) - \log_2 S_C\)。因此，码长是诱导分布 \(Q_C\) 下的信息内容，偏移了相同的非负量 \(-\log_2 S_C\)。当 Kraft 不等式紧致时（即 \(S_C = 1\)），对应关系是精确的：\(\ell_C(x) = -\log_2 Q_C(x)\)。 定长码是最简单的例子。如果每个对象获得相同的长度，那么每个值 \(2^{-\ell_C(x)}\) 相等，归一化后产生对象上的均匀分布。非均匀码诱导非均匀分布，其中较短的码字对应于更可能的对象。这并不意味着需要概率分布来定义码。上一节的计数论证在假设信源的情况下产生了定长码。这意味着一旦选择了唯一可解码码，其长度总能给出概率解释。码约束概率分配，而概率分配又建议码长。 诱导分布还证明了熵下界期望码长。在信源分布下对 \(\ell_C(x) = -\log_2 Q_C(x) - \log_2 S_C\) 求平均得到 \(L_P(C) = -\sum_{x \in \mathcal{X}} P(x) \log_2 Q_C(x) - \log_2 S_C\)。减去信源熵得到 \(L_P(C) - H(P) = \sum_{x \in \mathcal{X}} P(x) \log_2 \frac{P(x)}{Q_C(x)} - \log_2 S_C = D_{\mathrm{KL}}(P \Vert Q_C) - \log_2 S_C\)。两项都是非负的。第一项是从信源分布到码诱导分布的 KL 散度。第二项非负是因为 \(S_C \leq 1\)。因此，每个唯一可解码码都满足 \(L_P(C) \geq H(P)\)。 额外长度有两个来源：散度衡量码长与信源概率匹配的差程度；当 Kraft 不等式不紧致时，项 \(-\log_2 S_C\) 衡量未使用的编码容量。可以通过对每个概率进行