一种更高效的基于压缩的主题分类实现
最近发表的题为“低资源”文本分类：一种无参数分类方法与压缩器 [1] 的论文在最近几天引起了很多公众的关注。他们的关键发现是，使用简单的想法，即如果两个文本文档可以压缩成更小的文件大小，那么它们在某些情况下可以超越像BERT这样的大型语言模型(尽管对于他们的结果的有效性存在争议，请参阅这篇博文和这个包括作者回复的讨论)。
他们方法的主要思想是，根据Bennet等人定义的文档之间的“信息距离”，作为文本分类中使用的好的距离度量。由于信息距离本身是不可计算的，他们用标准化压缩距离(NCD) [3] 进行近似，NCD使用gzip等“真实数据”压缩器估计信息距离。NCD具有这样的特性，即更好的压缩器(即具有更好压缩比的压缩器)将允许更好地估计真实信息距离。
因此，可以预期较好的压缩器将在分类中实现更好的性能。但是，他们无法通过实验证实这一点；论文中考虑的最佳压缩器bz2在准确性方面表现不如gzip。他们解释说：“[…]bz2使用的Burrows-Wheeler算法通过在压缩期间对字符进行排列来忽略字符顺序的信息” [1, p.6817]。这意味着仅通过压缩无法解释他们的发现，而与字符顺序有关。
这让我想知道：他们的结果有多少是由于压缩，有多少是由于比较两个文档之间的字符串？
为了探究这个问题，我将他们的结果与两种替代方法进行比较：(1)一种仅依赖于替换重复字符串的简单压缩器，和(2)一种在查询文档和属于某个主题的所有文档之间显式进行子字符串匹配的算法。
第一个消融研究：LZ4是否能胜任？压缩算法gzip基于DEFLATE，它使用LZ77和Huffman编码对数据进行压缩。让我们更详细地看看这两种算法，并思考将其应用于我们的用例时意味着什么。
在压缩过程中，LZ77在先前看到的数据上使用一个滑动窗口。如果一个字符字符串重复出现，存储对字符字符串的第一次出现的引用，而不是字符串本身。因此，如果我们将两个连接的文档的长度作为距离度量，如果它们在滑动窗口(通常为32KB)的大小范围内具有更多重叠的子字符串，那么文档之间的距离将更近。
Huffman编码进一步压缩结果文本：它不是为每个字符使用8位，而是用较少的位数表示频繁出现的字母，用更多的位数表示不经常出现的字母。如果我们将Huffman编码应用于连接的文档，如果它们使用相似频率的字符，压缩后的两个文档将更小。
人们预期匹配的子字符串对于主题分类比相似字符频率更重要。因此，我通过使用LZ4算法 [4] 进行压缩 (基本上是LZ77，但在python中提供了快速实现)来进行消融研究。由于LZ4的压缩比远低于gzip，他们的解释将暗示LZ4的性能不如gzip。然而，如果主要的问题是子字符串匹配，那么LZ4的性能将与gzip一样好。
一种更明确的算法为了更进一步，我实现了一种简单的算法，它显式地进行子字符串匹配：它将文档分配给具有最相似子字符串的主题(这里的子字符串是字符级n-gram)。它的工作方式如下：
文本编码：1. 提取文本中所有的字符n-gram，其中5≤n≤50。2. 对提取的n-gram，使用`hash(n_gram) % int(10e8)`在python中计算一个8位哈希码(因为我想控制要跟踪的不同事物的数量)。3. 用集合来跟踪这些哈希码(因此丢失有关给定代码出现次数的信息)。
训练：1. 为给定主题的每个文本计算哈希码集合。2. 取并集以获得在该主题中出现的哈希码集合。
推理：1. 对于某个查询文本，计算其哈希化n-gram的集合。2. 对于训练过程中遇到的每个主题，计算主题集合与查询集合之间的交集大小。3. 将查询文本分配给与交集最大的主题。
实验和结果我在100-shot设置下进行了gzip、lz4和哈希n-gram算法的比较，并进行了5次运行，如他们的论文所述。对于这三种方法，我遵循它们的实验设置以重现他们报告的结果（同样，这可能导致了可能夸大的准确度测量）。代码可以在github上找到。
您可以在下表中看到来自torchtext的三个数据集（AG_NEWS [5]、DBpedia [6]和YahooAnswers [5]）的性能：
我们可以看到，在所有三个考虑的数据集上，lz4和哈希n-gram的性能优于gzip，其中哈希n-gram算法在3个数据集中有2个最佳。但它仍然无法与BERT相竞争，在AG_NEWS上的性能为0.82，在DBpedia上接近1，这些数据是根据他们的论文在100-shot设置下得出的。
这些结果具有重要的实际意义：在我们的实验中，基于lz4的算法运行速度大约比基于gzip的算法快10倍。而更重要的是，哈希n-gram算法甚至在推理时改进了计算复杂性：您只需将查询文档与每个主题集进行比较，而不是与文本语料库中的每个其他文档进行比较。
我们从中学到了什么？我的结果表明，gzip令人印象深刻的性能报告的驱动力可以归因于他们的方法隐式地在文档之间比较字符级n-gram。这一发现使得可以使用lz4等更快的压缩器而无需损失性能。此外，甚至可以重写他们的算法，使得推理时间的计算复杂度与数据集大小保持恒定，使得他们的方法更接近在大型数据集上的实际应用。如果您确实希望在实践中使用它，我已经在这里开始实现了一个遵循scikit-learn API的建议算法。
唯一剩下的问题是，为什么这比TF-IDF方法表现得更好，后者也比较文档之间的单词？
也许考虑字符级n-gram在某些任务上表现更好，而不是将文本分割为单个单词。但可能更重要的是，这种方法给予所有n-gram相等的权重，而不考虑它们的出现次数。这意味着它非常重视所谓的长尾（即罕见）信息，显然对于某些文本任务（如主题检测）很重要。请注意，变形器网络对建模这种长尾信息的能力并不太好（有关证据，请参见例如[5]），因此这些非常简单的方法是衡量您的百万参数模型的一个非常有趣的基准。
参考文献[1] Z. Jiang, M. Yang, M. Tsirlin, R. Tang, Y. Dai, J. Lin. “Low-Resource” Text Classification: A Parameter-Free Classification Method with Compressors (2023), ACL 2023[2] C. H. Bennett, P. Gács, M. Li, P. MB Vitányi, and W. H. Zurek, Information distance (1998), IEEE Transactions on information theory[3] M. Li, X. Chen, X. Li, B. Ma, and P. Vitányi, The similarity metric (2004), IEEE transactions on Information Theory[4] N. Kandpal, H. Deng, A. Roberts, E. Wallace, C. Raffel, Large Language Models Struggle to Learn Long-Tail Knowledge (2022), arxiv.org/abs/2211.08411
感谢Joel Niklaus和Marcel Gygli的讨论和反馈。