PERANCANGAN APLIKASI PERINGKAS KALIMAT DENGAN MENGGUNAKAN METODE NOISY CHANNEL MODEL

PERANCANGAN APLIKASI PERINGKAS KALIMAT DENGAN MENGGUNAKAN METODE NOISY CHANNEL MODEL Helmy Thendean, Hartono Mochtar Program Studi Teknik Informatika Universitas Tarumanagara Jl. Let. Jend. S. Parman No. 1, Jakarta 11440 Telp.: +6221-5676260, +6221-5638351 Ext. 11, e-mail: [email protected], [email protected]

Abstract Sentence-compression task is usually done to create a shorter sentence but still contained important information and grammatically correct. The objective to create a shorter sentence is to decrease the time consuming in natural language processing. This research was intended to design and implement a sentence-compression model using noisy channel model. The initial learning database in this model used a Ziff Davis Corpus (newspaper articles about computer) that contained 1067 pair of sentences and its compression by the human expert. The experiment showed that this adaptive model can compress the sentence in the level “good enough” by using 80% level of summary. Keywords: noisy channel model, compression, Ziff Davis corpus.

perhitungannya. Probabilitas ini didapat dengan cara menghitung kemunculan tiap kata yang ada dalam sebuah corpus (data latih). Dalam perancangan ini, rumus probabilitas yang digunakan adalah rumus probabilitas Bayes. Dalam merancang aplikasi ini digunakan tiga buah program yang akan dimodifikasi sesuai dengan kebutuhan aplikasi peringkas kalimat ini. Program-program tersebut antara lain Brill Tagger untuk menandai kelas dari tiap kata dalam kalimat, Collins Parser untuk membentuk tree dari kalimat tersebut, dan Tiburon untuk membentuk expansion-template atau kumpulan kalimat yang mungkin sebagai hasil ringkasan. Ketiga program tersebut digabungkan dalam program untuk pembentukan hasil ringkasan kalimat yang dirancang dengan menggunakan Visual Basic.Net.

sentence-

2. METODE

1. PENDAHULUAN Dalam meringkas sebuah teks, yang biasa dilakukan manusia adalah dengan membuat kalimat baru yang sesuai dengan tata bahasa dan tidak merubah informasi aslinya. Namun, tanpa disadari, proses utama dari meringkas teks tersebut adalah dengan mencari kata-kata kunci dalam kalimat tersebut. Hal inilah yang menjadi dasar/langkah awal dari meringkas teks, yaitu meringkas kalimat. Perancangan aplikasi peringkas kalimat menggunakan metode noisy channel model. Metode noisy channel model menganggap sebuah kalimat terdiri atas sebuah kalimat inti dan ditambah noise. Jadi metode ini berusaha untuk mendapatkan kalimat inti dengan cara menghapus noise yang ditambahkan tersebut [a]. Perancangan aplikasi peringkas kalimat ini dibatasi hanya pada penggunaan bahasa Inggris yang sesuai dengan tata bahasa dan kaedah ejaan bahasa Inggris. Metode noisy channel model menerapkan rumus-rumus probabilitas sebagai dasar

Gambar 1. Struktur noisy channel model Noisy Channel Model Di dalam noisy channel model, terdapat tiga proses yang harus dilalui seperti pada gambar 1. Ketiga bagian tersebut antara lain [b]: Model sumber (source/encoder). Pada bagian ini ditentukan nilai probabilitas awal P(s) untuk setiap kalimat s, di mana s dianggap sebagai sebuah kalimat pendek. Dalam model ini, P(s) harus bernilai sangat kecil. Model channel. Untuk setiap pasangan kata (s,t), ditentukan nilai probabilitas P(t|s), di mana apabila kalimat pendek s diperluas, maka akan menghasilkan kalimat panjang t. Dalam model ini, nilai P(t|s) harus bernilai sangat kecil. Model decoder. Ketika meneliti kalimat panjang t, kalimat pendek s yang dicari harus

Perancangan Aplikasi Peringkas… (H. Thendean, H. Mochtar)

201

memaksimalkan P(s|t). Dalam model ini, nilai P(s|t) harus paling besar. Model Probabilitas Di dalam penelitian ini, probabilitas yang dihitung adalah probabilitas P(s) dan P(t|s). Untuk memudahkan perhitungan probabilitas tersebut, maka kalimat masukan harus diubah menjadi bentuk tree daripada menghitung dalam bentuk kalimat. Pertama adalah dengan mengubah bentuk kalimat menjadi bentuk tree (menggunakan Collins Parser [1]), kemudian baru dihitung probabilitas untuk masing-masing tree tersebut. Probabilitas P(s) adalah kombinasi dari perhitungan standar probabilistic context free grammar (PCFG), yang mana dihitung berdasarkan aturan produksi yang menyusun tree s, dan standar perhitungan bigram, yang dihitung berdasarkan leaves yang menyusun tree s. Sebagai contoh, dari Collins Parser didapati tree s sebagai berikut: s = S (NP I) (VP (VB eat) (NP cake))) Maka perhitungan probabilitas menjadi: P(s) = P(TOP->S | TOP) . P(S->NP VP | S) . P(NP->I | NP) . P(VP->VB NP | VP) . P(VB->eat | VB) . P(NP->cake | NP) . P(I | <s>) . P(eat | I) . P(cake | eat) . P( | cake) Sedangkan untuk menghitung P(t|s), adalah dengan membandingkan kedua tree t dan s, kemudian hitung probabilitas tree t terhadap s. Misalkan tree t adalah sebagai berikut: t = S (NP I) (VP (VB eat) (NP cake)) (PP (IN with) (NP spoon))) Maka perhitungan probabilitas P(t|s) menjadi: P(t|s) = P(S->NP VP PP | S->NP VP) . P(PP->IN NP | PP) . P(IN->with | IN) . P(NP->spoon | NP) Untuk memperoleh nilai probabilitas tersebut diperlukan sebuah basis data yang diperoleh dari data latih. Bigram Bigram adalah menghitung probabilitas kata berdasarkan kemunculan satu kata

202

sebelumnya, atau dengan kata lain, bigram adalah probabilitas sebuah kata dengan kondisi kemunculan kata sebelumnya. Perhitungan probabilitas bigram memiliki sebuah kelemahan, yaitu adanya kemungkinan sebuah bigram bernilai 0 (nol) apabila tidak pernah ditemukan dalam data latih (corpus). Untuk mengatasi hal tersebut, digunakanlah pendekatan yang disebut smoothing. Dalam perancangan aplikasi ini pendekatan smoothing yang digunakan adalah algoritma Witten-Bell dengan konsep “Things Seen Once: Use the count of things you've seen once to help estimate the count of things you've never seen” [2]. Persamaan probabilitas [3] yang digunakan dalam WittenBell algorithm adalah: PWB ( wi wi 1 )

PMLE ( wi wi 1 )

N1 ( wi 1 ) Pbackoff ( wi ) Ch ( wi 1 )

(1)

PWB (wi wi 1 ) adalah probabilitas kemunculan sebuah

kata apabila diikuti oleh kata lain yang pernah muncul sebelum kata tersebut. Nilai (lambda) dapat ditentukan bebas agar jumlah distribusi probabilitas yang terjadi mendekati 1. Nilai Ch merupakan count history (perhitungan kemunculan) dari kata tersebut. Data Latih Untuk dapat menghitung probabilitas tersebut, diperlukan sebuah data latih. Data latih yang digunakan adalah Ziff Davis corpus, yaitu kumpulan kalimat yang berjumlah 1067 kalimat dari artikel surat kabar mengenai produk komputer. Ziff Davis corpus ini tidak hanya berisi artikel, melainkan juga berisi ringkasan dari kalimat artikel tersebut yang dibuat manusia. Alasan mengapa menggunakan Ziff Davis corpus ini karena ringkasan yang dibuat manusia tersebut bersifat gramatikal, dan masih mengandung arti dari artikel aslinya. Dengan ini diharapkan sistem yang dibuat bisa mempelajari bagaimana membuat ringkasan yang bersifat gramatikal dan mengandung arti dengan kalimat asli. Contoh isi data latih Ziff Davis corpus adalah: All design goals were achieved. All of our design goals were achieved and the delivered performance matches the speed of the underlying device. Data tersebut menggambarkan contoh kalimat yang mengandung isi yang berhubungan dengan produk komputer. Kalimat-kalimat tersebut dianggap memiliki kebenaran dari sisi ringkasan yang dibuat oleh manusia sehingga nantinya

Jurnal Ilmiah Ilmu Komputer, Vol. 7 No. 2 Maret 2011: 201-206

probabilitas masing-masing kata dapat dihitung berdasarkan contoh data kalimat tersebut dengan menggunakan persamaan 1. Decoding Terdapat banyak kombinasi kalimat ringkasan yang dapat dihasilkan dari kalimat masukan. Untuk dapat menghasilkan kombinasi tersebut, maka dilakukanlah decoding terhadap aturan produksi dari tree t. Proses decoding tersebut antara lain untuk setiap aturan produksi yang memiliki lebih dari satu node di sisi kanan aturan: Bentuk aturan produksi baru sebanyak 2n-2 dari kombinasi aturan di sisi kanan. Tambahkan aturan produksi tersebut ke dalam kumpulan aturan produksi kalimat masukan awal.

they must be shielded (73.09556562) they must be shielded (88.24409127) also must be shielded . (75.26537568) also must be shielded (90.41390131) they also must be shielded . (81.06131186) they also must be shielded (96.20983777) Output: they must be shielded.

Sebagai contoh, misalkan terdapat sebuah aturan produksi S->NP VP PP, maka proses decoding yang dihasilkan adalah membentuk aturan produksi baru dari kombinasi node di sisi kanan. Aturan produksi baru yang terbentuk adalah sebagai berikut: S->NP VP S->NP PP S->VP PP

S->NP S->VP S->PP

Dari hasil decoding di atas, apabila ada aturan yang belum ditemukan di dalam corpus, maka aturan tersebut tersebut dihapus. Proses yang dilakukan di dalam model rancangan dapat dijabarkan pada gambar 2. Contoh proses meringkas adalah sebagai berikut: Kalimat masukan awal: they also must be shielded. Parse string: (TOP (S (NP (PRP they)) (ADVP (RB also)) (VP (MD must) (VP (VB be) (VP (VBN shielded) (. .)))))) Expansion-template dengan (probabilitas lebih kecil lebih baik): they (81.16572826) must be (84.78729523) they also (89.02531436) they must be (83.83508192) also must be (86.00489149) must be shielded (74.04777915) must be shielded (89.19630466) they also must be (91.80082846)

probabilitas

Gambar 2. Rancangan Di dalam menentukan keluaran, terdapat dua cara yang digunakan. Cara tersebut antara lain: Berdasarkan persentase panjang kalimat ringkasan (level of summary). Dalam hal ini, diperlukan interaksi dengan pengguna untuk menentukan persentase kalimat ringkasan yang diinginkan. Kalimat keluaran, adalah kalimat dengan persentase yang mendekati keinginan pengguna dan dengan nilai probabilitas terbesar. Berdasarkan pembagian probabilitas dengan panjang kalimat ringkasan. Dengan cara ini, aplikasi akan menentukan kalimat ringkasan tanpa campur tangan dari pengguna. Cara yang dilakukan adalah menentukan peringkat kalimat ringkasan dengan membagi probabilitas kalimat ringkasan dengan panjang kalimat ringkasan. Kalimat keluaran

Perancangan Aplikasi Peringkas… (H. Thendean, H. Mochtar)

203

adalah kalimat ringkasan dengan peringkat terbesar.

aslinya. Contoh hasil pengujian adaptive sebagai berikut:

Cara penentuan keluaran otomatis bergantung dari kebutuhan pengguna. Apabila pengguna ingin terlibat langsung dengan aplikasi maka cara pertama yang dipilih. Pengujian dalam penelitian ini akan difokuskan pada cara yang kedua

Original Sentence

Before adaptive

3. DISKUSI Berdasarkan pengujian proses peringkasan kalimat, didapati bahwa parser yang digunakan terkadang menghasilkan parse tree yang menyalahi kaidah tata bahasa Inggris yang berlaku. Contoh kesalahan parser yang terjadi dapat dilihat pada gambar 3 (pada bagian yang ditulis lebih besar). Menurut tata bahasa Inggris, NP (noun phrase) harus diikuti paling tidak sebuah kata benda, sedangkan dari parse tree yang dihasilkan, NP tidak diikuti oleh kata benda, melainkan hanya sebuah kata kerja saja. Pengujian juga dilakukan terhadap fitur adaptive yang ditambahkan. Dari hasil pengujian diperoleh hasil bahwa sebelum melakukan pembelajaran, kalimat ringkasan yang dihasilkan kurang begitu baik, sedangkan setelah dilakukan pembelajaran, kalimat ringkasan yang dihasilkan lebih baik berdasarkan struktur gramatikalnya dan tata bahasanya. Apabila sebelumnya, kalimat ringkasan yang dihasilkan kurang begitu mempunyai arti, namun setelah dilakukan proses adaptive ini, kalimat yang dihasilkan jadi lebih mempunyai arti, dan lebih sesuai dengan kalimat

After adaptive

: accepted entries would be placed on the official contest website for consideration and public voting. : accepted entries would be placed on the for consideration and public voting. : accepted entries would be placed on website for consideration and public voting.

Untuk menilai keluaran yang dihasilkan, maka diadakan survey. Survey dilakukan dengan cara memberikan kuesioner kepada orang-orang yang ahli dan sering menggunakan bahasa Inggris. Di dalam kuesioner, kalimat yang diuji berisi 8 kalimat, dengan pembagian 4 kalimat yang belum pernah dilatih, dan 4 kalimat yang sudah pernah dilatih. Dari setiap kalimat tersebut diberikan 10 pilihan kalimat ringkasan berdasarkan cara penentuan kalimat ringkasan dan persentase kalimat ringkasan. Dari 10 kalimat ringkasan tersebut, responden memberi tanda pada kalimat ringkasan yang tidak sesuai dengan kalimat asli, dan paling sesuai dengan kalimat asli. Contoh bentuk kuesioner pengujian data dapat dilihat pada tabel 1.

TOP

S

NP

VP

DT

NN

NN

NN

VBZ

the

transfer

program

interface

falls

ADJP

ADVP

RB

short

PP

IN

NP

of

VBG

S

JJ

,

intuitive

,

VP

VBG

leading

PP

TO

to

being

Gambar 3. Kesalahan parsing

204

Jurnal Ilmiah Ilmu Komputer, Vol. 7 No. 2 Maret 2011: 201-206

NP

JJ

NN

.

possible

confusion

.

Gambar 4. Hasil pengujian dengan data latih

ringkasan terbaik berdasarkan perhitungan tertentu. Nilai level of summary antara 10 sampai 90 menunjukkan persentase panjang kalimat ringkasan yang dihasilkan. Tiga grafik menunjukkan tiga penilaian yang diberikan oleh responden. Sign X berarti kalimat ringkasan tidak sesuai dengan kalimat asli. No-sign berarti kalimat ringkasan masih sesuai dengan kalimat asli. Sign O berarti kalimat ringkasan paling sesuai dengan kalimat asli.

Tabel 1. Contoh pengujian data (original sentence: in my opinion , goals should stretch your maximum capabilities) Level of Summary NA 90 80 70 60 50

Summary Sentences in my opinion , goals should stretch your capabilities in my opinion , goals should stretch your capabilities in my opinion , goals should stretch capabilities in my opinion , goals should stretch your goals should stretch your maximum capabilities should stretch your maximum capabilities

40

should stretch capabilities

30

should stretch your

20

should stretch

10

Goals

Berdasarkan pengujian seperti pada gambar 4, 5 dan 6, diperoleh hasil: Pada kalimat yang belum dilatih, kalimat ringkasan yang masih dapat diterima adalah pada kalimat dengan tingkat 90% (panjang kalimat ringkasan sama dengan 90% dari panjang kalimat utama). Pada kalimat yang sudah dilatih, kalimat ringkasan yg dapat diterima adalah ada tingkat 60%. Secara keseluruhan, persentase kalimat ringkasan yang masih dapat diterima adalah pada tingkat 80%. Keterangan pada gambar hasil pengujian (gambar 4, 5 dan 6): Pada level of summary, NA berarti aplikasi tidak menggunakan level of summary, melainkan menentukan sendiri kalimat

Gambar 5. Hasil pengujian dengan data baru

Gambar 6. Hasil pengujian dengan data baru dan latih

4. HASIL Berdasarkan pengujian diperoleh hasil bahwa aplikasi dapat menghasilkan kalimat ringkasan yang cukup baik sampai batas level of summary sama dengan 80%. Aplikasi peringkas kalimat ini dapat beradaptasi terhadap penggunanya walaupun belum mampu menghasilkan ringkasan untuk kalimat asli yang memiliki panjang kata lebih dari 20 kata (kompleks). Dikarenakan jumlah basis data yang dimiliki masih tergolong sedikit dan hanya pada bidang tertentu saja (artikel komputer), maka aplikasi peringkas kalimat ini harus sering digunakan dan

Perancangan Aplikasi Peringkas… (H. Thendean, H. Mochtar)

205

dilatih untuk dapat menghasilkan kalimat ringkasan yang lebih baik. Masih terdapatnya kesalahan yang dilakukan oleh parser dalam membentuk parse string dari kalimat yang dimasukkan sehingga berakibat adanya aturan produksi yang tidak sesuai dengan tata bahasa Inggris yang semestinya.

Recognition, Prentice Hall, Englewood Cliffs, 2000. [3] H. Ney and U. Essen, “On Smoothing Techniques for Bigram-Based Natural Language Modeling”, International Conference in Acoustics, Speech and Signal Processing (ICASSP), 1991.

5. DAFTAR PUSTAKA

Websites: [a] K. Knight and D. Marcu, (2009), StatisticsBased Summarization - Step One: Sentence Compression, http://www.isi.edu/naturallanguage/mt/statsum.ps. [b] H. Daume III and D. Marcu, (2009), A Noisy-Channel Model for Document Compression, http://www.isi.edu/~marcu/ papers/doccompression-acl2002.pdf.

[1] M. K. Collins, Head-Driven Statistical Models for Natural Language Processing, Faculty of Computer and Information Science University of Pennsylvania (dissertation), Philadelphia, 1999. [2] D. Jurafsky and J. H. Martin, Speech and Language Processing: An Introduction to Natural Language Processing, Computational Linguistic and Speech

206

Jurnal Ilmiah Ilmu Komputer, Vol. 7 No. 2 Maret 2011: 201-206