两部分编码

玻尔百科

核心要点

两部分编码通过首先定义一个模型，然后使用该模型高效地对数据进行编码来描述数据，其目标是最小化总描述长度。
该原则为了解学习的成本提供了一个框架，其中通用编码中的冗余代表了从数据中推断模型所必须付出的代价。
从稳定的数值算法到数据压缩和生物分类，将问题分解为“模型”和“给定模型的数据”可以带来更鲁棒、更高效的解决方案。
两部分编码统一了来自实际数据压缩、学习的统计成本以及描述复杂度的理论极限等概念。

引言

当我们试图理解或传达复杂信息时，我们本能地会寻找模式并创造叙事。这种先建立一个框架，然后填充细节的直观策略，被信息论中最强大的概念之一——两部分编码——所形式化。其核心在于，该原则断言，描述任何数据最有效的方法是将其描述分为两个部分：一个捕捉数据底层结构的模型，以及一个由该模型解释的数据本身的描述。这种方法解决了寻找最简单、最紧凑、最有意义的信息表示这一根本性挑战，这个概念被形式化为最小描述长度（MDL）原则。

本文深入探讨了这一简单思想的优雅而深远的影响。在接下来的章节中，您将发现两部分编码的核心机制并看到其实际应用。首先，“原理与机制”部分将解析其理论基础，探讨它如何实现高效的数据压缩，定义通用编码中统计学习的成本，甚至触及由柯尔莫哥洛夫复杂度描述的极限。随后，“应用与跨学科联系”部分将揭示，这一原则不仅是一个理论上的奇珍，更是一个在计算机工程、统计学乃至生物学等不同领域中反复出现，并提供鲁棒且富有洞察力的解决方案的模式。

原理与机制

你是否曾尝试向朋友解释一个复杂的概念？你不会只向他们抛出一堆原始事实。相反，你会先建立一个框架、一个通用原则或一个简单的类比。你可能会说：“你可以这样想……”一旦他们掌握了核心模型，你再补充细节。你已经直观地使用了一种两部分描述：先是模型，然后是由该模型解释的数据。这种非常自然的人类策略，正处于信息论和计算机科学中最强大的概念之一的核心：两部分编码。

这个想法极其简单而优雅。要描述一段数据，你将描述分成两部分。第一部分描述一个模型或一套规则。第二部分描述数据本身，但现在你可以利用你刚刚描述的模型来高效地完成这件事。目标是使总描述——模型加数据——尽可能短。这就是最小描述长度（MDL）原则，是对奥卡姆剃刀定律的一个优美形式化：最好的解释是那个在符合事实的前提下最简单的解释。

一个好模型的力量

让我们看看为什么我们首先要费心去建立一个模型。想象一下，你是一名深空探测器的工程师。探测器有一个传感器，报告四种状态之一：“标称”(A)、“轻微波动”(B)、“中度异常”(C)和“严重事件”(D)。一个旧系统可能会为每种状态分配一个定长编码，比如 A='00'，B='01'，C='10'，D='11'。每条消息的成本恰好是 2 比特。这很简单，但聪明吗？

假设你根据过去的经验知道，探测器几乎总是处于“标称”状态。比如说，概率是 $P(A) = 0.80$ , $P(B) = 0.10$ , $P(C) = 0.05$ , $P(D) = 0.05$ 。为一个超级常见的事件和一个非常罕见的事件使用相同数量的比特似乎是一种浪费。这时一个好的模型就派上用场了。概率分布就是我们的模型。一个现代系统可以使用最优变长编码，比如 Huffman 编码，它为更可能出现的符号分配更短的码字。对于这个分布，一个最优编码可能是 A='0'，B='10'，C='110'，D='111'。

现在，让我们看看平均成本。使用定长编码传输 100 条消息将花费 $100 \times 2 = 200$ 比特。而使用变长编码，平均来说，80 条消息将是 'A'（花费 $80 \times 1=80$ 比特），10 条是 'B'（花费 $10 \times 2=20$ 比特），5 条 'C'（花费 $5 \times 3=15$ 比特），5 条 'D'（花费 $5 \times 3=15$ 比特）。100 条消息的总成本为 $80+20+15+15=130$ 比特，平均每条消息仅 $1.3$ 比特！这代表了高达 35% 的效率提升。使用模型的力量——即使是发送方和接收方之间共享的隐式模型——是不可否认的。

让模型显式化

在深空探测器的例子中，我们假设探测器和地球指挥中心都已经知道概率。但如果他们不知道呢？如果模型需要被传达呢？这正是两部分编码真正闪耀的地方。

让我们尝试编码一个整数，比如 $n = 1000$ 。1000 的标准二进制表示是 1111101000，有 10 位。但对于一个通用系统来说，仅仅发送这 10 位是不够的。接收方如何知道这个数字在哪里结束？我们可以使用一个固定大小的槽，比如 32 位，但如果我们主要发送小数字，这就很浪费。

两部分编码提供了一个巧妙的解决方案。

第一部分（模型）： 首先，我们描述数字的大小。数字 $n=1000$ 需要 $k=10$ 位。我们需要以一种让解码器知道长度描述本身何时结束的方式来编码这个长度参数 $k=10$ （即所谓的无前缀编码）。一个巧妙的方案可能会使用 8 位来编码这个长度。
第二部分（数据）： 现在解码器知道要接收 10 位，我们只需发送 1000 的 10 位二进制表示。

总长度是 $8 + 10 = 18$ 位。注意这里的权衡。我们在“模型”（长度）上多花了 8 位，但我们获得了编码任何整数的灵活性，而无需在固定大小的容器上浪费空间。其他优雅的方案，如 Golomb-Rice 编码，也使用同样的原则，将一个数 $n$ 分成商和余数。商用一个简单的变长编码来表示，充当模型选择器；余数则用由模型决定的固定位数来编码，充当数据。

这种“模型+数据”的结构随处可见。想一想标准的压缩文件（如 .zip 文件）。它通常包含一个“头部”或“字典”（模型），解释了文件的其余部分是如何被压缩的，然后是压缩数据本身。一个两遍的 Huffman 编码方案就是一个完美的例子：第一遍分析文件以构建最优的频率表和 Huffman 树（模型）。最终的压缩文件则由对这棵树的描述和随后使用该树编码的数据组成。

学习的普适代价

当我们在事先不知道模型，而必须从我们试图压缩的数据中学习模型时，两部分编码最激动人心的应用就出现了。这被称为通用信源编码。

想象一下，你正在从一颗卫星接收一个非常长的比特序列。你怀疑信源很简单——就像一枚有偏见的硬币，以某个固定概率 $p$ 产生'1'，以概率 $1-p$ 产生'0'——但你完全不知道 $p$ 是多少。你如何压缩这个序列？你可以使用两部分编码！

第一部分（模型）： 首先，你读取整个长度为 $n$ 的序列。你数出其中'1'的数量，假设有 $k$ 个。你对未知概率 $p$ 的最佳猜测就是经验频率， $\hat{p} = k/n$ 。所以，你编码的第一部分是对 $k$ 的描述。由于 $k$ 可以是 $0$ 到 $n$ 之间的任何整数，这大约需要 $\log_2(n)$ 比特。
第二部分（数据）： 现在，你只需要告诉接收方你观察到的是 $n$ 个比特中含有 $k$ 个'1'的具体哪个序列。共有 $\binom{n}{k}$ 个这样的序列。一个理想的编码会用 $\log_2 \binom{n}{k}$ 比特来指明是哪一个。

你的描述总长度大约是 $\log_2(n) + \log_2 \binom{n}{k}$ 。这是一个关于你的数据的完整、自包含的描述。

但这里有一个深刻的问题：这种描述与一个从一开始就知道 $p$ 真实值的“精灵”所能产生的描述相比如何？精灵的编码长度将是理论最小值，即香农信息量，大约为 $n H(p)$ 比特，其中 $H(p)$ 是二元熵函数。你的编码长度与精灵的编码长度之差就是冗余——你为不知道 $p$ 而付出的代价。这是学习的代价。

有人可能会猜测这个代价是某个固定数量的比特。但经过仔细分析揭示的惊人事实是，对于一个长序列，平均冗余度不是恒定的。它随着序列长度 $n$ 的增长而增长。这个冗余度的首项是：

$R_n \approx \frac{1}{2}\log_2(n)$

这是信息论中最优美、最基本的结论之一。这个小小的公式讲述了一个深刻的故事。 $\log_2(n)$ 项的出现是因为随着我们的数据序列变长，我们需要区分的潜在模型变得更多，需要更高的精度来指定。确定我们估计的模型 $\hat{p}$ 的成本随着我们用来估计它的数据量的增加而对数增长。而系数 $\frac{1}{2}$ 呢？它并非任意。对于任何简单的单参数统计模型，它都是一个普适常数，源于估计的深层统计特性（特别是中心极限定理和费雪信息）。这是从数据中进行推断的根本且不可避免的代价。

实践中的两部分编码

这个原则不仅仅是一个理论上的奇珍；它解释了实际算法的行为。考虑基于字典的压缩器，如 Lempel-Ziv (LZ) 家族。一个简单的“在线”版本顺序读取数据，并在其最近的内存中寻找重复的字符串。它的视野有限且局部。

现在，想象一个理想化的两遍编码器。在第一遍中，它扫描整个文件，以找到最有用的、大的、重复的块来添加到其字典中。例如，如果输入是一个背靠背重复的海量文档， $S=BB$ ，一个内存缓冲区小于块 $B$ 的在线编码器将无法发现这种重复，从而无法实现压缩。但我们的两遍全局编码器会识别出 $B$ 是完美的字典条目。它的两部分输出将是：（1）块 $B$ 本身作为“模型”，然后是（2）一个极小的有效载荷，包含两个指针，指示“打印 B 两次”。这种全局视野使其能够找到一个好得多的模型，从而实现远为优越的压缩。这展示了投入比特于一个好模型以实现更短总描述的力量。

终极两部分编码：描述现实

我们可以将这个想法推向其终极的哲学极限，通过提问：一个二进制字符串 $x$ 的最短可能描述是什么？答案是它的柯尔莫哥洛夫复杂度， $K(x)$ ，定义为能生成 $x$ 并停机的最短计算机程序的长度。这个“最短程序”是 $x$ 的终极压缩版本。在某种程度上，程序本身就是模型，计算机执行它则生成了数据。

现在来看一个真正令人费解的场景。假设一个字符串 $x$ 是由一个过程生成的，该过程由一个本身是算法随机的参数 $p$ 控制——一个像 Chaitin 常数 $\Omega$ 这样的不可计算数，其数字是无模式且不可预测的。我们怎么可能描述这样一个字符串呢？

即使在这里，两部分编码也提供了答案。我们无法完美地描述模型参数 $p$ ，因为它是无限复杂的。但我们可以近似它。

第一部分（模型）： 我们描述不可计算参数 $p$ 的前 $k$ 个比特。这个描述的长度约为 $k$ 比特。
第二部分（数据）： 然后，我们使用基于这个近似模型的最优编码来编码字符串 $x$ 。

其中的奥妙在于选择最佳的精度 $k$ 。如果 $k$ 太小，我们的模型就很差，数据描述就会很长。如果 $k$ 太大，我们就在描述模型上浪费了太多比特。通过找到最小化总长度的 $k$ 值，我们得到了最佳的可能描述。而当我们进行这种优化时，在得到的字符串复杂度表达式中发现了什么？我们的老朋友， $\frac{1}{2}\log_2(n)$ 项，再次出现了。

这就是两部分编码的统一之美。它表明，同样的基本原则支配着从实际的数据压缩算法，到从数据中学习的统计成本，再到描述复杂对象的终极理论极限的一切。它是一个简单而强大的思想：要理解某事物，你必须首先找到一个关于它的正确故事。故事是模型，细节是数据。最短的完整故事才是赢家。

应用与跨学科联系

在我们穿越了两部分编码的原理与机制之旅后，人们可能会留下这样的印象：这是一个相当抽象，甚至有些哲学的概念。但是，自然界以及我们这些试图理解它的人类，有一个奇妙的习惯，那就是总能偶然发现最优雅、最有效的解决方案。两部分编码不仅仅是一个巧妙的想法；它是一个深刻而反复出现的模式，编织在科学、工程乃至我们思考和组织世界的方式之中。它是描述的通用语法。要看到这一点，我们只需看看当我们试图解决实际问题时会发生什么——从计算一个简单的统计量到跨越太空的虚空进行通信。

机器中的幽灵：在近似世界中寻找稳定性

让我们从一件看起来极其简单的事情开始：计算一组数的方差。你会记得，方差衡量的是数字的离散程度。如果你有一列数字 $x_i$ ，你首先计算它们的均值 $\mu$ ，然后计算平方差 $(x_i - \mu)^2$ 的平均值。这是一个完全合乎逻辑的两步过程。首先，你找到数据的中心；其次，你看所有数据点离那个中心有多远。

但一个聪明的数学家可能会注意到一个捷径。通过一些代数运算，方差的公式 $V = \frac{1}{n}\sum (x_i - \mu)^2$ 可以改写为 $V = \left(\frac{1}{n}\sum x_i^2\right) - \mu^2$ 。这个“单遍”公式看起来更有效率：你可以一次性计算出数字的总和与它们的平方和，而无需先计算均值。这似乎是数学优雅的胜利。

然而，当我们让计算机执行这个任务时，可能会发生奇怪的事情，特别是如果我们的数字非常大但又聚集得非常紧密——比如说，一系列围绕十亿这个值的精确测量值。计算机由于其有限的小数位数，计算出 $\frac{1}{n}\sum x_i^2$ 和 $\mu^2$ 。这两个都是巨大的数字，而且它们几乎完全相同。当计算机将它们相减时，前面的、最有效位的数字相互抵消，留下的结果主要由舍入误差构成。这种被称为“灾难性抵消”的现象，可能导致计算出的方差结果极不准确、为零，甚至是负数——对于一个衡量离散程度的指标来说，这是一个荒谬的结果！

然而，原始的“两遍”方法却能完美工作。为什么？因为它实现了两部分编码。

第一部分（模型）： 第一遍计算均值 $\mu$ 。这是我们对数据的简单模型。它是一个单一的数字，表示“数据大致在这个值附近”。
第二部分（给定模型的数据）： 第二遍计算小的偏差 $x_i - \mu$ 。这些是模型没有解释的“误差”或“意外”。通过处理这些小的、可管理的数字，计算机避免了灾难性抵消，并计算出准确的方差。

这不仅仅是一个编程技巧。这是一个深刻的教训。为了稳健地描述一组数据，你首先建立一个简单的模型（均值），然后根据数据与该模型的偏差来描述数据。幼稚的单遍方法之所以失败，是因为它将模型和数据混杂在一起，使其在现实世界的限制面前变得脆弱。

巴别塔图书馆员：压缩的艺术

同样的原则也处于数据压缩的核心。想象一下，你的任务是存储一种新发现生物的完整基因组。这是一个由四字母字母表（A、C、G、T）组成的巨大字符串。仅仅原始存储它会占用巨大的空间。我们想找到一个更短的描述。

一种方法是建立一个统计模型。我们可以计算序列中每个字母的频率。如果 'A' 出现了 $50\%$ 的时间，而其他字母很罕见，我们可以为 'A' 使用短编码，为其他字母使用长编码，就像摩尔斯电码为常见的字母 'E' 使用短的“点”一样。压缩后的消息于是有了两个部分：

第一部分（模型）： 对字母频率的描述（例如，“A=0.5，C=0.2，...”）。
第二部分（给定模型的数据）： 序列本身，使用从模型中派生出的优化编码进行编码。

我们压缩文件的总长度是模型描述的长度加上编码数据的长度。现在，我们面临一个有趣的策略选择。我们应该为整个基因组使用一个单一的统计模型吗？还是将基因组分成几个章节——比如不同的基因或调控区域——并为每个章节创建一个单独的、专门的模型会更好？

如果一个基因组有一个富含'G'和'C'的区域，而另一个区域富含'A'和'T'，那么一个针对整体的、平均化的单一模型在描述这两个区域时都会表现平平。将序列分开并使用两个特定的模型，将允许对每个部分的数据进行更有效的编码。然而，这是有代价的：我们现在必须存储两个模型描述而不是一个。

这正是现代压缩算法必须处理的权衡。一个复杂的算法只有在*信息增益——通过使用更精确的局部模型所节省的比特数——大于存储额外模型的开销成本*时，才会决定分割一个数据块。这一指导哲学，即最小描述长度（MDL）原则，是两部分编码的正式体现。它告诉我们，一组数据的“最佳”模型是那个能导致最短总描述的模型：模型 + 用该模型编码的数据。这个原则在机器学习和统计学中是防止“过拟合”的有力工具——即防止创建出过于复杂以至于最终描述的是随机噪声而非真实底层结构的模型。

名字里有什么？生命世界的结构

两部分编码模式是如此基本，以至于它甚至出现在远离计算的学科中。在信息论诞生前的几个世纪，生物学家面临着一项艰巨的任务：如何命名和组织地球上惊人多样的生命？一个为每个物种分配完全独特、任意名称的系统将是混乱且无信息的。它将是一本没有结构的字典。

由 Carl Linnaeus 形式化的解决方案是双名法——为每个物种提供一个由两部分组成的名字。想想家猫 Felis catus，或者来自一个偏远岛屿的一群假想的发光青蛙，它们的名字可能是 Lucirana nebulae（“云光蛙”）和 Lucirana canora（“悦鸣光蛙”）。这个系统是一个完美的概念性两部分编码。

第一部分（“名词”或模型）： 第一个名字，即属名（Felis，Lucirana），确立了总的类别。它就是模型。仅仅听到 Felis 这个名字，生物学家就已经了解了关于这种动物的大量信息：它很可能是一种中小型食肉哺乳动物，具有特定的牙齿和颅骨特征。模型带有预测能力。
第二部分（“形容词”或数据）： 第二个名字，即种加词（catus，nebulae），指定了该类别中的特定成员。它是将该物种与同一属中所有其他物种区分开来的“数据”，通常描述一个关键特征、栖息地或位置。

这种“名词-形容词”结构不仅仅是为了方便；它是进化现实的反映。属代表了一组共享共同祖先并因此共享一套共同特征的密切相关的物种。种加词则精确定位了生命之树那一部分上的一个独特分支。这是一种既高效又富有深刻见解的组织方案，表明两部分的思维方式对于构建复杂知识是自然的。

噪声中的信号：信息论的胜利

也许两部分原则最深刻的应用是在赋予其数学严谨性的领域：信息论。考虑将数据从深空探测器发送回地球的挑战。探测器的科学仪器产生一个连续的模拟信号。这个信号必须被转换成一和零的数字流，并通过一个充满随机噪声（如宇宙微波背景辐射）的信道传输数百万公里。我们怎么可能指望完美地重建原始信号呢？

答案在于构建一个多层次的两部分描述。首先，我们必须创建原始模拟信号的数字模型。我们以高频率对信号进行采样，然后“量化”每个样本，从一个有限集合中为其分配一个数值。我们为每个样本使用的比特数决定了我们数字模型的保真度。如果我们想要非常高的信号量化噪声比（SQNR）——一个非常干净的数字副本——我们就必须为每个样本使用更多的比特。这是我们的第一个两部分编码：一个关于信源的模型。

但是，如果这个纯净的数字流在传输过程中被噪声破坏，它就变得毫无用处。因此，我们必须用第二个保护性模型——一个旨在对抗*信道*的模型——来包裹它。我们使用前向纠错（FEC）码来添加冗余比特。这些额外的比特不属于原始数据；它们被巧妙地构建，以便即使在传输过程中有一些比特被噪声翻转，地球上的接收器也能推断出原始消息必定是什么。

整个传输过程是一个宏伟的两部分编码：一个数据的描述，嵌套在一个如何保护该数据免受噪声影响的描述之中。著名的香农-哈特利定理给出了一个惊人的结论：只要我们的总数据速率（包括纠错开销）低于一个称为“信道容量”的阈值 $C$ ，我们就可以实现无差错通信。容量本身由 $C = B \log_2(1 + S/N)$ 给出，取决于信道的带宽（ $B$ ）和信噪比（ $S/N$ ）。现代通信工程就是设计这些嵌套的两部分编码以尽可能接近那个终极速度极限的艺术，让我们能够穿过一片静电的海洋，接收来自太阳系边缘的清晰图像。

从平凡到宇宙，原则是相同的。要描述、压缩、分类或通信，最鲁棒和最有洞察力的策略是首先建立一个简单的模型——一个规则、一个基线、一个类别、一个保护码——然后在此基础上阐明具体细节。这种将可预测与不可预测、规律与实例分离的做法，是我们宇宙智能描述的标志。