破解ACL论文：Gzip和KNN在文本分类中与BERT竞争

破解ACL论文：Gzip和KNN在文本分类中与BERT竞争

在今年著名的自然语言处理（NLP）ACL 会议上发表的一篇新论文在研究人员中引起了热议。该论文表明，使用 gzip 和 K-nearest neighbour (KNN) 组合对文本进行分类的性能与包括 BERT 在内的最先进模型不相上下。

在大量研究工作都围绕大型语言模型发表的时候，这种创新方法提供了一个令人耳目一新的视角。

这篇论文虽然只有十页（两栏格式），但读起来并不简单。

我决定撰写两篇系列文章来剖析这篇论文。

系列文章的第一篇--这篇文章--旨在用通俗易懂的语言来揭开论文重要发现的神秘面纱。随后的文章将深入探讨这种方法为何有效、它对未来的 NLP 研究有何影响，以及这项研究的更多细节。

文本分类的现有方法及其局限性

文本分类是 NLP 领域的经典问题之一。其目标是将给定的文本归入几个预定义的类别之一。

例如，让我们考虑一个报纸文章数据集，其中每篇文章都被分配了四个主题之一作为其目标标签：[体育、政治、娱乐、科学]。模型的任务就是能够准确地将一篇文章归入这四个类别之一。

解决机器学习中的任何分类问题通常都需要训练一个有监督的模型，如线性回归、逻辑回归、支持向量机或神经网络。

监督学习指的是一类通过在标注数据集上进行训练来学习的机器学习模型。

对于前面提到的报纸文章数据集，每篇文章都有四个主题中的一个作为目标标签。

所有有监督机器学习策略都以各种形式的数学模型为基础。这些模型包含一些未知参数，需要通过训练来学习。

实世界中的先进模型通常包含数百万个参数。

训练这些大型模型需要大量的计算时间，在生产环境中运行这些模型的成本也很高。

例如，基于深度学习的先进模型 BERT 就有 1.09 亿个参数。运行这种深度学习模型需要包括 GPU 在内的专用硬件，从而导致成本急剧增加。

用于分类的 Gzip 和 K 近邻算法

近来，NLP 研究的趋势是建立越来越大的模型。虽然这一趋势引发了 LLM 革命，但对于文本分类这样的简单问题来说，运行如此庞大的模型实在是矫枉过正。

ACL论文提出了一种更简单的方法，它与最先进的模型一样好用，而且不需要昂贵的训练过程，也不需要运行它的专用硬件。

ACL论文提出的方法非常简单，可按以下步骤描述：

对样本 t 进行分类：
1 使用 gzip 压缩 t
2 对训练数据集中的每个样本 s 进行分类：
  2.1 使用 gzip 压缩 s
  2.2 计算 gzip(s) 和 gzip(t) 之间的距离
3 根据 2.2 中计算的距离为 t 找到 k 个近邻
4 从 k 个近邻中选出多数类别作为目标标签

问题在于如何计算两个压缩文件之间的距离？

ACL论文介绍了一种名为归一化压缩距离（NCD）的距离。（计算公式点击标题见原文）

从本质上讲，NCD 是对 x 和 y 之间共享信息量的估计。如果 x 和 y 有很多共同的内容，那么它们的合并将实现更高的压缩率，从而导致较小的 NCD 值。

因此，这个方法的假设前提是：属于同一类别的文本比不同类别的文本有更多的共同特征，这是是有道理的。

压缩算法、信息论和 NCD

对于熟悉压缩算法和信息工作原理的人来说，NCD 的概念应该不难理解。不过，为了方便初学者，我们还是对其进行细分。

压缩算法的目的是将一段数据编码成尽可能少的比特，同时确保解码器能够重建原始数据。

这些算法分为两类：无损和有损。顾名思义，无损算法重建数据时不会丢失任何原始信息，而有损算法在解码过程中可能会丢失一些信息。文本压缩通常采用无损压缩，而图像、音频和视频等媒体则采用有损压缩技术。

信息

在谈到无损压缩和有损压缩时，我提到了 "信息 "一词。让我们通过一个例子来理解。

试想一枚有偏差的硬币，抛出后有 98% 的概率是正面。如果我抛掷 100 次，并通过网络传输结果，将每个正面编码为 0，每个背面编码为 1，我将需要 100 比特。由于在这条信息中，0 的概率为 98%，因此它们传递的信息并不多，而 1 则非常罕见，因此能提供更多有关实验结果的信息。我们可以干脆省略 0 的传输，只发送 1，这样就能达到 98% 的压缩率。而这正是压缩的本质，即对数据中的信息进行有效编码。

回到 NCD

既然我们已经对压缩有了更好的了解，那么让我们试着了解一下 NCD 如何帮助我们进行文本分类。

从根本上说，压缩文本就是对文本中的信息进行有效编码的过程。

• 如果两篇文本 x 和 y 属于同一类别，那么它们可能有许多共同的单词、术语、短语和模式。因此，它们的联合文档 xy 应该拥有大量信息。
• 由于 xy 信息量大，压缩后的输出应该更短，这反过来又对应于 x 和 y 之间的 NCD 更小。
• 简单地说，NCD 是 x 和 y 这两个文本之间信息距离的度量。如果 x 和 y 有许多共同元素，那么它们的共享信息就很重要，从而导致较小的 NCD。

Gzip + KNN 分类器的意义

该论文之所以意义重大，有几个原因。让我们来讨论一下。

• 首先，gzip + KNN 方法既轻便又经济，尤其是与繁琐的深度学习模型相比。
• 与需要训练的最先进模型不同，该模型是非参数模型--这意味着它不包含需要学习的参数，从而大大降低了成本。
• 参数模型通常需要在特定数据集上进行训练，在与这些数据集类似的数据上表现良好。但是，它们在处理分布外数据时可能会遇到困难--这些数据与训练模型的数据集有很大差异。压缩算法则不存在这一缺陷，因为它们与数据集无关，在非分布数据上表现一致。值得注意的是，论文表明基于 gzip + KNN 的方法在非分布数据集上的表现优于所有其他模型（如下表所示）。

Gzip + KNN 分类器的局限性

这种方法也并非充满乐趣和荣耀。这种方法也有一些局限性。

在处理大型数据集时，KNN 的速度可能会很慢。这种方法需要对每个新样本进行 KNN 计算以进行预测，虽然 KNN 不需要专门的硬件，但在数据集很大的情况下可能会比较慢。

为了执行 KNN，我们必须将整个数据保存在内存中，这可能会消耗大量数据集的资源。相反，如果我们根据需要从磁盘加载数据，可能会加剧算法的整体速度。

论文的一些潜在问题

随着这篇论文的疯传，它也经历了来自社区的大量审查。特别是，Ken Schutte 发现了论文中 KNN 实现的一个错误，他在自己的博客中对此进行了描述。他发现论文报告了前 2 个结果的准确率，而不是在 k=2 的情况下实现 KNN（如论文所述）。在进行 k=2 的实验时，他发现分类器的准确率略有下降--他只指出了四个数据集的准确率。令人吃惊的是，它从 KirundiNews 上表现最好的模型变成了效果最差的模型。

从根本上说，我们最好对论文中的数据持谨慎态度，尤其是这些数据无法按照描述精确复制。尽管如此，这种方法仍然取得了意想不到的效果。

总结

面对大量关于 LLM 和大语言模型的论文，本文采用更简单技术的方法不失为一股清流。尽管很少有人对他们报告的数据提出质疑，但我们还是希望更多的研究能关注这种简单而实用的方法。

还有一个问题没有得到解答，那就是为什么这种技术会有如此出色的表现。这篇论文没有花时间解释这个问题。