Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

78% MNIST accuracy using GZIP in under 10 lines of code

jakobs.dev

Post reply on HN
Print view View original

131–140 of 141 posts

Re: 78% MNIST accuracy using GZIP in under 10 lines of code

#131

Post by vintermann »

anitil wrote: post #113
esafak wrote: post #44

Earlier quoted context omitted.

The article emphasizes the wrong thing, in my view. The interesting part is that compression -- without learning a model -- can be used for classification. This raises the question of what other information-theoretic measures can be used; cheaper, lossy ones. To Compress or Not to Compress- Self-Supervised Learning and Information Theory: A Review https://arxiv.org/abs/2304.09355\ *

I remember seeing an example of using zip to classify languages. You take a set of documents of equal size where you know the languages, then individually concatenate and zip them with the unknown text. The smallest compressed output is likely to be the target language. I can't find the original blog, but there's a note about it here - https://stackoverflow.com/questions/39142778/how-to-determin...

Ideally, you'd take all the documents in each language, and compress them in turn with the unclassified text, to see which compresses it better. But this won't work very well with gzip, since it compresses based on a 32KB sliding window. You might as well truncate the training data for each class to the last 32KB (more or less). So to get any performance at all out of a gzip-based classifier, you need to combine a ton of individually quite bad predictors with some sort of ensemble method. (The linked code demonstrates a way of aggregating them which does not work at all).

Re: 78% MNIST accuracy using GZIP in under 10 lines of code

#132

Post by vintermann »

6510 wrote: post #129
anitil wrote: post #113

Earlier quoted context omitted.

I remember seeing an example of using zip to classify languages. You take a set of documents of equal size where you know the languages, then individually concatenate and zip them with the unknown text. The smallest compressed output is likely to be the target language. I can't find the original blog, but there's a note about it here - https://stackoverflow.com/questions/39142778/how-to-determin...

How much better would that get if you append all but one of the equal size documents? (or other combinations like 2 of the top results after using a single one)

Better, if the compressor can use all that extra context. Gzip, and most traditional general purpose compressors, can't.

It's hard to use distant context effectively. Even general purpose compression methods which theoretically can, often deliberately reset part of their context, since assuming a big file follows the same distribution throughout as in its beginning often hurts compression more than just starting over periodically.

Re: 78% MNIST accuracy using GZIP in under 10 lines of code

#133

Post by vintermann »

3abiton wrote: post #13

Didn't it turn out that authors of that paper have made mistakes that catapulted their results to the top of the benchmark charts? I thought the theory was inconsistent after that incident. 78% accuracy from just GZIP is impressive.

This is 78% accuracy from Gzip-based compression distance + KNN, which seems to be worse than any other distance measure you can think of + KNN.

Re: 78% MNIST accuracy using GZIP in under 10 lines of code

#134

Post by cqz »

montebicyclelo wrote: post #99

I tried replacing the distance function in the code with some simpler distance measures: Gzip distance: ~3 minutes, 78% accuracy Euclidean distance: ~0.5 seconds, 93% accuracy Jaccard distance * : ~0.7 seconds, 94% accuracy Dice dissimilarity * : ~0.8 seconds, 94% accuracy * after binarising the images So, as a distance measure for classifying MNIST digits, GZIP has lower accuracy, and is much more computationally de…

Very cool. I tried using PNG compression, it does actually do better, slightly:

    PNG : ~15.1 seconds, 83% accuracy
I also tried dropping in zstandard compression:

    Zstd (level=3) : ~3.5 seconds, 88% accuracy
Much faster than gzip, at least. And iff I use (x1-x2)*2 instead of x1+x2 to calculate Cx1x2 that pushes zstd up to 93% accuracy.

I'm somewhat interested in the fact that if I stack the two arrays on top of each other instead of adding them together, I get absolutely garbage performance (<20%), however as far as I can tell that actually works well when classifying strings.

Re: 78% MNIST accuracy using GZIP in under 10 lines of code

#135

Post by w-m »

cqz wrote: post #134
montebicyclelo wrote: post #99

I tried replacing the distance function in the code with some simpler distance measures: Gzip distance: ~3 minutes, 78% accuracy Euclidean distance: ~0.5 seconds, 93% accuracy Jaccard distance * : ~0.7 seconds, 94% accuracy Dice dissimilarity * : ~0.8 seconds, 94% accuracy * after binarising the images So, as a distance measure for classifying MNIST digits, GZIP has lower accuracy, and is much more computationally de…

Very cool. I tried using PNG compression, it does actually do better, slightly: PNG : ~15.1 seconds, 83% accuracy I also tried dropping in zstandard compression: Zstd (level=3) : ~3.5 seconds, 88% accuracy Much faster than gzip, at least. And iff I use (x1-x2)*2 instead of x1+x2 to calculate Cx1x2 that pushes zstd up to 93% accuracy. I'm somewhat interested in the fact that if I stack the two arrays on top of each ot…

Re garbage performance on stacking: I had tried interleaving the values (creating a 56x28 img), it dropped one percentage point of accuracy when using gzip.

Re: 78% MNIST accuracy using GZIP in under 10 lines of code

#136

Post by ActivePattern »

sundarurfriend wrote: post #26
tdr2d wrote: post #11

Obviously, the code may be elegant and compact, 78% accuracy is considered very very bad for MNIST. A dummy model written with Tensorflow easilly reaches 90% accuracy. The best models ranked at 99,87%, see the benchmark : https://paperswithcode.com/sota/image-classification-on-mnis...

The point is not to have "elegant and compact" code, this is meant to be a fun curiosity, and doing it in 10 lines is just an additional layer of challenge for the heck of it. The interesting thing is not in whether GZip can achieve SOTA, it's that it can do a decent job at all. (The interesting thing is not in whether the bear can recreate Mozart exactly, it's that it can play the piano at all.)

Yeah, it does demonstrate that you can use compression to measure similarity of two images.

But it also demonstrates that it's a pretty poor similarity measure. Something as simple as counting % of matches between the black and white pixels performs much better.

Re: 78% MNIST accuracy using GZIP in under 10 lines of code

#137

Post by TimPC »

d3w4s9 wrote: post #109
TimPC wrote: post #69

Earlier quoted context omitted.

It's a bad benchmark because it's artificially clean. It's effectively a 2d dataset with no occlusions. So nearly everything you try on it will work, and many things you try on it won't scale to typical image problems. There are good 3d datasets with more realistic examples that are still fairly simplistic compared to the state of the art large datasets, but at least give you signal that your technique is robust to c…

What's wrong with "artificially clean"? The goal of benchmarks is to compare and know whether one model is better than the other. There is never a "perfect" or "objective" benchmark. Different benchmarks may highlight advantages in certain models, which is a good thing, but there is absolutely nothing wrong with using MNIST as a dataset to give you a basic idea of how models perform.

Artificially clean gives you too many false positives. Most researchers I know these days start on CIFAR10 which is much more real world and has far fewer false positive signals. A portion of the hype in CV is a paper showing a technique works on MNIST that then fails to go anywhere on any other dataset.

Re: 78% MNIST accuracy using GZIP in under 10 lines of code

#138

Post by burnished »

IcyWindows wrote: post #125
burnished wrote: post #82

Earlier quoted context omitted.

I don't know off hand, but go take a look at the images - I would expect near 100%.

Sadly,there are several errors in the labeled data, so no one should get 100%. See https://labelerrors.com/

Just looking at a few of those I think I see them mostly as MNIST reports them? But yes, no one could get 100% due to ambiguity.

Very neat site though, I appreciate you showing that to me

Re: 78% MNIST accuracy using GZIP in under 10 lines of code

#139

Post by tripzilch »

What they mean with "“intelligence is compression”" is that there's actually an equivalence between them.

See, an "intelligence" is a predictor. Like a LLM, it predicts the next char/token depending on what it's seen before.

In order to turn this into a compressor, you store the "difference" between the predicted token and the actual token. If the predictor is good, this stream of data will be very low entropy which can be compressed with arithmetic encoding or something similar.

In the case of arithmetic encoding you get lossless compression. (additionally, because arithmetic encoding is based on probabilities (frequencies), if the predictor outputs probabilities instead of a single prediction, this can also be used to crunch the entropy)

Now look at for instance the speech codecs in GSM. They use Linear Prediction Coding, which has the same concept of using a predictor and storing the error stream. Except the latter's coefficients are rounded down, making it a form of lossy compression.

And yes, you can probably make a pretty good (lossless or perhaps even lossy, but I don't think you want that) text compressor by using an LLM to (deterministically) predict (the likelihood of) tokens and storing only the errors/differences. It should be able to outperform zip or gzip, because it can make use of language knowledge to make predictions.

There's a catch, however, which is that in the case of LLM compression you also need to store all those weights somewhere, cause you need the predictor to decode. This is always the catch with compression, there is always some kind of "model" or predictor algorithm that is implicit to the compressor. In the case of gzip it's a model that says "strings tend to repeat in patterns", which is of course "stored" (in some sense) in the gzip executable code. But with gzip we don't count the size of gzip to our compressed files either, because we get to compress a lot of files with one model. Similarly for this hypothetical LLM-text compression scheme, but you just need to compress a whole lot more text before it's worth it.

All that said, however, like many others pointed out, 78% isn't a great score for MNIST.

Then again, I also don't think that gzip compression is the best predictor for gray scale image similarity. For one if you have two pixels of grayscale values 65 and 66, gzip will see them as "different bytes", regardless of them being very similar in grayscale level. You might even be able to increase the score by thresholding the training set to BW 0/255.

Re: 78% MNIST accuracy using GZIP in under 10 lines of code

#140

Post by tripzilch »

bob1029 wrote: post #63

General purpose compressors and information distance measures have become super interesting to me while I've been investigating alternative language models. I've been playing around with an attention mechanism that combines the idea of using normalized compression distance (gzip) with discrete convolution between candidate sequences (sliding window of N bytes over each). Another round of normalization over the convol…

So, if I understand your sliding window explanation right, would the distance between two strings X and Y then be a feature vector of all the NCDs of its windows?

Kind of reminds me of auto correlation :)

Also, just a note about your NCD formula, if C(xy) is the compressed size of the concatenation of x and y, then I would recommend also trying (C(xy)+C(yx))/2 for that term, because a lot of compressors don't compress xy the same as yx, and you probably want your distance to be symmetrical.

Post reply on HN