🔢 mathematics

Data Compression with Stochastic Codes

本文全面概述了作为有损源压缩中传统量化与熵编码之随机替代方案的相对熵编码，旨在阐明其理论基础，同时强调其应用实践与计算层面。

原作者： Gergely Flamich, Deniz Gündüz

发布于 2026-06-09

📖 1 分钟阅读🧠 深度阅读

原作者： Gergely Flamich, Deniz Gündüz

原始论文采用 CC BY 4.0 许可（http://creativecommons.org/licenses/by/4.0/）。 ✨ 这是对下方论文的AI生成解释。它不是由作者撰写或认可的。如需技术准确性，请参阅原始论文。阅读完整免责声明

想象一下，你想给你的朋友发送一条秘密信息，但你不能直接把它写下来。相反，你们两人都拥有一本相同的巨著（比如《银河系漫游指南》）。

旧方法（“卡丹格里尔”网格法）：
在过去，你会拿一块挖了孔的硬纸板（一个“网格”），把它盖在书上，然后把你的秘密信息写在那些孔洞里。你的朋友使用与其完全相同的网格来揭示信息。

问题所在： 如果你想发送一个特定的字母，你必须寄希望于这个字母恰好出现在书中的正确位置。如果字母“Z”在书中很少见，你可能不得不等待很长时间才能找到放置它的位置，这会让你的网格变得巨大且效率低下。

新方法（相对熵编码）：
这篇论文引入了一个聪明的转折点，称为相对熵编码（Relative Entropy Coding）。与其等待书本为你提供所需的字母，不如让你和你的朋友约定使用一个共享的随机数生成器（就像一个数字化的掷骰子过程），你们两人都可以访问它。

以下是其工作原理及重要性的简单拆解：

1. 核心思想：“大海捞针”

想象一下，你想发送一个特定的数字（比如温度读数或像素颜色）。

设置： 你和你的朋友都拥有由同一个“种子”（共享随机性）生成的庞大随机数列表。
技巧： 你在列表中寻找一个看起来与你想发送的数字“足够接近”的数字。你并不发送这个数字本身，你只需向你的朋友发送该项在列表中的索引（位置编号）。
结果： 你的朋友在他们的列表中查找相同的位置，找到那个数字，于是——瞧！——他们得到了你的信息。

因为你是在从一个共享的随机列表中进行选择，所以你可以选择任何你想要的数字分布。你不会被传统压缩中那种僵化的“盒子”（量化）所束缚。

2. 为什么这意义重大？（三大超能力）

该论文认为，这种方法之所以成为游戏规则的改变者，是因为三个具体原因：

力量 1：从错误中学习（机器学习）
传统的压缩将数据强行塞入僵化的桶中。这种新方法允许“桶”呈现出由神经网络定义的灵活形状。这就像教计算机学习如何添加完美的“噪声”，以便在压缩图像时，图像看起来依然完美。论文展示了这在联邦学习（即手机在不共享私密数据的情况下训练共享 AI）中表现出色，节省了大量的带宽。
力量 2：让事物看起来真实（真实感）
当你对图像进行重度压缩时，它通常会变得模糊或出现色块。传统方法试图最小化“模糊”。而这种新方法试图最小化“违和感”。它确保即使在极低的数据量下，压缩后的图像看起来也像一张真实的照片。论文强调了使用扩散模型（生成 AI 图像背后的技术）来创建即便在极低数据规模下也能看起来极其真实的图像。
力量 3：守护秘密（隐私）
如果你想在不泄露确切数据（比如你的位置）的情况下发送数据，你会添加“噪声”。这篇论文表明，由于这种编码方法本质上是建立在添加噪声的基础之上，它自然地契合了隐私规则。你可以压缩私密数据，同时保证没有人能通过逆向工程推导出原始的精确值。

3. 缺陷：它很慢

论文非常诚实地指出了缺点。

速度问题： 在“大海”中寻找那根“针”需要时间。传统方法就像一条快速的传送带；而这种方法更像是为了找一本特定的书而在图书馆里搜寻。目前它比标准压缩要慢得多。
同步问题： 你和你的朋友必须拥有运行完全同步的、完全相同的随机数生成器。如果你们的时钟偏差哪怕只有一点点，整个系统就会崩溃。

总结

可以将相对熵编码视为一种权衡了速度与灵活性的数据压缩新方式。

旧方法： “这是一个像素。它要么是红色，要么是蓝色。我会发送‘红色’。”（快速，但僵化）。
新方法： “这是一个像素。我会查看我们共享的随机列表，找到一个感觉上接近正确颜色的数字，然后告诉你它在列表中的位置。”（较慢，但允许更智能、更真实且更具隐私性的压缩）。

论文得出结论，虽然这项技术目前对于日常用途（如观看 Netflix 流媒体）来说太慢了，但它为未来在 AI、隐私以及高质量图像压缩领域（即“看起来真实”比“加载即时”更重要）的突破打开了大门。

技术摘要：基于随机编码的数据压缩

问题陈述

本文探讨了传统有损源编码中的一个基本局限性：对**量化（quantisation）**的依赖。标准量化器将连续的源数据映射到一组离散值，这迫使重建分布成为狄拉克测度（即单点）。这种约束限制了压缩机制的灵活性，往往导致在速率、失真和“真实感”（输出分布与源统计特性的拟合度）之间的权衡处于次优状态。

作者提出了相对熵编码（Relative Entropy Coding, REC）作为一种通用的替代方案。REC 旨在构建随机编码（stochastic codes），使其能够模拟任何期望的条件分布 $P_{\hat{X}|X}$ 进行重建，而不仅仅局限于确定性的量化。其核心挑战在于，如何在保持计算可行性的同时，实现尽可能接近互信息 $I[X; \hat{X}]$ 的码长。

方法论

论文将随机编码定义为一个三元组 $(Z, \text{enc}_Z, \text{dec}_Z)$ ，其中：

$Z$ 是共享随机性（独立于输入 $X$ ）。
$\text{enc}_Z$ 是将 $X$ 映射为比特串的编码器。
$\text{dec}_Z$ 是将比特串映射回样本 $\hat{X}$ 的解码器。

目标是满足 $\text{dec}_Z(\text{enc}_Z(X)) \sim P_{\hat{X}|X}$ ，同时最小化期望码长。该码长的理论下界是互信息 $I[X; \hat{X}]$ 。

论文详细介绍了以下几种构建方法：

1. 选择采样器 (Selection Samplers)

作者将 REC 视为一个采样问题，即解码器必须从一个共享的 i.i.d. 提议序列 $\{Y_i\} \sim P_Y$ 中选择一个样本，使得所选样本遵循 $P_{\hat{X}|X}$ 。

拒绝采样 (Rejection Sampling)： 最简单的方法。编码器寻找第一个满足密度比阈值的索引 $K$ ，使得提议 $Y_K$ 被接受。随后对索引 $K$ 进行编码。然而，标准的拒绝采样通常会产生 $O(\|r\|_\infty)$ 的码长，如果密度比是无界的或很大的话，这可能比 $I[X; \hat{X}]$ 指数级大。
泊松泛函表示法 (Poisson Functional Representation / A 编码)：* 为了克服标准拒绝采样的低效性，作者描述了一种使用泊松过程来模拟提议的方法，通过对提议进行重排序以最小化索引。这种“重排序”方法（A* 编码）保证了期望码长在互信息的一个对数因子范围内，使其成为有效的相对熵码。
运行时间限制： 论文指出，对于一般的选择采样器，期望运行时间至少按 $E[\|r_X\|_\infty]$ 缩放，这在信息量较大时通常是指数级的。这使得通用的 REC 算法与熵编码相比在实际应用中速度过慢。

2. 抖动与分层量化器 (Dithered and Layered Quantisers)

为了实现计算效率，论文侧重于特定的信道结构：

抖动量化 (Dithered Quantisation)： 对于加性均匀噪声信道（ $Y = X + U$ ），作者利用“抖动恒等式”构建了一个编码器发送量化值之熵编码索引的码。这实现了 $I[X; Y] + O(1)$ 的码长和线性运行时间。
分层量化 (Layered Quantisation)： 该方法将抖动量化扩展到单峰加性噪声信道，通过将噪声表示为平移均匀分布的尺度混合（SMSU）。通过随机缩放和移动量化网格，该方法针对一维单峰分布实现了最优码长和快速运行时间。

3. 近似与高级方法

近似编码 (Approximate Codes)： 为了处理无界密度比（例如扩散模型）或减少运行时间，论文讨论了步数限制采样器 (step-limited samplers)。这些算法在超过预算时提前终止并输出近似样本。这是在精确分布匹配与多项式运行时间及可并行性之间进行的权衡。
分支定界 (Branch-and-Bound, BnB) 采样器： 对于单峰分布，BnB 搜索策略可以将期望运行时间从关于密度比的指数级降低到对数级，为分层量化器提供了一种替代方案。
信道编码： 论文提到了使用极化码（polar codes）的最新工作，作为构建具有最优运行时间的高维 i.i.d. 伯努利信道 REC 的方法。

核心贡献与应用

论文将 REC 定位为不仅是一个理论上的奇思妙想，更是学习型压缩和隐私保护数据发布的实用工具。

学习型有损压缩：
- REC 支持端到端训练压缩系统。与不可微的量化不同，REC 允许使用重参数化技巧（reparameterization trick）通过梯度下降直接优化条件分布 $P_{\hat{X}|X}$ 。
- 案例研究 (INRs)： 作者强调了贝叶斯隐式神经表示 (Bayesian Implicit Neural Representations)，其中神经网络权重被视为随机变量。系统不再量化权重，而是学习后验分布并使用 REC 对其进行采样编码。
- 案例研究 (联邦学习)： 在联邦概率掩码训练（FedPM）中，REC 通过编码所选子网络掩码的索引而非掩码本身，显著降低了通信成本，实现了高达 82 倍的比特率降低。
带有真实感约束的压缩：
- REC 允许重建结果 $\hat{X}$ 遵循符合源统计特性的分布（真实感），而不是仅仅最小化像素级失真。论文认为，量化器在处理此类问题时天生处于劣势，而 REC 可以通过利用噪声机制（如扩散模型）在给定的真实感约束下实现更低的速率。
扩散模型 (DiffC)：
- 论文提出了 DiffC，一种使用高斯扩散模型的变速率压缩方案。通过将扩散过程视为沿轨迹的一系列 REC 问题，该方法实现了“完美真实”的重建。
- 实用性： 由于由于密度比无界，精确的 REC 对于扩散模型而言是不可行的，因此作者提倡使用步数限制近似采样器，这使得在 GPU 上进行并行化成为可能，将编码时间从数小时缩短至数秒。
隐私与强化学习：
- 差分隐私： REC 提供了一个高效编码隐私化数据（例如拉普拉斯或高斯噪声机制）的框架，同时保持隐私保证。
- 远程强化学习： REC 允许控制器传输一个标识代理策略中候选动作的短索引，而非动作本身，从而显著降低了通信开销。

结果与主张

理论边界： 论文建立了一个结论：虽然通用的 REC 算法具有 $I[X; \hat{X}] + \log(I[X; \hat{X}] + 1)$ 的码长下界，但特定的构建方法（如抖动量化器）可以达到 $I[X; \hat{X}] + O(1)$ 。
计算权衡： 作者明确指出通用 REC 的计算成本很高。选择采样器的运行时间通常是关于信息量的指数级的。然而，对于特定分布（如单峰噪声、带近似的扩散模型），存在高效算法。
经验性能： 论文引用了相关工作的实验结果显示：
- 在联邦学习（FedPM）中实现了高达 82 倍的比特率降低。
- 与直接传输动作或奖励相比，在远程强化学习中实现了 12 倍和 41 倍的降低。
- 在 GPU 上成功实现了 DiffC，将编码时间从数小时缩短至数秒。

重要性与局限性

重要性：
论文认为 REC 不仅改变了有损压缩的范式——从“选择一个量化器并分析其误差”转变为“选择一个期望的重建分布并实现它”。这种灵活性对于需要真实感（如生成式 AI）和隐私（输出分布比点对点准确性更重要）的现代应用至关重要。它架起了信息论与机器学习之间的桥梁，使可微压缩流水线成为可能。

局限性：
作者承认有两个主要障碍阻碍了广泛采用：

速度： 通用 REC 算法明显慢于基于量化的方法。虽然针对特定分布存在专门算法，但实现通用的快速 REC 算法仍是一个开放性问题。
同步： REC 依赖于共享随机性（例如 PRNG 种子）。在编码器和解码器之间保持完美的同步是一项工程挑战；同步失效会导致灾难性的失败。

结论：
论文总结道，REC 是一个新兴领域，具有深刻的理论优雅性和实际潜力，特别是在学习型压缩和隐私保护方面。然而，其目前的实际效用受限于计算复杂度和工程开销，开发快速、专用用途的 REC 算法是未来的关键研究方向。