Title: “Low-Resource” Text Classification: A Parameter-Free ClassificationMethod with Compressors URL: https://aclanthology.org/2023.findings-acl.426/ Code: https://github.com/bazingagin/npc_gzip

文本分类作为自然语言处理（NLP）中最基本的任务之一，在神经网络的帮助下得到了显著的改进。然而，大多数神经网络都是数据饥饿的，其程度随着参数的数量而增加。必须针对不同的数据集仔细调整超参数，并且文本数据的预处理（例如，分词、删除停用词等）需要根据特定的模型和数据集进行调整。尽管复杂的深度神经网络能够捕捉潜在的相关性并识别隐式模式，但对于主题分类等简单任务来说，它们可能过于致命，而轻量的替代品通常就足够了。

1. Motivation

问题：深度神经网络参数量大，需要大量的标记数据，使用成本高。

2. Contribution

• 将NCD与KNN用于主题分类
• 与未训练的DNN相当
• OOD数据集上，由于所有的方法，包括使用预训练模型的方法
• 适用于少样本数据集

3. Method

基本思想：将无损压缩器、基于压缩器的距离度量与最近邻分类器（kNN）相结合的文本分类方法。它利用压缩器捕获规则性，然后通过基于压缩器的距离度量将其转换为相似性得分。最后利用重新得到的距离矩阵，使用knn进行分类。 无损压缩器旨在通过为概率较高的符号分配较短的编码，用尽可能少的比特来表示信息 使用压缩器进行分类的原因：压缩器善于捕捉规则性；同一类别的对象比不同类别的对象具有更多的规则性。 例如，x1和x2属于同一类，与x3属于不同的类别，则C(x1x2)-C(x1)< C(x1x3)-C(x1)，C(·)代表压缩的长度。

使用压缩器进行分类的方法有两种：①基于Shannon信息理论的压缩器来估计熵；②利用压缩器来逼近Kolmogorov 复杂度和信息距离。 该论文使用第二种方法，从Kolmogorov复杂度中导出距离矩阵。Kolmogorov复杂度K(x)表示生成最短二进制程序的长度。 为了测量两个对象之间共享的信息内容，有研究者定义了信息距离E(x,y)，表示x转换为y的最短二进制程序的长度，等同于程序中两个对象之间的相似性

由于Kolmogorov复杂度不可计算，使的E(x,y)不可计算。后来有研究者提出归一化压缩距离NCD，利用压缩长度C(x)近似Kolmogorov复杂度 K(x)。 NCD的最简单理解：C(x)作为真实世界压缩器产生的长度，相当于K(x)，将E(x,y)公式转换，再添加一个归一化即可。 NCD的推导过程是根据NID(归一化信息距离)转换。

该论文方法实现的主要代码： 代码简单，理解应该没有问题。

为了研究训练集数量、类别数量、文本长度、分布差异的影响，实验使用12个数据集。 以前的研究表明，文本长度会影响压缩器的方法的准确性。

比较模型： 注意，TextLength是一个基线模型，使用数据的文本长度作为特征输入到KNN中用于文本分类，以此研究文本长度对分类的影响。

4. Result Analysis

如表3所示，在YahooAnswers数据集上，gzip的分类方法比神经网络模型方法低7%左右，因此此数据集数量大，压缩器很难进行压缩。 基于Bert的模型整体相对稳定；在数据集小而词汇表较大时，charCNN和VDCNN等基于字符的模型表现不佳。基于词的模型更擅长处理较大的词汇量。在数据文本长度较低时，NCD没有从不同类别的长度分布中受益。 gzip方法在大型数据集表现不佳，在中小数据集中表现较好。

从表5发现，gzip方法在OOD数据表现较好，说明压缩器本质上对数据类型是不可知的，非参数方法在训练过程中不会引入诱导偏差。

图2显示，随着数据集数量的增多，gzip和深度学习方法之间的准确度差异逐渐变小，W2V在精度上表现很大的差异，因为W2V是有限的单词训练的，测试集中的许多词不存在于词表中。

gzip与其他压缩器（bz2,lzma,zstandard）相比,表现较好。

压缩器的精确度和压缩比之间具有单调线性关系。对于单个压缩器，数据集越容易压缩，gzip能够达到的精度就越高。当压缩器对高度可压缩的数据集具有高压缩比时，其性能最佳，除非其压缩算法忽略了关键信息。

gzip(KNN)优于gzip(ce)。gzip(ce)在YahooAnswers数据集上表现较好。由众多在线用户创建的分散数据集YahooAnswers上，将一个类中的所有样本串联起来，使得交叉熵方法能够充分利用来自单个类的所有信息。gzip(ce)不能充分利用大型数据集。

5. Conclusion

gzip+KNN在中小型数据集表现较好。 缺点：数据集非常大时，速度非常慢；由于压缩器只能捕捉正交相似性，不能满足情感等较难分类的复杂任务。