Satu langkah merge BPE

Byte-pair encoding membangun kosakata subword dengan berulang kali menggabungkan pasangan simbol yang paling sering muncul berdampingan. Implementasikan satu langkahnya:

Hitung semua pasangan simbol bersebelahan di semua kata (setiap kata dihitung sekali per kemunculannya di list).
Pilih pasangan dengan hitungan terbanyak. Jika seri, pilih pasangan terkecil secara leksikografis, yaitu bandingkan simbol pertama lalu simbol kedua.
Gabungkan setiap kemunculan pasangan itu di setiap kata, dipindai dari kiri ke kanan tanpa tumpang tindih.

Kembalikan [[a, b], kata_baru], atau [None, words] jika tidak ada pasangan sama sekali.

[["m","a","k","a","n"], ["m","a","k","a"]]
pasangan: (m,a)=2, (a,k)=2, (k,a)=2, (a,n)=1  →  seri, pilih ("a","k")
→ [["a","k"], [["m","ak","a","n"], ["m","ak","a"]]]

[["a","a","a"]]  →  [["a","a"], [["aa","a"]]]   // tidak tumpang tindih

Kenapa subword

Kosakata kata utuh tidak bisa menangani kata baru (“dimakan”, “kemakan”, typo). Kosakata karakter bisa menangani semuanya, tetapi urutannya sangat panjang. BPE adalah jalan tengah: kata yang sering muncul menjadi satu token, sedangkan kata langka dipecah menjadi potongan yang lebih umum, misalnya di + makan.

Algoritmanya

kosakata = semua karakter
ulangi sampai ukuran kosakata tercapai:
    pasangan terbanyak (a, b)  →  tambahkan "ab" ke kosakata
    ganti setiap a b di korpus dengan ab

Urutan merge disimpan. Untuk men-tokenisasi teks baru, terapkan merge yang sama dengan urutan yang sama. GPT-2 menjalankan BPE di level byte dengan 50 ribu merge, sehingga teks apa pun (emoji, kode, bahasa apa pun) selalu bisa direpresentasikan.

Efek samping

Tokenisasi menjelaskan banyak keanehan LLM: susah menghitung huruf dalam kata (karena model melihat token, bukan huruf), angka dipecah tidak konsisten, dan bahasa selain Inggris butuh lebih banyak token untuk teks yang sama.

Penjelasan

Yang diminta. Satu putaran BPE: hitung pasangan bersebelahan, pilih yang terbanyak, gabungkan semua kemunculannya.

Langkah di kode:

Hitung. for pair in zip(w, w[1:]) memberi semua pasangan bersebelahan dalam satu kata (zip berhenti di yang terpendek). Hitungannya dikumpulkan di dict counts.
Pilih. min(counts, key=lambda p: (-counts[p], p)). Kuncinya tuple: -count membuat hitungan terbesar menjadi yang terkecil, lalu jika seri, p (tuple string) dibandingkan secara leksikografis. Satu min menangani dua aturan sekaligus.
Gabung. Untuk setiap kata, berjalan dengan indeks i: jika (w[i], w[i+1]) == (a, b), tambahkan a + b dan lompat 2; jika tidak, tambahkan w[i] dan lompat 1.

Kenapa lompat 2. Di ["a", "a", "a"] dengan pasangan ("a", "a"), setelah menggabung posisi 0–1, posisi 1 sudah terpakai. Lompat 2 mencegah tumpang tindih, jadi hasilnya ["aa", "a"], bukan ["aa", "aa"].

Cek case 1. (m,a), (a,k), (k,a) masing-masing muncul 2 kali. Secara leksikografis ("a","k") paling kecil, jadi "ak" yang digabung.

Yang dikembalikan: [[a, b], kata_baru], atau [None, words] jika tidak ada pasangan (semua kata hanya 1 simbol).