gzip 可以作为语言模型吗？

不久前，我写了一篇关于没有神经网络的语言建模的文章，其中我使用无界 n-gram 模型生成了莎士比亚：没有权重，没有训练，只是计数。偶然间，我看到了《语言建模就是压缩》这篇论文，其中提到了压缩与预测的等价性：每个预测模型本质上都是一个压缩器，所有的压缩算法都是预测模型。这就引出了一个自然的问题：gzip 可以进行语言建模吗？没有神经网络，没有学习参数，什么都没有。只是操作系统附带的压缩机。您用语料库填充它，给它一个普通的文本提示，然后它通过搜索压缩效果最好的字节序列来继续该提示。以下是在小莎士比亚上启动后的一些真实的、未经编辑的输出： gzipt --corpus data/tinyshakespeare.txt --prompt $'MENENIUS:\n' --length 200 MENENIUS: '尽管一下子就可以了 MARCIUS: 现在祈祷，不要吃一点东西。拉蒂乌斯：因此，我最终还是佩服G；然后是 ag 。事实证明，有点？它不是完全连贯的文本，但它显然了解文本的一些内容。比我预期 gzip 知道的要多得多。那么压缩机如何产生这个呢？压缩就是预测 # 想想压缩器的作用。它在它“期望”的数据上花费很少的字节，在不期望的数据上花费很多字节。如果我给你一个文件，其中字母 A 重复了一百万次，你可以用一句话来描述它。另一方面，一百万个随机字节没有可利用的结构，而且根本无法压缩。这并非巧合，而是巧合。它是信息论的核心。编码符号所需的位数为 $-\log_2 p$，其中 $p$ 是模型分配给它的概率。高概率意味着很少的比特。因此，任何压缩器内部都隐藏着一个概率模型，无论是否有人写下来。 gzip 使用 DEFLATE ，它通过在 32 KiB 滑动窗口中查找与最近文本的匹配来压缩下一个字节。如果延续回显窗口中已有的内容，则 DEFLATE 将其编码为廉价的反向引用而不是文字字节。所以：gzip“预期”的延续，因为它回显窗口中已有的文本，压缩到几乎没有。这给了我们一个分数。如果我有一些上下文，并且想知道候选延续有多好，我只需测量： $$\text{score}(\text{candidate}) = \texttt{len(gzip(context + Candidate))}$$ 压缩长度越小，候选者就越“可预测”。为了准备模型，我在 gzip 的窗口中添加了一个语料库。任何看起来像语料库的延续都会压缩得较小，而任何不会压缩得较大的延续。通过波束搜索生成 # 评分是一回事；生成是另一回事。选择压缩效果最好的下一个字节的简单方法会严重失败，原因很微妙：gzip 只给出整数字节长度（没有分数）。添加一个字节通常根本不会改变压缩长度，因此许多候选者并列，信号被淹没在量化噪声中。解决方法是在提交之前先展望整个跨度。 gzipt 对字节序列运行波束搜索。在每一步中，当前上下文是：语料库窗口 + 最近的尾部（提示 + 生成的字节） 然后 gzipt 尝试可能的下一个字节。通过压缩上下文+候选并检查压缩结果占用了多少字节来对每个候选延续进行评分。循环是：提示。从用户提示作为初始文本开始继续。没有启动令牌；提示字节只是 gzip 看到的上下文的一部分。语境。显示 gzip 语料库窗口以及提示/生成文本的最新尾部。搜索。保持beam_width最可压缩的部分延续。按语料库中出现的每个字节进行扩展，按压缩长度对所有字节进行评分，然后修剪回最佳的 beam_width 。对水平字节重复此操作。犯罪。取最可压缩的全跨度（如果温度为正，则在决赛中进行采样），将其附加，然后重新开始循环。一个重要的细节是，只有生成的输出的最后一个尾部字节保留在评分上下文中。附近的 DEFLATE 代码比远处的代码匹配起来更便宜，因此，如果 gzip 可以看到其整个历史记录，最便宜的做法通常是陷入逐字循环，重复复制刚刚发出的文本。您可以在上面的动画中看到解码和评分过程，这与顶部显示的重播相同。整个事情就是一个纯标准 Python 库文件（只是 zlib ）。如果您想使用，代码位于 GitHub 上。