Mencapai Akurasi 78% di MNIST dengan GZIP dalam Kurang dari 10 Baris Kode

• Eksperimen ini menaikkan klasifikasi digit tulisan tangan MNIST hingga sekitar 78% akurasi hanya dengan kompresi GZIP dan k-nearest neighbors (k-NN), menunjukkan bahwa kompresi bisa dipakai sebagai alat klasifikasi tanpa model
• Normalized Compression Distance (NCD) dihitung dari seberapa banyak panjang kompresi berubah saat dua sampel gambar dikompresi bersama, lalu digunakan sebagai metrik kemiripan antar-gambar
• Setiap sampel uji dibandingkan dengan 100 sampel latih, dan label mayoritas dari k=5 tetangga dengan jarak terdekat menjadi prediksi
• Karena biaya komputasi, akurasi diukur pada sebagian gambar uji, bukan seluruh test set; memakai seluruh set dapat membuat evaluasi lebih akurat
• Contoh publik masih menyisakan kesalahan refactoring: cache panjang kompresi dibuat tetapi tidak dipakai dalam perhitungan NCD sebenarnya, sehingga cache perlu dihapus atau compute_ncd perlu disesuaikan

---

Mengklasifikasikan MNIST dengan GZIP + k-NN

• Eksperimen ini mengklasifikasikan dataset digit tulisan tangan MNIST dengan kombinasi GZIP + k-NN
• Contoh kode singkat memakai panjang hasil gzip.compress(z.tobytes()) sebagai panjang kompresi, menghitung NCD, lalu memilih nilai yang paling sering muncul di antara label 5 tetangga terdekat
• Contoh yang bisa dijalankan tersedia di Jupyter Notebook
• Tujuannya bukan akurasi tertinggi, melainkan memverifikasi secara sederhana gagasan menggunakan kompresi sebagai alat klasifikasi tanpa model
• Kode kurang dari 10 baris lebih merupakan elemen code golf untuk bersenang-senang daripada inti eksperimen

Perhitungan kemiripan dan prosedur klasifikasi

• NCD mengukur kemiripan dengan menormalkan seberapa berbeda biaya mengompresi dua titik data bersama dibandingkan mengompresinya masing-masing secara terpisah
• Panjang kompresi dihitung dalam bentuk berikut
  • Cx1 = len(gzip.compress(x1.tobytes()))
  • Cx2 = len(gzip.compress(x2.tobytes()))
  • Cx1x2 = len(gzip.compress((x1 + x2).tobytes()))
• Rumus NCD berbentuk (Cx1x2 - min(Cx1, Cx2)) / max(Cx1, Cx2)
• Klasifikasi dilakukan dengan menghitung jarak antara tiap gambar uji dan gambar latih, mengurutkannya dari yang terdekat, lalu memakai voting mayoritas label dari 5 yang paling dekat
• Dalam eksperimen, perbandingan dilakukan terhadap 100 sampel latih, dan karena biaya komputasi, test set juga hanya dipakai sebagian

Ide rujukan dan catatan pada kode

• Pendekatan ini terinspirasi dari artikel text generation from data compression dan paper parameter free text classification
• Setelah tulisan dibuat, ditemukan juga artikel MNIST by ZIP yang ditulis Andreas Kirsch pada 2019 dengan pendekatan serupa
• Kode contoh membuat cache panjang kompresi untuk sampel latih, tetapi nilai cache tersebut tidak digunakan dalam loop sebenarnya
  • Baik versi biasa maupun versi yang diobfuscate membuat compressed_lengths atau cls, tetapi tidak memakai panjang yang di-cache dalam perhitungan NCD
  • Jika cache dihapus dan training_set langsung dipakai, atau compute_ncd diubah agar memanfaatkan nilai cache, maksud kode dan implementasinya akan selaras

[GN⁺]

Pendapat Hacker News

• Saat fungsi jarak pada kode diganti dengan metrik yang lebih sederhana, jarak GZIP pada klasifikasi MNIST akurasinya lebih rendah dan komputasinya jauh lebih besar
  Jarak Gzip: sekitar 3 menit, akurasi 78% / jarak Euclidean: sekitar 0,5 detik, 93% / jarak Jaccard: sekitar 0,7 detik, 94% / dissimilarity Dice: sekitar 0,8 detik, 94%
  Jaccard dan Dice diukur setelah gambar dibinerisasi
  Saya tidak terlalu familier dengan algoritma GZIP, tetapi menarik bahwa hasilnya serendah ini, dan saya penasaran apakah algoritma kompresi yang berfokus pada gambar mungkin akan lebih baik
  Tulisannya sendiri kreatif, dan kode serta penjelasannya juga bagus, tetapi menurut saya baseline di atas menambahkan konteks pada skor gzip

  • Hasil terbaik yang saya temukan adalah normalized mutual information dengan 95%, dan meski sedikit lebih kompleks, pada gambar biner bisa dihitung cukup cepat
    NMI skimage: sekitar 30 detik, akurasi 95% / NMI numba: sekitar 0,6 detik, akurasi 95%
    Saya menghitung hitungan gabungan 2x2, entropi, dan normalized mutual information dengan kode numba yang diberikan ChatGPT
  • Saya tahu MNIST itu sederhana, tetapi tidak menyangka sampai sejauh ini; kalau potongan kode yang digunakan dibagikan, sepertinya akan sangat bagus dijadikan baseline
    Secara pribadi saya tertarik pada pelatihan cepat CIFAR10, jadi pendekatan seperti ini tampaknya bisa cukup berguna juga di area lain
  • Implementasi metode kernel dari ben recht mencapai 98% dalam 10 baris
    https://github.com/benjamin-recht/mnist_1_pt_2/tree/main
  • Saya juga mencoba kompresi PNG, dan ternyata sedikit lebih baik: PNG akurasinya 83% dalam sekitar 15,1 detik
    Saat zstandard juga dicoba, Zstd(level=3) jauh lebih cepat daripada gzip, dengan akurasi 88% dalam sekitar 3,5 detik
    Jika saat menghitung Cx1x2 memakai (x1-x2)*2 alih-alih x1+x2, akurasi zstd naik sampai 93%
    Jika dua array tidak dijumlahkan melainkan ditumpuk atas-bawah, performanya benar-benar hancur hingga di bawah 20%; menariknya, untuk klasifikasi string, cara itu tampaknya bekerja baik
  • Metode gzip memang keren, tetapi pada akhirnya tampaknya menghasilkan performa lebih rendah dengan lebih banyak langkah

• Dibandingkan dengan teknik lain, Linear SVC sekitar 92%, SVC kernel RBF 96,4%, SVC kernel polinomial 94,5%, regresi logistik 89%, dan Naive Bayes sekitar 81%
  Sumber: https://dmkothari.github.io/Machine-Learning-Projects/SVM_wi...
  Dari tulisan-tulisan online, tampaknya K-NN saja bisa menghasilkan hasil yang jauh lebih baik, jadi mungkin penulis justru membuat pekerjaannya lebih sulit dengan memakai gzip

  • Banyak orang tidak tahu bahwa regresi logistik bisa mencapai akurasi sekitar 90% di MNIST
    Saya suka memulai dengan model sederhana lalu menambah kompleksitas belakangan, tetapi saya sering mendengar “regresi logistik tidak bisa” bahkan pada masalah yang sebenarnya dapat bekerja dengan baik
    Saat ditanya kira-kira berapa performa baseline di MNIST, banyak yang menebak 20–30%
    Bahkan orang-orang yang mengerjakan machine learning pun sering meremehkan seberapa cepat diminishing returns muncul saat kompleksitas model dinaikkan besar-besaran
    Dalam banyak kasus, jika performanya tidak bagus pada model sederhana, sulit mendapatkan performa luar biasa bahkan dengan model yang lebih kompleks
  • Blog itu bukan menampilkan performa terbaik terbaru, melainkan lebih berupa perbandingan beberapa implementasi SVM yang relatif sederhana
    Paper asli yang memperkenalkan dataset MNIST juga mencapai akurasi sekitar 98%, dan neural network masa kini mencapai akurasi hingga 99,87%
    https://paperswithcode.com/sota/image-classification-on-mnis...
  • Intinya bukan menjadi lebih baik, melainkan menunjukkan bahwa setelah kompresi pun masih tersisa informasi yang cukup untuk memperoleh sinyal besar
    Kompresi memang dimaksudkan untuk membuat masalah aslinya lebih sulit, dan pada praktiknya masih bekerja seperti itu
  • Keren bahwa ini berhasil, tetapi karena MNIST sudah menjadi terlalu mudah, saya berharap kita berhenti memakainya sebagai benchmark
  • Artinya ada algoritma kompresi yang lebih optimal untuk hubungan antara input dan output MNIST
    Karena model lain cenderung menambahkan noise di suatu tempat, saya bertanya-tanya bagaimana jika feature engineering dimasukkan sebelum gzip
    Misalnya, mungkin saja menerapkan Gaussian blur dan konvolusi terlebih dahulu, lalu memakai deep learning untuk seleksi fitur

• Kodenya mungkin elegan dan pendek, tetapi akurasi 78% di MNIST tergolong sangat buruk
  Model dummy yang dibuat dengan TensorFlow pun mudah mencapai akurasi 90%, dan model terbaik mencapai 99,87%
  Benchmark: https://paperswithcode.com/sota/image-classification-on-mnis...

  • Menurut saya, penekanan tulisannya keliru
    Bagian yang menarik adalah kompresi bisa dipakai untuk klasifikasi bahkan tanpa melatih model
    Jadi ini membuat kita bertanya apakah metrik teori informasi lain yang lebih murah dan lossy juga bisa dipakai
    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\)*
  • Tujuannya bukan membuat kode yang “elegan dan pendek”, melainkan menunjukkan rasa ingin tahu yang menarik; melakukannya dalam 10 baris hanya semacam tantangan tambahan
    Yang menarik bukan apakah GZip mencapai performa terbaik mutakhir, melainkan fakta bahwa klasifikasi bisa berjalan lumayan
    Mirip seperti bukan soal apakah seekor beruang bisa memainkan ulang Mozart dengan sempurna, tetapi fakta bahwa ia bisa memainkan piano itu sendiri sudah mengejutkan
  • Ini bukan upaya memecahkan rekor, melainkan contoh yang menunjukkan sisi menarik dari kompresi
    Meski begitu, hasilnya 8 kali lebih baik daripada baseline, dan menunjukkan bahwa kompresi bisa mempelajari representasi

• Jika compute_ncd diganti dengan jarak Euclidean, akurasi pengujian naik 15 poin persentase dan beban komputasi juga jauh berkurang
  Cukup ubah menjadi seperti distances = [(np.sqrt(np.sum(np.square(x1-x))), label) for x, _, label in compressed_lengths]

• Untuk buku yang membahas keterkaitan mendalam antara teori informasi, kompresi, dan algoritma pembelajaran, MacKay adalah yang terbaik menurut saya
  Bagi orang yang terdidik secara formal ini mungkin pengetahuan umum, tetapi sebagai orang yang belajar mandiri machine learning praktis, saya mengalami momen “aha!” yang kuat saat melihat topik ini terhubung hingga bidang seperti fisika partikel dan kosmologi
  Saya meninggalkan ini dengan harapan setidaknya satu orang lain bisa mendapatkan pencerahan yang sama

  • Saya sudah memasukkan MacKay ke daftar tugas
    Cukup mengesankan saat mengetahui bahwa kompresi Lempel-Ziv asli, salah satu dasar gzip, muncul bukan sekadar dari upaya mengecilkan ukuran, melainkan dari penelitian tentang “kompleksitas deret hingga”
    https://ieeexplore.ieee.org/document/1055501

• Secara adil, MNIST hampir terpisah sempurna hanya dengan melewatkannya melalui UMAP
  Menurut saya, sekarang perlu usaha cukup keras agar performanya buruk di MNIST
  https://github.com/lmcinnes/umap_paper_notebooks/blob/master...
  Menurut saya dataset ini sebaiknya dipensiunkan sekarang, dan dataset seperti QuickDraw jauh lebih masuk akal

  • Sebagai penulis, saya sepenuhnya setuju
    Sulit menyebutnya pencapaian besar dengan sendirinya, tetapi tetap menarik melihatnya bekerja
    Saat pulang nanti saya akan menambahkan ke tulisan bahwa menyelesaikan MNIST relatif mudah
  • Dari sudut pandang riset, MNIST pada dasarnya sudah menjadi masalah yang terselesaikan, dan saya rasa performa saat ini sudah lebih baik daripada manusia
    Meski begitu, sebagian besar algoritma yang sederhana dan masuk akal bisa mencapai akurasi 97%, jadi dataset ini masih bernilai sebagai alat pendidikan atau dataset Hello world
    Bahkan jika membuat alat sendiri dari nol, skalanya cocok untuk tugas kuliah, dan ini adalah tugas berguna yang bisa dipahami siapa pun, seperti “pengenalan angka pada surat”
  • gzip bukan “teknologi masa kini”; ia jauh lebih tua daripada UMAP, bahkan daripada MNIST itu sendiri
    Jika memahami kompresi, pendekatan ini juga ide yang sangat sederhana, sehingga bisa saja ditulis pada hari pertama MNIST dirilis dan tetap menghasilkan akurasi 78%
    Hal itu terasa cukup mengejutkan
  • Ini sampai membuat orang kasar yang mengeluhkan akronim itu terlihat cukup masuk akal
    Repositorinya juga tidak mendefinisikan UMAP, tetapi jika mempercayai ChatGPT, UMAP adalah singkatan dari Uniform Manifold Approximation and Projection, sebuah teknik reduksi dimensi dan visualisasi yang digunakan dalam machine learning dan analisis data

• Saya hanya mengikuti bidang ini di tingkat hobi, tetapi data yang sangat terkompresi bukankah memiliki entropi tinggi, mirip data terenkripsi?
  Jika kita bisa menemukan pola pada data terkompresi untuk mengetahui angka aslinya, bukankah pola itu seharusnya bisa dimanfaatkan untuk kompresi yang lebih baik?

  • Demonstrasi ini bukan mengklasifikasikan dengan melihat data terkompresi, melainkan berdasarkan seberapa baik data itu dapat dikompresi
    Idenya, “7 7” seharusnya lebih mudah dikompresi daripada “7 3”, dan “7 7” dalam gambar raster juga akan lebih mudah dikompresi daripada “7 3”
  • Data terenkripsi yang ideal seharusnya tidak dapat dikompresi
    Ketidakmampuan untuk dikompresi adalah ciri operasi kriptografi yang efisien
    Lihat bagian kompresi pada artikel kompleksitas Kolmogorov: https://en.wikipedia.org/wiki/Kolmogorov_complexity#Compress...
    Salah satu konsep favorit saya dalam kompresi adalah prinsip rumah merpati, yang menyatakan bahwa untuk setiap algoritma kompresi, pasti ada keluaran yang lebih besar daripada masukannya
    Payload terenkripsi yang dirancang dengan baik tetap bisa dicoba untuk dikompresi, tetapi rata-rata keluarannya akan lebih besar daripada masukan sehingga kompresi menjadi tidak berguna; karena itu disebut “tidak dapat dikompresi”
    https://en.wikipedia.org/wiki/Pigeonhole_principle#Uses_and_...

• Sepertinya beberapa tahun lalu ada kasus yang menggunakan ukuran gambar MNIST sebagai “fitur meta”, tetapi saya tidak bisa langsung menemukannya
  Seingat saya, bahkan hanya dengan satu fitur itu tanpa melihat gambarnya pun akurasinya kira-kira sekitar 90%

  • Beberapa tahun lalu saya mengerjakan proyek untuk membuat sidik jari screenshot halaman web, dan ukuran gambar terkompresi saja bekerja sebaik salah satu metode sidik jari untuk membandingkan kemiripan antar-screenshot
  • Saya penasaran apa yang dimaksud dengan “ukuran” di sini
    Apakah ukuran setelah dikompresi dengan gzip? Jika hanya melihat seberapa gelap gambar MNIST, yaitu proporsi piksel gelap, akurasinya sekitar 20%, dua kali lebih baik daripada tebakan acak tetapi masih jauh dari 90%

• Saya curiga penulis makalah itu membuat kesalahan sehingga hasilnya melompat ke papan atas benchmark
  Setelah kejadian itu, saya menganggap teorinya tidak konsisten, tetapi tetap saja akurasi 78% hanya dengan GZIP itu mengesankan

  • Mungkin yang Anda ingat adalah tulisan ini: https://kenschutte.com/gzip-knn-paper/
  • Ini adalah akurasi 78% dengan jarak kompresi berbasis Gzip dan KNN, jadi tampaknya lebih buruk daripada hampir semua metrik jarak lain yang bisa terpikirkan jika dipadukan dengan KNN

• Terlepas dari apakah masalah ini cocok untuk trik kompresi, orang yang bereksperimen sebaiknya berhenti memakai gzip dan memakai zlib
  Jika baris pertama diubah dari gzip.compress menjadi zlib.compress, kecepatan akan 3 kali lebih cepat dengan performa klasifikasi yang sama