gzip能成为语言模型吗？

# gzip 能成为语言模型吗？ 来源：https://nathan.rs/posts/gzip-lm/ 不久前我写过关于无需神经网络的语言建模（https://nathan.rs/posts/unbounded-n-gram/），当时我用无界 n-gram 模型生成了莎士比亚文本：没有权重，没有训练，只有计数。机缘巧合下，我看到了论文《语言建模即压缩》（https://arxiv.org/abs/2309.10668），文中提到了**压缩-预测等价性**： > **每个预测模型本质上都是一个压缩器，而所有压缩算法都是预测模型**。 这引出了一个自然的问题：*`gzip` 能进行语言建模吗？*1（https://nathan.rs/posts/gzip-lm/#fn:1）没有神经网络，没有学习参数，什么都没有。只有你的操作系统自带的压缩器。你用语料库“喂养”它，给它一个正常的文本提示，它会通过搜索压缩效果最好的字节序列来继续这个提示。以下是在小型莎士比亚语料上“喂养”后的真实未编辑输出： ``` gzipt --corpus data/tinyshakespeare.txt --prompt $'MENENIUS:\n' --length 200 ``` ``` MENENIUS: 'Though all at once canq MARCIUS: Pray now, nocamest thou to a morsel . LARTIUS: Hence, and I' the end admire, where G again; and after it ag . ``` 结果居然有点意思？虽然文本不太连贯，但它显然*知道*一些关于文本的东西。比我预想的 `gzip` 会*知道*的要多得多。2（https://nathan.rs/posts/gzip-lm/#fn:2）那么，一个压缩器如何能生成这样的输出呢？ ## 压缩即预测#（https://nathan.rs/posts/gzip-lm/#compression-is-prediction） 想想压缩器在做什么。它对“预期”的数据用很少的字节，对不预期的数据用很多字节。如果我给你一个重复了百万次字母 `A` 的文件，你可以用一句话描述它。而一百万个随机字节则没有可用的结构，几乎无法压缩。 这不是巧合，而是信息论的核心。编码一个符号所需的比特数是 $-\log_2 p$，其中 $p$ 是模型分配给它的概率。高概率意味着少比特数。所以任何压缩器内部都隐藏着一个概率模型，无论是否有人明确写出来。 `gzip` 使用 DEFLATE（https://en.wikipedia.org/wiki/Deflate），它通过在 32 KiB 滑动窗口中查找与最近文本的匹配来压缩后续字节。如果某个延续内容与窗口中已有的内容重复，DEFLATE 会将其编码为廉价的回引，而不是原始字节。所以： > gzip “预期”的延续内容，因为它与窗口中已有的文本重复，几乎不占用任何压缩空间。 这给了我们一个评分标准。如果我有一些上下文，想知道一个候选延续内容的好坏，只需测量： $$\text{score}(\text{candidate}) = \texttt{len(gzip(context + candidate))}$$ 压缩后的长度越小，该候选内容被“预测”的程度越高。为了“喂养”模型，我将一个语料库包含在 gzip 的窗口中。任何类似于语料库的延续内容都会压缩得很小，而不像的则会压缩得很大。 ## 通过束搜索生成#（https://nathan.rs/posts/gzip-lm/#generating-by-beam-search） 评分是一回事，生成是另一回事。简单选择压缩效果最好的单个下一个字节的方法效果很差，原因很微妙：gzip 只给出整数字节长度（没有小数）。增加一个字节通常不会改变压缩后的长度，因此许多候选内容会并列，信号被量化噪声淹没。 解决办法是 *预先* 看一段完整的跨度再做出决定。`gzipt` 在字节序列上运行束搜索（https://en.wikipedia.org/wiki/Beam_search）。每一步，当前上下文是： ``` 语料库窗口 + (提示 + 已生成文本) 的最近尾部 ``` 然后 `gzipt` 尝试可能的后续字节。每个候选延续内容通过压缩 `context + candidate` 并检查压缩结果占用的字节数来评分。 循环过程是： 1. **提示。** 从用户的提示作为初始待续文本开始。没有起始标记；提示字节只是 gzip 看到的上下文的一部分。 2. **上下文。** 让 gzip 看到语料库窗口加上提示/已生成文本的最近尾部。 3. **搜索。** 保留 `beam_width` 个最可压缩的部分延续内容。用语料库中出现的每个字节扩展每个部分，通过压缩长度对所有结果评分，并修剪回最好的 `beam_width` 个。重复进行 `horizon` 个字节。 4. **提交。** 取最可压缩的完整跨度（如果 `temperature` 为正，则在最终候选者中抽样），追加它，然后重新开始循环。 一个重要的细节是：**只有已生成输出的最后 `tail` 个字节保留在评分上下文中。** DEFLATE 对近处的匹配编码比远处的更廉价，因此如果 gzip 能看到其全部历史，最廉价的做法往往会陷入逐字循环，不断复制刚刚发出的文本。 你可以在上面的动画中看到解码和评分过程，这与顶部显示的回放相同。整个代码就是一个纯标准库 Python 文件（只用到了 `zlib`）。如果你想试试，代码在 GitHub（https://github.com/nathan-barry/gzipt）上。