“Low-Resource” Text Classification: A Parameter-Free Classification Method with Compressors (2023)

Abstract: Deep neural networks (DNNs) are often used for text classification due to their high accuracy. However, DNNs can be computationally intensive, requiring millions of parameters and large amounts of labeled data, which can make them expensive to use, to optimize, and to transfer to out-of-distribution (OOD) cases in practice. In this paper, we propose a non-parametric alternative to DNNs that’s easy, lightweight, and universal in text classification: a combination of a simple compressor like gzip with a k -nearest-neighbor classifier. Without any training parameters, our method achieves results that are competitive with non-pretrained deep learning methods on six in-distribution datasets.It even outperforms BERT on all five OOD datasets, including four low-resource languages. Our method also excels in the few-shot setting, where labeled data are too scarce to train DNNs effectively.

## our approach our approach consists of a lossless compressor, a compressor-based distance metric, and a k-nearest-neighbor classifier. lossless compressors aim to represent information using as few bits as possible by assigning shorter codes to symbols with higher probability. the intuition of using compressors for classification is that (1) compressors are good at capturing regularity; (2) objects from the same category share more regularity than those from different categories. for example, x 1 below belongs to the same category as x 2 , but a different category from x 3 . if we use c(•) to represent compressed length, we will find c(x 1 x 2 ) -c(x 1 ) < c(x 1 x 3 ) -c(x 1 ) where c(x 1 x 2 ) means the compressed length of concatenation of x 1 and x 2 . in other words, c(x 1 x 2 ) -c(x 1 ) can be interpreted as how many bytes do we still need to encode x 2 based on the information of x 1 : this intuition can be formalized as a distance metric derived from @xcite . kolmogorov complexity k(x) characterizes the length of the shortest binary program that can generate x. k(x) is theoretically the ultimate lower bound for information measurement. to measure information content shared between two objects, bennett et al. (1998) define information distance e(x, y) as the length of the shortest binary program that converts x to y: as the incomputable nature of kolmogorov complexity renders e(x,y) incomputable, @xcite proposes a normalized and computable version of information distance, normalized compression distance (ncd), utilizing compressed length c(x) to approximate kolmogorov complexity k(x). formally, it's defined as follows (detailed derivation is shown in appendix a): the intuition behind using compressed length is that the length of x that has been maximally compressed by a compressor is close to k(x). generally, the higher the compression ratio, the closer c(x) is to k(x). our method can be implemented with 14 lines of python code below. the inputs are training_set, test_set, both consisting of an array of (text, label) tuples, and k as shown in listing 1. our method is a simple, lightweight, and universal alternative to dnns. it's simple because it doesn't require any preprocessing or training. it's lightweight in that it classifies without the need for parameters or gpu resources. it's universal as compressors are data-type agnostic, and non-parametric methods do not bring underlying assumptions. ## conclusions and future work in this paper, we use gzip with a compressorbased distance metric to do text classification. our method achieves an accuracy comparable to non-pretrained neural network classifiers on indistribution datasets and outperforms both pretrained and non-pretrained models on out-ofdistribution datasets. we also find that our method has greater advantages under few-shot settings. for future works, we will extend this work by generalizing gzip to neural compressors on text, as recent studies @xcite show that combining neural compressors derived from deep latent variables models with compressor-based distance metrics can even outperform semi-supervised methods for image classification.