PEMBENTUKAN POLA GENERIK KALIMAT TANYA PADA SISTEM TANYA JAWAB MELALUI PEMBELAJARAN ANALOGI Hapnes Toba Fakultas Teknologi Informasi Universitas Kristen Maranatha hapnes.toba@ eng.maranatha.edu ABSTRAK Sistem tanya jawab sebagai sebuah penerapan penelusuran informasi sangat memerlukan identifikasi tipe pertanyaan untuk dapat memperkirakan bentuk jawaban akhir dari sebuah pertanyaan. Penelitian-penelitian terkini dalam identifikasi pertanyaan lebih banyak mengandalkan pendekatan berbasis aturan yang disusun secara manual. Dalam makalah ini akan dipaparkan sebuah usulan pendekatan yang memanfaatkan pembelajaran analogi dengan Bayesian Analogical Reasoning, untuk membentuk pola-pola kalimat tanya. Eksperimen yang dilakukan dalam penelitian ini menggunakan himpunan pertanyaan dan jawaban (berupa paragraf), dari forum evaluasi sistem tanya jawab untuk bahasa Inggris, yaitu: ResPubliQA tahun 2009 dan 2010. Sebagai metode evaluasi, pola kalimat tanya yang berhasil diidentifikasi, selanjutnya akan dibandingkan dengan pola manual yang digunakan dalam sistem tanya jawab Open Ephyra. Hasil perbandingan menunjukkan bahwa pembentukan pola kalimat tanya dengan pembelajaran analogi memiliki bentuk yang sepadan dengan pola manual yang tertanam dalam sistem Open Ephyra. Keywords: sistem tanya jawab, pembelajaran analogi, ResPubliQA, Open Ephyra
1. PENDAHULUAN Sistem tanya jawab (STJ) adalah sebuah bentuk khusus dari sistem penelusuran informasi. Perbedaan utamanya terletak pada hasil akhir yang diharapkan, bahwa melalui STJ pengguna akan mendapatkan satu jawaban tunggal yang dianggap paling tepat. Sebagai contoh, jika ada pertanyaan: “In which country is Cornell University located?”, maka sistem harus dapat memberikan jawaban akhir: New York State, United States of America. Demikian pula jika ada pertanyaan lain yang sepadan dengan itu: “In which country will the 2010 FIFA World Cup be held?”, sistem harus dapat memberikan jawaban: South Africa. Kedua pertanyaan dalam contoh di atas mengacu pada hal yang sama yaitu mengenai sebuah lokasi, baik berupa negara atau kota. Persamaan lainnya adalah bahwa lokasi tersebut harus ditentukan melalui sebuah cuplikan teks yang menyediakan jawaban akhir, misalnya dalam sebuah paragraf tekstual [1]. Dengan demikian, permasalahan yang harus diatasi oleh sebuah STJ untuk dapat mengambil jawaban yang tepat adalah: bagaimana mengidentifikasi pertanyaan sejenis dan bagaimana mengetahui bentuk jawaban akhir yang diharapkan. Sebagaimana diuraikan dalam [2, 6, 7], sebuah arsitektur STJ biasanya tersusun atas beberapa komponen utama, yaitu: penganalisis pertanyaan, pembentuk kueri, penelusuran informasi, dan penyaring jawaban. Komponen analisis pertanyaan dan penyaring jawaban, pada umumnya sangat bergantung pada perangkat
pemrosesan bahasa alami, seperti: pengenalan entitas-nama [3], pengurai kalimat [4], ataupun label semantik [2]. Kedua komponen tersebut saling terkait erat karena pengenalan tipe pertanyaan akan sangat menentukan bentuk jawaban akhir yang diharapkan. Misalnya jika diketahui sebuah pertanyaan memiliki tipe 'LOKASI', maka bentuk jawaban akhir harus mengandung unsur kota, negara atau tempat lainnya. Komponen pembentuk kueri dan penelusuran informasi bergantung pada model pelacakan informasi, misalnya dengan model bahasa (Indri [5]), ataupun berbasis vektor (Lucene1). Hasil pelacakan informasi – biasanya berupa dokumen atau paragraf – akan dipakai untuk menyaring jawaban akhir, yang dibatasi oleh bentuk yang diidentifikasi pada saat analisis pertanyaan. Khusus di dalam komponen analisis pertanyaan, ada dua teknik yang umum digunakan. Teknik yang pertama adalah dengan memanfaatkan algoritma pembelajaran mesin, seperti: SVM, Maximum Entropy ataupun AdaBoost [6]. Teknik yang kedua adalah dengan membangun aturan-aturan secara manual berupa pola-pola kalimat untuk dikenali pada saat ada sebuah pertanyaan baru [7]. Akurasi klasifikasi tipe pertanyaan dengan pembelajaran mesin sangat bergantung pada fitur pembelajaran, dan banyak ditentukan oleh perangkat pemroses bahasa alami. Teknik berbasis aturan memiliki akurasi yang lebih baik, walaupun demikian terdapat keterbatasan dalam menentukan seberapa banyak pola yang harus dibuat, karena tidak mungkin semua pola dapat ditentukan sebelumnya. 1 http://lucene.apache.org/
Gambar 1. Mekanisme eksperimen pemanfaatan BAR dalam pembentukan pola kalimat tanya Di dalam penelitian ini, akan dilakukan sebuah pendekatan yang mencoba untuk membentuk pola kalimat tanya secara otomatis. Pendekatan dilakukan dengan memanfaatkan pembelajaran secara analogi dari pasangan pertanyaan-jawaban. Dengan demikian dapat mengurangi peran perangkat pemrosesan bahasa alami, dan di sisi lain tetap mempertahankan akurasi pola kalimat. Tujuan dari penelitian adalah untuk menguji pemanfaatan model analogi sebagai pengganti metode pembentukan pola secara manual. Harapan lain dengan pemakaian metode ini adalah bahwa pola yang terbentuk akan dapat lebih spesifik terhadap domain pertanyaan. Domain pertanyaan yang digunakan dalam penelitian ini adalah koleksi dokumen mengenai peraturan parlementer Uni Eropa dari forum evaluasi ResPubliQA2 2009 dan 2010. Penelitian [8], telah memodifikasi bagian pola kalimat pada komponen analisis pertanyaan dalam STJ Open Ephyra [7], dan akan dijadikan sebagai pembanding terhadap hasil dari penelitian ini. 2. MODEL DAN ALGORITMA 2.1 Bayesian Analogical Reasoning Pembelajaran analogi dilakukan dengan pendekatan Bayesian (Bayesian Analogical Reasoning = BAR), sebagaimana dijelaskan dalam [9]. Ide dasar dari pembelajaran analogi adalah untuk mencari nilai fungsi yang tersembunyi di antara dua pasang obyek yang berelasi. Dalam penelitian ini, pasangan obyek yang direlasikan adalah pertanyaan-jawaban. Sebagai contoh pasangan pertanyaan-jawaban pada bagian 'Pendahuluan' di atas, dapat dianggap sebagai dua pasang pertanyaan-jawaban yang saling berelasi, Q1:A1 :: Q2:A2. Algoritma BAR bertugas untuk memperkirakan parameter model (priors), untuk setiap fitur yang mengidentifikasikan relasi, dan menghitung nilai fungsi sesuai fitur tersebut. Dengan demikian, jika terdapat sebuah pertanyaan-jawaban baru, akan 2 http://celct.isti.cnr.it/ResPubliQA/
dapat dicari pasangan yang memiliki relasi paling kuat terhadapnya, di dalam kumpulan pasangan perta-nyaan-jawaban yang telah dipelajari. Ringkasan penjelasan mengenai BAR dapat dilihat pada Lampiran 1. Asumsi yang diambil untuk algoritma BAR dalam penelitian ini adalah: jika sebuah pertanyaan memiliki kemunculan kata-kata dan fitur pendukung yang sama dengan analoginya, maka keduanya akan memiliki maksud yang sama dalam menentukan jawaban akhir. Dengan demikian urutan kemunculan kata yang sama tersebut akan dapat dipakai sebagai pembentuk pola dalam kalimat tanya. 2.2 Fitur Pembelajaran dan Data Sebagaimana halnya algoritma pembelajaran mesin pada umumnya, diperlukan adanya fitur pembelajaran untuk mewakili obyek yang akan dipelajari. Untuk penelitian ini, digunakan fitur yang dibagi ke dalam dua kelompok, yaitu fitur untuk pertanyaan, berupa 'kata tanya', dan fitur untuk jawaban berupa 'nama-entitas' (lokasi, waktu, nama orang, organisasi, dsb). Kata tanya terdiri atas kata-kata yang biasanya mengawali sebuah pertanyaan dalam bahasa Inggris, seperti: what, who, when, where, which, how, is, are, do, does dan sejenisnya. Untuk pengenalan namaentitas, digunakan tiga macam pendekatan, yaitu: menggunakan model dari Stanford NER3 dan OpenNLP4, menggunakan ekspresi regular untuk mengenali angka-angka, dan berbasis kamus seperti dalam [6]. Pembelajaran dilakukan dengan mempelajari 500 pasang pertanyaan-jawaban ResPubliQA 2009, yang terbagi atas: 95 pertanyaan dalam tipe 'DEFINITION', 139 'FACTOID', 187 'REASONPURPOSE', dan 79 'PROCEDURE'. Untuk pengujian, digunakan 133 pertanyaan-jawaban, yang diambil dari ResPubliQA 2010, terdiri atas: 32 'DEFINITION', 35 'FACTOID', 33 'REASONPURPOSE', dan 33 'PROCEDURE'. Yang hendak diuji adalah: apakah untuk kumpulan pasangan 3 http://nlp.stanford.edu/javanlp/ 4 http://opennlp.sourceforge.net/projects.html
pertanyaan-jawaban dari tahun 2010, dapat menghasilkan pola yang sepadan dalam setiap tipe pertanyaan, sebagaimana yang terdapat dalam pola manual Open Ephyra yang telah dimodifikasi dalam [8]. Ringkasan mekanisme eksperimen dapat dilihat pada Gambar 1. 2.3 Pembentukan Pola Pembentukan pola dilakukan dengan mencari keterurutan kata (n-gram, dengan nilai n minimal = 3), yang muncul dalam himpunan pasangan analogi partanyaan-jawaban. Jika terdapat sejumlah keterurutan kata, maka dari urutan kata-kata tersebut akan dirangkai sebagai kalimat tanya.
Algoritma pembentukan pola dapat dilihat pada Gambar 2. Alasan dipilihnya nilai minimal n = 3, adalah untuk mengantisipasi obyek target dan konteks yang muncul dalam sebuah kalimat tanya. Sebagai contoh, misalnya pertanyaan: “In which country is Cornell University located?”, dapat diubah sebagai pola “In which
is located”. Pola yang terbentuk memberikan placeholders (semacam penampung kata) bagi fokus pertanyaan, yang akan dijadikan sebagai kueri pada saat penelusuran informasi dilakukan, yaitu “country Cornell University located”.
Gambar 2. Algoritma pembentukan pola dengan melihat pada keterurutan kemunculan kata dalam pertanyaan 3. HASIL DAN DISKUSI Sebuah contoh terbentuknya pasangan analogi pertanyaan-jawaban dapat dilihat pada Gambar 3. Bila dilihat pada Gambar 3, seolah-olah antara pertanyaan dengan analoginya tidak terdapat kaitan. Namun jika melihat pada isi dari pasangan secara keseluruhan akan tampak bahwa algoritma BAR telah berhasil menemukan keterkaitan antara pertanyaan dengan analoginya, yaitu untuk sebuah pertanyaan yang mengandung nama-entitas 'organisasi', akan memerlukan jawaban yang mengandung unsur 'lokasi' (tipe pertanyaan 'FACTOID'), meskipun tidak dengan kata tanya yang sama. Dari contoh pada Gambar 3, terlihat pula bahwa sebenarnya dengan menggunakan algoritma BAR, terdapat kemungkinan untuk membentuk aturan pada saat penyaringan jawaban dilakukan, namun
hal tersebut berada di luar lingkup dari penelitian ini, yang hanya melihat pada pola kalimat tanya. Salah satu contoh pasangan pertanyaan-jawaban dari hasil eksperimen yang memiliki maksud yang sama dengan analoginya, dengan melihat pada urutan kemunculan kata dalam pertanyaan, adalah: “What does MFF signify in a financial context?”, dengan “What does EIB denote in correlation with investments?”. Kedua pertanyaan ini memiliki maksud untuk mendapatkan definisi dari sebuah istilah. Contoh pola-pola yang terbentuk dan padanannya dalam koleksi pola manual Open Ephyra, dapat dilihat dalam Tabel 1 s.d 4. Terlihat dalam tabeltabel tersebut bahwa pola yang terbentuk lebih generik dibandingkan dengan pola manual, namun tetap dapat menampung maksud dari pertanyaan sehingga dapat diidentifikasikan ke dalam sebuah
tipe pertanyaan pada saat analisis pertanyaan dilakukan. Adapula terlihat beberapa pola yang sebelumnya tidak terbentuk namun berhasil didapatkan setelah dilakukan pembelajaran analogi, misalnya pola 'who' atau pertanyaan yang didahului oleh preposisi, seperti 'in', atau 'on' untuk kelompok tipe pertanyaan 'FACTOID', dalam Tabel 2. Bagian yang sukar untuk diidentifikasi dalam pembentukan pola adalah bagian konteks sebuah pertanyaan yang biasanya sangat bervariasi, dan sangat bergantung pada domain pertanyaan, meskipun berada dalam sebuah tipe yang sama. Yang dimaksud dengan konteks adalah kata-kata yang memberikan informasi spesifik terhadap jawaban yang akan dicari. Misalnya untuk pertanyaan: “In which country is Cornell University located?”, yang menjadi konteks disini adalah Cornell University, sedangkan country menunjukkan target entitas yang harus divalidasi saat penyaringan jawaban dilakukan. Karena konteks sangat bervariasi, maka algoritma pembentukan pola yang mengandalkan keterurutan kata tidak dapat dipakai sepenuhnya untuk mendeteksi. Pada sisi lain fitur 'kata tanya' dan kata-kata yang mengikutinya secara langsung, dapat dideteksi oleh algoritma pembentukan pola untuk membentuk target pertanyaan. Hal lain yang menarik untuk diperhatikan adalah bahwa untuk pertanyaan-pertanyaan yang singkat, dengan kata-kata yang terbatas dalam penyajiannya, dapat memiliki lingkup pola yang lebih lengkap. Sebagai contoh pola yang terbentuk untuk pertanyaan-pertanyaan dalam tipe 'DEFINITION' dan 'FACTOID', dalam Tabel 1 dan 2. Dibandingkan pertanyaan-pertanyaan dalam tipe 'REASON-PURPOSE' dan 'PROCEDURE', pertanyaan bertipe 'DEFINITION' dan 'FACTOID' memiliki pola yang lebih seragam. Keseragaman pola dalam pengajuan pertanyaan, sebenarnya tidak menjamin bahwa pertanyaan
lebih mudah untuk ditelusuri jawabannya. Fakta dalam penyelenggaraan ResPubliQA 2010 [8, 10], menunjukkan bahwa pertanyaan dalam tipe 'DEFINITION', memiliki nilai akurasi (jawaban benar), yang paling rendah. Salah satu penyebabnya adalah bahwa dalam pembentukan kueri, pola hanya berperan untuk menampung bentuk pertanyaan, namun bukan untuk dijadikan sebagai 'kata kunci' pada saat penelusuran informasi. Hal itu dapat dilihat kedua contoh berikut ini: -. Pertanyaan 1 : 'What is maladministration?'. -. Pertanyaan 2 : 'Why was Perwiz Kambakhsh sentenced to death?'. Untuk pertanyaan pertama, kata kunci yang dijadikan kueri hanya 'maladministration', sedangkan untuk pertanyaan kedua, kata-kata kuncinya adalah 'Perwiz, Kambakhsh, sentenced, death'. Sebuah mesin penelusuran informasi akan lebih memiliki peluang untuk menemukan dokumen / paragraf yang relevan bagi pertanyaan kedua. Oleh karena hal inilah, analisis tipe pertanyaan memang penting untuk mengidentifikasi bentuk pertanyaan, namun pada saat penyaringan jawaban dilakukan sangat diperlukan adanya mekanisme untuk validasi maksud pertanyaan (sesuai identifikasi tipenya), seperti misalnya: dengan ontologi [6] untuk memperjelas maksud sebuah kata dalam domain, dengan irisan kemunculan kata [8], ataupun menggunakan teknik logika, seperti: inferensi dan deduksi [11]. Teknik ontologi dan logika banyak berperan untuk validasi tipe pertanyaan 'FACTOID' dan 'DEFINITION', yang memungkinkan adanya validasi terhadap semantik kata. Teknik irisan kemunculan kata, seperti: n-gram, containment, dan resemblance [12], memungkinkan perhitungan terhadap coverage area (ruang lingkup) kueri di dalam sebuah cuplikan teks, sehingga banyak berperan dalam tipe 'REASONPURPOSE' dan 'PROCEDURE' [8].
Gambar 3. Contoh terbentuknya pasangan analogi pertanyaan-jawaban (jawaban dalam ukuran paragraf / text snippets)
Tabel 1. Pola untuk tipe 'DEFINITION'
Tabel 2. Pola untuk tipe 'FACTOID'
Tabel 3. Pola untuk tipe 'REASON-PURPOSE' (generalisasi dengan ekspresi regular)
Tabel 4. Pola untuk tipe 'PROCEDURE'
4. KESIMPULAN Dari penelitian ini dapat disimpulkan beberapa hal sebagai berikut: 1. Algoritma BAR dapat dimanfaatkan untuk menyediakan pasangan analogi untuk sepasang pertanyaan-jawaban. 2. Pasangan analogi yang dihasilkan oleh algoritma BAR ditentukan oleh kedua bagian pertanyaan dan jawaban sebagai kesatuan, dan secara umum tidak dapat dipisahkan hanya dengan melihat pada bagian pertanyaan atau jawaban saja. Dengan demikian, pasangan analogi yang dihasilkan bisa saja tidak menggunakan kata tanya yang sama, namun memiliki berelasi jika melihat pada pertanyaanjawaban sebagai kesatuan. 3. Algoritma pembentukan pola yang melihat pada kemunculan keterurutan kata (n-gram), dapat digunakan untuk membentuk pola generik dalam sebuah kelompok tipe pertanyaan. 4. Kelompok tipe pertanyaan 'DEFINITION' dan 'FACTOID' memiliki pola yang lebih seragam dibanding dengan tipe pertanyaan 'REASONPURPOSE' ataupun 'PROCEDURE'. 5. Pola-pola yang dihasilkan berpadanan dengan pola yang terdapat dalam STJ Open Ephyra.
6. Algoritma pembentukan pola perlu dilengkapi dengan mekanisme untuk dapat menangkap kata yang berisi konteks pertanyaan, yang biasanya sangat variatif, dan tidak selalu beriringan dengan kata tanya. Beberapa usulan yang dapat dilakukan sebagai kelanjutan dari penelitian ini antara lain: 1. Menambahkan mekanisme untuk menangkap konteks pertanyaan, layak untuk dicoba adalah dengan memanfaatkan deteksi 'kata benda', misalnya dengan perangkat part-of-speech (POS) tagger, pada bagian kalimat yang lebih dalam. 2. Menggantikan pola pertanyaan manual dalam STJ Open Ephyra, dengan pola yang terbentuk dari penelitian ini, dan menilai pengaruhnya. 5. DAFTAR PUSTAKA [1]. Lin, J., Quan, D., Sinha, V., Bakshi, K., Huynh, D., Katz, B., Karger, D.R., 2003, “The Role of Context in Question Answering Systems”, Extended Abstracts on Human Factors in Computing Systems, pp. 10061007, Fort Lauderdale, Florida. [2]. Bilotti, M.W., 2009, “Linguistic and Semantic Passage Retrieval Strategies for Question
Answering”, Dissertation Thesis, Language Technologies Institute. School of Computer Science, Carnegie Mellon University. [3]. Pizzato, L.A., Molla D., Paris C., 2006, “Pseudo-Relevance Feedback using Named Entities for Question Answering”, Australasian Language Technology Workshop (ALTW). [4]. Cui, H., Sun, R., Li, K., Kan, M.-Y., Chua, T.-S., 2005, “Question answering passage retrieval using dependency relations”, SIGIR, pp. 400–407, ACM, New York. [5]. Strohman, T., Metzler, D., Turtle, H., Croft, W.B., “Indri: A language-model based search engine for complex queries”, http://ciir.cs. umass.edu. [6]. Schlaefer, N., 2007, “Deploying Semantic Resources for Open Domain Question Answering”, Diploma Thesis, Language Technologies Institute School of Computer Science Carnegie Mellon University. [7]. Schlaefer, N., Gieselmann, P., Schaaf, T., Waibel, A., 2006, “A Pattern Learning
Approach to Question Answering within the Ephyra Framework”, LNAI 4188, pp. 687– 694, Springer-Verlag. [8]. Toba, H., Sari, S., Mirna, A., Manurung, R., 2010, “Contextual Approach for Paragraph Selection in Question Answering Task”, Working Notes of CLEF ResPubliQA. [9]. Silva, R. Heller, K. Ghahramani, Z., Airoldi, E., 2010, “Ranking Relations Using Analogies in Biological and Information Networks”, The Annals of Applied Statistics Vol. 4 (2). [10]. Peñas, A., Forner, P., Rodrigo A., Sutcliffe R., Forascu C., Mota C., 2010, “Overview of ResPubliQA 2010: Question Answering Evaluation over European Legislation”, Working Notes of CLEF ResPubliQA. [11]. Glöckner, I., Pelzer, B., 2010, “The
LogAnswer Project at ResPubliQA 2010”, Working Notes of CLEF ResPubliQA. [12]. Broder, A. Z., 1998, “On the resemblance and
containment of documents”, Compression and Complexity of Sequences, IEEE Computer Society.
LAMPIRAN 1. RINGKASAN ALGORITMA BAYESIAN ANALOGICAL REASONING
