GZIP ile 10 satırdan kısa kodda MNIST'te %78 doğruluk

 (jakobs.dev)
1 puan yazan GN⁺ 2023-09-21 | 1 yorum | WhatsApp'ta paylaş
  • Bu deney, MNIST el yazısı rakam sınıflandırmasını yalnızca GZIP sıkıştırma ve k-en yakın komşu (k-NN) ile yaklaşık %78 doğruluğa kadar çıkararak, sıkıştırmanın modelsiz bir sınıflandırma aracı olarak kullanılabileceğini gösteriyor
  • İki görüntü örneği birlikte sıkıştırıldığında uzunluğun ne kadar değiştiğine göre normalize sıkıştırma mesafesi (NCD) hesaplanıyor ve bu değer görüntüler arası benzerlik ölçütü olarak kullanılıyor
  • Her test örneği 100 eğitim örneğiyle karşılaştırılıyor ve mesafesi en yakın k=5 komşunun çoğunluk etiketi tahmin sonucu oluyor
  • Hesaplama maliyeti nedeniyle doğruluk tüm test kümesi yerine test görüntülerinin bir kısmı üzerinde ölçüldü; tüm küme kullanılırsa değerlendirme daha doğru olabilir
  • Paylaşılan örnekte, sıkıştırma uzunluğu önbelleği oluşturulmasına rağmen bunun gerçek NCD hesabında kullanılmadığı bir refactoring hatası kalmış; önbelleğin kaldırılması veya compute_ncd içine yansıtılması gerekiyor

GZIP + k-NN ile MNIST sınıflandırma

  • Deney, MNIST el yazısı rakam veri kümesini GZIP + k-NN kombinasyonuyla sınıflandırıyor
  • Kısa kod örneği, gzip.compress(z.tobytes()) sonucunun uzunluğunu sıkıştırma uzunluğu olarak kullanıyor, ardından NCD'yi hesaplayıp en yakın 5 komşunun etiketleri arasından en sık görüleni seçiyor
  • Çalıştırılabilir örnek Jupyter Notebook içinde yer alıyor
  • Amaç en yüksek doğruluk değil, sıkıştırmayı modelsiz bir sınıflandırma aracı olarak kullanma fikrini basitçe doğrulamak
  • 10 satırdan kısa kod, deneyin özünden çok eğlence amaçlı bir code golf unsuru gibi duruyor

Benzerlik hesabı ve sınıflandırma süreci

  • NCD, iki veri noktasını birlikte sıkıştırmanın maliyetinin ayrı ayrı sıkıştırmaya göre ne kadar farklı olduğunu normalize ederek benzerliği ölçüyor
  • Sıkıştırma uzunluğu şu şekilde hesaplanıyor
    • Cx1 = len(gzip.compress(x1.tobytes()))
    • Cx2 = len(gzip.compress(x2.tobytes()))
    • Cx1x2 = len(gzip.compress((x1 + x2).tobytes()))
  • NCD formülü (Cx1x2 - min(Cx1, Cx2)) / max(Cx1, Cx2) biçiminde
  • Sınıflandırmada her test görüntüsü ile eğitim görüntülerinin mesafesi hesaplanıyor, bunlar yakınlığa göre sıralanıyor ve en yakın 5 etiketin çoğunluk oyu kullanılıyor
  • Deneyde karşılaştırma için 100 eğitim örneği baz alındı ve hesaplama maliyeti nedeniyle test kümesinin de yalnızca bir bölümü kullanıldı

İlham alınan fikirler ve kod üzerindeki dikkat noktaları

  • Bu yaklaşım, text generation from data compression yazısından ve parameter free text classification makalesinden ilham alıyor
  • Yazı yayımlandıktan sonra Andreas Kirsch'ün 2019'da benzer yaklaşımla yazdığı MNIST by ZIP yazısı da fark edilmiş
  • Örnek kod, eğitim örnekleri için bir sıkıştırma uzunluğu önbelleği oluşturuyor, ancak gerçek döngüde bu önbellek değerlerini kullanmıyor
    • Hem normal sürüm hem de obfuscated sürüm compressed_lengths veya cls oluşturuyor, ancak NCD hesabında önbelleğe alınmış uzunlukları kullanmıyor
    • Önbelleği kaldırıp doğrudan training_set kullanmak ya da compute_ncd işlevini önbellek değerlerinden yararlanacak şekilde değiştirmek, kodun niyetiyle uygulamayı hizalar

İlgili okumalar

1 yorum

 
GN⁺ 2023-09-21
Hacker News yorumları

  • Koddaki uzaklık fonksiyonunu daha basit ölçülerle değiştirmeyi denedim; MNIST sınıflandırmasında GZIP uzaklığı hem daha düşük doğruluk veriyor hem de hesaplama maliyeti çok daha yüksek
    Gzip uzaklığı: yaklaşık 3 dakika, %78 doğruluk / Öklid uzaklığı: yaklaşık 0,5 saniye, %93 / Jaccard uzaklığı: yaklaşık 0,7 saniye, %94 / Dice benzemezliği: yaklaşık 0,8 saniye, %94
    Jaccard ve Dice, görüntüler ikilileştirildikten sonra ölçüldü
    GZIP algoritmasına çok aşina değilim ama sonucun bu kadar düşük olması ilginç; görüntü odaklı bir sıkıştırma algoritmasıyla daha iyi olup olmayacağını da merak ediyorum
    Yazının kendisi yaratıcı, kodu ve açıklaması da iyiydi; ancak bence yukarıdaki taban çizgileri gzip skoruna bağlam katıyor

    • Bulduğum en iyi sonuç normalize karşılıklı bilgi ile %95’ti; biraz daha karmaşık olsa da ikilileştirilmiş görüntülerde oldukça hızlı hesaplanabiliyor
      NMI skimage: yaklaşık 30 saniye, %95 doğruluk / NMI numba: yaklaşık 0,6 saniye, %95 doğruluk
      ChatGPT’nin verdiği numba koduyla 2x2 birleşik sayım, entropi ve normalize karşılıklı bilgiyi hesapladım
    • MNIST’in basit olduğunu biliyordum ama bu kadarını beklemiyordum; kullandığın kod parçasını paylaşırsan taban çizgisi olarak almak gerçekten iyi olur
      Kişisel olarak CIFAR10’da hızlı eğitime ilgi duyuyorum, bu yüzden böyle bir yaklaşım başka alanlarda da epey yararlı olabilir gibi görünüyor
    • ben recht’in kernel yöntemleri uygulaması 10 satırda %98’e ulaşıyor
      https://github.com/benjamin-recht/mnist_1_pt_2/tree/main
    • PNG sıkıştırmayı da denedim; gerçekten biraz daha iyiydi: PNG yaklaşık 15,1 saniyede %83 doğruluk verdi
      zstandard’ı da ekleyince Zstd(level=3), yaklaşık 3,5 saniyede %88 doğrulukla gzip’ten çok daha hızlıydı
      Cx1x2 hesaplanırken x1+x2 yerine (x1-x2)*2 kullanılırsa zstd %93 doğruluğa kadar çıkıyor
      İki diziyi toplamak yerine alt alta/üst üste yığarsanız performans tamamen çöküp %20’nin altına düşüyor; ama metin sınıflandırmada bu yöntem iyi çalışıyor gibi göründüğü için ilginç
    • gzip yöntemi havalı olsa da sonuçta daha fazla adımla daha düşük performans üretiyor gibi görünüyor

  • Diğer tekniklerle karşılaştırınca Linear SVC %92, RBF çekirdekli SVC %96,4, polinom çekirdekli SVC %94,5, lojistik regresyon %89, Naive Bayes ise yaklaşık %81 veriyor
    Kaynak: https://dmkothari.github.io/Machine-Learning-Projects/SVM_wi...
    Çevrimiçi yazılara bakınca yalnızca K-NN ile bile çok daha iyi sonuçlar mümkün görünüyor; yazar gzip kullanarak işi gereğinden zorlaştırmış olabilir

    • Pek çok kişi lojistik regresyonun MNIST’te yaklaşık %90 doğruluğa ulaşabileceğini bilmiyor
      Basit bir modelle başlayıp karmaşıklığı sonradan artırmayı seviyorum; gerçekten iyi çalışabilecek problemlerde bile sık sık “lojistik regresyon olmaz” dendiğini duydum
      MNIST’te taban performansın ne olacağını sorduğumda çoğu kişi %20-30 diye tahmin ediyor
      Makine öğrenmesi yapanlar bile model karmaşıklığını ciddi biçimde artırırken azalan getirinin ne kadar hızlı devreye girdiğini sık sık hafife alıyor
      Basit modelde performans iyi değilse, daha karmaşık modellerde de harika performans almanın zor olduğu çok durum gördüm
    • O blog güncel en iyi performansı göstermiyor; daha çok görece basit SVM uygulamalarını karşılaştırıyor
      MNIST veri kümesini tanıtan özgün makale de yaklaşık %98 doğruluk elde etmişti; günümüz sinir ağları ise %99,87 doğruluğa kadar çıkıyor
      https://paperswithcode.com/sota/image-classification-on-mnis...
    • Asıl mesele daha iyi yapmak değil; sıkıştırmadan sonra da yeterli bilginin kalıp güçlü bir sinyal elde edilebildiğini göstermek
      Sıkıştırma zaten asıl problemi daha zor hale getirmek için var ve pratikte de hâlâ böyle çalışıyor
    • Bunun çalışması harika ama MNIST artık fazlasıyla kolaylaştığı için keşke benchmark olarak kullanmayı bıraksak
    • MNIST girdisi ile çıktısı arasındaki ilişki için daha optimal bir sıkıştırma algoritması var demek
      Diğer modeller bir yerlerde gürültü ekleme eğiliminde olduğundan, gzip’ten önce özellik mühendisliği koymak nasıl olur diye düşünüyorum
      Örneğin önce Gaussian blur ve evrişim uygulayıp ardından özellik seçimi için deep learning kullanmak da mümkün görünüyor

  • Kod zarif ve kısa olabilir ama MNIST’te %78 doğruluk oldukça kötü
    TensorFlow ile yapılmış basit bir dummy model bile kolayca %90 doğruluğa ulaşır; en iyi model ise %99,87’de
    Benchmark: https://paperswithcode.com/sota/image-classification-on-mnis...

    • Bence yazının vurguladığı nokta yanlış
      İlginç olan, bir modeli eğitmeden de sıkıştırmanın sınıflandırmada kullanılabilmesi
      Bu da daha ucuz ve kayıplı başka bilgi kuramsal ölçülerin de kullanılıp kullanılamayacağını sorduruyor
      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\)*
    • Amaç “zarif ve kısa” kod yazmak değil, eğlenceli bir merakı göstermek; 10 satırda yapmak sadece ek bir meydan okuma gibi
      İlginç olan GZip’in güncel en iyi performansa ulaşıp ulaşmaması değil, bir şekilde sınıflandırma yapabilmesi
      Bu, bir ayının Mozart’ı kusursuz icra edip etmemesi değil de, piyano çalabiliyor olmasının başlı başına şaşırtıcı olması gibi
    • Rekor kırmaya çalışmıyor; sıkıştırmanın ilginç bir yönünü gösteren bir örnek
      Yine de taban çizgisinden 8 kat daha iyi ve sıkıştırmanın temsili öğrenebildiğini gösteriyor

  • compute_ncdyi Öklid mesafesiyle değiştirirseniz test doğruluğu 15 yüzde puan artıyor ve hesaplama yükü de ciddi ölçüde azalıyor
    distances = [(np.sqrt(np.sum(np.square(x1-x))), label) for x, _, label in compressed_lengths] gibi değiştirmeniz yeterli

  • Bilgi teorisi, sıkıştırma ve öğrenme algoritmaları arasındaki derin bağlantıları ele alan kitaplar arasında MacKay bana en iyisi gelmişti
    İyi eğitim almış kişiler için bu genel kültür sayılabilir ama kendi kendine, uygulama odaklı makine öğrenmesi öğrenmiş biri olarak bu konunun parçacık fiziği ve kozmoloji gibi alanlara kadar uzandığını görünce güçlü bir “Aha!” anı yaşamıştım
    Bir kişi bile aynı farkındalığı yaşasın diye bırakıyorum

    • MacKay’i yapılacaklar listeme ekledim
      gzip’in temellerinden biri olan özgün Lempel-Ziv sıkıştırmasının, yalnızca boyutu küçültme girişiminden ziyade “sonlu dizilerin karmaşıklığı” araştırmasından çıktığını öğrendiğimde epey etkilenmiştim
      https://ieeexplore.ieee.org/document/1055501

  • Adil olmak gerekirse MNIST, yalnızca UMAP’ten geçirilse bile neredeyse kusursuz biçimde ayrışıyor
    Bugünlerde MNIST’te kötü performans almak için epey uğraşmak gerektiğini düşünüyorum
    https://github.com/lmcinnes/umap_paper_notebooks/blob/master...
    Artık bu veri kümesini emekliye ayırmak daha iyi olur; QuickDraw gibi veri kümelerinin çok daha mantıklı olduğunu düşünüyorum

    • Yazar olarak tamamen katılıyorum
      Kendi başına büyük bir başarı saymak zor ama yine de çalıştığını görmek ilginç
      Eve gidince MNIST’i çözmenin görece kolay olduğu noktasını yazıya ekleyeceğim
    • Araştırma açısından MNIST fiilen çözülmüş bir problem ve mevcut performansın insanlardan daha iyi olduğunu düşünüyorum
      Yine de basit ve makul algoritmaların çoğu %97 doğruluğa ulaştığı için eğitim aracı ya da Hello world veri kümesi olarak hâlâ değerli
      Araçları en baştan kendiniz yapsanız bile ödev ölçeğine uygun ve “posta üzerindeki rakamları tanıma” gibi herkesin anlayabileceği faydalı bir görev
    • gzip “güncel bir şey” değil; UMAP bir yana, MNIST’in kendisinden bile çok daha eski bir teknoloji
      Sıkıştırmayı anlıyorsanız bu yaklaşım da çok basit bir fikir; MNIST’in yayımlandığı ilk gün de yazılabilirdi ve yine %78 doğruluk verirdi
      Bu nokta bana oldukça şaşırtıcı geliyor
    • Kısaltmadan şikâyet eden kaba kişiyi bile makul gösterecek kadar
      Depo da UMAP’i tanımlamıyor; ChatGPT’ye güvenecek olursak UMAP, Uniform Manifold Approximation and Projection’ın kısaltması ve makine öğrenmesi ile veri analizinde kullanılan bir boyut indirgeme ve görselleştirme tekniği

  • Bu alanda hobi düzeyindeyim ama güçlü biçimde sıkıştırılmış verinin, şifrelenmiş veri gibi yüksek entropili olmadığını mı düşünmeliyiz
    Sıkıştırılmış veride desenler bulup özgün rakamı anlayabiliyorsanız, o desenleri daha iyi sıkıştırma için kullanabilmeniz gerekmez mi

    • Bu gösterim, sıkıştırılmış veriye bakıp sınıflandırma yapmıyor; verinin ne kadar iyi sıkıştırıldığına göre sınıflandırıyor
      “7 7”, “7 3”ten daha iyi sıkıştırılmalı; raster görüntüdeki “7 7”nin de “7 3”ten daha iyi sıkıştırılacağı fikri bu
    • İdeal şifrelenmiş veri sıkıştırılamaz olmalı
      Sıkıştırılamazlık, verimli kriptografik işlemlerin bir özelliğidir
      Kolmogorov karmaşıklığı maddesindeki sıkıştırma bölümüne bakın: https://en.wikipedia.org/wiki/Kolmogorov_complexity#Compress...
      Sıkıştırmada sevdiğim kavramlardan biri güvercin yuvası ilkesi; buna göre her sıkıştırma algoritmasında girdiden daha büyük çıkan bir çıktı mutlaka vardır
      İyi tasarlanmış bir şifreli payload üzerinde de sıkıştırma denenebilir ama ortalamada çıktı girdiden daha büyük olur ve sıkıştırma işe yaramaz hâle gelir; bu yüzden “sıkıştırılamaz” denir
      https://en.wikipedia.org/wiki/Pigeonhole_principle#Uses_and_...

  • Birkaç yıl önce MNIST görüntülerinin boyutunu “meta özellik” olarak kullanan bir örnek vardı sanırım ama hemen bulamıyorum
    Görüntüye hiç bakmadan, yalnızca o tek özellikle kabaca %90 civarı doğruluk verdiğini hatırlıyorum

    • Birkaç yıl önce web sayfası ekran görüntüsü parmak izi çıkaran bir proje yapmıştım; yalnızca sıkıştırılmış görüntü boyutu bile ekran görüntüleri arasındaki benzerliği karşılaştıran bir tür parmak izi yöntemi kadar iyi çalışmıştı
    • Burada “boyut” ile ne kastedildiğini merak ediyorum
      gzip ile sıkıştırılmış boyut mu? Sadece MNIST görüntüsünün ne kadar koyu olduğuna, yani koyu piksel oranına bakarsanız yaklaşık %20 doğruluk elde edersiniz; rastgele tahminden iki kat iyi ama %90’ın çok uzağında

  • O makalenin yazarları hata yapmış ve sonuçlar benchmark’ın üst sıralarına fırlamış olabilir diye düşünüyorum
    O olaydan sonra teorinin tutarlı olmadığını düşünmüştüm ama yine de yalnızca GZIP ile %78 doğruluk etkileyici

    • Muhtemelen şu yazıyı hatırlıyorsunuz: https://kenschutte.com/gzip-knn-paper/
    • Bu, Gzip tabanlı sıkıştırma mesafesi ve KNN ile elde edilmiş %78 doğruluk; akla gelebilecek hemen hemen herhangi başka bir mesafe metriğiyle KNN’i birleştirmekten daha kötü görünüyor

  • Bu problemin sıkıştırma numarası için iyi bir uygulama alanı olup olmamasından bağımsız olarak, deney yapanların gzip kullanmayı bırakıp zlib kullanması iyi olur
    İlk satırı gzip.compressten zlib.compresse değiştirirseniz aynı sınıflandırma performansıyla hız 3 kat artacaktır