A Parameter-Free Classification Method with Compressors

Intuitively, the key idea is that if you have two documents, say, x1 and x2, and a target document y, if x1's statistical regularities are more similar to y's than to x2's, then len(compress(x1+y)) - len(compress(y)) < len(compress(x2+y)) - len(compress(y)), where "+" means concatenation and "compress" is a compression program like gzip.

len(compress(x1+y)) - len(compress(y)) is, quite literally, the number of additional bytes we need to compress the statistical regularities in x1 given the statistical regularities in y. The more similar the statistical regularities between x1 and y, the fewer bytes we need to compress them together.

The authors use kNN using a distance function called normalized compression distance (NCD), based on the above idea. Remarkably, this simple, intuitive method outperforms BERT on a variety of zero-shot classification tasks!

https://arxiv.org/abs/2212.09410