GZIP से 10 पंक्तियों से कम कोड में MNIST पर 78% accuracy हासिल

 (jakobs.dev)
1 पॉइंट द्वारा GN⁺ 2023-09-21 | 1 टिप्पणियां | WhatsApp पर शेयर करें
  • MNIST handwritten digit classification को सिर्फ GZIP compression और k-nearest neighbors (k-NN) से लगभग 78% accuracy तक पहुंचाने वाला यह प्रयोग दिखाता है कि compression को model-free classification tool के रूप में इस्तेमाल किया जा सकता है
  • दो image samples को साथ में compress करने पर length कितनी बदलती है, इसके आधार पर normalized compression distance (NCD) calculate किया गया और इसे images के बीच similarity metric के रूप में इस्तेमाल किया गया
  • हर test sample की तुलना 100 training samples से की जाती है, और सबसे कम distance वाले k=5 neighbors के majority label को prediction माना जाता है
  • computational cost की वजह से accuracy पूरे test set पर नहीं, बल्कि test images के एक हिस्से पर मापी गई; पूरे set का इस्तेमाल करने पर evaluation अधिक सटीक हो सकता है
  • public example में compression length cache बनाने के बावजूद उसे actual NCD calculation में इस्तेमाल न करने वाली refactoring mistake बची हुई है, इसलिए cache हटाने या compute_ncd में उसे शामिल करने की जरूरत है

GZIP + k-NN से MNIST classify करना

  • प्रयोग में MNIST handwritten digit dataset को GZIP + k-NN combination से classify किया गया
  • छोटा code example gzip.compress(z.tobytes()) के result की length को compressed length के रूप में इस्तेमाल करता है, NCD calculate करता है, और फिर 5 nearest neighbors के labels में से mode चुनता है
  • runnable example Jupyter Notebook में है
  • लक्ष्य highest accuracy नहीं, बल्कि compression को model-free classification tool के रूप में इस्तेमाल करने के idea को सरल तरीके से validate करना है
  • 10 पंक्तियों से कम वाला code प्रयोग का core होने से ज्यादा, मजे के लिए code golf element जैसा है

Similarity calculation और classification process

  • NCD यह normalize करके similarity मापता है कि दो data points को साथ में compress करने की cost, उन्हें अलग-अलग compress करने की तुलना में कितनी अलग है
  • compressed length इस रूप में calculate की जाती है
    • Cx1 = len(gzip.compress(x1.tobytes()))
    • Cx2 = len(gzip.compress(x2.tobytes()))
    • Cx1x2 = len(gzip.compress((x1 + x2).tobytes()))
  • NCD formula (Cx1x2 - min(Cx1, Cx2)) / max(Cx1, Cx2) के रूप में है
  • classification में हर test image और training image के बीच distance calculate किया जाता है, उन्हें nearest order में sort किया जाता है, और सबसे नजदीकी 5 labels के majority vote का इस्तेमाल होता है
  • प्रयोग में 100 training samples के आधार पर comparison किया गया, और computational cost की वजह से test set का भी सिर्फ एक हिस्सा इस्तेमाल किया गया

संदर्भित ideas और code से जुड़ी सावधानी

  • यह approach text generation from data compression article और parameter free text classification paper से प्रेरित है
  • article लिखने के बाद Andreas Kirsch द्वारा 2019 में इसी तरह लिखी गई MNIST by ZIP post भी मिली
  • example code training samples की compressed length cache बनाता है, लेकिन actual loop में उस cache value का इस्तेमाल नहीं करता
    • normal version और obfuscated version दोनों compressed_lengths या cls बनाते हैं, लेकिन NCD calculation में cached length का इस्तेमाल नहीं करते
    • cache हटाकर सीधे training_set इस्तेमाल किया जाए, या compute_ncd को cache values इस्तेमाल करने के लिए बदला जाए, तो code की मंशा और implementation मेल खाएंगे

संबंधित पढ़ाई

1 टिप्पणियां

 
GN⁺ 2023-09-21
Hacker News की राय

  • कोड के distance function को एक और सरल माप से बदलकर देखा, तो MNIST classification में GZIP distance की accuracy भी कम थी और compute भी कहीं ज़्यादा था
    Gzip distance: लगभग 3 मिनट, 78% accuracy / Euclidean distance: लगभग 0.5 सेकंड, 93% / Jaccard distance: लगभग 0.7 सेकंड, 94% / Dice dissimilarity: लगभग 0.8 सेकंड, 94%
    Jaccard और Dice को image binarize करने के बाद मापा गया
    GZIP algorithm से मैं बहुत परिचित नहीं हूं, लेकिन result इतना कम होना दिलचस्प है, और सोचता हूं कि image-केंद्रित compression algorithm हो तो शायद बेहतर हो
    पोस्ट अपने आप में creative है और code व explanation भी अच्छे थे, लेकिन मुझे लगता है कि ऊपर की baselines gzip score को context देती हैं

    • मुझे मिला सबसे अच्छा result normalized mutual information से 95% था, और यह थोड़ा ज़्यादा complex है, लेकिन binarized images पर काफ़ी तेज़ी से calculate किया जा सकता है
      NMI skimage: लगभग 30 सेकंड, 95% accuracy / NMI numba: लगभग 0.6 सेकंड, 95% accuracy
      ChatGPT द्वारा दिए गए numba code से 2x2 joint count, entropy, और normalized mutual information calculate किया
    • पता था कि MNIST सरल है, लेकिन इतना होगा यह नहीं सोचा था; अगर इस्तेमाल किए गए code snippets share कर दें तो baseline के तौर पर लेना सच में अच्छा रहेगा
      व्यक्तिगत रूप से मेरी रुचि CIFAR10 fast training में है, इसलिए यह approach दूसरे domains में भी काफ़ी उपयोगी लग सकती है
    • ben recht का kernel methods implementation 10 lines में 98% तक पहुंचता है
      https://github.com/benjamin-recht/mnist_1_pt_2/tree/main
    • PNG compression भी करके देखा, और असल में वह थोड़ा बेहतर निकला: PNG ने लगभग 15.1 सेकंड में 83% accuracy दी
      zstandard भी जोड़कर देखा, तो Zstd(level=3) ने लगभग 3.5 सेकंड में 88% accuracy दी, यानी gzip से बहुत तेज़
      Cx1x2 calculate करते समय x1+x2 की जगह (x1-x2)*2 इस्तेमाल करें तो zstd 93% accuracy तक पहुंचता है
      दोनों arrays को जोड़ने के बजाय ऊपर-नीचे stack करने पर performance पूरी तरह बिगड़कर 20% से कम हो जाती है, लेकिन string classification में वही तरीका अच्छा काम करता लगता है, इसलिए यह दिलचस्प है
    • gzip वाला तरीका cool तो है, लेकिन आखिर में यह ज़्यादा steps में कम performance देने जैसा दिखता है

  • दूसरी techniques से तुलना करें तो Linear SVC करीब 92%, RBF kernel SVC 96.4%, polynomial kernel SVC 94.5%, logistic regression 89%, और naive Bayes करीब 81% है
    स्रोत: https://dmkothari.github.io/Machine-Learning-Projects/SVM_wi...
    online posts देखकर लगता है कि सिर्फ K-NN से भी कहीं बेहतर results संभव हैं, इसलिए शायद author ने gzip इस्तेमाल करके काम को और मुश्किल बना दिया

    • कई लोगों को नहीं पता कि logistic regression MNIST पर लगभग 90% accuracy दे सकता है
      मुझे simple model से शुरू करना और बाद में complexity जोड़ना पसंद है, लेकिन जिन समस्याओं में यह सच में अच्छा काम करता है, उनमें भी “logistic regression नहीं चलेगा” अक्सर सुनने को मिला
      जब पूछा जाता है कि MNIST पर baseline performance कितनी होगी, तो कई लोग 20–30% का अनुमान लगाते हैं
      machine learning करने वाले लोग भी अक्सर underestimate करते हैं कि model complexity बहुत बढ़ाने पर diminishing returns कितनी जल्दी आने लगते हैं
      कई मामलों में अगर simple model पर performance अच्छी नहीं थी, तो अधिक complex model से भी बेहतरीन performance पाना मुश्किल रहा
    • वह blog latest best performance दिखाने के बजाय, अपेक्षाकृत simple SVM implementations की तुलना जैसा है
      MNIST dataset पेश करने वाले original paper ने भी लगभग 98% accuracy हासिल की थी, और आजकल neural networks 99.87% accuracy तक पहुंचते हैं
      https://paperswithcode.com/sota/image-classification-on-mnis...
    • मुख्य बात बेहतर करना नहीं, बल्कि यह दिखाना है कि compression के बाद भी इतना information बचा रहता है कि बड़ा signal मिल सके
      compression मूल समस्या को कठिन बनाने के लिए ही है, और वास्तव में यह अब भी वैसा ही काम करता है
    • यह काम करता है, यह cool है, लेकिन MNIST अब बहुत आसान हो चुका है, इसलिए उम्मीद है कि अब इसे benchmark के रूप में इस्तेमाल करना बंद किया जाए
    • MNIST input और output के बीच relation के लिए कोई और ज़्यादा optimal compression algorithm मौजूद है
      दूसरे models कहीं न कहीं noise जोड़ने की प्रवृत्ति रखते हैं, तो सोचता हूं gzip से पहले feature engineering डालने पर कैसा रहेगा
      उदाहरण के लिए, पहले Gaussian blur और convolution लागू करके, फिर feature selection के लिए deep learning का इस्तेमाल करना भी संभव लगता है

  • code elegant और छोटा हो सकता है, लेकिन MNIST पर 78% accuracy बहुत खराब मानी जाएगी
    TensorFlow से बनाया गया dummy model भी आसानी से 90% accuracy तक पहुंच जाता है, और best model 99.87% पर है
    benchmark: https://paperswithcode.com/sota/image-classification-on-mnis...

    • मुझे लगता है कि पोस्ट जिस बात पर जोर दे रही है, वह गलत है
      दिलचस्प हिस्सा यह है कि model train किए बिना भी compression को classification के लिए इस्तेमाल किया जा सकता है
      इसलिए सवाल उठता है कि क्या और सस्ते व lossy information-theoretic measures भी इस्तेमाल किए जा सकते हैं
      To Compress or Not to Compress- Self-Supervised Learning and Information Theory: A Review
      [https://arxiv.org/abs/2304.09355\)" class="ud link">https://arxiv.org/abs/2304.09355\](https://arxiv.org/abs/2304.09355\)*
    • उद्देश्य “elegant और छोटा” code बनाना नहीं, बल्कि एक मज़ेदार curiosity दिखाना है; 10 lines में करना बस एक अतिरिक्त challenge जैसा है
      GZip latest best performance तक पहुंचता है या नहीं, यह interesting नहीं है; interesting यह है कि किसी हद तक classification हो जाती है
      यह इस बात जैसा है कि भालू Mozart को perfect reproduce कर सकता है या नहीं, नहीं; बल्कि वह piano बजा सकता है, यही अपने आप में हैरान करने वाली बात है
    • यह record तोड़ने की कोशिश नहीं, बल्कि compression का एक दिलचस्प पहलू दिखाने वाला example है
      फिर भी यह baseline से 8 गुना बेहतर है, और दिखाता है कि compression representation सीख सकता है

  • अगर compute_ncd को Euclidean distance से बदल दें, तो test accuracy 15%p बढ़ जाती है और computation भी काफ़ी कम हो जाता है
    इसे distances = [(np.sqrt(np.sum(np.square(x1-x))), label) for x, _, label in compressed_lengths] जैसा बदलना होगा

  • सूचना सिद्धांत, compression और learning algorithms के गहरे संबंधों पर किताबों में MacKay सबसे अच्छी लगी
    ठीक से प्रशिक्षित लोगों के लिए यह शायद सामान्य ज्ञान हो सकता है, लेकिन self-taught तरीके से practical machine learning करते आए मेरे लिए यह देखना कि यह विषय particle physics और cosmology जैसे क्षेत्रों तक जाता है, एक ज़बरदस्त “आहा!” पल था
    उम्मीद है कि कम से कम एक व्यक्ति को भी वैसी ही समझ मिले, इसलिए यह छोड़ रहा/रही हूँ

    • MacKay को अपनी to-do list में डाल लिया है
      जब पता चला कि gzip की बुनियादों में से एक, मूल Lempel-Ziv compression, सिर्फ़ size घटाने की कोशिश से ज़्यादा “finite sequences की complexity” के अध्ययन से निकला था, तो यह काफ़ी प्रभावशाली लगा
      https://ieeexplore.ieee.org/document/1055501

  • निष्पक्ष तौर पर कहें तो MNIST को सिर्फ़ UMAP से गुज़ार देने पर भी वह लगभग पूरी तरह अलग-अलग हो जाता है
    आजकल MNIST पर खराब performance लाने के लिए काफ़ी मेहनत करनी पड़ेगी, ऐसा लगता है
    https://github.com/lmcinnes/umap_paper_notebooks/blob/master...
    अब इस dataset को retire कर देना बेहतर होगा, और QuickDraw जैसे dataset कहीं ज़्यादा वाजिब लगते हैं

    • लेखक के तौर पर पूरी तरह सहमत हूँ
      इसे अपने-आप में कोई बड़ी उपलब्धि मानना मुश्किल है, फिर भी यह देखना दिलचस्प है कि यह काम करता है
      घर पहुँचकर लेख में जोड़ दूँगा/दूँगी कि MNIST solve करना अपेक्षाकृत आसान है
    • research के नज़रिए से MNIST असल में solved problem है, और मौजूदा performance शायद इंसानों से बेहतर है
      फिर भी ज़्यादातर सरल और reasonable algorithms 97% accuracy तक पहुँच जाते हैं, इसलिए educational tool या Hello world dataset के रूप में इसकी value अभी भी है
      शुरू से tools खुद बनाएं तब भी यह homework के scale में फिट बैठता है, और “postal digits recognition” जैसा काम है जिसे हर कोई समझ सकता है
    • gzip कोई “आजकल की चीज़” नहीं है; यह UMAP ही नहीं, MNIST खुद से भी कहीं ज़्यादा पुरानी technology है
      अगर compression समझते हैं, तो यह approach भी बहुत सरल idea है, इसलिए MNIST के public होने के पहले दिन भी इसे लिखा जा सकता था और फिर भी 78% accuracy मिलती
      यही बात काफ़ी चौंकाने वाली लगती है
    • यह तो acronyms पर शिकायत करने वाले rude व्यक्ति को भी उल्टा काफ़ी plausible बना देता है
      repository भी UMAP को define नहीं करती, और ChatGPT पर भरोसा करें तो UMAP का full form Uniform Manifold Approximation and Projection है, जो machine learning और data analysis में इस्तेमाल होने वाली dimension reduction और visualization technique है

  • इस क्षेत्र में मेरी समझ hobby level की है, लेकिन strongly compressed data, encrypted data की तरह high entropy वाला नहीं होता क्या
    अगर compressed data में patterns ढूँढकर original digit पता लगाया जा सके, तो क्या उन patterns का इस्तेमाल बेहतर compression में नहीं होना चाहिए

    • यह demo compressed data देखकर classify नहीं करता, बल्कि data कितनी अच्छी तरह compress होता है इसके आधार पर classify करता है
      idea यह है कि “7 7”, “7 3” से बेहतर compress होना चाहिए, और raster image में “7 7” भी “7 3” से बेहतर compress होगा
    • आदर्श encrypted data compressible नहीं होना चाहिए
      incompressibility efficient cryptographic operations की विशेषता है
      Kolmogorov complexity लेख का compression section देखें: https://en.wikipedia.org/wiki/Kolmogorov_complexity#Compress...
      compression में मेरी पसंदीदा concepts में से एक pigeonhole principle है, जिसके मुताबिक हर compression algorithm के लिए ऐसा output ज़रूर मौजूद होता है जो input से बड़ा हो जाता है
      अच्छी तरह design किए गए encrypted payload को compress करने की कोशिश तो की जा सकती है, लेकिन average में output input से बड़ा हो जाता है और compression बेकार हो जाता है, इसलिए उसे “incompressible” कहा जाता है
      https://en.wikipedia.org/wiki/Pigeonhole_principle#Uses_and_...

  • कुछ साल पहले MNIST images के size को “meta feature” की तरह इस्तेमाल करने का एक example था, ऐसा याद है, लेकिन अभी तुरंत ढूँढ नहीं पा रहा/रही हूँ
    मुझे याद है कि image देखे बिना सिर्फ़ उसी एक feature से भी लगभग 90% के आसपास accuracy मिली थी

    • कुछ साल पहले मैंने webpage screenshots के fingerprints बनाने का project किया था, और सिर्फ़ compressed image size से भी screenshots के बीच similarity compare करने वाली किसी fingerprinting method जितना ही अच्छा काम हो रहा था
    • यहाँ “size” से क्या मतलब है, यह जानना चाहूँगा/चाहूँगी
      क्या gzip से compressed size? केवल यह देखना कि MNIST image कितनी dark है, यानी dark pixels का ratio, लगभग 20% accuracy देता है, इसलिए random guessing से दोगुना बेहतर है लेकिन 90% से बहुत दूर है

  • लगता है उस paper के authors से कोई गलती हुई थी, जिससे result benchmark के top tier में उछल गया था
    उस घटना के बाद से मुझे लगा कि theory consistent नहीं है, फिर भी सिर्फ़ GZIP से 78% accuracy प्रभावशाली है

    • शायद आप यह लेख याद कर रहे हैं: https://kenschutte.com/gzip-knn-paper/
    • यह Gzip-based compression distance और KNN से निकली 78% accuracy है, इसलिए KNN के साथ लगभग किसी भी अन्य distance metric की तुलना में खराब लगती है

  • यह problem compression trick के लिए अच्छा application है या नहीं, इससे अलग, experiments करने वालों को gzip छोड़कर zlib इस्तेमाल करना चाहिए
    पहली line को gzip.compress से zlib.compress में बदल देने पर वही classification performance मिलेगी और speed 3 गुना तेज़ होगी