Gzip+ kNN文本分类竟然击败Transformers：无需预训练、14行代码实现
标签：
gzip
knn
文本
| 发表时间：2023-07-17 14:27 | 作者：机器之心
出处：https://www.jiqizhixin.com/
几天前，ACL 2023 大奖公布，引起了极大的关注。
但在众多收录的论文中，一篇名为《 “Low-Resource” Text Classification: A Parameter-Free Classification Method with Compressors 》的论文开始引起大家热议。这篇论文由滑铁卢大学、 AFAIK 机构联合完成，但既不是获奖论文更不是主会议论文。- 论文地址：https://aclanthology.org/2023.findings-acl.426.pdf
- 代码地址：https://github.com/bazingagin/npc_gzip
UCSB 助理教授王威廉形容这篇论文比 95% 的 ACL 主要会议论文更有创造性，因而不明白为什么只是作为 Findings 论文被录取：这篇论文到底有何创新，得到大家如此的好评。接下来我们看看具体内容。这篇文章主要是针对文本分类任务的。文中表示文本分类作为自然语言处理（NLP）中最基础的任务之一，在神经网络的帮助下取得了显著的改进。然而，大多数神经网络对数据的需求很高，这种需求随着模型参数数量的增加而增加。在众多模型中，深度神经网络（DNN）由于准确率高，因此常常被用来进行文本分类。然而，DNN 是计算密集型的，在实践中使用和优化这些模型以及迁移到分布外泛化 (OOD) 的成本非常高。研究者开始寻求替代 DNN 的轻量级方法，使用压缩器进行文本分类开始得到大家的关注。在这一领域，已经有研究者入局，但是，已有的方法在性能上还是无法与神经网络相媲美。针对这一缺陷，本文提出了一种文本分类方法，他们将无损压缩器（如 gzip）与 k 最近邻分类器（kNN）相结合。文中表示，采用这种方法在没有任何训练参数的情况下，他们在七个分布内数据集和五个分布外数据集上的实验表明，使用像 gzip 这样的简单压缩器，他们在七个数据集中的结果有六个与 DNNs 结果相媲美，并在五个分布外数据集上胜过包括 BERT 在内的所有方法。即使在少样本情况下，本文方法也大幅超越了所有模型。网友也对这一结果感到惊讶，gzip+kNN 在文本分类任务中竟然胜过了 BERT 和其他神经网络方法。更令人意外的是这个算法没有训练过程、没有调优、没有参数 —— 有的只是 14 行代码，这就是整个算法内容。本文方法包含了一个无损压缩器、一个基于压缩器的距离度量以及一个 K 最近邻分类器。其中无损压缩器旨在通过将较短代码分配给概率更高的符号，来使用尽可能少的比特表示信息。使用压缩器进行分类源于以下两个直觉知识：1）压缩器善于捕捉规律，2）同一类别的对象比不同类别的对象具有更强的规律性。举例而言，下面的 x_1 与 x_2 属于同一类别，但与 x_3 属于不同类别。如果我们用 C (・) 来表示压缩长度，会发现 C (x_1x_2) − C (x_1) < C (x_1x_3) − C (x_1)，其中 C (x_1x_2) 表示 x_1 和 x_2 串联的压缩长度。这一直觉知识可以形式化为从柯尔莫哥洛夫（Kolmogorov）复杂度中导出的距离度量。为了测量两个对象之间共享的信息内容，Bennett 等研究人员在 1998 年发表的论文《Information distance》中将信息距离 E (x, y) 定义为将 x 转化成 y 的最短二进制程序的长度。由于柯尔莫哥洛夫复杂度的不可计算性导致了 E (x,y) 不可计算，因而 Li et al. 在 2004 年的论文《The similarity metric》中提出信息距离的归一化和可计算版本，即归一化压缩距离（Normalized Compression Distance, NCD），它利用压缩长度 C (x) 来近似柯尔莫哥洛夫复杂度 K (x)。定义如下：使用压缩长度的背后在于被压缩器最大化压缩的 x 的长度接近 K (x)。一般来说，压缩比越高，C (x) 就越接近 K (x)。研究者表示，由于主要实验结果使用 gzip 作为压缩器，所以这里的 C (x) 表示 x 经过 gzip 压缩后的长度。C (xy) 是连接 x 和 y 的压缩长度。有了 NCD 提供的距离矩阵，就可以使用 k 最近邻来进行分类。本文方法可以用如下 14 行 Python 代码实现。输入的是 training_set、test_set，两者均由（文本、标签）元组数组和 k 组成。该方法是 DNN 的简单、轻量级和通用的替代方案。简单在于不需要任何预训练或训练；轻量级在于无需参数或 GPU 资源即可进行分类；通用在于压缩器与数据类型无关，并且非参数方法不会带来潜在的假设。在实验部分，研究者选择多种数据集来研究训练样本数量、类别数量、文本长度以及分布差异对准确性的影响。每个数据集的细节如下表 1 所示。研究者将自己的方法与 1）需要训练的神经网络方法和 2）直接使用 kNN 分类器的非参数方法，这里有或没有对外部数据进行预训练。他们还对比了其他三种非参数方法，即 word2vec、预训练句子 BERT（SentBERT）和实例长度，它们全部使用 kNN 分类器。研究者在下表 3 中七个数据集上训练所有基线方法，结果显示，gzip 在 AG News、R8 和 R52 上表现得非常好。其中在 AG News 数据集上，微调 BERT 在所有方法中取得了最佳性能，而 gzip 在没有任何预训练情况下取得了有竞争力的结果，仅比 BERT 低了 0.007。在 R8 和 R52 上，唯一优于 gzip 的非预训练神经网络是 HAN。在 YahooAnswers 数据集上，gzip 的准确率比一般神经方法低了约 7%。这可能是由于该数据集上的词汇量较大，导致压缩器难以压缩。因此可以看到，gzip 在极大的数据集（如 YahooAnswers）上表现不佳，但在中小型数据集上很有竞争力。研究者在下表 4 中列出了所有基线模型的测试准确率平均值（TextLength 除外，它的准确率非常低）。结果显示，gzip 在除 YahooAnswers 之外的所有数据集上都高于或接近平均值。下表 5 中，无需任何预训练或微调，gzip 在所有数据集上优于 BERT 和 mBERT。结果表明，gzip 在 OOD 数据集上优于预训练和非预训练深度学习方法，表明该方法在数据集分布方面具有通用性。研究者还在少样本设置下比较 gzip 与深度学习方法，并在 AG News、DBpedia 和 SogouNews 上对非预训练和预训练深度神经网络进行实验。结果如下图 2 所示，在三个数据集上，gzip 的性能优于设置为 5、10、50 的非预训练模型。当 shot 数量少至 n = 5 时，gzip 的性能大幅优于非预训练模型。其中在 AG News 5-shot 设置下，gzip 的准确率比 fastText 高出了 115%。此外，在 100-shot 设置下，gzip 在 AG News 和 SogouNews 上的表现也优于非预训练模型，但在 DBpedia 上的表现稍差。研究者进一步在五个 OOD 数据集上研究了 5-shot 设置下，gzip 与 DNN 方法的比较结果。结果显示，gzip 大大优于所有深度学习方法。在相应的数据集，该方法较 BERT 准确率分别增加了 91%、40%、59%、58% 和 194%，较 mBERT 准确率分别增加了 100%、67%、40%、12% 和 130%。相关 [gzip knn 文本] 推荐：
- - 机器之心
几天前，ACL 2023 大奖公布，引起了极大的关注. 但在众多收录的论文中，一篇名为《 “Low-Resource” Text Classification: A Parameter-Free Classification Method with Compressors 》的论文开始引起大家热议.
- - 樂天笔记
本文讲述如何使用scikit-learn的KNN工具对文本进行分类. K-近邻算法，简称KNN（k-Nearest Neighbor），是一个相当简单的分类/预测算法. 其主要思想就是，选取与待分类/预测数据的最相似的K个训练数据，通过对这K个数据的结果或者分类标号取平均、取众数等方法得到待分类/预测数据的结果或者分类标号.
- - 开心平淡对待每一天。热爱生活
Nginx GZip 模块文档详见： http://wiki.nginx.org/HttpGzipModule 常用配置片段如下：. # 压缩比例，比例越大，压缩时间越长. 默认是1
gzip_types. text/css text/javascript; # 哪些文件可以被压缩
gzip_disable.
- - 标点符
最近邻(KNN)是一种非常简单、易于理解、通用性强的机器学习算法，广泛应用于金融、医疗、政治、手写检测、图像识别、视频识别等领域. 在信用评级中，金融机构会预测客户的信用评级. 在贷款支付中，银行机构将预测贷款是否安全或有风险. 在政治学中，将潜在选民分为两类，要么投票，要么不投票. 上一篇《 K-近邻算法KNN学习笔记》主要讲解的是KNN的理论内容，今天主要学习怎么用KNN进行实战.
- - bob007abc的专栏
Android 官方文档对 HttpURLConnection 的 Performance 的描述有一段：. 参见： http://developer.android.com/reference/java/net/HttpURLConnection.html. 就是说 使用HttpURLConnection发请求时，默认的request hearder里会加上 Accept-Encoding: gzip.
- - 标点符
识别验证码的方式很多，如tesseract、SVM等. 前面的几篇文章介绍了 KNN算法，今天主要学习的是如何使用KNN进行验证码的识别. 本次实验采用的是CSDN的验证码做演练，相关的接口：https://download.csdn.net/index.php/rest/tools/validcode/source_ip_validate/10.5711163911089325.
- - Tsung's Blog
網站只要能啟用 gzip 壓縮, 都能節省非常多的流量, 下述幾種與對應壓縮方式名稱對應:. apache2.x: deflate (啟用方式: a2enmod deflate). 只是壓縮啟用後, 在 IE6 會有一些問題, 有時候會出現空白頁 / JS 沒載入完. IE6 (含 IE6 以前的版本)不支援 "Transfer-Encoding: chunked", 所以會有問題..
- - 开源软件 - ITeye博客
tomcat7配置gzip没有效果 http://www.oschina.net/question/142859_70497. tomcat7里面js的mime类型改了，新版的是: web.xml. Tomcat配置改为: server.xml . Tomcat 采用的是 HTTP/1.1 的 GZIP 压缩协议，它会根据浏览器送过来的请求中的 accept-encoding 值是否包含 gzip 来判断浏览器是否支持 gzip 压缩协议，如果浏览器支持就启用 gzip 压缩，否则就不进行任何压缩处理.
- - CSDN博客推荐文章
本文主要研究基于贝叶斯算法及KNN算法的newsgroup18828文档分类器的设计及实现，数据预处理、贝叶斯算法及KNN算法实现工程源码下载见：. 对newsgroup文档集进行预处理，提取出30095 个特征词. 计算每篇文档中的特征词的TF*IDF值，实现文档向量化，在KNN算法中使用. 用JAVA实现了KNN算法及朴素贝叶斯算法的newsgroup文本分类器.
- -
大圆那些事| 文章可以转载，请以超链接形式标明文章原始出处和作者信息. GZIP、LZO、Zippy/Snappy是常用的几种压缩算法，各自有其特点，因此适用的应用场景也不尽相同. 这里结合相关工程实践的情况，做一次小结. 以下是Google几年前发布的一组测试数据（数据有些老了，有人近期做过测试的话希望能共享出来）：.
