Pembangkitan Template Event Secara Otomatis dari Tuple Relasi Open Information extraction Ade Romadhony, Dwi Widyantoro dan Ayu Purwarianti Sekolah Teknik Elektro dan Informatika Institut Teknologi Bandung Indonesia
[email protected] {dwi,ayu}@stei.itb.ac.id
1
Abstrak
Extraction (ACE) (Doddington et al., 2004), dan Text Analysis Conference/TAC.
Kebebasan dalam batasan jenis relasi pada Open Information extraction (Open IE) menyebabkan konversi menjadi data terstruktur sulit untuk dilakukan. Dalam makalah ini dibahas mekanisme untuk pembangkitan template event dari tuple relasi hasil ekstraksi Open IE sehingga dapat dihasilkan informasi terstruktur. Untuk membangkitkan template event, dilakukan proses deteksi sinonim tuple relasi dan kemudian clustering. Proses clustering akan menghasilkan kelompok tupletuple relasi dengan keterkaitan erat dan diasosiasikan dengan template sebuah event. Berbeda dengan penelitian-penelitian sebelumnya tentang pembangkitan template event secara otomatis dari hasil ekstraksi sistem Open IE, metode clustering yang dibahas pada makalah ini melibatkan informasi keterkaitan semantik yang bersumber dari basis pengetahuan. Sementara penelitian-penelitian sebelumnya hanya mengandalkan informasi keterkaitan co-occurence. Hasil eksperimen menunjukkan bahwa dengan penambahan informasi dari basis pengetahuan, cluster yang terbentuk mempunyai kualitas yang lebih baik dibanding jika hanya menggunakan informasi co-occurrence.
Dalam perkembangannya, penelitian pada ekstraksi informasi mengikuti juga perkembangan informasi yang beredar pada jaringan Internet. Informasi yang beredar pada jaringan Internet sangat banyak dan beragam jenisnya, sehingga tidak dapat dilakukan pembatasan jenis informasi apa saja yang perlu untuk diekstrak. Hal ini melatarbelakangi berkembangnya penggunaan pendekatan semi-supervised dan unsupervised ekstraksi relasi, serta munculnya Open Information extraction (Open IE).
Pendahuluan
Ekstraksi informasi (information extraction) adalah sebuah task untuk menemukan bagian tertentu data dari dokumen yang dituliskan dalam bahasa natural, sehingga dapat diperoleh informasi terstruktur dari teks yang tidak terstruktur (Mooney, 1999). (2007)Bahasan tentang ekstraksi informasi dimulai dari keberadaan sistem untuk ekstraksi isi dokumen berdasar pola tertentu, seperti pada FRUMP (DeJong, 1979). Kemudian mulai popular dengan adanya program Message Understanding Conference (MUC) (Sundheim & Chinchor, 1993), Automatic Content
Pada Open IE, tidak ada batasan jenis relasi yang akan diekstrak, sistem akan memproses semua dokumen/informasi yang beredar pada jaringan Internet, dan berusaha untuk dapat mengekstrak sebanyak mungkin relasi serta entitas penting (Banko, Cafarella, Soderland, Broadhead, & Etzioni, 2007). Hal ini berlawanan dengan batasan pada task information extraction sebelumnya di mana diberlakukan batasan serta definisi yang jelas untuk entitas dan relasi yang harus diekstrak. Sistem Open IE tergolong dalam ekstraksi informasi berbasis penemuan relasi. Munculnya istilah Open IE membuat sistem IE yang tidak menggunakan paradigma yang sama dengan Open IE disebut dengan istilah sistem IE tradisional/konvensional. Istilah Open IE dicetuskan oleh (Banko et al., 2007), dan sistem serupa antara lain adalah NELL (Carlson et al., 2010), Wanderlust (Akbik & Broß, 2009) dan PATTY (Nakashole, Weikum, & Suchanek, 2013). Sistem Open IE yang ada telah dapat menghasilkan relasi berukuran sangat besar, namun tidak adanya struktur/skema membuat tujuan awal ekstraksi informasi dalam menghasilkan data terstruktur belum dapat dicapai. Untuk dapat menstrukturkan informasi tersebut, diperlukan proses identifikasi template secara otomatis. Penelitian awal tentang identifikasi template secara otomatis untuk ekstraksi informasi dilakukan oleh (Chambers & Jurafsky, 2011). Pada penelitian tersebut dilakukan identifikasi pola event dengan aturan heuristik dan kemudian dilakukan proses clustering. Penelitian lain yang melakukan
identifikasi template event secara otomatis dilakukan oleh (Balasubramanian, Soderland, Etzioni, & others, 2012) dengan model Rel-Grams. Model Rel-Grams kemudian dikembangkan untuk menampung informasi co-occurence lintas dokumen (Jiang, Sha, & Sui, 2014). Penelitian-penelitian tentang identifikasi template event secara otomatis yang telah disebutkan semuanya berfokus pada keterkaitan antara pola event/tuple relasi berdasar co-occurence. Metode pengelompokan berdasar co-occurence mempunyai kelemahan berupa kebergantungan pada kondisi serta kualitas data. Selain itu, jika dilihat dari cluster yang terbentuk pada penelitian (Chambers & Jurafsky, 2011) dan (Balasubramanian et al., 2012), anggota cluster terdiri atas pola-pola/tuple-tuple yang sebenarnya merupakan sinonim atau bagian atribut/slot dari relasi yang sama. Hal tersebut menyebabkan cluster yang tidak compact, dan keterkaitan semantik antar anggota cluster hanya bergantung pada data dari dokumen. Keterkaitan semantik antar tuple relasi dapat diperoleh dari basis pengetahuan luar, sebagai contoh WordNet. Dengan memanfaatkan informasi keterkaitan semantik dari basis pengetahuan luar, kualitas cluster dapat diperbaiki. Seperti telah disebutkan sebelumnya, tuple relasi Open IE mempunyai kelemahan berupa recall rendah, mengandung banyak noise dan mengandung informasi yang tidak berarti. Oleh karena ini, pada makalah ini diusulkan proses deteksi sinonim tuple relasi dan proses clustering untuk identifikasi template menggunakan fungsi kesamaan yang ditambahkan dengan informasi keterkaitan semantik.
2
Penelitian Terkait
Sistem Open IE melakukan proses ekstraksi relasi yang menghasilkan tuple relasi. Tuple relasi umumnya dinyatakan dalam bentuk nama_relasi(argumen1,argumen2,..,argumenn). Terdapat beberapa sistem Open IE dengan metode ekstraksi yang berbeda-beda. Pada penelitian ini, digunakan sistem Open IE Exemplar yang telah dimodifikasi untuk menghasilkan tuple relasi sebagai masukan proses pembangkitan template event. Sistem Open IE Exemplar dipilih karena berdasar proses pengujian terhadap beberapa sistem Open IE, Exemplar mempunyai performansi paling baik. Modifikasi dilakukan pada prapemrosesan kalimat masukan dan penambahan aturan identifikasi argumen. Setelah tuple relasi diperoleh, beberapa tuple relasi mempunyai arti semantik yang sama. Tuple-tuple relasi dengan arti semantik yang sama tersebut dapat dikelompokkan dengan identifikasi sinonim. Dengan identifikasi sinonim, tuple relasi yang mempunyai semantik sama dapat dijamin berada pada cluster template event yang sama.
Himpunan sinonim (synonym set/synset) tuple relasi selanjutnya akan dicluster untuk menghasilkan kelompok synset yang merepresentasikan sebuah template event. Pada makalah ini diusulkan clustering synset berdasar keterkaitan semantik, tidak hanya berdasarkan informasi co-occurrence seperti pada penelitian-penelitian sebelumnya.
2.1
Synonym Resolution
Pada awal perkembangan sistem Open IE, tuple relasi dinyatakan dengan frase yang menyatakan relasi serta pasangan argumen yang berupa noun-phrase. Fenomena yang menjadi perhatian kemudian adalah beberapa tuple relasi mempunyai arti semantik yang sama. Sebagai contoh, relasi is_capital_of(D.C, United States) mempunyai arti yang sama dengan is_capital_city_of(Washington, US). Kedua tuple relasi tersebut mempunyai penyebutan frase relasi dan argumen yang berbeda walaupun artinya sama. Fenomena ini melatarbelakangi munculnya kajian tentang synonym resolution untuk relasi, khususnya pada tuple relasi yang dihasilkan oleh sistem Open IE. Penelitian tentang synonym resolution pada tuple relasi sistem Open IE diawali oleh sistem Resolver (Yates & Etzioni, 2009). Pada sistem Resolver digunakan generative probabilistic model untuk mengukur similarity antar frase relasi. Untuk mengukur similarity string, digunakan metode yang berbeda pada argumen dan frase relasi. Metode Monge-Elkan string distance diterapkan pada argumen dan metode Levenshtein distance diterapkan pada relasi. Untuk mengelompokkan relasi yang mempunyai arti yang sama, dilakukan clustering dengan algoritma Greedy Agglomerative Clustering. Pendekatan Greedy diterapkan untuk peningkatan optimasi pemrosesan clustering. Terdapat penelitian lain tentang synonym resolution relasi Open IE yang memasukkan proses identifikasi sinonim ke dalam rangkaian proses ekstraksi relasi, seperti yang dilakukan pada (Yao, Haghighi, Riedel, & McCallum, 2011) dan (Riedel, Yao, McCallum, & Marlin, 2013). Pada penelitian yang dilakukan oleh Yao et al didefinisikan model Rel-LDA yang merupakan modifikasi dari algoritma LDA untuk mengelompokkan tuple relasi yang mempunyai arti semantik sama. Sementara pada penelitian oleh Riedel, diterapkan collaborative filtering pada matriks co-occurrence antara argumen-relasi untuk mendapatkan nilai kesamaan antar frase relasi. Pendekatan yang berbeda dilakukan pada sistem PATTY (Nakashole et al., 2013) di mana didefinisikan pola Syntactic Ontological Lexical (SOL) untuk frase relasi, dan kemudian dilakukan generalisasi tuple relasi. Argumen pada frase relasi mempunyai tipe yang diambil dari basis pengetahuan (Freebase dan YAGO). Proses generalisasi pola frase relasi merupakan proses pengelompokan sinonim relasi. Proses
generalisasi dilakukan berdasarkan informasi statistik, dengan parameter yang digunakan adalah support dan confidence. Metode lain yang digunakan untuk pengelompokan sinonim relasi yang dinyatakan dengan pola SOL adalah Probabilistic Soft Logic/PSL (Grycner, Weikum, Pujara, Foulds, & Getoor, 2014). Berbeda dengan penelitian-penelitian yang sebelumnya disebutkan, penelitian untuk synonym resolution yang dilakukan pada (Dutta, Meilicke, & Stuckenschmidt, 2015) memasukkan faktor kesamaan semantik dari basis pengetahuan luar (WordNet). Fungsi similarity yang digunakan untuk proses clustering menggabungkan informasi statistik dari dokumen yang ada pada penilaian kesamaan argumen, dan informasi keterkaitan semantik dari WordNet untuk bagian frase relasi.
2.2
Ekstraksi Template Event menggunakan Tuple Relasi
Penelitian awal tentang ekstraksi template event secara otomatis dilakukan oleh (Chambers & Jurafsky, 2011). Proses pertama yang dilakukan adalah ekstraksi pola event. Pola event yang akan diproses lebih lanjut adalah sebuah verb, noun dengan synset Event (dari WordNet), atau verb+head-wordnya. Selanjutnya pola event yang terambil dari kumpulan dokumen akan dicluster. Metode clustering yang digunakan adalah LDA dan Agglomerative Clustering berdasar fungsi Pointwise Mutual Information (PMI). Metode clustering Agglomerative menghasilkan cluster dengan kualitas lebih baik dibanding cluster dari metode LDA. (
)
∑
( (
∑
))
pmi(wi, wj) = Pdist(wi, wj) / (P(wi) P(wj)) ( (
(
) )
∑
) (
∑
(2) (3)
) (
∑
(1)
) (
)
(4)
Bagian penting dari agglomerative clustering adalah pendefinisian fungsi distance. Penelitian tersebut mendefinisikan fungsi distance berdasarkan kedekatan posisi co-occurrence pasangan pola event. Semakin dekat jarak kemunculan pasangan pola event (dalam kalimat yang sama), maka nilai similarity akan semakin besar. Pendefinisian tersebut berdasar hipotesis bahwa pola event yang mempunyai keterkaitan erat akan muncul berdekatan. Jika g(wi, wj) menyatakan distance antara pola event i dan j, maka g(wi, wj) akan bernilai 1 jika wi dan wj muncul dalam kalimat yang sama, 2 jika muncul pada kalimat yang bersebelahan, dan seterusnya. Formula distance antara dua pola event dapat dilihat pada formula (1). Clustering secara agglomerative dilakukan berdasar nilai Pointwise Mutual Information (PMI) seperti yang didefinisikan pada formula (2).
(
)
{
(
)
(
)
}
(5)
Penelitian selanjutnya dalam ekstraksi template event secara otomatis dari tuple relasi Open IE menggunakan model Rel-Grams (Balasubramanian et al., 2012). Model Rel-Grams merupakan model yang mengadopsi model N-Grams. Pada model Rel-Grams tersebut, akan dicatat jumlah kemunculan pasangan tuple relasi yang muncul secara bersamaan dalam sebuah dokumen dengan jarak maksimum tertentu. Berdasarkan data Rel-Grams, dibangun Rel-Graphs dengan simpul berupa tuple relasi, dan sisi antar simpul mempunyai bobot berdasar nilai PMI antar pasangan tuple relasi. Fungsi PMI antara pasangan tuple R dan R’ dapat dilihat pada formula (5), di mana k adalah jarak (window) kemunculan pasangan tuple relasi R dan R’. Proses clustering dilakukan pada RelGraphs dengan menggunakan algoritma Markov Clustering.
2.3
Relation Similarity
Kesamaan antara dua buah string/teks sering kali disebut dengan istilah sinonim atau text similarity. Akan tetapi, ternyata similarity antara dua buah string tidak selalu berupa sinonim. Peter D. Turney mendefinisikan dua jenis similarity, yaitu attributional similarity dan relation similarity (Turney, 2006). Attributional similarity adalah korespondensi antar atribut atau umum disebut sebagai sinonim. Sementara relation similarity menyatakan korespondensi antar relasi. Penelitian tentang semantic textual similarity yang dilakukan oleh UMBC juga membagi similarity menjadi dua tipe, yaitu concept similarity dan relation similarity (Han, Kashyap, Finin, Mayfield, & Weese, 2013). Concept similarity menyatakan similarity untuk tipe kata noun atau noun-phrase. Sementara relation similarity dapat mendeteksi similarity kata atau frase dengan POSTag yang berbeda. Sebagai contoh frase marry to mempunyai nilai relation similarity dengan frase is the wife of. Secara singkat dapat disimpulkan bahwa concept similarity menyatakan sinonim, sementara relation similarity menyatakan keterkaitan erat dalam sebuah topik. WordNet merupakan basis pengetahuan kata terbesar yang mempunyai informasi keterkaitan sangat lengkap. Terdapat beberapa metode untuk pengukuran similarity antar teks yang menggunakan informasi dari WordNet. Metode-metode tersebut umum disebut sebagai WordNet similarity. Di antara metode-metode WordNet similarity, metode yang dapat mengukur similarity antar kata dengan POSTag yang berbeda adalah LESK dan HSO. Penelitian ini mengusulkan penggunaan relation similarity dengan mengadopsi metode LESK untuk dimasukkan dalam fungsi distance pada proses clustering.
Gambar I Alur Pemrosesan Ekstraksi Template Event
3
Ekstraksi Template Event
Untuk mengidentifikasi template event secara otomatis dari tuple relasi Open IE, terdapat 4 langkah yang diusulkan, yaitu : filtering tuple relasi, konversi tipe relasi, pengelompokan tuple relasi yang bersinonim, dan clustering tuple relasi. Diagarm alur pemrosesan dapat dilihat pada Gambar I. Sebagai langkah awal, dilakukan analisis terlebih dahulu terhadap tuple relasi yang diperoleh dari pemrosesan dengan sistem Open IE Exemplar. Terdapat 3 tipe tuple relasi yaitu: relai verb, relasi verb+noun, dan relasi copula+noun. Di antara ketiga tipe tersebut, untuk tipe verb dan verb+noun ditemui kondisi-kondisi yang menyebabkan tuple relasi dapat dikonversi menjadi tipe relasi verb. Berikut adalah contoh kondisi yang ditemui : a.
b.
c.
Relasi
kidnap_peasant(PER, POBJOF:attribute). Pada relasi tuple tipe ini, dapat
diketahui bahwa relasi tersebut dapat dipetakan menjadi relasi kidnap(PER, DOBJ:person;POBJ-OF:attribute). Pusat dari relasi adalah bagian verb, dan noun adalah atribut/slot. Relasi place_bomb(ORG, POBJIN:artifact). Pada relasi tuple tipe ini, diketahui bahwa yang menjadi pusat adalah bagian noun (bomb), karena terdapat juga bentuk lain dari kata bomb sebagai kata kerja/verb. Tuple relasi tersebut dapat dikonversi menjadi bomb(ORG, POBJ-IN:artifact). Relasi enter-territory(ORG, POBJOF:MISC). Pada relasi tipe ini, arti/semantik relasi akan menjadi berbeda jika dikonversi ke bentuk relasi verb. Konversi dari bagian noun tidak memungkinkan karena kata territory tidak mempunyai sense sebagai kata kerja/verb.
Berdasarkan pengamatan terhadap relasi tipe verb+noun tersebut, didefinisikan aturan heuristik untuk mengkonversi relasi tipe verb+noun menjadi relasi verb. Proses konversi perlu dilakukan karena terkait dengan pemrosesan selanjutnya, yaitu synonym resolution dan clustering dengan fungsi similarity dari
relation similarity. Kondisi yang ada pada saat ini pengukuran kesamaan teks/text similarity masih banyak berfokus pada level kata tunggal, belum pada level frase. Oleh karena itu, dilakukan konversi ke tipe relasi yang dapat dinyatakan dalam bentuk kata tunggal, bukan frase.
3.1
Filtering Tuple Relasi
Observasi terhadap tuple relasi hasil ekstraksi Open IE menghasilkan kesimpulan bahwa terdapat beberapa informasi yang tidak tepat. Ketidaktepatan tersebut antara lain terjadi pada ekstraksi kalimat pasif yang seharusnya dapat dideteksi dengan benar pada relasi tipe A dan ketidaksesuaian tipe argumen relasi. Pada kasus ekstraksi kalimat pasif, ditemui bahwa tuple relasi terdeteksi sebagai tipe C (copula+noun), dengan identifikasi subject dan direct object yang tidak tepat. Oleh karena itu dilakukan proses filtering untuk memeriksa apakah pada tuple relasi tipe C tedapat bentuk to-be+verb dalam tenses lampau. Jika ditemukan, maka dilakukan proses normalisasi untuk mengubah tuple relasi tersebut ke dalam bentuk aktif, dan menyesuaikan argumennya. Sebagai contoh kalimat masukan “According to reports , Oqueli and his companion Gilda Flores , a member of the Social Democratic Party of Guatemala , were abducted by heavily armed men between 0630 and 0700 as they were heading to La Aurora airport to board their flight”, akan diidentifikasi sebagai relasi tipe C dengan tuple relasi be_abducted(SUBJ:Gilda Flores[PER], POBJ-BY:men[person]). Setelah dilakukan proses
filtering, maka tuple relasi tersebut akan diubah menjadi relasi tipe A abducted(SUBJ:men[person], DOBJ:Gilda Flores[PER]). Sementara dalam hal ketidaksesuaian tipe, hal ini dilakukan untuk mencegah tuple relasi mempunyai informasi argumen yang tidak sesuai. Beberapa relasi mempunyai batasan bahwa tipe argumen pada subject-nya terbatas hanya pada makhluk hidup atau manusia. Pada bentuk awalnya, sistem Open IE Exemplar hanya mengidentifikasi relasi dengan argumen berupa Named Entity yang bertipe PERSON, ORGANIZATION, LOCATION, dan MISCELLA-
NOUS. Namun berdasarkan observasi dan analisis, jika batasan tersebut digunakan, banyak informasi penting yang tidak terambil. Oleh karena itu pada eksperimen dilakukan perluasan kriteria argumen berupa Noun Phrase dengan tipe argumen diidentifikasi berdasar kategori dari WordNet. Untuk menjamin bahwa sebuah relasi mempunyai tipe argumen yang tepat, dilakukan pengecekan berdasarkan verb frame sebuah relasi (untuk tipe A dan B). Jika semua verb frame menyatakan bahwa subject adalah somebody, maka relasi tersebut harus mempunyai subject dengan tipe manusia. Tipe argumen yang termasuk dalam kriteria manusia adalah PERSON dan ORGANIZATION (dari Named Entity Recognizer) serta person dan group (dari WordNet). Langkah terakhir filtering adalah pengecekan kelengkapan argumen. Sistem Open IE Exemplar dapat menghasilkan tuple relasi yang tidak lengkap argumennya, hanya mempunyai subject atau object saja. Proses filtering akan mengeliminasi tuple relasi yang tidak lengkap tersebut. Hanya tuple relasi dengan argumen yang lengkap yang akan dimasukkan ke proses clustering.
3.2
Konversi Tipe Relasi
Berdasarkan analisis terhadap relasi tipe B (verb+noun) didefinisikan aturan heuristik untuk mengkonversi relasi tipe B menjadi relasi tipe A (verb). Aturan heuristik digunakan untuk memutuskan apakah bagian verb atau noun yang akan diambil sebagai inti dari frase relasi tersebut. Aturan yang pertama adalah pengecekan bagian noun apakah mempunyai sense sebagai verb dalam WordNet. Jika kondisi tersebut dipenuhi dan terdapat relasi dengan tipe A dengan teks yang sama, maka bagian noun yang akan dipilih untuk merepresentasikan relasi tersebut. Relasi yang memenuhi kondisi tersebut antara lain place_bomb, launch_bomb, yang akan dikonversi menjadi relasi bomb. Untuk tuple relasi B yang tidak memenuhi kondisi tersebut maka yang diambil sebagai inti relasi adalah bagian verb. Penyesuaian dilakukan pada argumen object dengan cara menambahkan informasi bagian noun sebagai direct object, sekaligus pengecekan tipe argumen. Sebagai contoh pada relasi kidnap_peasant, karena tidak terdapat sense peasant sebagai verb, maka relasi dikonversi menjadi kidnap, dengan direct object adalah peasant dan tipenya adalah person. Pemberian tipe argumen berdasarkan klasifikasi noun pada WordNet.
3.3
Pengelompokan Sinonim
Berbeda dengan penelitian-penelitian sebelumnya (Chambers & Jurafsky, 2011)(Balasubramanian et al., 2012) yang tidak melakukan pengelompokan berdasar sinonim untuk pola atau tuple relasi, pada usulan ini dilakukan pengelompokan. Proses pengelompokan
dilakukan berdasarkan synset(synonym set) trigger relasi dari WordNet. Dua buah tuple relasi dikatakan sebagai sinonim apabila synset dari trigger relasinya sama. Dalam hal ini digunakan asumsi single-sense seperti yang diterapkan pada (Yates & Etzioni, 2009). Beberapa kata dapat mempunyai sense yang berbedabeda, disebut sebagai polisemi. Namun pada eksperimen yang dilakukan, domain dokumen yang digunakan seragam, yaitu tentang event terorisme, sehingga kemungkinan adanya polisemi pada tuple relasi kecil. Oleh karena itu digunakan asumsi single-sense, sehingga hanya dipilih satu sense untuk menentukan synset dari sebuah trigger relasi. Sense sebuah trigger relasi yang dipilih untuk digunakan adalah sense dengan urutan nomor satu pada WordNet. Sense dengan synset urutan nomor satu menunjukkan sense yang paling sering muncul pada dokumen sumber dari WordNet (Most Frequent Synset). Hasil penelitian dari (Grycner & Weikum, 2014) menunjukkan bahwa performansi Most Frequent Synset menduduki peringkat kedua setelah metode yang diusulkan untuk pemetaan sense tuple relasi Open IE ke sense WordNet.
3.4
Clustering
Menggunakan tuple relasi yang telah dikelompokkan ke dalam synset, proses clustering untuk identifikasi template dilakukan. Dalam proses clustering, penentuan kriteria untuk menyatakan kemiripan anggota yang akan membentuk cluster merupakan hal yang penting. Menurut penelitian-penelitian sebelumnya, digunakan informasi co-occurrence (Yates & Etzioni, 2009)(Balasubramanian et al., 2012). Dengan informasi co-occurrence tersebut, dua buah tuple relasi dikatakan mempunyai keterkaitan yang erat jika sering muncul secara bersamaan dalam dokumen. Fungsi distance yang digunakan pada penelitian ini diadopsi dari (Yates & Etzioni, 2009), di mana jarak kemunculan antara dua tuple relasi menentukan nilai kedekatan keduanya. Formula untuk menyatakan distance antara dua tuple relasi dapat dilihat pada formula (2) pada subbab 2.3 . Perbedaannya terletak pada level pengukuran distance yang digunakan. Jika pada penelitian sebelumnya level pengukuran adalah antara pola event (tuple relasi), pada penelitian ini level pengukuran yang digunakan adalah kelompok/cluster sinonim tuple relasi. Kemudian bagian penting pada usulan pendekatan untuk identifikasi template pada penelitian ini adalah penggunaan informasi relation similarity. Dengan adanya penambahan komponen relation similarity, diharapkan pengukuran tidak hanya bergantung pada co-occurrence, namun juga dari informasi semantik. Modifikasi fungsi similarity yang diusulkan dapat dilihat pada formula (6) dan (9).
∑
∑
( ( (
( (
(
Tabel I Golden-Truth Cluster Template
) ))
) )
(
(
(
)
( (
) (
)
)) (6)
(
(7) (8)
)))
)
(
)
(9)
Pada formula (6), komponen relation similarity akan memperkuat pasangan tuple relasi yang mempunyai hubungan co-occurrence. Sementara pada formula (9), nilai relation similarity digabungkan sebagai komponen similarity untuk clustering. Penentuan nilai relation similarity dilakukan dengan mengadopsi pengukuran kesamaan pada WordNet dengan metode Lesk. Pada metode Lesk, digunakan informasi irisan kata yang muncul pada gloss (definisi) dan synset sebuah kata. Semakin banyak kata yang muncul secara beririsan, semakin besar nilai kesamaan antara dua buah kata. ( ( ) ( )
)
( ( (
)
) )
(10)
Penyesuaian dilakukan dalam penelitian ini, yaitu pengukuran kesamaan hanya dilakukan pada gloss dan synset trigger relasi, tidak sampai ke hypernim dan hyponym. Kemudian untuk penilaian, tidak dipertimbangkan panjang irisan/overlap, melainkan hanya digunakan jumlah kata yang beririsan. Oleh karena nilai total irisan maksimal tidak terbatas, dilakukan normalisasi dengan membagi nilai total dengan maksimum panjang gloss dari dua trigger relasi. Proses clustering dilakukan dengan menggunakan tools Markov Clustering (mcl), yang menerapkan clustering berbasis graf.
4
Eksperimen
Dataset yang digunakan pada eksperimen adalah dataset MUC34 yang berisi transkrip berita event terorisme. Dataset MUC34 terdiri atas data pembelajaran dan data test. Pada data pembelajaran terdapat total 1300 dokumen. Terdapat 6 template event, namun hanya 4 template yang mempunyai frekuensi cukup tinggi, yaitu: bombing, kidnap, attack, dan arson. Seperti telah disebutkan pada bab 3, sesudah proses ekstraksi relasi dengan sistem Exemplar*, dilakukan proses filtering tuple relasi untuk mengeliminasi tuple relasi yang tidak lengkap dan tipe argumen yang tidak sesuai. Kemudian dilakukan konversi relasi tipe B menjadi relasi tipe A. Dari tiga tipe relasi, hanya tipe A dan B yang akan digunakan untuk mengekstrak
Cluster
Trigger Relasi
kidnap
kidnap, abduct, release, kidnapping, ransom, perpetrate, disappear, find
bombing
explode, blow_up, bomb, bombing, locate, cause, damage, explosion, detonate, destroy, outage, injure, fire, blow
attack
kill, shoot, killing, shooting, shot, die, murder, massacre, assassinate, gun, attack, down, downs
arson
burn, search, burning, fire, Open_fire, firing
Tabel II Perbandingan Kualitas Cluster Baseline dan Modifikasi Fungsi Distance Template kidnap bombing attack arson
Max Cmatch Baseline Modified Distance 0.176 0.167 0.105 0.095 0.118 0.133 0.107 0.107
Max Overlap Baseline Modified Distance 3 3 2 2 3 3 3 3
template event, karena trigger event mayoritas berupa kata kerja/verb. Memasuki tahapan selanjutnya yaitu identifikasi sinonim, berdasarkan informasi synset dari WordNet, didapatkan himpunan sinonim tuple relasi sejumlah 1814. Dari seluruh himpunan sinonim tersebut dipilih tuple relasi dengan tipe A serta muncul di setidaknya 5 dokumen. Himpunan synset tuple relasi tersebut kemudian dicluster menggunakan tools Markov Clustering untuk mendapatkan cluster template. Markov Clustering adalah metode clustering berbasis graf, yang terkenal akan performansinya dan kecepatan pemrosesannya. Untuk mengukur kualitas cluster yang dihasilkan, dilakukan pendefinisian cluster target. Cluster target ini digunakan untuk mengukur kesesuaian cluster yang dihasilkan dari proses clustering dengan informasi pada template event yang harus ada. Cluster target ini disebut juga sebagai golden-truth cluster, dapat dilihat pada Tabel I. Cluster target berisi informasi relasi tuple apa saja yang sesuai dimasukkan sebagai anggota sebuah cluster yang diasosiasikan dengan sebuah template. Sebagai contoh cluster target untuk template kidnap akan berisi relasi tuple yang berhubungan dengan topik kidnap. Pendefinisian golden-truth cluster dilakukan dengan mengadopsi isian daftar cluster yang berasosiasi dengan template terorisme pada penelitian (Chambers & Jurafsky, 2011) dan observasi pada tuple relasi yang diperoleh dari dataset.
Tabel III Perbandingan Nilai CMatch Cluster Baseline dan Modifikasi Fungsi Similarity Tem plate
kidnap bom bing attack arson
Base line
Mod. Sim I=2.0
0.17 6 0.10 5 0.11 8 0.10 7
0.045
Max CMatch Mod. Mod. Mo Sim Sim d. I=2.1 I=2.2 Sim I=2. 3 0.045 0.052 0.1
0.25
0.25
0.25
0.047
0.059
0.2
0.625
0.417
0.417
Mo d. Sim I=2. 4 0.08 3 0.26 7 0.26 7 0.5
0.26 7 0.18 8 0.41 7
Mo d. Sim I=2. 5 0.07 1 0.26 7 0.26 7 0.55 6
Tabel IV Perbandingan Jumlah Overlap Cluster Baseline dan Modifikasi Fungsi Similarity Tem plate
kidnap bom bing attack arson
3
4
Max Overlap Mod Mod. Mod . Sim . Sim I=2.2 Sim I=2. I=2. 1 3 5 5 3
2
4
4
4
4
4
4
3
8
8
5
4
4
4
3
5
5
5
5
5
5
Base line
Mod .Sim I=2. 0
Mod . Sim I=2. 4 3
Mod . Sim I=2. 5 3
)
(
)
(
)
(
)
(
)
5
Kesimpulan
Dalam penelitian tahap ini, telah berhasil diidentifikasi template event terorisme secara otomatis menggunakan tuple relasi hasil ekstraksi sistem Open IE. Berdasar pengamatan terhadap nilai CMatch tertinggi antara cluster target dengan cluster hasil clustering pada masing-masing template, dapat dikatakan bahwa cluster dengan nilai CMatch tertinggi sudah mewakili template. Namun masih terdapat anggota cluster yang mempunyai keterkaitan semantik rendah dengan anggota cluster lainnya. Oleh karena itu diperlukan pemrosesan lebih lanjut untuk memisahkan anggota cluster yang mempunyai keterkaitan rendah dengan anggota cluster lainnya.
Referensi
Pengukuran tingkat kesesuaian antara cluster target dan cluster yang terbentuk dari proses clustering dilakukan dengan penghitungan nilai CMatch serta jumlah overlap anggota cluster. (
overlap tidak seiring dengan peningkatan nilai maksimum Cmatch dikarenakan perhitungan nilai Cmatch memperhatikan jumlah total anggota cluster target dan hasil clustering. Sementara pada penerapan modifikasi fungsi similarity, terdapat beberapa cluster dengan jumlah anggota yang berbeda jauh (lebih banyak), sehingga menyebabkan nilai Cmatch kecil. Untuk memodifikasi granularity cluster, dilakukan percobaan pengaturan parameter Inflation, yang dilakukan pada rentang 2.0-2.5. Perbedaan pengaturan nilai Inflation menunjukkan perubahan ukuran cluster, sehingga berpengaruh pada nilai Cmatch.
(11)
Penghitungan nilai CMatch antara cluster target Ct dan cluster yang diperoleh dari hasil clustering Cc dilakukan berdasar formula(11). Perbandingan nilai Cmatch maksimum dan jumlah overlap maksimum antara kondisi baseline (hanya menggunakan deteksi sinonim) dengan penerapan modifikasi fungsi distance pada formula PMI dapat dilihat pada Tabel II. Sementara perbandingan nilai Cmatch maksimum antara baseline dengan modifikasi fungsi similarity dapat dilihat pada Tabel III. Berdasarkan nilai-nilai pada Tabel II, terlihat bahwa tidak terjadi peningkatan terhadap jumlah overlap maupun nilai Cmatch. Observasi terhadap anggota cluster juga tidak menunjukkan tuple relasi yang berkaitan erat seperti bomb dan detonate berhasil dikumpulkan dalam satu cluster. Hasil yang berkebalikan ditunjukkan pada penerapan modifikasi fungsi similarity. Terlihat pada Tabel IV, terjadi peningkatan jumlah overlap yang signifikan, dan tuple relasi dengan keterkaitan semantik termasuk dalam anggota cluster yang sama. Peningkatan jumlah
Akbik, A., & Broß, J. (2009). Wanderlust: Extracting semantic relations from natural language text using dependency grammar patterns. WWW Workshop. Balasubramanian, N., Soderland, S., Etzioni, O., & others. (2012). Rel-grams: a probabilistic model of relations in text. Proceedings of the Joint Workshop on Automatic Knowledge Base Construction and Web-scale Knowledge Extraction (pp. 101–105). Association for Computational Linguistics. Banko, M., Cafarella, M. J., Soderland, S., Broadhead, M., & Etzioni, O. (2007). Open Information extraction for the web. IJCAI (Vol. 7, pp. 2670– 2676). Carlson, A., Betteridge, J., Kisiel, B., Settles, B., Hruschka Jr, E. R., & Mitchell, T. M. (2010). Toward an Architecture for Never-Ending Language Learning. AAAI. Chambers, N., & Jurafsky, D. (2011). Template-based information extraction without the templates. Proceedings of the 49th Annual Meeting of the Association for Computational Linguistics: Human Language Technologies-Volume 1 (pp. 976–986). Association for Computational Linguistics. DeJong, G. (1979). Prediction and Substantiation: A New Approach to Natural Language Processing*. Cognitive Science, 3(3), 251–273. Wiley Online Library. Doddington, G. R., Mitchell, A., Przybocki, M. A., Ramshaw, L. A., Strassel, S., & Weischedel, R. M. (2004). The Automatic Content Extraction
(ACE) Program-Tasks, Data, and Evaluation. LREC. Dutta, A., Meilicke, C., & Stuckenschmidt, H. (2015). Enriching Structured Knowledge with Open Information. Proceedings of the 24th International Conference on World Wide Web (pp. 267–277). International World Wide Web Conferences Steering Committee. Feldman, R., & Sanger, J. (2007). The text mining handbook: advanced approaches in analyzing unstructured data. Cambridge University Press. Grycner, A., & Weikum, G. (2014). HARPY: Hypernyms and Alignment of Relational Paraphrases. 25th International Conference on Computational Linguistics (pp. 2195–2204). ACL. Grycner, A., Weikum, G., Pujara, J., Foulds, J., & Getoor, L. (2014). A Unified Probabilistic Approach for Semantic Clustering of Relational Phrases. 4th Workshop on Automated Knowledge Base Construction. AKBC Board. Han, L., Kashyap, A., Finin, T., Mayfield, J., & Weese, J. (2013). UMBC EBIQUITY-CORE: Semantic textual similarity systems. Atlanta, Georgia, USA, 44. Jiang, T., Sha, L., & Sui, Z. (2014). Event Schema Induction Based on Relational Co-occurrence over Multiple Documents. Natural Language Processing and Chinese Computing (pp. 23–33). Springer. Mooney, R. (1999). Relational learning of pattern-match rules for information extraction. Proceedings of the Sixteenth National Conference on Artificial Intelligence (pp. 328–334). Nakashole, N., Weikum, G., & Suchanek, F. (2013). Discovering Semantic Relations from the Web and Organizing them with PATTY. ACM SIGMOD Record, 42(1), 29–34. ACM. Riedel, S., Yao, L., McCallum, A., & Marlin, B. M. (2013). Relation extraction with matrix factorization and universal schemas. Sundheim, B. M., & Chinchor, N. A. (1993). Survey of the message understanding conferences. Proceedings of the workshop on Human Language Technology (pp. 56–60). Association for Computational Linguistics. Turney, P. D. (2006). Similarity of semantic relations. Computational Linguistics, 32(3), 379–416. MIT Press. Yao, L., Haghighi, A., Riedel, S., & McCallum, A. (2011). Structured relation discovery using generative models. Proceedings of the Conference on Empirical Methods in Natural Language Processing (pp. 1456–1466). Association for Computational Linguistics. Yates, A., & Etzioni, O. (2009). Unsupervised methods for determining object and relation synonyms on the web. Journal of Artificial Intelligence Research, 34(1), 255.
