Pengarang: Rodrigo Agundez
Awalnya diterbitkan di Menuju AI.
Dukungan ChunkDot untuk matriks jarang
Foto oleh Nabil Boukala di Unsplash
Dalam posting blog saya sebelumnya, saya memperkenalkan ChunkDot, sebuah perpustakaan yang melakukan multi-threaded matrix multiplication dan cosine similarity. ChunkDot sesuai untuk menghitung K item yang paling mirip untuk sejumlah besar item dengan membagi representasi matriks item (embeddings) dan menggunakan Numba untuk mempercepat penghitungan.
Kemiripan Cosinus untuk 1 Triliun Pasang Vektor
Memperkenalkan ChunkDot
pub.towardsai.net
Saya menjelaskan bagaimana ChunkDot bekerja secara tersembunyi dan saya menunjukkan beberapa tolok ukur terhadap waktu eksekusi dan konsumsi memori untuk penyematan yang padat. Saya baru-baru ini memperluas dukungan ke matriks jarang, posting blog ini bertujuan untuk menjelaskan metodologi dan menunjukkan contoh bagaimana Anda dapat menggunakannya.
Jika Anda ingin melewatkan penjelasan dan langsung masuk ke petunjuk penggunaan:
chunkdot
Perkalian matriks multi-utas dan perhitungan kesamaan kosinus. Sesuai untuk perhitungan K paling…
pypi.org
Motivasi
Perhitungan kesamaan cosinus menggunakan representasi vektor jarang mengalami masalah yang sama seperti menggunakan representasi vektor padat. Meskipun item direpresentasikan sebagai matriks penyisipan yang jarang, semua perhitungan kesamaan berpasangan mungkin bukan nol. Jika Anda memiliki N item, perhitungan persamaan berpasangan akan menghasilkan matriks kesamaan yang padat N x N, dengan jejak memori yang diskalakan sebagai N². Untuk item 100K, ini adalah ~80GB, dan untuk 1 juta ~8000GB.
ChunkDot membagi matriks penyematan menjadi beberapa bagian dan memparalelkan perhitungan kesamaan kosinus, mengambil K item yang paling mirip per item. Diagram di bawah menunjukkan cara kerja ChunkDot, tetapi silakan merujuk ke posting blog saya sebelumnya untuk detailnya.
Diagram yang menjelaskan algoritma Cosine Similarity Top K ChunkDot
Ada beberapa kasus penggunaan yang melakukan perhitungan kesamaan atas representasi vektor yang jarang, misalnya, sering terjadi di NLP bahwa vektorisasi korpus teks dilakukan melalui penggunaan token, n-gram, atau kata-kata. Ini menghasilkan representasi matriks yang sangat jarang di mana kosakata untuk korpus total jauh lebih besar daripada kosakata untuk setiap dokumen. Dengan memperluas dukungan ChunkDot ke matriks jarang, ChunkDot dapat membantu meningkatkan perhitungan ini dan mendukung penggunaan kasus seperti:
Deduplikasi dokumen. Rekomendasi untuk dokumen serupa. Clustering / Tagging / Pengelompokan dokumen.
ChunkDot untuk Matriks Jarang
Untuk mendukung matriks renggang, ChunkDot menggunakan metodologi multi-threading Numba yang sama. Rilis baru ini menambahkan logika perkalian matriks renggang yang kompatibel dengan Numba dalam mode tanpa-python. Kemudian logika perkalian matriks jarang ini disematkan di setiap utas paralel untuk menghitung kesamaan cosinus terpotong.
Paralelisasi bagian dari algoritma Top K ChunkDot’s Cosine Similarity
Saya ingin menggunakan implementasi perkalian matriks jarang SciPy tetapi sayangnya, SciPy tidak didukung oleh Numba, jadi saya harus menulis logikanya sendiri. Saya membuat keputusan untuk mendukung semua format matriks jarang SciPy tetapi, di balik layar, melakukan perkalian matriks dalam format CSR; itu terlihat seperti ini:
nilai = np.nol((kiri_n_baris, kanan_n_kolom))
untuk row_left dalam rentang(left_n_rows):
untuk left_i dalam rentang (matrix_left_indptr[row_left]matrix_left_indptr[row_left + 1]):
col_left = matrix_left_indices[left_i]
nilai_kiri = matriks_kiri_data[left_i]
untuk right_i dalam rentang (matrix_right_indptr[col_left]matrix_right_indptr[col_left + 1]):
col_right = matrix_right_indices[right_i]
nilai_hak = matriks_hak_data[right_i]
nilai-nilai[row_left, col_right] += nilai_kiri * nilai_kanan
Jika Anda tidak terbiasa dengan matriks renggang, logikanya mungkin agak menantang untuk dipahami. Setidaknya bagi saya. Singkatnya, apa yang dilakukan logika di atas adalah untuk mendapatkan, per baris, indeks kolom dari setiap item bukan nol di matriks kiri dan kemudian melompat langsung ke baris matriks kanan untuk indeks kolom itu, akhirnya digabungkan ke entri matriks perkalian kedua nilai tersebut.
Kesamaan Kosinus pada korpus entri blog
Dalam contoh ini, saya hanya berkonsentrasi pada penerapan ChunkDot untuk perhitungan kesamaan. Saya tidak berusaha membersihkan atau menormalkan korpus seperti yang seharusnya dilakukan dalam kasus penggunaan yang sebenarnya.
Mari kita baca 100 ribu posting blog dan lihat beberapa contoh:
impor panda sebagai pd
blogs = pd.read_csv(“blogtext.csv”, usecols=[“text”]nrows=100000)
untuk _, teks di blogs.sample(3).iterrows():
cetak(teks.teks, “n”)
“Cordy memiliki momennya. Anda tahu apa yang dimiliki? ‘Inside Out’ oleh urlLink Eve 6 . Saya akan benar-benar membuat diri saya terlihat muda di sini dan hanya mengatakan bahwa lagu itu adalah salah satu lagu kebangsaan generasi saya. Saya bergoyang sampai hampir kehilangan suara saya dalam perjalanan pulang kerja hari ini. Itu menendang pantat sebanyak itu. Anda tahu apa lagi yang dimiliki? Tuna meleleh yang enak. Kuharap aku bisa bahagia hari ini tidak merasa begitu bersalah tentang betapa buruknya kekalahan kita saat ini. “
“Tentang Bubb Rubb dan Woo Woo….. Untuk sepenuhnya memahami sedikit komedi yang luar biasa yaitu Bubb Rubb dan Woo Woo, pertama-tama Anda harus menonton sedikit urlLink News Clip dari Oakland. Setelah Anda menonton klipnya, langsung buka situs urlLink Bubb Rubb dan campur sendiri….. beri tahu saya pendapat Anda… Saya membuang waktu 20 menit untuk bermain-main dengannya…. selamat menikmati! “
“Ini yang saya dengar hari ini (artinya dia mengatakannya untuk pertama kalinya AFAIK) > pizza (pee-zah)(pee-tah) domba (seep) kick wagon paper printer (pin-tah) fishie movie sit down (sih down ) tongkat bouncing — — — — — — Saya pikir itu saja. Dia mengulangi begitu banyak hal akhir-akhir ini, dan mengeluarkan begitu banyak kata yang belum pernah saya dengar dia gunakan sehingga saya tidak bisa melacaknya lagi. Sulit dipercaya bagaimana kosakatanya, atau setidaknya upayanya untuk menggunakan kosakata yang ada, baru saja meledak akhir-akhir ini. Dia akan menjadi mesin bicara dalam waktu singkat.”
Posting blog kaya akan konten dan jumlah kata yang digunakan, korpus realistis yang bagus untuk contoh kita. Plot di bawah ini menunjukkan bahwa kumpulan data ini memiliki teks yang tersebar di seluruh spektrum dalam hal jumlah kata yang digunakan.
Histogram jumlah kata dalam postingan blog
Sekarang mari kita buat vektor korpus. Di sini saya menggunakan TfidfVectorizer dari SciKit-Learn untuk kesederhanaan tetapi logika ini dapat diganti dengan apa pun yang akan menghasilkan representasi matriks jarang dari korpus teks.
dari sklearn.feature_extraction.text impor TfidfVectorizer
vektorizer = TfidfVectorizer(analyzer=”kata”, stop_words=”bahasa inggris”)
embeddings = vectorizer.fit_transform(blog[“text”])
embeddings
<100000x214146 jarang matriks tipe '
dengan 6817666 elemen yang disimpan dalam format Compressed Sparse Row>
Matriks penyematan yang dihasilkan terdiri dari 100K baris yang mewakili setiap posting blog dan 214K kolom yang mewakili setiap kata dalam kosakata korpus. Jika penyematan direpresentasikan dalam bentuk padat, penyematan akan menempati ~171 GB memori, sebaliknya penyematan direpresentasikan sebagai matriks jarang dengan kepadatan ~0,003.
Sekarang mari kita hitung 10 posting blog paling mirip per posting blog menggunakan ChunkDot.
dari chunkdot impor cosine_similarity_top_k
kesamaan = cosine_similarity_top_k(embeddings, top_k=10)
kesamaan
<100000x100000 jarang matriks tipe '
dengan 1.000.000 elemen tersimpan dalam format Compressed Sparse Row>
Perhitungan kesamaan kosinus memakan waktu ~1 menit.
dari waktu impor waktu itu
timeit(lambda: cosine_similarity_top_k(embeddings, top_k=10), angka=1)
67.77648650599997
Untuk jarang atau tidak jarang, itulah pertanyaannya
Karena penyematan dapat direpresentasikan sebagai padat atau jarang dan logika perkalian matriks berbeda untuk keduanya, wajar untuk bertanya, haruskah saya selalu menggunakan representasi jarang? Jawabannya adalah tidak.
Ada penalti kinerja pada perhitungan atas matriks renggang yang tidak cukup renggang. Di bawah ini adalah perbandingan kinerja perkalian matriks saat menggunakan matriks padat dan perkalian matriks padat versus saat menggunakan matriks jarang dan perkalian matriks jarang. Hasilnya disajikan sebagai rasio, nilai yang lebih besar dari satu berarti representasi jarang lebih cepat.
Waktu eksekusi untuk perkalian matriks saat menggunakan matriks padat atau matriks jarang. Tampaknya hasil yang semakin berkurang menggunakan matriks jarang mulai sudah di atas 0,02.
Seperti yang bisa kita lihat, menggunakan representasi renggang masuk akal hanya untuk kerapatan di bawah ~0,03. Untuk kepadatan yang lebih tinggi, keuntungannya berkurang dengan cepat, tetapi pada saat yang sama, untuk matriks besar dan kepadatan rendah ~.001, ada keuntungan 100x menggunakan representasi jarang. Dalam contoh NLP di atas, densitas matriks embedding adalah ~0,003.
Kesimpulan
Saya harap posting blog ini dan ChunkDot bermanfaat bagi Anda! Saya senang menambahkan dukungan matriks jarang. Beberapa peningkatan potensial:
Perluas fungsionalitas ke 2 matriks masukan yang berbeda. Hitung kesamaan cosinus antara baris matriks dan baris matriks lainnya. Alih-alih mengembalikan K item yang paling mirip, kembalikan item yang kemiripannya di atas/di bawah ambang batas tertentu. Tambahkan dukungan GPU karena Numba mendukungnya.
Numba untuk GPU CUDA – dokumentasi Numba 0.56.4+0.g288a38bbd.dirty-py3.7-linux-x86_64.egg
Callback ke Python Interpreter dari dalam kode JIT
numba.readthedocs.io
Diterbitkan melalui Menuju AI
