Dekripsi Cipher Part 4

Add-One Smoothing

Sekarang setelah kita memahami model bahasa dasar, mari kita bahas sebuah modifikasi penting yang disebut add-one smoothing (atau Laplace smoothing). Tujuannya adalah untuk mengatasi masalah probabilitas nol pada model bahasa.

Masalah yang terjadi tanpa smoothing

Bayangkan kita punya bigram (pasangan kata/huruf) yang tidak pernah muncul di data pelatihan kita, tapi ternyata muncul di kalimat yang ingin kita proses.

• Jika suatu bigram tidak pernah muncul, probabilitasnya dihitung sebagai 0.
• Karena model kalimat dihitung sebagai perkalian probabilitas kata-kata/huruf, jika ada satu probabilitas nol, seluruh kalimat jadi nol.
• Ini jelas tidak bagus, karena kita kehilangan informasi apakah kalimat tersebut masih mungkin masuk akal.

Solusi: Add-One Smoothing

Rumusnya adalah:

• count(xt-1 → xt) = jumlah transisi dari huruf/katа sebelumnya ke huruf/katа berikutnya.
• +1 = menambahkan “satu kemunculan imajiner” agar probabilitas tidak pernah nol.
• V = jumlah total huruf dalam alfabet (atau jumlah kata dalam kosakata). Ditambahkan ke penyebut agar distribusi tetap valid (jumlah probabilitas tetap 1).

Artinya: setiap kemungkinan transisi, bahkan yang belum pernah muncul, tetap mendapat probabilitas kecil.

Pembuktian

• Kita ambil jumlah semua probabilitas kemungkinan huruf berikutnya (dari 1 sampai V).

• Masukkan rumus add-one smoothing. Karena penyebut tidak bergantung pada v, kita bisa keluarkan dari sigma.
• Di dalam sigma, ada dua bagian:

1. Jumlah count (xt-1 → v) = total kemunculan xt−1​.
2. Jumlah dari 1 sebanyak V kali = V.

• Jadi:

• Setelah disubstitusi kembali, atas = bawah → hasilnya 1. Artinya distribusi probabilitas valid.

Intinya

• Tanpa smoothing → bigram baru dapat probabilitas 0, kalimat jadi nol.
• Dengan add-one smoothing → setiap transisi punya peluang kecil tapi bukan nol, sehingga kalimat tetap bisa dievaluasi.

Cara Menggunakan Model

Hal berikutnya yang perlu kita pertimbangkan adalah bagaimana cara menggunakan model ini untuk benar-benar mendekripsi pesan. Intinya, setelah kita membangun model dengan menghitung semua probabilitas menggunakan corpus teks bahasa Inggris, maka kita bisa menghitung probabilitas dari setiap rangkaian huruf atau kalimat.

Misalnya, jika saya menerjemahkan pesan dengan salah dan hasilnya berupa teks acak seperti “G BGWQ LRPM”, maka probabilitasnya akan sangat rendah karena itu bukan bahasa Inggris.

Sebaliknya, jika saya menerjemahkan dengan benar menjadi “I LIKE CATS”, maka probabilitasnya akan sangat tinggi karena itu adalah bahasa Inggris yang benar.

Dengan kata lain, ini mirip dengan masalah maximum likelihood (kemungkinan maksimum). Kita ingin menemukan hasil decoding sedemikian rupa sehingga pesan keluarannya memiliki kemungkinan paling besar.

Masalah Praktis

Ada satu hal praktis yang harus dipertimbangkan sebelum melangkah lebih jauh.

Masalahnya, probabilitas dalam language modeling biasanya sangat kecil. Misalkan rata-rata probabilitas sebuah transisi adalah 1/10 atau 0,1 (anggap saja benar).

Sekarang bayangkan jika kita punya kalimat sepanjang 100 karakter. Maka probabilitas keseluruhannya adalah 10 pangkat –100, yang merupakan angka sangat kecil.

Angka probabilitas sekecil ini biasanya akan dianggap nol oleh komputer (dibulatkan ke bawah).

Itu masalah, karena kalau semuanya dianggap nol, kita tidak bisa membedakan mana probabilitas yang paling besar.

Log — likelihood

Solusinya adalah menggunakan log-likelihood alih-alih likelihood mentah. Karena likelihood asli adalah hasil perkalian dari probabilitas, ketika kita mengambil log, perkalian berubah menjadi penjumlahan sesuai aturan logaritma.

Kenapa ini bekerja? Misalnya, jika saya mengambil log dari 0,1, saya mendapatkan -2,3. Tapi jika saya mengambil log dari angka yang jauh lebih kecil, misalnya jutaan atau miliaran kali lebih kecil dari 0,1, hasil log-nya masih hanya sekitar -20,7. Jadi meskipun angka aslinya sangat kecil, nilai log-nya tetap bisa dikelola oleh komputer.

Sekarang, mungkin muncul pertanyaan: apakah ini mengubah jawaban? Sebenarnya tidak, karena logaritma adalah fungsi monotonik naik. Ingat, yang kita pedulikan bukan nilai likelihood sebenarnya, melainkan hanya urutan relatifnya untuk menentukan terjemahan yang benar. Dengan kata lain, kita tidak perlu tahu nilai likelihood persisnya; kita hanya perlu tahu terjemahan mana yang menghasilkan likelihood maksimum.

• Grafik kiri menunjukkan likelihood mentah (hasil perkalian probabilitas). Nilainya cepat sekali mengecil hingga hampir nol, sehingga sulit dikelola.
• Grafik kanan menunjukkan log-likelihood (hasil penjumlahan log probabilitas). Nilainya menurun secara bertahap, sehingga jauh lebih mudah ditangani oleh komputer.