8 ms·
78% MNIST accuracy using GZIP in under 10 lines of code
- petters 3y agoI wonder why you started with a code-golfed version? That seems original to the main point of the post
- seeknotfind 3y agooriginal -> orthogonal? I like short code! It's like a joke "this is so easy, 10 loc" :)
- hinkley 3y agoThe internet has turned into a game of “is it him or is it autocorrect?” I can’t count how many times I’ve looked up at a line of text to spot check it, type in a couple more letters, hit save without looking, and find later that I sound like I’m having a stroke. Never mind the times I’ve simply forgotten to look. Yes that’s a word, stop trying to replace it. (Five minutes ago I had to type “laissez-faire” three times. Yesterday it turned “understanding” into god knows what. And if iOS doesn’t stop adding apostrophes to “its” I’m gonna fuckin lose my shit)
- burnished 3y agoI ended up turning auto correct off due to iOS being more aggressive with its corrections than my previous android phones (both of which frequently fail to recognize common words, and maybe both but certainly the android was absurdly brand aware).
- hinkley 3y ago> brand aware I got so tired of Mathematica italicizing its own name when I was in college so I figured out how to type it in two phases so it wouldn’t. It was my tiny little petty victory over Stephen Wolfram ruining math for me. I know that struggle.
- hinkley 3y ago[flagged]
- telotortium 3y agoMNIST (and OCR) are acronyms that are so well-known to anyone who has taken any kind of intro to ML class that there's no more need to define them in a short blog post than there would be for us to define HTML. I learned about MNIST in 2008, and I was just taking a class on numerical methods as a physics major in Matlab where MNIST was just one project.
- hinkley 3y agoThis isn’t a forum about machine learning, though. It’s a general forum of geek news. I could talk to you all day about compression. Gzip plus MNIST rings no bells.
- telotortium 3y agoFortunately MNIST is a pretty distinctive Google search term. At most you would need to search for (MNIST machine learning).
- hinkley 3y agoAre you running google searches on https://news.ycombinator.com/news https://news.ycombinator.com/news before clicking on stuff? Or expecting an executive summary. I think you can guess which one I’m doing. And which one I believe is normal human behavior.
- itishappy 3y agoNo need to guess, you requested a summary: > you’ve missed the most important hyperlink: what the fuck is a MNIST?
- 3y ago
- benob 3y agoWhat explains the huge difference in perf with the approach from 2019 mentioned at the end? For image classification, couldn't one use the residual from applying a jpeg codebook learned on a training example as metric?
- tdr2d 3y agoObviously, 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-mnist https://paperswithcode.com/sota/image-classification-on-mnis...
- sundarurfriend 3y agoThe 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.)
- ActivePattern 3y agoYeah, 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.
- esafak 3y agoThe 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\ https://arxiv.org/abs/2304.09355\*
- a_wild_dandan 3y agoAn increasingly common refrain in machine learning is “intelligence is compression.” Folks who believe that might bristle at the distinction between learning and compression.
- 3abiton 3y agoDidn'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.
- 0xfffafaCrash 3y agohaven’t looked through this post yet but I think this is what you have in mind: https://kenschutte.com/gzip-knn-paper/ https://kenschutte.com/gzip-knn-paper/
- vintermann 3y agoThis is 78% accuracy from Gzip-based compression distance + KNN, which seems to be worse than any other distance measure you can think of + KNN.
- tjungblut 3y agoI don't immediately find it, but couple of years back there was a "meta-feature" which was the size of the MNIST image. I think that scored about 90'ish % accurate results on its own - without even looking at the image.
- p1esk 3y agoWhat do you mean by “size”? Gzipped size? If you simply look at how dark a Mnist image is (count the percentage of dark pixels) you’ll get about 20% accuracy, which is twice better than random guess but a long way from 90’ish %.
- yvdriess 3y agoWhat do you mean with accuracy here? Usually 50% accuracy means cointoss, meaning 20% accuracy is equal to 80% accuracy, which is better than the article's 78% and not that far from 90%.
- rjh29 3y agoThere are ten choices, so getting the answer right 20% of the time is very plausible.
- p1esk 3y agoThere are 10 classes in Mnist. Random guess would is 10%.
- tysam_and 3y ago"One simple trick to beat the statistical odds...."
- Frotag 3y ago> meaning 20% accuracy is equal to 80% accuracy, Only if your model is outputting a yes/no answer right? And that your definition of accuracy is "class with highest probability" (and not "N classes with highest prob") If your dataset has more than 2 classes like MNIST, a super low accuracy only tells you to ignore the class the model guesses. It doesn't tell you which of the remaining classes is correct
- GaggiX 3y agoFor a comparison with others techniques: Linear SVC (best performance): 92 % SVC rbf (best performance): 96.4 % SVC poly (best performance): 94.5 % Logistic regression (prev assignment): 89 % Naive Bayes (prev assignment): 81 % From this blog page: https://dmkothari.github.io/Machine-Learning-Projects/SVM_with_MNIST.html https://dmkothari.github.io/Machine-Learning-Projects/SVM_wi... Also it seems from reading online articles that people are able to obtain much better results just by using K-NN, so I imagine that the author just made his job harder by using gzip but I could be wrong about this.
- grandma_tea 3y agoWhile it's cool that this works at all, I wish we would stop using MNIST as a benchmark given how trivial it is.
- unoti 3y agoMNIST is pretty good as a proof of concept. While I agree it's trivial, I see MNIST as being more like how when you're making a toy programming language, the first thing you do with it is writing a recursive Fibonacci function.
- dmazzoni 3y agoIt's still a great data set because it's real-world, useful, high-quality, and an excellent size (~60k examples), and the "correct" classification isn't very subjective at all - humans can easily get 99% accuracy.
- antiquark 3y agoTake a look at the EMNIST - Extended MNIST dataset. It has both digits and letters of the alphabet.
- IKantRead 3y agoIt's a good benchmark because it's so trivial. Sure it's not great at differentiating between SotA techniques, but it's very useful for sanity checks like this one. Even for SotA models, it's still useful to verify that you can get greater than 98% accuracy on MNIST, before exploring larger, more complex bench marks. It certainly shouldn't be the only benchmark but it's a great place to start iterating on ideas.
- jszymborski 3y agoIn fairness you can run MNIST through UMAP and get near perfect seperation. I'm of the belief that you have to try pretty hard not to do well on MNIST these days. https://github.com/lmcinnes/umap_paper_notebooks/blob/master/UMAP%20MNIST.ipynb https://github.com/lmcinnes/umap_paper_notebooks/blob/master... EDIT: I should add, unless it isn't clear, that we really should retire the dataset. Something like the QuickDraw dataset makes a lot more sense to me.
- sundarurfriend 3y agoY'all are making the (rude) person below complaining about acronyms look reasonable. The repository doesn't define UMAP either, but if you believe ChatGPT it is: > UMAP, which stands for Uniform Manifold Approximation and Projection, is a dimensionality reduction technique and data visualization method commonly used in machine learning and data analysis.
- tomrod 3y agoUMAP is as ubiquitous as T-SNE these days, though to be fair those on HN that focus on JVM, LLVM, NPM, or TLS may not know about UMAP/T-SNE.
- jszymborski 3y agoIt's[0] a non-linear dimensionality reduction technique in the vein of t-SNE[1] that is very well known in the field. My two cents is that if your problem can be solved with something like UMAP + kNN[2], then you really shouldn't be using Deep Learning to solve it. [0] https://en.wikipedia.org/wiki/Nonlinear_dimensionality_reduction#Uniform_manifold_approximation_and_projection https://en.wikipedia.org/wiki/Nonlinear_dimensionality_reduc... [1] https://en.wikipedia.org/wiki/T-distributed_stochastic_neighbor_embedding https://en.wikipedia.org/wiki/T-distributed_stochastic_neigh... [2] https://en.wikipedia.org/wiki/K-nearest_neighbors_algorithm https://en.wikipedia.org/wiki/K-nearest_neighbors_algorithm
- selimthegrim 3y agoDoesn’t your choice of initialization really affect the results? Lior Pachter really seems to keep beating that drum
- Karellen 3y agoYou solved some problem, including implementing the GZIP algorithm, in less than 10 lines of code? ... Oh, ok, not that.
- yannccc2 3y agoAll these ideas date back to at least 2010, probably earlier. It was called "information distance". https://arxiv.org/abs/1006.3520 https://arxiv.org/abs/1006.3520
- great_psy 3y agoHaving some artificial intelligence algorithm that is completely understood and tu able like gzip is would be great for many uses. I think it’s pretty hard to just improve a NN without more data or some non trivial amount of effort.
- m00x 3y agoIt goes along the same lines as the recent paper from Deepmind stating that DL (language modeling in their case) is compression. https://arxiv.org/pdf/2309.10668.pdf https://arxiv.org/pdf/2309.10668.pdf
- tysam_and 3y agoIf you'd like to play around with MNIST yourself, I wrote a PyTorch training implementation that gets ~99.45%+ val accuracy in <13.6 seconds on a V100, est. < 6.5 seconds on an A100. Made to be edited/run in Colab: https://github.com/tysam-code/hlb-CIFAR10 https://github.com/tysam-code/hlb-CIFAR10 It's originally kitted for CIFAR10, but I've found the parameters to be quite general. The code is very easy to read and well-commented, and is a great starting place for exploration. Min-cut deltas to run MNIST: .datasets.CIFAR10(' -> .datasets.MNIST(' (both occurences) 'whiten': Conv(3, -> 'whiten': Conv(1, crop_size = 28 - > `crop_size = 28 Compute for the project funded by Carter Brown and Daniel Gross, my appreciation to them both for helping make this possible. Their support via encouragement has been very helpful as well. <3 :)
- _a_a_a_ 3y ago"MNIST"? accuracy - but of what? what's this about?
- simonw 3y agoMNIST is a classic image classification exercise - a dataset of 60,000 training images and 10,000 testing images where each image is a handwritten numeral as a 28x28 pixel grayscale image. The challenge is to build a computer vision model that can tell which numeral each handwritten digit represents. https://en.wikipedia.org/wiki/MNIST_database https://en.wikipedia.org/wiki/MNIST_database 78% accuracy on a solution is pretty bad, but achieving it just using GZIP is a very neat hack.
- _a_a_a_ 3y agothank you
- Detrytus 3y agoWhat's the average human performance for this task?
- burnished 3y agoI don't know off hand, but go take a look at the images - I would expect near 100%.
- IcyWindows 3y agoSadly,there are several errors in the labeled data, so no one should get 100%. See https://labelerrors.com/ https://labelerrors.com/
- burnished 3y agoJust 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
- tysam_and 3y agoAdditionally, try flipping your images and averaging the size before comparing the distance between them. I'd expect a boost of about 78% -> 84% or so, based on how this typically works as TTA.
- jdthedisciple 3y agoCan you elaborate more on that technique? Why would it improve the result so much? Sounds very interesting so I'm curious.
- tysam_and 3y agofacepalm I just realized I was talking about this in the context of MNIST -- my apologies. It would be better in a problem with horizontal symmetry like CIFAR, esp if the zipping is serialized by unwinding the 2d pixel array into 1d. One trick that _should_ work is by comparing the distances of starting the compression at the 4 different corners of the image, in the 2 separate directions for each corner. That should provide way more than enough information for k-means clustering. My apologies again for my mistake, thank you for asking, I wouldn't have really seen that otherwise :')))).
- bob1029 3y agoGeneral 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 convolution outputs - accommodating varying lengths - allows for us to compare candidate sequences for relevant information on equal grounds. The NCD formula I am using right now: NCD(x,y) = (C(xy) - MIN(C(x),C(y))) / MAX(C(x),C(y)) No weird parameters or any other things to tune. The only parameters are the source documents and the input context/query.
- tripzilch 3y agoSo, 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.
- jp57 3y agoLeaving aside whether this problem is a good application of this compression trick, I want to say that everyone experimenting with this should stop using `gzip` and start using `zlib`. If you change the first line from `gzip.compress` to `zlib.compress` you should get the same classifier performance with a 3x speedup.
- 0xDEF 3y agoHas anyone tried how different compression algorithms compare when doing NCD classification? gzip first does LZ77 and then Huffman coding. ANS is a more modern alternative to Huffman coding that can achieve higher compression ratios than Huffman coding.
- tobeyey 3y agoReplacing the NCD distances = [(compute_ncd(x1, x), label) for x, _, label in compressed_lengths] with the Euclidean distance distances = [(np.sqrt(np.sum(np.square(x1-x))), label) for x, _, label in compressed_lengths] gives you +15% test accuracy and saves you a lot of compute.
- Lerc 3y agoI'm sure there was something like this mentioned in "Managing Gigabytes" or thereabouts. It might have been using bitwise arithmetic compression which makes sense for the problem at hand.
- wayeq 3y agoI'm merely a hobbyist in this domain but isn't highly compressed data (like encrypted data) also high entropy? If this is finding patterns in the compressed data to figure out which digit the uncompressed data represents, shouldn't those patterns be exploitable for better compression?
- fritzo 3y agoThe demonstration isn't classifying based on compressed data, rather it's classifying on the compressibility of data. The idea is that "7 7" should be more compressible than "7 3", and similarly raster images of "7 7" should be more compressible than raster images of "7 3".
- wayeq 3y agoAh ok, that makes sense. Thank you for the explanation.
- Zamicol 3y agoEncrypted data ideally is incompressible. Incompressibility is a hallmark of efficient cryptographic operations. See the Wikipedia article on Kolmogorov complexity, which has a short section about compression. https://en.wikipedia.org/wiki/Kolmogorov_complexity#Compression https://en.wikipedia.org/wiki/Kolmogorov_complexity#Compress... Edit: One of my favorite concepts in the domain of compression is the pigeonhole principle, that states that for all compression algorithms, some outputs will be larger than the inputs. Well designed encrypted payloads may be compressed, but the outputs should on average be larger than the inputs, rendering compression useless thus it is said to be "incompressible". https://en.wikipedia.org/wiki/Pigeonhole_principle#Uses_and_applications https://en.wikipedia.org/wiki/Pigeonhole_principle#Uses_and_...
- montebicyclelo 3y agoI 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 demanding than other measures. I'm not that familiar with how the GZIP algorithm works, it's kind of interesting that it's so much lower. I wonder whether image focused compression algorithms might do better? (Edit: Btw, I enjoyed the post; it's a creative idea, the writing and code was great, and it's sparked some good discussion. But after having a closer look, I think the baselines above provide some context to the gzip scores.)
- tysam_and 3y agoHoly cow, I knew that MNIST was simple, but not that simple. Could you post a snippet of the code that you used to achieve this? It would be really, really nice to have a baseline to work from I'm sure, and I feel like this could be really useful to a few other areas (my personal obsession is speed-training on CIFAR10 :')))) ) Holy cow, that's insane. :O
- montebicyclelo 3y agoI used the notebook linked in the original post [1]. It evaluates using 100 samples from the test set, (I'm guessing because the gzip method is slow - it would take ~7 hours on the full test set, on my machine). I plugged in the distance measures, for the `compute_ncd` function. (Jaccard/Dice have been negated and the -1 removed.) def euclidean(x1, x2): return np.sum(np.square(x1 - x2)) def jaccard(x1, x2): x1_binary = x1 > 0.5 x2_binary = x2 > 0.5 return np.logical_or(x1_binary, x2_binary).sum() / np.logical_and(x1_binary, x2_binary).sum() def dice(x1, x2): x1_binary = x1 > 0.5 x2_binary = x2 > 0.5 return 2 * np.logical_or(x1_binary, x2_binary).sum() / (x1_binary.sum() + x2_binary.sum()) [1] https://github.com/Jakob-98/mono/blob/73168bc0ea904e7586581573da5907020d88736f/python/gzip_mnist/mnist_gzip.ipynb https://github.com/Jakob-98/mono/blob/73168bc0ea904e75865815...
- benreesman 3y agoMy favorite book about the deep connections between information theory, compression, and learning algorithms is MacKay (most probably know about it but I didn’t for a long time so maybe some will benefit from the mention). I gather this is common knowledge (if not sufficiently emphasized at times) among those with serious educations, but as a self-taught, practical application-type ML person this profound thread running through all these topics (and seemingly into heavy-ass particle physics and cosmology and stuff like that) was a blinding “Aha!” moment that I’ll venture this comment in the hopes that even one other person has that unforgettable moment.
- doubloon 3y agoi have put MacKay on my to do list, thank you i was quite struck when i learned the original Lempel Ziv compression (which gzip is partly based on) came out of their study of the "complexity of finite sequences" not necessarily trying to shrink things, https://ieeexplore.ieee.org/document/1055501 https://ieeexplore.ieee.org/document/1055501
- thomasahle 3y agoSimilar result (2019) using ZIP, getting 74%: https://www.blackhc.net/blog/2019/mnist-by-zip/ https://www.blackhc.net/blog/2019/mnist-by-zip/
- yieldcrv 3y agoI want someone to show me how to use compression to compile exploits on emulated logic gates, like NSOGroup keeps doing Seems like a sufficiently novel and important advancement that should be taught in universities at this point, since we need to harden software around this kind of possibility.
- SomewhatLikely 3y agoWouldn't it make more sense to create ten streams of images of the same class and then see which one results in the smallest compressed size for a test image? That is, if I gzip a hundred '6's plus my test image and get a compressed size for my test image of 10 bytes, but doing the same for other digits gives me say 15 bytes then I conclude the test image is a '6'.
- tripzilch 3y agoWhat 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.