Gzip+ kNN文字分類竟然擊敗Transformers：無需預訓練、14行程式碼實現

 2023-07-17 16:18:07.0

幾天前，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 之外的所有資料集上都高於或接近平均值。


在分佈外（OOD）資料集上的結果

下表 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%。

文章來源：機器之心