gzip is all you need (gzip + kNN outperforms Transformers)

Overview

  1. Abstract
  2. Introduction
  3. Approach
  4. Experiment
  5. Result
  6. Limitation
  7. Reference

Abstract

“Low-Resource” Text Classification: A Parameter-Free Classification Method with Compressors (Jiang et al., ACL Findings 2023)

大多數神經網絡對data的需求很高，這種需求隨著模型參數數量的增加而增加。

在眾多模型中，Deep neural networks（DNN）由於準確率高，因此常被用來進行文本分類。然而，DNN 是計算密集型的，在實踐中使用和優化這些模型以及遷移到Out of distribution (OOD) 的成本非常高。

針對這一缺陷，這篇論文提出了一種文本分類方法，將 $gzip$ 與 $k$NN 相結合。

採用這種方法在沒有任何訓練參數的情況下，他們在七個分布內數據集和五個分布外數據集上的實驗表明，使用像 $gzip$ 這樣的簡單壓縮器，他們在七個數據集中的結果有六個與 DNNs 結果相當，並在五個 OOD datasets 上勝過包括 BERT 在內的所有方法。即使在few-shot setting下，方法也大幅超越了所有模型。

Introduction

在為DNN提供更輕替代方案的所有努力中，有幾篇論文側重於使用壓縮器進行文本分類。就是將文檔和壓縮器構建的類的語言模型之間的最小化cross entropy指示文檔的類。然而，以前的研究未能與神經網絡的準確度相匹配。

這篇論文的貢獻如下：

  1. 第一個使用NCD和$k$NN進行主題分類，使能夠使用基於壓縮器的方法在大型數據集上進行全面的實驗。
  2. 方法在七個分佈數據集中的六個上取得了與非預訓練 DNN 相當的結果。
  3. 在 OOD datasets上，表明我們的方法優於所有方法，包括 BERT 等預訓練模型。
  4. 在few-shot setting of scarce labeled data中表現出色。

Approach

作者使用Compressor進行壓縮源於兩個直覺：

  1. Compressors 擅長捕捉規律
  2. 同一類別的對象比不同類別的對象具有具有更多的規律性

For example:

下面的 $x_1$ 與 $x_2$ 屬於同一類別，但與 $x_3$ 屬於不同類別。如果我們用 $C(\cdot)$ 來表示壓縮長度，會發現 $C (x_1x_2)$ − $C (x_1)$ < $C (x_1x_3)$ − $C (x_1)$，其中 $C (x_1x_2)$ 表示 $x_1$ 和 $x_2$ 串聯的壓縮長度。

$x_1$ = Japan’s Seiko Epson Corp. has developed a l2-gram flying microbot.
$x_2$ = The latest tiny flying robot has been unveiled in Japan.
$x_3$ = Michael Phelps won the gold medal in the individual medley.

由於柯氏複雜性 (Kolmogorov complexity) 的不可計算性導致了 $E(x,y)$ 不可計算，因而 Li et al. 在 2004 年的論文《The similarity metric》中提出信息距離的歸一化和可計算版本，即（Normalized Compression Distance, NCD），它利用壓縮長度 $C(x)$ 來近似柯氏複雜性 $K(x)$。定義如下：

$$ NCD(x, y) = \frac{C(xy) - \min\{C(x), C(y)\}}{\max\{C(x), C(y)\}} $$

$x$和$y$是需要比較的兩個檔案的byte大小，$C$指壓縮，$C(xy)$就是將$xy$放進一個壓縮包中，$C(x)$就是單獨壓縮$x$以後壓縮包的byte大小，$C(y)$就是單獨壓縮y以後壓縮包的byte大小。 NCD的原理就是如果兩個二進制檔案非常相似，那麽它們被共同壓縮以後，重疊的部分就會很多，這樣壓縮以後的檔案的byte大小就會越小，假如是兩個完全相同的二進制檔案，那麽它們被壓縮以後的體積應該和單獨壓縮一個這個檔案的體積一樣大。也就是：

$$Idempotency: C(xx) = C(x) $$

由於主要實驗結果使用 $gzip$ 作為壓縮器，所以這里的 $C(x)$ 表示 $x$ 經過 $gzip$ 壓縮後的長度。
$C(xy)$ 是連接 $x$ 和 $y$ 的壓縮長度。有了 NCD 提供的距離矩陣，就可以使用 $k$NN 來進行分類。

14 lines of Python code for implement this idea…

The inputs are training_set, test_set, both consisting of an array of $(text, label)$
tuples, and $k$ as shown below.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
# Python Code for Text Classification with gzip

import gzip
import numpy as np

for (x1, _) in test_set:
    
    Cx1 = len(gzip.compress(x1.encode()))
    distance_from_x1 = []
    
    for (x2, _) in training set:
        
        Cx2 = len(gzip.compress(x2.encode()))
        x1x2 = " ".join([x1, x2])
        Cx1x2 = len(gzip.compress(x1x2.encode()))
        ncd = (Cx1x2 - min(Cx1, Cx2)) / max(Cx1, Cx2)
        distance_from_x1.append(ncd)
    
    sorted_idx = np.argsort(np.array(distance_from_x1))
    top_k_class = training_set[sorted_idx[:k], 1]
    predict_class = max(set(top_k_class), key=top_k_class.count)

Experiment

Dataset

Model

提案手法的結果與（1）需要訓練的神經網絡方法和（2）直接使用$k$NN的非參數方法進行比較，無論是否對外部數據進行pre-trained。

還對比了包括其他三種非參數方法：word2vec、SentBERT和TextLength，所有這些都使用了$k$NN。

Result

Result on in-distribution Datasets

  1. 作者在下面Table 3中七個數據集上訓練所有baseline，結果顯示，$gzip$ 在 AG News、R8 和 R52 上表現得非常好。

  2. 其中在 AG News 上，fine-tuning BERT 在所有方法中取得了最佳性能，而 gzip 在沒有任何預訓練情況下取得了有競爭力的結果，僅比 BERT 低了 0.007。

  3. 在 R8 和 R52 上，唯一優於 $gzip$ 的非預訓練神經網絡是 HAN。在 YahooAnswers上，gzip 的準確率比一般神經方法低了約 7%。這可能是由於該數據集上的詞匯量較大，導致壓縮器難以壓縮。

  4. gzip 在極大的數據集（例：YahooAnswers）上表現不佳，但在中小型數據集上很有競爭力。

在下面Table 4 中列出了所有baseline models的測試準確率平均值（TextLength 除外）。結果顯示，gzip 在除 YahooAnswers 之外的所有數據集上都高於或接近平均值。

Result on out-of-distribution Datasets

  1. 在下面Table 5中, 無需任何pre-train或fine-tuning，gzip 在所有數據集上優於 BERT 和 mBERT。

  2. 結果表明，gzip 在 OOD 數據集上優於預訓練和非預訓練深度學習方法，表示該方法在數據集分布方面具有通用性。

Few-Shot Learning

作者還在少樣本設置下比較 $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$ 大大優於所有深度學習方法。在相應的dataset，該方法比 BERT 準確率分別增加了 91%、40%、59%、58% 和 194%，比 mBERT 準確率分別增加了 100%、67%、40%、12% 和 130%。

Limitation

由於$k$NN的 computation complexity 為 $O(n^2)$，當數據集的大小變得非常大時，速度成為這個方法的限制之一。 但可以透過Multi-threads 和 multi-processes 可以大大提高速度。

Reference

  1. https://github.com/bazingagin/npc_gzip
#Natural Language Processing
gzip is all you need (gzip + kNN outperforms Transformers)
https://bominc0624.dev/2023/08/15/gzip-is-all-you-need-gzip-kNN-outperforms-Transformers/
Author
Bomin Chuang
Posted on
2023年8月15日
Licensed under