- Ada kemungkinan performa pengklasifikasi kNN berbasis gzip yang mendapat perhatian dalam makalah “Low-Resource” Text Classification karya Jiang et al. dihitung bukan sebagai akurasi kNN biasa, melainkan dengan cara yang mendekati top-2 saat k=2
calc_accdiexperiments.pypada repositori resmi memperlakukan hasil sebagai benar jika ada satu saja label jawaban yang cocok di antara kandidat seri, sehingga jika hanya satu dari dua sampel pelatihan terdekat yang benar, itu tetap dihitung sukses- Jika kolom “Full” untuk empat dataset pertama dihitung ulang, sejumlah angka berubah, dan pada KirundiNews metode gzip turun dari performa terbaik menjadi yang terburuk
- Hasil implementasi ulang terpisah menunjukkan keluaran kode resmi selalu sama dengan
top2, dan jika seri pada k=2 dipecahkan dengan memprioritaskan sampel yang lebih dekat, hasilnya pada praktiknya sama dengan k=1 - Opsi
rand==Truememecahkan seri denganrandom.choice, tetapi tampaknya tidak digunakan untuk hasil makalah, dan SogouNews masih belum dijalankan karena ukuran datanya
Masalah perhitungan akurasi yang terungkap saat mereproduksi hasil makalah
- Yang dibahas adalah “Low-Resource” Text Classification: A Parameter-Free Classification Method with Compressors karya Jiang et al.; tabel yang menunjukkan metode berbasis
gzipmengungguli beberapa metode berbasis jaringan saraf sempat menarik perhatian di Twitter - Dalam proses mereproduksi kode sumber resmi, ditemukan bahwa cara menghitung akurasi pada pengklasifikasi kNN bekerja berbeda dari cara yang umum
- Khususnya pada k=2, hasilnya lebih dekat ke akurasi top-2 daripada akurasi kNN(k=2) yang normal, sehingga performa metode dalam makalah bisa terlihat lebih tinggi
Mengapa seri menjadi masalah pada kNN k=2
- Metode dalam makalah memakai kNN classifier, dan menurut Appendix C, semua eksperimen menggunakan k=2
- Klasifikasi k=2 mencari dua sampel pelatihan terdekat untuk setiap sampel uji, sehingga keadaan labelnya sederhana
- Jika dua label sama, label itu diprediksi, dan hasilnya menjadi sama seperti k=1
- Jika dua label berbeda, muncul seri 1:1, sehingga dibutuhkan aturan pemecah seri terpisah, misalnya memprioritaskan sampel yang lebih dekat
- Jika seri dipecahkan secara acak, maka pada separuh kasus seri 1:1 sistem akan memilih sampel yang lebih jauh, sehingga sulit menjadi lebih baik daripada k=1
Cara calc_acc menangani seri
- Titik masalah ada pada metode
calc_accdiexperiments.py - Alur kodenya mengumpulkan label dan jumlah kemunculan sampel top-k ke dalam
sorted_pred_lab, lalu mengelompokkannya per label dan mengurutkannya berdasarkan jumlah tersebut - Saat menelusuri label-label yang seri pada jumlah tertinggi, jika salah satunya sama dengan label uji,
if_right = 1akan disetel sehingga dianggap benar - Pada k=2, jika dua label berbeda masing-masing mendapat 1 suara, ini pada dasarnya hanya memeriksa apakah salah satu dari dua kandidat itu adalah jawaban benar
- Hasil ini mirip dengan akurasi top-k pada ImageNet, tetapi bedanya di sini acuannya adalah k sampel pelatihan, bukan k label yang dipilih
- Metode ini menerima nilai k berapa pun, tetapi tidak menghitung top-k untuk semua k; pada k=2 muncul situasi khusus ketika semua kandidat tergabung pada jumlah maksimum 1
calc_accmemiliki flagrand, dan ketikarand==Trueseri dipecahkan denganrandom.choice, tetapi tampaknya itu tidak digunakan dalam hasil makalah
Perubahan akurasi setelah dihitung ulang
- Untuk kolom “Full” pada empat dataset pertama, angka pada makalah dan angka
knn2dyang diperbaiki adalah sebagai berikut
| Kategori | KinyarwandaNews | KirundiNews | DengueFilipino | SwahiliNews |
|---|---|---|---|---|
| Makalah | 0.891 | 0.905 | 0.998 | 0.927 |
knn2d diperbaiki |
0.835 | 0.858 | 0.999 | 0.850 |
- Dataset kelima, SogouNews, masih belum dijalankan karena ukurannya besar
- Perbedaan ini sangat mengubah interpretasi eksperimen; pada KirundiNews, metode
gzipturun dari performa terbaik menjadi yang terburuk
Hasil yang dikonfirmasi dengan implementasi terpisah
- Implementasi terpisah menggunakan dua strategi pemecah seri
r: pilih secara acakd: kurangi k sampai tidak ada lagi seri
- Hasil implementasi ulangnya adalah sebagai berikut
| Metode | kinnews | kirnews | filipino | swahili | Penjelasan |
|---|---|---|---|---|---|
table5 |
0.891 | 0.905 | 0.998 | 0.927 | Angka tabel di makalah |
code |
0.891 | 0.906 | 1.000 | 0.927 | Menggunakan repositori npc_gzip |
top2 |
0.891 | 0.906 | 1.000 | 0.927 | top-2 |
knn1r |
0.835 | 0.858 | 0.999 | 0.850 | kNN, k=1, seri acak |
knn1d |
0.835 | 0.858 | 0.999 | 0.850 | kNN, k=1, kurangi k saat seri |
knn2r |
0.828 | 0.807 | 0.851 | 0.842 | kNN, k=2, seri acak |
knn3r |
0.838 | 0.791 | 0.851 | 0.881 | kNN, k=3, seri acak |
knn2d |
0.835 | 0.858 | 0.999 | 0.850 | kNN, k=2, kurangi k saat seri |
knn3d |
0.843 | 0.794 | 0.904 | 0.883 | kNN, k=3, kurangi k saat seri |
- Hasil verifikasi menunjukkan apa yang sebenarnya dihitung oleh kode resmi
table5dekat dengancodedalam selisih 0.001 atau 0.002, sehingga angka makalah bisa direproduksicodeselalu sama dengantop2, sehingga hasil kode resmi cocok dengan hasil top-2 dari implementasi terpisahknn1r == knn1d, dan pada k=1 tidak terjadi seriknn2d == knn1d, dan pada k=2, jika seri dipecahkan dengan memilih sampel pertama, hasilnya menjadi sama dengan k=1knn2r < knn2d, dan pada seri 1:1 di k=2, pemilihan acak akan memilih sampel yang lebih jauh pada separuh kasus
Hal-hal yang masih perlu dipastikan
- Implementasi ulang baru yang mencakup lebih banyak nilai k tersedia di gzip-knn
- Alasan mengapa DengueFilipino dalam beberapa kasus sangat tinggi seperti 1.0 dibahas pada tulisan lanjutan Part 2
- Alasan
table5dancodesedikit berbeda pada dua kasus masih menjadi hal yang perlu dipastikan
1 komentar
Komentar Hacker News
Mungkin mengecewakan bagi para penulisnya, tetapi menurut saya ini sanggahan yang bagus
Dalam machine learning, kesalahan seperti ini sangat mudah terjadi, dan yang lebih buruk, kesalahan metodologi yang halus biasanya tidak muncul sebagai kegagalan fatal seperti di bidang rekayasa atau sains lain, melainkan sebagai perubahan performa yang samar
Jika data buruk tercampur ke set pelatihan atau informasi nilai target bocor masuk, sistem tetap berjalan lumayan, hanya hasilnya sedikit terkontaminasi
Menerapkan algoritma kompresi yang sudah ada ke machine learning terasa terlalu seperti makan siang gratis, tidak seperti yang diharapkan. Jika ada sihir khusus dalam algoritma kompresi, kita akan memakai algoritma kompresi sebagai encoder, bukan memakai transformer sebagai kompresor
Karena itu saya sering berargumen bahwa publikasi terbuka adalah bentuk peer review yang lebih baik daripada konferensi atau jurnal. Peer review berarti rekan sejawat meninjau pekerjaan saya; kriteria arbitrer dan penuh noise yang dikedepankan konferensi atau jurnal bukanlah intinya
Sepanjang sebagian besar sejarah, prosesnya berjalan seperti ini, dan peer review dalam pengertian modern adalah konsep yang cukup baru dari pertengahan 1970-an. Jurnal lama lebih dekat pada tugas menyebarkan riset, seperti yang dilakukan arxiv hari ini
https://mitcommlab.mit.edu/broad/commkit/peer-review-a-histo...
Alasan lain untuk menghapus konferensi dan jurnal adalah agar pekerjaan penting seperti makalah replikasi dan makalah kegagalan dapat didorong secara aktif. Kita tidak perlu terikat pada kriteria “kebaruan”, dan pada kenyataannya hampir semua riset bersifat bertahap
“Publikasi” adalah menyampaikan pekerjaan saya kepada rekan sejawat agar mereka dapat memverifikasi atau membantah hasilnya
Namun, hal baik dari konferensi adalah bahwa ia mengumpulkan orang dan mendorong kolaborasi. Yang dikritik di sini adalah penggunaan konferensi dan jurnal sebagai sarana untuk menilai validitas riset
Jika sistem konferensi hanya menjadi ajang untuk mengundang riset dan komunitas, sama sekali tidak ada masalah. Jurnal juga secara teoretis bagus karena ada dialog antara penulis dan reviewer, tetapi menurut saya ini pun mudah dilakukan dengan arxiv + github atau OpenReview
Performanya buruk, tetapi jelas ada dan juga sangat mudah didistribusikan. Teks yang mirip cenderung terkompresi lebih baik, jadi saya pernah melihat gzip dipakai untuk deteksi plagiarisme
Rasio kompresi juga bisa dipakai sebagai bobot dalam model pegas untuk visualisasi, dan dapat diterapkan pada metadata komunikasi jaringan
Terutama ketika hasilnya mengonfirmasi pemikiran yang sudah ada
Jika satu titik koma terlewat, error langsung muncul
Tetapi meskipun perhitungan gradien di salah satu dari tiga layer salah, kadang-kadang tetap bisa berjalan. Hanya saja hasilnya menjadi aneh
Dunia dengan jumlah makalah sains setengahnya dan kehati-hatian dua kali lipat akan menghasilkan jauh lebih banyak nilai, tetapi seluruh sistem sudah sangat tergamifikasi dan nyaris tanpa harapan
Saya orang yang menulis posting blog ini. Saya cukup yakin dengan isi yang saya tulis di sini, tetapi jika ada yang terlewat, mungkin para penulisnya perlu menjelaskan langsung
Saya baru saja membuka issue di GitHub: https://github.com/bazingagin/npc_gzip/issues/3
Makalahnya sendiri tetap solid
Namun memang benar bahwa pilihan ini agak aneh. Seperti yang saya katakan di makalah dan Twitter, hasil berubah ketika nilai k berubah, dan yang kami laporkan adalah hasil maksimum yang bisa diperoleh, sehingga itu merepresentasikan situasi ideal ketika prediksi selalu benar
Kami menggunakan strategi yang sama untuk W2V dan SentBERT. Namun ini bukan berarti top-2 accuracy. Sepengetahuan saya, top-2 accuracy memberi skor jika salah satu dari 2 kelas teratas yang diprediksi benar
Tetapi seperti yang ditunjukkan, dalam kNN dengan k=2 ada situasi ketika 2 tetangga terdekat menunjuk ke kelas yang sama, dan dalam kasus ini, jika melaporkan top-2 accuracy, satu kandidat kelas lain akan terlewat
Ketika ada waktu untuk mengunggah versi baru ke arxiv, saya ingin menambahkan hasil untuk strategi lain dan nilai k lain. Strategi decrement yang disebut di blog itu benar-benar bagus, dan jika mau, saya ingin menambahkannya ke repositori
Maaf atas jawaban yang singkat dan terlambat. Saya belum sempat memeriksa repositori. Saya sedang menyiapkan review makalah besok, jadi setelah selesai saya akan menjawab dan menyelesaikan issue tersebut
Saya penasaran apakah Anda juga sudah mencoba mereproduksi tabel hasil lain, yaitu Table 3
Jika pemahaman saya benar, ketika hanya ada 2 kelas, top-2 accuracy menjadi 1, tetapi semakin banyak jumlah kelas, secara rata-rata selisihnya dengan accuracy “biasa” makin mengecil. Jadi jika dataset memiliki banyak kelas, hasil Table 3 mungkin tidak akan berubah terlalu besar
Bagaimanapun, top-2 accuracy 0,685 pada dataset 20-newsgroups cukup mengesankan untuk metode yang bahkan tidak melihat karakter sebagai karakter[1]. Belum lagi alat-alat bagus seperti token, n-gram, dan embedding yang telah dikerjakan para peneliti pemrosesan bahasa alami selama bertahun-tahun
[1] Sepemahaman saya, gzip hanya menangani bitstream, yang tidak harus selaras dengan batas kata, yaitu batas byte
Saat melakukan eksperimen relevansi pencarian di Shopify, saya juga banyak membuat kesalahan, jadi saya bersimpati kepada para penulis. Saya sendiri punya cukup banyak kesalahan yang membuat malu di depan publik
Menjelang akhir masa saya di Shopify, saya belajar bahwa sains yang baik membutuhkan rekayasa perangkat lunak yang baik. Karena terlalu mudah membuat kesalahan di begitu banyak titik dalam stack
Karena itu, agar kami bisa memercayai angka-angkanya dan mereproduksi eksperimen satu sama lain, kami menghabiskan banyak waktu membuat perangkat lunak eksperimen yang ketat, banyak diuji, dan berkualitas tinggi
Kami berusaha menghindari metode evaluasi sekali pakai; jika membuat metode baru, kami menambahkannya ke rangkaian alat evaluasi lalu mengujinya untuk memahami apa arti metrik tersebut
Ini terdengar jelas, tetapi dari pengalaman saya melakukan eksperimen semacam ini, sayangnya hal itu tidak sesering yang diharapkan. Perusahaan menginginkan kecepatan, dan berpikir mendalam secara statistik atau membangun alat internal biasanya tidak terlalu selaras dengan kepentingan para petinggi
Pertama, kita bisa memakai lebih banyak keahlian rekayasa perangkat lunak, dan kedua, ada insentif untuk tidak terlalu melebih-lebihkan klaim. Karena jika kita mengatakan sesuatu berfungsi, ada ekspektasi agar itu benar-benar dimasukkan ke lingkungan operasional
Senang sekali tulisan blog ini dipublikasikan
Saya juga sangat sering mengerjakan proyek-proyek kecil seperti ini, dan bahkan pekerjaan yang menunjukkan masalah pada sebuah makalah seperti ini pun sering kali tidak pernah terlihat. Biasanya hanya sempat sedikit bersuara, lalu berakhir terkubur di hard disk
Jadi terima kasih sudah merilisnya seperti ini
Setelah menghabiskan sehari untuk pekerjaan seperti ini, biasanya saya tidak punya tenaga untuk benar-benar menulis posting blog, jadi terasa sayang. Namun menulis thread Twitter pendek biasanya masih bisa dilakukan
Saya benar-benar senang melihat hasil ini. kNN + tugas klasifikasi + klasifikasi berbasis kemiripan teks murni adalah kombinasi yang mudah membuat hasil terlihat menguntungkan
Reaksi yang bersorak atas makalah ini salah memahami bahwa unsur bahasa alami sangat penting dalam embedding. Frasa yang berbagi kata akan mudah diklasifikasikan dan juga mudah untuk GZIP, jadi GZIP bisa dipakai sebagai classifier pengganti
Keajaiban BERT atau embedding adalah bahwa keduanya tidak harus berbagi kata. Misalnya, “what is my safe passcode?” sangat cocok dengan “my lockbox pin is 1234”, tetapi tidak dengan “my jewelry is stored safely in the safe”
Hal ini juga penting pada LLM. Banyak orang memakai embedding untuk kemiripan teks, padahal yang seharusnya dipakai adalah model SBERT yang dilatih agar pertanyaan berkorelasi dengan dokumen yang memuat jawabannya
Seluruh rabbit hole-nya bisa dilihat di https://www.sbert.net/
Tulisan sebelumnya: Should you use OpenAI's embeddings? Probably not, and here's why. https://iamnotarobot.substack.com/p/should-you-use-openais-e...
Diskusi HN: https://news.ycombinator.com/item?id=35377935
Dalam kondisi seperti ini, input pelatihan terlalu jarang sehingga model dengan banyak parameter mungkin sulit mempelajari embedding yang baik
Dalam pengaturan klasifikasi data berskala besar tradisional di dalam domain, metode nonparametrik seperti kompresi tidak mungkin mengalahkan representasi yang dipelajari
Tidak jelas mengapa para penulis memilih kNN sebagai classifier. Jika sudah membuat matriks jarak, mereka bisa mengubah matriks itu menjadi faktor dengan multidimensional scaling, lalu memakai algoritma pohon seperti xgboost, dan kemungkinan hasilnya akan jauh lebih baik karena memanfaatkan lebih banyak informasi daripada kNN
Mereka juga bisa memakai algoritma kompresi PAQ, yang jauh lebih baik daripada kompresor keluarga LZ. Pilihan-pilihan seperti ini bisa saja sangat memperbaiki hasil dan membawa mereka ke kesimpulan semula
Hal yang saya sukai dari makalah ini adalah bahwa mereka mengabstraksikan algoritma kompresi, sehingga membuat saya berpikir apa lagi yang bisa dilakukan dengan kompresi dari hubungan p(x) ~ K^(-|x|). Di sini K adalah ukuran alfabet, |x| adalah panjang string x, dengan asumsi pengodean optimal
Misalnya, saya terpikir bahwa klasifikasi tradisional juga bisa dilakukan dengan mengelompokkan faktor tiap respons sebagai dokumen terpisah, lalu dengan cara yang sama seperti makalah tersebut mencari dokumen yang paling baik mengompresi sampel berikutnya untuk menentukan kelas. Ini semacam klasifikasi terawasi menggunakan algoritma kompresi
Semakin dekat kompresor ke kode optimal untuk dataset tersebut, semakin baik pula cara ini akan bekerja
Metode prediksi deret juga sama sederhananya untuk diimplementasikan
Itu kejutan yang menyenangkan
Bisakah seseorang menjelaskan bagaimana algoritma kompresi bisa mengalahkan LLM? Kedengarannya seperti membandingkan bahwa kuda lebih baik daripada grafiti
Rasanya jawabannya ada di suatu tempat, tetapi saya tidak akrab dengan AI jadi sama sekali tidak paham
Peran model adalah memprediksi apa yang akan datang berikutnya, dan peran pengode entropi adalah mengodekan selisih antara prediksi dan nilai berikutnya yang sebenarnya, sambil membuat hasil yang lebih mungkin memakai bit sesedikit mungkin
Semakin akurat model, semakin kecil selisih antara realitas dan prediksi, dan semakin sedikit bit yang dibutuhkan pengode entropi, sehingga kompresinya lebih baik
Algoritma kompresi sederhana punya model sederhana seperti “jika sudah melihat byte yang sama 10 kali, kemungkinan besar yang ke-11 juga sama”. Namun LLM juga bisa dipakai sebagai model. Karena pekerjaan LLM adalah melengkapi teks dengan kata yang paling masuk akal
Di sini yang dilakukan adalah kebalikannya. Alih-alih memakai model untuk kompresi, mereka memakai algoritma kompresi seperti model dengan beberapa trik. Caranya adalah menganggap hasil yang dapat dikodekan oleh algoritma kompresi dengan bit lebih sedikit sebagai hasil yang paling mungkin
Para penulis makalah asli menunjukkan bahwa pada beberapa tugas, model sederhana yang bisa diekstrak dari gzip mengalahkan LLM yang jauh lebih kompleks
Dalam kompresi, deretan kata dengan probabilitas tinggi harus diberi kode yang lebih pendek, jadi hubungannya langsung. Metode terkenal untuk membuat kode semacam itu berdasarkan probabilitas adalah pengodean Huffman
Ini berlaku baik untuk model bahasa statistik yang memakai frekuensi kata, maupun LLM yang dipakai untuk estimasi probabilitas. Semakin baik model bahasanya, yaitu semakin rendah perplexity-nya, semakin pendek hasil kompresinya
Sebaliknya, bisa juga dikatakan bahwa algoritma kompresi secara implisit mendefinisikan model bahasa melalui panjang kode. Misalnya, ia berasumsi bahwa string yang berulang lebih mungkin daripada noise acak
Jika
ABCdikompresi, hasilnya menjadi X byte. Lalu jikaABCABCdikompresi, hasilnya tidak menjadi 2X byte. Semakin mirip dua string yang digabungkan, semakin sedikit jumlah byte yang dibutuhkanABCABDakan lebih besar daripadaABCABC, tetapi lebih kecil daripadaABCXYZBERT adalah LLM yang sangat kecil menurut standar sekarang, dan kita juga tahu performanya lebih lemah dibanding model berskala miliaran parameter yang sering kita jumpai belakangan ini
https://mattmahoney.net/dc/rationale.html
Metode seperti mendeteksi kata tertentu juga bisa bekerja cukup baik dalam beberapa kasus. Pada objek yang terkompresi dengan baik, substring yang sama sering muncul
Jika ini benar, saya ingin melihat bagaimana orang-orang yang dulu membesar-besarkan makalah itu sekarang diam-diam menghapus jejak mereka
Terutama para influencer di LinkedIn dan Twitter
Kalau ternyata tidak benar, saya akan terlihat bodoh, tetapi saya hanya membaca artikelnya sekilas
Gzip sebagai pengklasifikasi luar biasa bagus, dan seharusnya dipakai sebagai baseline untuk jaringan neural
Sebagai catatan, blognya sepertinya berhenti di 2022
Tanggal tulisannya tertulis 17 Juli 2022