Gzip and KNN Outperforms Transformers on Text Classification
twitter.com
twitter.com
Intuitively, the key idea is that if you have two documents, x1 and x2, and a new document x, if x's statistical regularities are more similar to x1's than x2's, then len(compress(cat(x1,x))) - len(compress(x)) < len(compress(cat(x2,x))) - len(compress(x)), where "cat" is concatenation and "compress" is a compressor like gzip.
Quite literally, len(compress(cat(x1,x))) - len(compress(x)) is the number of additional bytes we need to compress the statistical regularities in x1 given the statistical regularities in x. The more similar the statistical regularities of x1 and x, the fewer additional bytes we need to compress cat(x1,x) compared to compressing only x.
The authors apply kNN on the compressed documents using a distance function called "normalized compression distance" (NCD), based on the above idea. They also discuss the relationship of NCD to information, Shannon entropy, and Kolmogorov complexity.
Remarkably, this simple, intuitive method outperforms BERT (but not necessarily larger, more recent transformers) on a variety of zero-shot classification tasks!
What if x1 is in English and x is the same document in Hebrew? Would an LLM fare better?
It uses gzip instead of a pretrained model to map samples to the feature space.
I wonder if the same can be done for images
Been playing with images lately and outputting jpegs. It’s amazing how the exact same base pixels, can generate so many different images, but the more noisy/random the images get, the bigger their jpg file size is, and conversely, the more photo-like the image, smaller the jpg size
In the case of text documents you might have similar situations, and the algorithm still works, even across languages
I guess without trying, we’ll never know
An yes, it's a win -- it could be useful in certain settings that preclude use of a DNN.
https://news.ycombinator.com/item?id=36758433
It seems the results shown are inaccurate.
[1] There just aren't any good open source tools for creating that dictionary (but see https://blog.cloudflare.com/improving-compression-with-prese...), few examples of how to use the low-level library APIs to manage dictionaries (see, e.g., deflateSetDictionary at https://www.zlib.net/manual.html#Advanced), and common utilities don't expose this functionality, either.
Also worth a look is the Large Text Compression Benchmark http://mattmahoney.net/dc/text.html - currently the world's best compressor is a neural network made by ... the renowned Fabrice Bellard, creator of ffmpeg and QEMU!
And I really dig these pages' refreshingly appropriate text-only style!
Stuff like info theory are amazing bc of this... But easy to miss if you are just working through a drier text
The crazier version for me is we have a physics professor on our team whose grounding intuitions are use ideas like black holes for mental intuition... Which does not work as well for the rest of the team
(And a lot of modern ML/AI feels very engineered and interchangeable after that, like 'metric function of the month')
You can get a lot just by reading Wikipedia and following links in each article
It’s hard to grasp the formulas and proofs sometimes, but if you only care about understanding the concepts, there are a lot of dots to connect
other folks pick it up quickly in college.
There’s been a lot of study going the other direction - using neural networks to aid the entropy prediction in classical compression algorithms - but I’m not seeing the conceptual link between how transformer/attention models work internally and how gzip works internally beyond “similar words are easy to compress”
I’m not seeing it because GPT representations are just vectors of fixed, not varying, size
One way to measure the accuracy of the model, as in it's "intelligence", is to use the predictions to turn input into all the differences from the prediction; if it's good at predicting then there will be fewer differences and it will compress it.
So seeing how well your model can compress some really big chunk of text is a very good objective measure of it's strength and compare it to the strength of others?
So a competition is born! :)
The LLM vs a static tree has some interesting oppositions. With a static tree as emitted by a compression alg will probably many times beat an LLM. As it has full knowledge of the whole stream (or in gzips version that window). So it can do things where it can look back and say 'hm the tree I spit out was not that good let me build a better one'. Where as an LLM does not really have that before hand knowledge. Using a pre-cooked LZW tree for all inputs would be more akin to using an LLM.
Now I wouldn't expect it to be particularly competitive in enwik8 or enwik9, but the question would be: is there any max-model-size and input-length for which it would right now pull ahead and become the best known or at least competitive predictor?
It is an interesting hypothesis. But my gut feeling is I would expect a LLM to perform on average worse. Competitive? Yes, but still worse. But it is something I am sure someone will test.
From the hundreds of different compressor models I have made for myself over the years. Usually believe it or not the compressed data is usually the best part. It is the decode tree/table/key/whatever that usually ends up crowding out the savings on the compressed data. In this case it would be the LLM weights or whatever the LLM spits out for the tree/decode.
this kind of "compression" is essentially "understanding through theories" where theories are like those from physics
which are a lot like stories that explain many things with just the same "characters". in this context a 'character' is more like a concept. for example an atom would fit this bill.
This is a pretty old idea, see [1,2]. Old but still very useful, like perceptrons.
[1] Li and Vitanyi. An Introduction to Kolmogorov Complexity and Its Applications.
[2] Clustering by compression. https://arxiv.org/pdf/cs/0312044
Yahoo Questions it is not top performer. It's not far fetched to think that news are written in a similar way, sometimes even partly copied, and therefore have a lot of words in common. Yahoo Questions is a forum and I'd expect there to be a greater variation of word, but the word themself have a semantic similarity.
That is, gzip is strong when many words overlap (the size increase when gzipped is smaller) but if it's semantic similarity DNN's win everyday.
The results are interesting but not as interesting as it sounds IMO.
Gzip does not support a "semantic" mode, hence it won't and does not (according to the papers metric) perform as well.
Deep learning can capture these semantic similarities.
Really nice to see that such a simple method can be very effective though. Still, people should not oversell this too much.
But given your quotation this is actually even quite intuitive IMO. What is classification of texts in a completely unknown language? What would it be to ask you to classify texts in Kirundi language? You have no idea, what they mean, the best you can do it is to find out the frequency of some words (char sequences) and try to group texts with similar frequency fingerprints together. You still would have no clue what these texts actually mean, but it might (and turns out that it does) get you somewhere better than random. Well, good news: that's exactly what gzip+KNN do, it's their bread and butter, it's literally the only thing they live for.
Reading (trying to understand, predicting the next character) these texts gets you pretty much nowhere. As a sensible human being, you wouldn't even try that, because it's just hopeless, you don't speak the language, what's more to say about that… Well, unfortunately, it's exactly what BERT does. The only thing it knows to do. We can congratulate it with getting more use out of it than a typical (and not quite typical too, I suppose) human would.
If you concatenate two similar pieces of text together they will compress better than if you concatenated two dissimilar pieces of text.
With this whole LLM craze (and they are incredible) I think a lot of people just assume we made similar advancements on the Embedding layer for pure text similarity.
Thus, all this embeddings db bonanza. But as far as I can see there is close to no evidence for that.
>When Deepmind needs semantic retrieval, they just use the largest index on the planet.
Fun fact: Query-doc similarity was done via simple TF-IDF instead of vectors. It performed better than vector retrieval when retrieve docs > 45 (they used 50).
https://blog.vespa.ai/improving-zero-shot-ranking-with-vespa...
>This case illustrates that in-domain effectiveness does not necessarily transfer to an out-of-domain zero-shot application of the model. Generally, as observed on the BEIR dense leaderboard, dense embeddings models trained on NQ labels underperform the BM25 baseline across almost all BEIR datasets.
There may come a day when such a theory takes shape and it may not be surprising that two could be related(some how) in some space where the encoding of compressed bits and bytes and compressed human expression are closely related. Indeed such a theory(entropy based? physics based?) of it might help people choose a compression algorithm over an ML one for certain types of compression over Human Expression.
Looking at the problem from a data driven pov, what are the hard negatives that cause these algorithms to behave poorly? Maybe that theory for now can only be approximated in terms of the data on the varied kinds of human text available. An example of kind of texts problem(one among many) is predicting mixtures using statistical topic models does well on academic text but has a hard time with internet text.
Is there someone out there working on such theories(besides wolfaram physics which I know of)?
https://www.newyorker.com/tech/annals-of-technology/chatgpt-...
I say subset because understanding is more general. There might be a specific compression algorithm that performs well on floating point numbers. In contrary, the brains and ANNs might be able to compress any input patterns with a worse performance.
Anyone understand that?
How is it surprising that they would not be able to beat basic statistical techniques? That seems intuitive to me.
Also the title is misleading at best.
Simplicity aside, practicality is unclear. It seems you can’t escape the need to perform at least one compression operation, per class, per inference. Eg classifying X into one of 10 categories requires a minimum of 10 string compressions. Probably more if you want better accuracy.
Remember that GPTs, for all their flaws[1], are learning the joint distribution P(X,Y) which can then generate text(or image/audio) because knowing the joint is what allows generation and prediction. But certain prediction tasks alone can be done by discriminative models that learn P(Y|X) well but these models generally have no clue(or much less of a clue) what human text actually is.
[1] which is they are in the end highly efficient and generalized stochastic 16k* NGram model on steroids which is a of the human language on the web with RHLF based lobotomy of the conditional distribution of the NGram model to say "non-offensive" things.
I'm also curious whether a lossy text compression scheme would work better. Lossy compression schemes reduce data size by eliminating certain information and accepting some degree of loss of original data quality, similar to how JPEGs work for images. Examples include simplifying language (e.g., converting British English to American English), using synonyms, abbreviating words, or even removing certain parts of the text that are deemed less important.
Of course similar text compresses more efficiently, but NNs don’t work with compressed (varying-size) representations, they work with vector representations which happen to be close in similarity space
It's also often lossy, though it depends on your input space.
For example, if you accept all text of all length, then it's lossy for sure. But if you were to accept something like "the text of any book", then it's easy to make it non-lossy.
There's only like 140-150 million books in the world, at a rough estimate, so you could easily losslessly compress all the existing books in the world to a few bytes. Even if you multiply to all variants and translations, it would still likely hash to less than 100 bytes. But you still have to store the table of books somewhere at least once, and it wouldn't be able to compress new books :P
Well, in certain specific scenarios, a perfect hash (MPHF) can be used as a "compression" method.