Part of Speech Tagger untuk Bahasa Indonesia Menggunakan Konsep Hidden Markov Model (HMM) dan Algoritma Viterbi

Pada artikel ini saya akan membahas pengalaman saya dalam mengembangkan sebuah aplikasi Part of Speech Tagger untuk bahasa Indonesia menggunakan konsep HMM dan algoritma Viterbi.

Apa itu Part of Speech?

Part of Speech (POS) bisa juga dipandang sebagai kelas kata (word class). Sebuah kalimat tersusun dari barisan kata dimana setiap kata memiliki kelas kata nya sendiri. Sebagai contoh, kalimat “saya makan nasi” tersusun dari 3 buah kata, yaitu “saya”, “makan”, dan “nasi”. Dalam hal ini, urutan kelas kata dalam kalimat tersebut adalah kata ganti orang, kata kerja, dan kata benda.

Apa itu Part of Speech Tagging?

Part of Speech Tagging (POS Tagging) merupakan proses pemberian kelas kata terhadap setiap kata dalam suatu kalimat. Perangkat yang digunakan untuk melakukan POS Tagging disebut dengan POS Tagger.

Tujuan Part of Speech Tagging

Memberikan prediksi terhadap barisan kelas kata yang mungkin dari suatu barisan kata-kata. Secara probabilistik dapat dituliskan sebagai P (Y | X), dimana Y merupakan barisan kelas kata dan X merupakan barisan kata.

Dataset

Dataset yang digunakan sebagai training data adalah UI-1M-tagged yang diambil dari http://panl10n.net/english/OutputsIndonesia2.htm (One Million POS Tagged Corpus of Bahasa Indonesia) .

Bahasa dan Kelas Kata (tags)

POS Tagger diaplikasikan pada bahasa Indonesia. Kumpulan kelas kata yang digunakan adalah ‘nn’, ‘nnc’, ‘nnu’, ‘jj’, ‘in’, ‘,’, ‘vbt’, ‘cc’, ‘nnp’, ‘sym’, ‘cdp’, ‘vbi’, ‘fw’, ‘sc’, ‘.’, ‘rb’, ‘nng’, ‘cdi’, ‘cdo’, ‘neg’, ‘dt’, ‘prp’, ‘–‘, ‘md’, ‘wrb’, ‘:’, ‘-‘, ‘nns’, ‘prn’, ‘prl’, ‘rp’, ‘vb’, ‘wp’, ‘cdc’, dan ‘uh’. Dalam artikel ini, kelas kata akan disebut juga dengan istilah tags.

Metodologi

Model dibangun dengan metode Hidden Markov Model (HMM) dan algoritma Viterbi. Model dibangun berdasarkan peluang transisi (transition probability) dan emisi (emission probability) dari setiap kata yang ditemukan dalam training data.

Peluang transisi menyatakan seberapa besar kemungkinan munculnya suatu kelas kata dimana sebelumnya muncul kelas kata tertentu. Contoh dari peluang transisi adalah P(V | N) yang menyatakan peluang kemunculan kelas kata Verb setelah kelas kata Noun.

Peluang emisi menyatakan seberapa besar kemungkinan munculnya suatu kata diberikan kelas kata tertentu. Contoh dari peluang emisi adalah P(language | N) yang menyatakan peluang kemunculan kata ‘language’ dan memiliki kelas kata Noun.

Proses mencari nilai peluang transisi dan emisi terdiri dari dua langkah, yaitu menghitung jumlah kemunculan transisi atau emisi dan menghitung jumlah kelas kata yang bersangkutan. Sebagai contoh, pada Gambar 1. dapat dilihat bahwa dalam training data terdapat sebuah barisan kata “pemrosesan bahasa natural” yang memiliki barisan tags “JJ NN NN”. Peluang transisi dari kelas kata NN diikuti oleh JJ dihitung dengan rumus Pt (NN | JJ) = c (JJ NN) / c (JJ). Sedangkan peluang emisi dari kata bahasa diikuti kelas kata NN dihitung dengan rumus Pe (bahasa | NN) = c (NN bahasa) / c (NN).

Untuk menghitung peluang transisi dari kelas kata yang memiliki indeks pertama dan terakhir dalam barisan, maka digunakan dummy tags berupa <s> (memiliki indeks 0 dan terletak sebelum kelas kata pertama) dan </s> (memiliki indeks n+1 dan terletak setelah kelas kata terakhir). Sebagai contoh, barisan kelas kata JJ NN NN akan menjadi <s> JJ NN NN </ss>.

 

Gambar 1. Peluang transisi (merah) dan emisi (biru)^[1]

 

Metode HMM digunakan untuk membangun model probabilistik. Untuk melakukan pengujian terhadap testing data, digunakanlah algoritma Viterbi. Algoritma Viterbi untuk menentukan urutan tags terbaik terdiri dari dua tahap, yaitu forward step dan backward step. Forward step digunakan untuk mencari lintasan terbaik dari suatu graf kelas kata. Graf kelas kata merupakan matriks berukuran jumlah kelas kata x jumlah kata yang berisi semua tags sebagai kelas kata dari suatu kata tertentu. Prinsip dari forward step adalah mencari tag terbaik sebagai kelas kata dari kata pada indeks tertentu dengan mempertimbangkan konteks dari semua kata maupun kelas kata sebelumnya. Secara matematis, pencarian dilakukan dengan menemukan lintasan ke setiap kelas kata dengan nilai logaritma probabilitas terendah (the lowest negative log probability). Dengan menggunakan contoh sebelumnya, yaitu kalimat “pemrosesan bahasa natural” dan misalkan kelas kata yang tersedia dalam training data adalah NN, JJ, dan VBI, maka matriks yang terbentuk diilustrasikan pada Gambar 2..

 

Tabel 1. Graf kelas kata yang direpresentasikan dalam bentuk matriks

 

Gambar 2. Lintasan yang menunjukkan semua kemungkinan urutan kelas kata^[1]

 

Gambar 3. Lintasan yang menyatakan urutan kelas kata terbaik^[1]

 

Gambar 4. Menghitung peluang transisi dan emisi dari <s> untuk kata pertama dengan setiap
kelas kata^[1]

 

Gambar 5. Menemukan lintasan ke setiap kelas kata dengan nilai logaritma probabilitas terendah (the
lowest negative log probability)^[1]

 

Gambar 6. Pencarian nilai best score untuk kata terakhir^[1]

 

Forward step menghasilkan dua buah elemen penting dalam pembentukan lintasan, yaitu node N yang berisi nama kelas kata dan sisi lintasan E yang menunjukkan node kelas kata sebelumnya. Sebagai contoh, pada Gambar 3. dapat dilihat bahwa urutan kelas kata terbaik yang didapat adalah <s> natural (JJ), language (NN), processing (NN), ( (LRB), nlp (NN), ) (RRB), </s>. Node N menyatakan kelas kata yang bersangkutan, sementara E menyatakan node kelas kata sebelumnya, misalnya E(language, NN) adalah natural (JJ), sedangkan E(processing, NN) adalah language (NN).

Setelah mendapatkan lintasan terbaik, maka state terakhir berada pada kelas kata dummy, yaitu </s>. Untuk menghasilkan kembali lintasan yang didapat pada forward step, maka digunakanlah elemen E. Dimulai dari kelas kata terakhir, kelas kata berikutnya ditentukan berdasarkan nilai E. Sebagai contoh, dimulai dari kelas kata dummy </s> yang memiliki node ) (RRB) sebagai node sebelumnya, maka state sekarang berada pada node ) (RRB) tersebut. Node ) (RRB) memiliki node nlp (NN) sebagai node sebelumnya dan node nlp (NN) memiliki node ( (LRB) sebagai node sebelumnya. Proses ini dilakukan sampai state berada pada kelas kata dummy <s>. Setiap node yang didapat saat proses backward step ini akan dimasukkan ke dalam list. Setelah semua node didapatkan, isi dari list tersebut akan di reverse sehingga didapatkan urutan kelas kata terbaik untuk urutan kata yang diberikan.

 

Algoritma Pembelajaran

Berikut pseudocode dari algoritma pembelajaran menggunakan HMM untuk membangun model probabilistik.

 

Gambar 7. Algoritma pembelajaran menggunakan Hidden Markov Model ^[1]

 

Salah satu masalah yang muncul dalam pembangunan model probabilistik dengan HMM ini adalah Out Of Vocabulary (OOV). OOV membuat penghitungan peluang emisi tidak dapat dilakukan dengan pendekatan normal (rumus seperti yang dijelaskan sebelumnya). Masalah muncul ketika menjalankan bagian forward step dari algoritma Viterbi. Algoritma Viterbi melakukan pengecekan terhadap peluang emisi dari setiap kata dengan mempertimbangkan semua kelas kata yang tersedia. Kata-kata yang tidak terdapat dalam model tentu tidak memiliki peluang emisi, atau dengan kata lain algoritma akan melakukan assign value bernilai 0 terhadap peluang emisi. Walau demikian, tidak ada jaminan bahwa unknown words tidak akan muncul dengan kelas kata tertentu. Faktanya adalah bahwa training data tidak menyimpan semua kondisi yang mungkin terjadi.

Oleh karena itu, perlu adanya pemberian nilai terhadap peluang emisi bagi unknown words walaupun nilainya sangat kecil. Metode Laplace Smoothing dapat menjadi solusi bagi permasalahan ini. Prinsip kerja dalam menghitung nilai peluang sama seperti pendekatan normal tetapi ada dua elemen yang membuat nya dapat menjadi solusi. Elemen pertama adalah lambda score yang memiliki nilai bebas, tetapi biasanya memiliki nilai 1. Lambda score bertindak sebagai nilai tambah pada bagian pembilang dari suatu pecahan peluang, dimana ia berfungsi untuk memastikan bahwa nilai peluang dari unknown words tidak sama dengan 0. Elemen kedua adalah jumlah vocabulary. Vocabulary merupakan kumpulan kata-kata unik dalam training data yang bertindak sebagai nilai tambah pada bagian penyebut dari suatu pecahan peluang. Berikut potongan kode program untuk menghitung peluang emisi menggunakan Laplace Smoothing:

 

Gambar 8. Perhitungan peluan emisi menggunakan Laplace Smoothing

 

Pada bagian metodologi dijelaskan bahwa dengan model probabilistik yang sudah dibangun, urutan kelas kata dapat dicari dengan algoritma Viterbi. Berikut pseudocode dari masing-masing tahapan pada algoritma.

 

Gambar 9. Forward step dari algoritma Viterbi^[1]

 

Gambar 10. Backward step dari algoritma Viterbi^[1]

 

Referensi

[1] Neubig, G. 2015. NLP Programming Tutorial 5 – Part of Speech Tagging with Hidden Markov Models. http://www.phontron.com/slides/nlp-programming-en-04-hmm.pdf (Diakses pada 11 Januari 2018)