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

111–120 of 141 posts

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

#111

Post by w-m »

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…

Best one I found is Normalized Mutual Information at 95%. It's a little more complex, but you could still compute it relatively quickly on binarized images.

    NMI skimage: ~30 seconds, 95% accuracy
    NMI numba *: ~0.6 seconds, 95% accuracy
Here's the code, courtesy of ChatGPT:

    @njit(cache=True)
    def compute_joint(img1, img2):
        stacked = 2 * img1.ravel() + img2.ravel()
        return np.bincount(stacked, minlength=4).reshape(2, 2)

    @njit(cache=True)
    def entropy(counts, total):
        # Convert counts to probabilities
        p = counts / total
        # Only calculate for non-zero entries to avoid log(0)
        return -np.sum(p[p > 0] * np.log2(p[p > 0]))

    @njit(cache=True)
    def normalized_mutual_information(img1, img2):
        joint_counts = compute_joint(img1, img2)
        total_pixels = 28*28
        
        # Marginal counts
        c1 = np.sum(joint_counts, axis=1)
        c2 = np.sum(joint_counts, axis=0)
        
        # Compute entropies directly from counts
        h1 = entropy(c1, total_pixels)
        h2 = entropy(c2, total_pixels)
        joint_entropy = entropy(joint_counts.flatten(), total_pixels)
        
        mutual_info = h1 + h2 - joint_entropy
        return 2 * mutual_info / (h1 + h2)

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

#112

Post by tysam_and »

montebicyclelo wrote: post #107
tysam_and wrote: post #104

Earlier quoted context omitted.

Holy 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

I 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…

Ohhh, you know what? I think this makes sense, since it's basically like making prototypes from the training set, only it's instead comparing against every training example, then averaging. Cool. Did not know that would be remotely close to 90%, but that makes sense to me.

I wonder if something like a weighted max_mean would perform better or something L1. Or maybe L2 is ideal, it is at the center of a lot of things information theory, after all! ;PPPP

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

#113

Post by anitil »

esafak wrote: post #44
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 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...

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

#114

Post by esafak »

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...

Now that you mention it, I vaguely recall writing a language classifier based on character histograms as a youth. Good times.

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

#115

Post by bugglebeetle »

IKantRead wrote: post #51
GaggiX wrote: post #17

For 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_wi... Also it seems from reading online articles that people are able to obtain much better results just by using…

Thanks for posting this. Most people don't realize that Logistic regression can get ~90% accuracy on MNIST. As a big fan of starting with simple models first and adding complexity later, I've frequently been told that "logistic regression won't work!" for problems where it can in fact perform excellent. When faced with this resistance to logistic regression I'll often ask what they think the baseline performance of i…

> People, even machine learning people, often don't realize the rapidly diminishing returns you get for adding a lot of complexity in your models.

Are you me? I was just having this argument at work with someone about using an old (fasttext/word2vec) model vs. the overhead on fine-tuned BERT model for a fairly simple classification problem.

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

#116

Post by salty_biscuits »

IKantRead wrote: post #51
GaggiX wrote: post #17

For 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_wi... Also it seems from reading online articles that people are able to obtain much better results just by using…

Thanks for posting this. Most people don't realize that Logistic regression can get ~90% accuracy on MNIST. As a big fan of starting with simple models first and adding complexity later, I've frequently been told that "logistic regression won't work!" for problems where it can in fact perform excellent. When faced with this resistance to logistic regression I'll often ask what they think the baseline performance of i…

You can get 80ish percent with a linear model (if you one hot the labels).

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

#117

Post by doubloon »

benreesman wrote: post #103

My 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 runn…

i 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

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

#118

Post by sr192 »

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…

ben recht's kernel method implementation in 10 lines hits 98%

https://github.com/benjamin-recht/mnist_1_pt_2/tree/main

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

#120

Post by tbrownaw »

IKantRead wrote: post #66
grandma_tea wrote: post #20

Earlier quoted context omitted.

While it's cool that this works at all, I wish we would stop using MNIST as a benchmark given how trivial it is.

It'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.

So MNIST for ML models is kind of like FizzBuzz for humans doing software development.
Post reply on HN