Gzip dan KNN Mengungguli Transformers dalam Klasifikasi Teks

 (twitter.com/LukeGessler)
2 poin oleh GN⁺ 2023-07-15 | 1 komentar | Bagikan ke WhatsApp
  • Mengusulkan metode klasifikasi teks non-parametrik yang menggabungkan kompresor sederhana seperti gzip dengan pengklasifikasi k-nearest neighbors (kNN)
  • Meski sama sekali tidak memiliki parameter pelatihan, metode ini ringan dan serbaguna, dengan beban biaya komputasi yang lebih rendah dibanding DNN
  • Mencapai hasil yang kompetitif pada 6 dataset in-distribution dibandingkan metode deep learning yang tidak dipralatih
  • Mengungguli BERT pada seluruh 5 dataset OOD (out-of-distribution), termasuk 4 bahasa ber-sumber daya rendah
  • Menunjukkan performa unggul bahkan dalam lingkungan few-shot, saat data berlabel terbatas sehingga DNN sulit dilatih

Latar Belakang dan Masalah

  • DNN banyak digunakan untuk klasifikasi teks berkat akurasinya yang tinggi
  • Namun, DNN membutuhkan jutaan parameter dan data berlabel dalam jumlah besar, sehingga biaya komputasinya tinggi
  • Akibatnya, penggunaan, optimasi, dan transfer ke situasi OOD (out-of-distribution) menjadi pekerjaan yang mahal dalam praktik

Metode yang Diusulkan

  • Menghadirkan metode non-parametrik yang mudah, ringan, dan serbaguna sebagai alternatif DNN
  • Strukturnya menggabungkan kompresor sederhana seperti gzip dengan pengklasifikasi k-nearest neighbors
  • Ciri utamanya adalah sama sekali tidak memiliki parameter pelatihan

Hasil Eksperimen

  • Pada 6 dataset in-distribution, performanya berada di tingkat yang mampu bersaing dengan metode deep learning yang tidak dipralatih
  • Mengungguli BERT pada seluruh 5 dataset OOD, termasuk 4 bahasa ber-sumber daya rendah
  • Tetap kuat dalam lingkungan few-shot, ketika data berlabel terlalu sedikit untuk melatih DNN secara efektif

Bacaan terkait

1 komentar

 
GN⁺ 2023-07-15
Komentar Hacker News

  • Tautan langsung ke makalah: https://aclanthology.org/2023.findings-acl.426.pdf
    Secara intuitif, intinya adalah ketika ada dokumen x1, x2, dan dokumen baru x, jika keteraturan statistik x lebih dekat ke x1 daripada x2, maka len(compress(cat(x1,x))) - len(compress(x)) < len(compress(cat(x2,x))) - len(compress(x)). Di sini cat berarti menggabungkan, dan compress adalah kompresor seperti gzip
    Secara harfiah, len(compress(cat(x1,x))) - len(compress(x)) adalah jumlah byte tambahan yang dibutuhkan untuk mengompresi keteraturan statistik x1 dengan keteraturan statistik x yang telah diberikan. Semakin mirip x1 dan x, semakin sedikit byte tambahan yang dibutuhkan untuk mengompresi cat(x1,x) dibanding hanya mengompresi x saja
    Para penulis menggunakan fungsi jarak bernama Normalized Compression Distance (NCD) berbasis ide ini untuk menerapkan k-nearest neighbors (kNN) pada dokumen yang telah dikompresi. Mereka juga membahas hubungan antara NCD, informasi, entropi Shannon, dan kompleksitas Kolmogorov
    Yang mengejutkan, metode yang sederhana dan intuitif ini mengungguli BERT pada berbagai tugas klasifikasi zero-shot. Namun, itu tidak berarti pasti mengalahkan Transformer yang lebih besar dan lebih baru

    • Metode ini hanya lebih baik pada data di luar distribusi dan ketika token saling tumpang tindih. Ia tidak punya kemampuan memahami makna, hasilnya memang benar, tetapi judulnya menyesatkan
    • Saya penasaran apakah hasilnya akan sedikit lebih baik jika alih-alih sekadar menggabungkan dokumen, digunakan dukungan kamus kompresi zstd
      Caranya dengan membandingkan ukuran kompresi ketika dokumen dipakai sebagai kamus kompresi dan ketika tidak dipakai. Setidaknya pada level 20+, zstd memberi rasio kompresi jauh lebih tinggi daripada gzip, jadi jika alasan metode ini bekerja baik di gzip adalah karena pendekatan terhadap kompleksitas Kolmogorov, mungkin ini bisa bekerja lebih baik
    • Jika masalah yang ingin diselesaikan pada akhirnya adalah “apakah x lebih mirip ke x1 atau x2”, ini tampak berbeda dari masalah yang diselesaikan LLM, jadi tidak terlalu mengejutkan jika hasilnya lebih baik
      Jika x1 berbahasa Inggris dan x adalah terjemahan dokumen yang sama dalam bahasa Ibrani, rasanya LLM akan lebih baik
    • Secara ketat ini bukan zero-shot melainkan few-shot. Tetap diperlukan himpunan prototipe latih yang menjadi acuan
    • Saya penasaran apakah pendekatan yang sama bisa diterapkan pada gambar
      Belakangan saya menangani gambar dan mencoba menghasilkan JPEG, dan ternyata dari piksel dasar yang sama bisa muncul gambar yang sangat beragam. Menarik bahwa makin berisik dan acak sebuah gambar, makin besar ukuran file JPG-nya, dan sebaliknya makin mirip foto, makin kecil ukuran JPG-nya

  • Jika tertarik pada kesetaraan AI dan kompresi, Hutter Prize layak dilihat :) http://prize.hutter1.net/
    Large Text Compression Benchmark juga menarik http://mattmahoney.net/dc/text.html - saat ini kompresor terbaik di dunia adalah jaringan saraf buatan Fabrice Bellard yang terkenal karena membuat ffmpeg dan QEMU
    Saya juga sangat suka gaya khusus teks yang pas dari halaman-halaman seperti ini

    • Terutama algoritma kompresi berbasis arithmetic coding yang menyesuaikan bobot interval dengan memprediksi apa yang akan datang berikutnya sangat mirip
      Ia menyesuaikan arithmetic coding (https://en.wikipedia.org/wiki/Arithmetic_coding) sesuai konteks byte/bit yang akan diprediksi, jadi semakin akurat memprediksi kelanjutannya, semakin efisien pengodeannya. Tugasnya sendiri sangat mirip dengan Transformer seperti GPT
      Prediksi sempurna tidak akan mengecilkan interval aritmetika, sehingga hampir tidak ada biaya penyimpanan tambahan, dan karenanya tidak ada bit yang disimpan. Namun, untuk benchmark yang adil, ukuran dekompresor juga harus dihitung
    • Jika matematika digali lebih dalam, banyak hal pada dasarnya menjadi sama. Super-resolution adalah dekonvolusi yang dikemas secara meyakinkan, perceptron satu lapis adalah SVM kernel linear sekaligus regresi logistik, dan FFT hanyalah faktorisasi
    • Yang penting adalah para penulis menggunakan Normalized Compression Distance (NCD). NCD adalah cara mendekati kompleksitas Kolmogorov
      Ini ide yang cukup lama, lihat [1,2]. Sudah lama, tetapi seperti perceptron tetap sangat berguna
      [1] Li and Vitanyi. An Introduction to Kolmogorov Complexity and Its Applications
      [2] Clustering by compression. https://arxiv.org/pdf/cs/0312044
    • Fabrice Bellard benar-benar legenda hidup. QuickJS, jslinux, tcc, dan TinyGL juga harus ditambahkan ke daftar itu
    • “Kompresi” jenis ini pada dasarnya lebih dekat ke pemahaman melalui teori, seperti teori dalam fisika
      Teori mirip cerita yang mampu menjelaskan banyak hal hanya dengan “tokoh” yang sama. Di sini tokoh lebih dekat ke konsep, misalnya atom cocok masuk dalam kategori ini

  • Saya ingin menekankan bahwa metode ini lebih kuat hanya pada berita
    Pada Yahoo Questions, ini bukan yang berkinerja terbaik. Tidak berlebihan untuk menganggap berita ditulis dengan cara yang mirip dan kadang sebagian isinya disalin, sehingga banyak kata yang sama
    Yahoo Questions adalah forum, jadi variasi katanya lebih besar, tetapi ada kemiripan semantik di antara kata-kata itu
    Artinya gzip kuat ketika banyak kata saling tumpang tindih (kenaikan ukuran saat kompresi gzip kecil), sedangkan jika kemiripan semantik penting, DNN selalu menang
    Hasilnya menarik, tetapi menurut saya tidak semenarik kedengarannya

    • Jika kemiripan semantik berbeda, bagaimana cara kerjanya? Rasanya ini pada akhirnya hanya soal mengelompokkan ekspresi yang semantik-nya mirip selama pelatihan

  • Sangat penting untuk menekankan bahwa hasil ini berasal dari data out-of-distribution. Misalnya berita dalam bahasa seperti ‘Kinyarwanda, Kirundi, Pinyin’
    Dalam pengaturan yang lebih umum, BERT masih menang telak
    Menarik bahwa metode sesederhana ini bisa sangat efektif, tetapi jangan dijual secara berlebihan

    • Poin ini benar-benar perlu lebih ditekankan. Saat hanya membaca judulnya, rasanya mengejutkan seolah-olah mereka secara kebetulan menemukan bukti hukum fisika yang sebelumnya tidak diketahui dan belum terjelaskan, dalam hal ini hukum linguistik
      Tetapi jika melihat kondisi yang dikutip, justru ini cukup intuitif. Apa artinya mengklasifikasikan teks dalam bahasa yang sama sekali tidak dikenal? Jika diminta mengklasifikasikan teks Kirundi, kita sama sekali tidak memahami maknanya, dan yang terbaik yang bisa dilakukan adalah mencari frekuensi urutan kata atau karakter lalu mengelompokkan teks yang punya sidik frekuensi serupa
      Kita tetap tidak memahami makna sebenarnya, tetapi hasilnya bisa lebih baik daripada acak, dan memang begitu. Kabar baiknya, itulah tepatnya yang dilakukan gzip+kNN, itulah fungsi utama dan alasan keberadaannya
      Mencoba membaca dan memahami teks ini atau memprediksi karakter berikutnya juga tidak banyak membantu. Orang normal, karena tidak tahu bahasanya, bahkan tidak akan mencoba sejak awal. Sayangnya BERT melakukan tepat hal itu. Karena itu satu-satunya hal yang BERT tahu cara lakukan. Tetap saja, patut diberi selamat karena berhasil mengekstrak kegunaan lebih besar daripada manusia biasa, dan mungkin juga lebih besar daripada manusia yang tidak biasa

  • Ini benar-benar cerdas dan mudah dipahami secara intuitif
    Jika Anda menyambungkan dua potong teks yang mirip, hasilnya akan terkompresi lebih baik daripada jika menyambungkan dua potong teks yang berbeda

    • Ini teknik yang memang sudah dikenal, tetapi tidak terlalu terkenal. Kontribusi utamanya di sini adalah formalisasi dan pengukuran

  • Ini tampaknya lebih merupakan sinyal negatif bagi kemiripan berbasis deep learning daripada kemenangan untuk metode ini
    Di tengah hype LLM, memang benar LLM itu hebat, tetapi tampaknya banyak orang mengasumsikan ada kemajuan serupa pada lapisan embedding untuk kemiripan teks murni
    Karena itu muncul ledakan berbagai database embedding, tetapi menurut saya hampir tidak ada bukti yang mendukungnya

    • https://twitter.com/eugeneyan/status/1678060204943097863

      When Deepmind needs semantic retrieval, they just use the largest index on the planet.
      Fakta menarik: kemiripan kueri-dokumen ditangani bukan dengan vektor, melainkan TF-IDF sederhana. Setelah jumlah dokumen pencarian melebihi 45, hasilnya lebih baik daripada pencarian vektor, dan dalam praktiknya mereka memakai 50
      https://blog.vespa.ai/improving-zero-shot-ranking-with-vespa...
      This case illustrates that in-domain effectiveness does not necessarily transfer to an out-of-domain zero-shot application of the model. Generally, as observed on the BEIR dense leaderboard, dense embeddings models trained on NQ labels underperform the BM25 baseline across almost all BEIR datasets.

    • Bisakah seseorang menjawab satu pertanyaan? Saat membuat embedding teks dengan LLM untuk dipakai mengukur kemiripan, lapisan mana yang digunakan? Lapisan input? Input + positional encoding? Lapisan tersembunyi? Lapisan output?

  • Tautannya seharusnya mengarah ke PDF makalah https://aclanthology.org/2023.findings-acl.426.pdf

  • Algoritma kompresi adalah penghematan/kompresi ruang, yaitu bit dan byte. Model machine learning, khususnya model generatif, adalah penghematan/kompresi ekspresi dan pikiran manusia
    Klasifikasi teks adalah salah satu jenis kompresi di atas ekspresi manusia. Adakah sifat mendasar dari bahasa manusia dan data yang bisa menjelaskan mana yang akan bekerja lebih baik pada tugas machine learning?
    Jika suatu hari teori semacam itu terbentuk, mungkin tidak akan terlalu mengejutkan bahwa encoding bit/byte yang terkompresi dan ekspresi manusia yang terkompresi saling berkaitan erat dalam suatu ruang, sehingga keduanya terhubung dengan cara tertentu. Bahkan teori semacam itu, misalnya teori berbasis entropi atau fisika, bisa membantu memilih kapan memakai algoritma kompresi atau model machine learning untuk jenis kompresi ekspresi manusia tertentu
    Dari sudut pandang data, seperti apa contoh negatif yang sulit yang membuat algoritma seperti ini tampak buruk? Untuk saat ini, mungkin teori itu hanya bisa didekati dari sudut pandang jenis-jenis data teks manusia yang beragam. Misalnya memprediksi campuran dengan model topik statistik bekerja baik pada teks akademik, tetapi kesulitan pada teks internet
    Adakah orang yang meneliti teori seperti ini selain Wolfram Physics?

  • Ini sepenuhnya masuk akal. Kompresi berkaitan dengan “pemahaman”, yaitu merepresentasikan input dengan cara yang memungkinkan kita mengenali dan memberinya label
    Jika bit yang dikenali lebih besar daripada labelnya, voilà, terjadilah kompresi. Tidak mengejutkan bahwa gzip bisa lebih baik daripada DNN untuk tugas ini

    • Kalau begitu saya jadi penasaran apakah algoritma kompresi lain bisa bekerja lebih baik
    • Saya melihat kompresi sebagai himpunan bagian dari pemahaman. Ketika seorang anak mulai berbicara secara gramatikal benar, ia telah mengompresi semua pola bahasa yang terpapar menjadi aturan tata bahasa
      Saya menyebutnya himpunan bagian karena pemahaman lebih umum. Algoritma kompresi tertentu mungkin bekerja baik pada bilangan floating-point. Sebaliknya, otak dan jaringan saraf tiruan mungkin bisa mengompresi pola input apa pun, meskipun kinerjanya bisa lebih buruk

  • Saya tidak mengerti bagaimana gzip bisa menangani kata seperti “not” yang membalikkan makna seluruh kalimat
    Ada yang paham?

    • Seperti juga disebutkan dalam beberapa komentar di Twitter, ini untuk topic modeling. Kata negasi mungkin kurang penting di sini dibandingkan pada tugas seperti analisis sentimen