BAB II STUDI LITERATUR 2.1 Ekstraksi Informasi Teknologi ekstraksi informasi (Information Extraction atau IE) adalah teknologi yang berkaitan dengan cara menjadikan dokumen teks tidak terstruktur dengan domain tertentu ke dalam sebuah struktur informasi yang relevan. Dengan kata lain, tujuan utama dari IE adalah mencari informasi-informasi yang relevan dengan domain dan tidak memperdulikan informasi yang tidak relevan [TEL05]. Secara garis besar, proses ekstraksi informasi terdiri dari dua tahap, yaitu mengidentifikasi data yang relevan, kemudian menyimpannya ke dalam bentuk terstruktur untuk digunakan kemudian [SIE05a]. Sebagai contoh, dilakukan proses ekstraksi informasi terhadap sebuah email mengenai undangan untuk menghadiri kuliah. Seperti yang dapat dilihat pada Gambar II-1, hasil dari proses ekstraksi informasi tersebut adalah informasi mengenai pembicara, tempat, dan waktu diadakannya kuliah tersebut. Riset dan pengembangan dari IE sebagian besar termotivasi karena adanya Message Understanding Conferences (MUC) dan Automatic Content Extraction (ACE).
Gambar II-1 Contoh proses ekstraksi informasi [SIE07]
II-1
II-2 Proses ekstraksi informasi secara manual dapat dilakukan dengan cara membaca teks, mengidentifikasi data yang relevan, kemudian menyimpannya ke dalam basis data untuk digunakan kemudian. Proses tersebut tentunya membutuhkan effort dan waktu yang sangat besar, karena berhubungan dengan informasi tekstual yang jumlahnya sangat banyak. Solusinya adalah dengan mendefinisikan aturan-aturan ekstraksi yang dapat digunakan untuk mengekstrak informasi yang diinginkan dari sebuah dokumen teks, sehingga proses ekstraksi informasi dapat dilakukan secara otomatis. Proses pembuatan aturan-aturan ekstraksi dapat dilakukan secara manual. Akan tetapi, untuk dapat membangun sebuah sistem berbasis aturan yang baik, aturan yang didefinisikan harus lengkap, sehingga membutuhkan effort dan waktu yang sangat besar. Selain itu, aturan biasanya terbatas pada domain tertentu, sehingga jika hendak diaplikasikan pada domain yang baru, proses pendefinisian aturan harus dilakukan kembali. Oleh
karena
itu,
diajukan
penerapan
teknik
pembelajaran
mesin
untuk
mengotomatisasi proses pembuatan aturan-aturan ekstraksi. Tantangannya adalah menciptakan model ekstraksi informasi yang dapat diaplikasikan untuk berbagai domain secara fleksibel. 2.1.1 Pembelajaran Mesin untuk Ekstraksi Informasi Dengan menggunakan teknik pembelajaran mesin, kompleksitas di dalam pembuatan dan pemilihan aturan-aturan ekstraksi yang terbaik diserahkan kepada algoritma pembelajaran. Algoritma pembelajaran akan mempelajari aturan-aturan ekstraksi berdasarkan contoh-contoh dokumen teks yang telah diberi anotasi mengenai entitasentitas yang relevan dan hendak diekstrak. Dengan demikian, peran manusia di dalam proses ekstraksi informasi tidak lagi membuat aturan-aturan ekstraksi, melainkan hanya memberikan label bagi entitas-entitas yang relevan di dalam sebuah dokumen teks. Arsitektur umum dari sistem ekstraksi informasi yang menggunakan pembelajaran mesin dapat dilihat pada Gambar II-2.
II-3
Gambar II-2 Arsitektur umum sistem ekstraksi informasi yang menggunakan pembelajaran mesin [SIE05a]
Komponen-komponen utama yang terdapat di dalam sebuah sistem ekstraksi informasi yang menggunakan pembelajaran mesin yaitu: 1. Pemrosesan awal (preprocessing) teks masukan Dokumen teks masukan biasanya berupa teks tidak terstruktur dan masih dalam bentuk natural language. Untuk itu dibutuhkan pemrosesan teks agar dapat menjadi masukan yang valid bagi algoritma pembelajaran. 2. Pembelajaran dan aplikasi model ekstraksi Algoritma pembelajaran mesin digunakan untuk membentuk model ekstraksi berdasarkan contoh data pelatihan dan struktur target atau template yang telah ditentukan sebelumnya (predefined). Kemudian model ekstraksi tersebut diaplikasikan pada data pengujian untuk menghasilkan keluaran berupa informasi
II-4 di dalam suatu dokumen teks yang relevan dengan tipe slot yang berkorespondensi di dalam struktur target. 3. Pemrosesan akhir (postprocessing) hasil keluaran Biasanya struktur target direpresentasikan dengan relasi di dalam basis data. Oleh karena itu, pemrosesan hasil keluaran berkaitan dengan mengisi struktur target dengan informasi relevan yang dihasilkan. Proses pengisian tersebut mencakup normalisasi ke dalam format tertentu (misalnya untuk representasi tanggal dan waktu). Selain itu, beberapa fakta yang ditemukan mungkin muncul beberapa kali di dalam dokumen teks, atau sudah ada di dalam basis data. Oleh karena dibutuhkan proses penggabungan fakta (instance unification). Terdapat dua pendekatan di dalam menerapkan teknik pembelajaran mesin untuk proses ekstraksi informasi, yaitu pembelajaran aturan dan statistik. Pada pendekatan pembelajaran aturan, sistem mempelajari aturan-aturan yang dapat digunakan untuk mengekstrak informasi dari suatu dokumen teks, berdasarkan contoh-contoh data pelatihan. Beberapa sistem ekstraksi yang menggunakan pembelajaran aturan antara lain SRV [FRE98], RAPIER [CAL98], WHISK [SOD99], BWI [FRE00], dan (LP)2 [CIR01]. Sedangkan pendekatan statistik secara umum mengurangi persoalan ekstraksi informasi menjadi persoalan prediksi, dengan membangun model representasi formal secara matematis [SIE05a], seperti HMM [FRE99], Maximum Entropy [CHI02], SVM [FIN06, ISO02, LI05a, MAY03], dan Perceptron [CAR03]. Dengan menggunakan pendekatan ini, data pelatihan digunakan secara efisien untuk mempelajari prediksi yang benar, sehingga dapat menghasilkan model ekstraksi. Salah satu metode yang dapat digunakan untuk memodelkan persoalan ekstraksi informasi adalah metode klasifikasi token. Pada [SIE05a] tersedia hasil perbandingan antara sistem-sistem yang menggunakan pendekatan pembelajaran aturan dan pendekatan statistik. Salah satu corpus yang sering digunakan untuk evaluasi sebuah sistem ekstraksi informasi adalah CMU Seminar Announcements corpus, terdiri dari 485 pemberitahuan seminar, dengan jumlah slot yang harus diisi adalah sebanyak 4 buah, yaitu: speaker, location, start
II-5 time, dan end time. Hasil evaluasi dengan menggunakan corpus tersebut adalah sistem-sistem yang menggunakan pendekatan statistik, yaitu ELIEL2 [FIN06] dan TIE [SIE05b], mencapai nilai terbaik dengan akurasi masing-masing 92.5% dan 90.7%. Sementara dua buah sistem yang menggunakan pembelajaran aturan yaitu BWI [FRE00] dan (LP)2 [CIR01] hanya mencapai akurasi masing-masing 84.5% dan 86.8%. Selain itu, corpus yang juga sering digunakan adalah job postings corpus, terdiri dari 300 buah posting berisi lowongan pekerjaan, dengan jumlah slot yang harus diisi adalah sebanyak 17 buah. Berdasarkan [SIE05a], sistem yang mencapai akurasi tertinggi diraih oleh ELIEL2 dengan nilai macroaverage sebesar 79.5%, sedangkan jika menggunakan penghitungan weighted average, nilai tertinggi diraih oleh (LP)2 sebesar 79.8%. Akan tetapi terdapat perbedaan cara penghitungan skor yang benar pada masing-masing sistem. (LP)2 menggunakan skema one answer per slot sedangkan ELIEL2 menggunakan skema one answer per occurrence. Hal ini mengakibatkan performansi (LP)2 yang lebih tinggi pada beberapa field seperti platform, application, dan area, yang muncul beberapa kali di dalam dokumen. Pada (LP)2 jawaban dianggap benar selama salah satu dari kemunculan tersebut berhasil diekstrak oleh sistem, sementara pada ELIEL2 jawaban dianggap benar jika semua kemunculan untuk beberapa field tersebut berhasil diekstrak oleh sistem. Berdasarkan hasil perbandingan tersebut, untuk sementara dapat disimpulkan bahwa pendekatan statistik, dengan menggunakan pemodelan persoalan ekstraksi informasi sebagai persoalan klasifikasi token, seperti yang digunakan oleh ELIEL2 memiliki prospek yang cerah di dalam bidang proses ekstraksi informasi. Oleh karena itu metode klasifikasi token akan menjadi fokus di dalam tugas akhir ini. 2.1.2 Ekstraksi Informasi Sebagai Persoalan Klasifikasi Token Proses ekstraksi informasi dapat dimodelkan sebagai persoalan klasifikasi, dalam hal ini klasifikasi token. Secara garis besar, yang dilakukan adalah membagi teks menjadi token-token, kemudian dengan menggunakan classifier yang terlatih setiap token ditentukan apakah merupakan bagian dari pengisi slot (slot filler) untuk template atau bukan [SIE05a]. Misalnya, menentukan apakah sebuah token yang berada di dalam
II-6 suatu dokumen teks mengenai iklan lowongan pekerjaan, merupakan bagian dari nama perusahaan yang menawarkan pekerjaan. Asumsi yang digunakan adalah setiap token mungkin merupakan bagian dari sebuah pengisi slot, dan dua atau lebih token-token yang berurutan maupun tidak, mungkin merupakan bagian dari sebuah pengisi slot yang sama. Selain itu, diasumsikan bahwa template atau struktur target yang akan digunakan sudah didefinisikan sebelumnya (predefined). Secara garis besar, untuk dapat memodelkan ekstraksi informasi sebagai persoalan klasifikasi, dibutuhkan 3 komponen utama [SIE07], yaitu: 1. Representasi konteks (context representation) 2. Algoritma klasifikasi (classifier) 3. Strategi tagging (combination strategies) Lebih lanjut mengenai penjelasan detil setiap komponen akan dijelaskan pada bagian berikut ini. 2.1.2.1 Representasi Konteks Agar dapat digunakan sebagai masukan untuk algoritma klasifikasi, maka token-token dari teks harus diubah ke dalam vektor fitur (feature vector). Cara yang paling mudah tentu dengan mengubah setiap token ke dalam vektor fitur berelemen tunggal yang hanya mengandung token tersebut sebagai elemennya. Akan tetapi, cara tersebut tidak akan memberikan informasi yang berguna bagi classifier untuk dapat mengklasifikasikan token, karena tidak ada informasi mengenai konteks tekstual tempat token tersebut berada, dan juga tidak ada informasi linguistik, semantik, dan morfologis dari token itu sendiri. Sebuah classifier dapat bekerja dengan baik apabila bekerja pada vektor fitur yang lebih “kaya”, yang memberikan informasi tambahan mengenai token tersebut, dan konteks di mana token tersebut muncul. Dalam hal ini, vektor fitur disebut sebagai representasi konteks. 2.1.2.2 Algoritma Klasifikasi Terdapat beberapa algoritma klasifikasi yang dapat digunakan untuk menghasilkan model ekstraksi, salah satunya adalah Support Vector Machine (SVM). SVM telah
II-7 mencapai performansi state-of-the-art untuk berbagai persoalan klasifikasi, termasuk untuk persoalan named entity recognition [LI05a]. 2.1.2.3 Strategi Tagging Tugas utama dari sebuah sistem ekstraksi informasi adalah mengisi sebuah struktur target yang terdiri dari beberapa slot (template filling), yang dilakukan dalam dua tahap [SIE05a], yaitu: 1. Pengisian slot (single-slot extraction), yaitu mencari pengisi yang cocok untuk slot tertentu 2. Unifikasi template (multi-slot extraction), yaitu mengkombinasikan setiap pengisi slot yang ditemukan ke dalam struktur target atau template. Hal ini perlu dilakukan karena sebuah struktur target memiliki beberapa slot, dan pengisi slot dapat terdiri dari beberapa token. Untuk menggabungkan token-token yang sudah terklasifikasi ke dalam struktur target, yaitu tahap kedua dari proses ekstraksi informasi, dapat digunakan beberapa strategi kombinasi atau disebut juga strategi tagging. Pemilihan strategi tagging akan menentukan jumlah kelas pada classifier. Pada Tabel II-1 dapat dilihat perbandingan penggunaan kelas dan jumlah kelas yang digunakan oleh strategi-strategi tagging tersebut. Tabel II-1 Perbandingan strategi tagging [SIE06] Strategi Kelas khusus untuk token awal Kelas khusus untuk token akhir Kelas khusus untuk token antara Kelas khusus untuk token tunggal Kelas khusus untuk token setelah token akhir Jumlah kelas Jumlah classifier
Triv -
IOB2 + + -
IOB1 (+) + -
BIE + + + +
BIA + + -
BE + + -
-
-
-
-
+
-
n +1 1
2n + 1 1
2n + 1 1
4n + 1 1
3n + 1 1
n +1 2
1. Strategi Triv (trivial) Merupakan strategi yang paling sederhana, yang menggunakan kelas tunggal untuk setiap tipe pengisi slot, dan kelas tambahan yaitu kelas “O” untuk token yang bukan merupakan pengisi slot. Jumlah kelas yang dibutuhkan dalam proses pembelajaran adalah n + 1 , dimana n adalah jumlah tipe pengisi slot.
II-8 Akan tetapi, strategi ini tidak dapat bekerja dengan benar jika dua nilai dari tipe pengisi slot yang sama muncul secara berurutan, misalnya nama dari dua orang SPEAKER yang hanya dipisahkan oleh baris, seperti yang dapat dilihat pada Gambar II-3, yaitu Emilie Roth dan Alexander I. Rudnicky. Dalam kasus ini, kedua nama tersebut akan dianggap sebagai satu kesatuan dari nilai tipe pengisi slot SPEAKER. HCI & G Seminar Wednesday, October 21, 1992 3:30 – 5:00pm Wean Hall 5409 Mode preference in a data-retrieval task By Emilie Roth Alexander I. Rudnicky (Carnegie Mellon Uneversity, School of Computer Science) Gambar II-3 Contoh dua nilai dari atribut yang sama muncul berurutan [SIE07]
Oleh karena itulah, dibutuhkan strategi yang lebih kompleks untuk mengatasi masalah tersebut, yaitu untuk menandai token pertama dan/atau token terakhir dari sebuah nilai atribut. 2. Strategi IOB1 dan IOB2 Dua variasi dari IOB tagging mungkin merupakan strategi yang paling umum. Pada variasi yang kedua, biasa disebut dengan IOB2, sebuah token diklasifikasikan sebagai: -
token awal dari nilai suatu tipe pengisi slot (B-type),
-
token lanjutan dari awal nilai suatu tipe pengisi slot (I-type), atau
-
bukan merupakan pengisi slot (O).
Strategi IOB1 berbeda dari IOB2 dalam hal penggunaan kelas B-type hanya jika diperlukan untuk menghindari ambiguitas (yaitu jika dua buah nilai tipe pengisi slot muncul secara berurutan seperti pada contoh pada Gambar II-3). Jika ambiguitas tidak terjadi maka digunakan kelas I-type, bahkan jika token merupakan awal dari nilai suatu tipe pengisi slot. Dengan menggunakan strategi IOB, jumlah kelas yang dibutuhkan adalah 2n + 1 .
II-9 3. Strategi BIE Pada strategi ini, digunakan kelas tambahan untuk token terakhir dari nilai suatu tipe pengisi slot. Jadi, sebuah token diklasifikasikan sebagai: -
token awal dari nilai atribut (B-type),
-
token yang berada di antara token awal dan token akhir (I-type),
-
token akhir dari nilai atribut (E-type),
-
token tunggal, sebagai token awal maupun token akhir (BE-type), atau
-
bukan merupakan pengisi slot (O).
Dengan demikian jumlah kelas yang dibutuhkan adalah 4n + 1 . 4. Strategi BIA Kekurangan dari strategi BIE adalah jumlah kelas yang digunakan sangat banyak. Masalah ini dapat diatasi oleh strategi BIA (atau Begin/After tagging). Pada strategi ini, sebuah token diklasifikasikan sebagai: -
token awal dari nilai tipe pengisi slot (B-type),
-
token lanjutan dari awal nilai suatu tipe pengisi slot (I-type),
-
token awal dari nilai tipe pengisi slot lain (A-type), atau
-
bukan merupakan pengisi slot (O).
Jumlah kelas yang dibutuhkan adalah 3n + 1 , lebih sedikit jika dibandingkan dengan strategi BIE. 5. Strategi BE Jika strategi-strategi tagging sebelumnya menggunakan sebuah classifier, strategi Begin/End (BE) tagging menggunakan dua buah classifier. Classifier pertama digunakan untuk mengklasifikasikan token sebagai: -
awal dari pengisi slot untuk setiap tipe slot (B-type), atau
-
bukan merupakan pengisi slot (O).
Sedangkan classifier kedua digunakan untuk untuk mengklasifikasikan token sebagai -
akhir dari pengisi slot untuk setiap tipe slot (E-type), atau
-
bukan merupakan pengisi slot (O).
Pengisi slot yang paling tepat ditentukan dengan mengkombinasikan pasangan tag begin dan end yang paling cocok untuk setiap tipe slot. Dengan demikian, jumlah kelas yang dibutuhkan untuk masing-masing classifier adalah n + 1 .
II-10
Ilustrasi penggunaan strategi-strategi tersebut untuk mengklasifikasikan token dapat dilihat pada contoh yang terdapat pada Tabel II-2. Contoh teks yang digunakan adalah "Our meeting with Mr. Irfan Ali will be at 1:30 pm in...". Tabel II-2 Contoh penggunaan strategi tagging [SIE06] Text
Our
meeting
with
Mr.
Irfan
Ali
Triv IOB2 IOB1 BIE BIA BE
O O O O O O/O
O O O O O O/O
O O O O O O/O
speaker B-speaker I-speaker B-speaker B-speaker B-speaker/O
speaker I-speaker I-speaker I-speaker I-speaker O/O
Speaker I-speaker I-speaker E-speaker I-speaker O/ E-speaker
Text
will
be
at
1:30
pm
in…
Triv IOB2 IOB1 BIE BIA BE
O O O O A-speaker O/O
O O O O O O/O
O O O O O O/O
stime B-stime I-stime B-stime B-stime B-stime / O
stime I-stime I-stime E-stime I-stime O / E-stime
O O O O A-stime O/O
2.1.3 Pemberian Anotasi pada Dataset untuk Ekstraksi Informasi Sebelum sebuah dataset dapat digunakan oleh sistem ekstraksi informasi secara otomatis, dataset tersebut harus melalui proses pemberian anotasi (annotation) atau catatan. Proses pemberian anotasi harus dilakukan secara manual sehingga membutuhkan perhatian lebih dan merupakan proses yang paling menyita waktu di dalam pembangunan sebuah sistem ekstraksi informasi. Secara garis besar proses pemberian anotasi dapat dipecah menjadi beberapa tahap, yaitu: 1. Mengidentifikasi dan mendefinisikan entitas yang menarik dan akan diekstrak dari sebuah koleksi dokumen Entitas yang akan diekstrak harus didefinisikan secara jelas, baik arti dari entitas itu sendiri, maupun aturan-aturan yang menjadikan sebuah token merupakan bagian dari entitas tersebut. Sebagai contoh, untuk field waktu, string yang bagaimanakah yang dapat menyatakan waktu. Misalkan terdapat string “at the weekend” atau “this afternoon” pada dokumen, apakah string tersebut dapat dianggap sebagai waktu.
II-11 2. Menentukan representasi dari anotasi yang akan diberikan Representasi yang paling sederhana adalah memberikan tag untuk menandai awal dan akhir kemunculan sebuah nilai field pada teks, yaitu dengan sintaks:
Isi field. Pada Gambar II-4 dapat dilihat contoh pemberian tag pada sebuah dokumen teks. From: "Brian Baccam" Newsgroups: austin.jobs Subject: VISUAL BASIC in San Antonio Date: <post_date>30 Aug 1997<post_date> 21:56:47 GMT Organization: Devon Tax Group Lines: 16 Message-ID: <[email protected]> NNTP-Posting-Host: pc22.devontax.com X-Newsreader: Microsoft Internet News 4.70.1162 Xref: cs.utexas.edu austin.jobs:120377 Visual Basic progammer needed in San Antonio. Will be working with a small team to develop a tax management program. Minimum Qualifications: * 2-4 yrs. of Visual Basic application development experience * strong working knowldge of Access and/or SQL Server a plus. Gambar II-4 Contoh pemberian anotasi berupa tag pada dokumen teks
3. Memberikan catatan pada koleksi dokumen sesuai dengan guideline pemberian anotasi yang dihasilkan pada tahap 1 dan 2 Merupakan proses yang paling sulit dan menyita waktu, karena berhubungan dengan koleksi dokumen yang sangat banyak dan dikerjakan secara manual oleh manusia. Biasanya menggunakan editor teks khusus untuk mempermudah proses pemberian anotasi. Terdapat beberapa dataset standar yang dapat digunakan untuk ekstraksi informasi. Dataset atau corpus tersebut dapat ditemukan pada RISE Repository yang dapat diakses pada URL: http://www.isi.edu/info-agents/RISE/repository.html. Beberapa corpus yang sering digunakan untuk evaluasi sebuah sistem ekstraksi informasi adalah CMU Seminar Announcements Corpus dan Job Postings Corpus. CMU Seminar Announcements Corpus terdiri dari 485 pemberitahuan seminar dalam bentuk file teks, yang dikoleksi dari newsgroup universitas [SIE05a]. Untuk corpus
II-12 ini, jumlah slot yang harus diisi adalah sebanyak 4 buah slot, yaitu: speaker, location, start time, dan end time. Sedangkan Job Postings Corpus, terdiri dari 300 buah posting berisi lowongan pekerjaan, dengan jumlah slot yang harus diisi adalah sebanyak 17 buah, yaitu: id, title, company, salary, recruiter, state, city, country, language, platform, application, area, required years experience, desired years experience, required degree, desired degree, dan post date. 2.1.4 Metodologi Evaluasi Sistem Ekstraksi Informasi Seperti yang didiskusikan pada [LAV04a] dan [LAV04b], terdapat beberapa hal yang berkaitan dengan metodologi evaluasi sebuah sistem ekstraksi informasi. Salah satunya adalah bagaimana jika hasil ekstraksi hanya benar sebagian, misalnya jika informasi mengenai SPEAKER yang seharusnya adalah “Dr. J. Lee”, hasil ekstraksinya hanya “J. Lee”. Menurut [LAV04a], terdapat 3 pendekatan untuk mencocokkan hasil ekstraksi dengan data yang sebenarnya, yaitu: -
exact, hasil prediksi ekstraksi harus sama persis dengan frase yang sebenarnya.
-
contains, hasil prediksi ekstraksi harus mengandung frase yang sebenarnya, dalam k token terdekat.
-
overlap, hasil prediksi ekstraksi overlap dengan frase yang sebenarnya.
Isu lainnya adalah bagaimana cara menghitung ekstraksi yang benar dan yang salah. Terdapat 3 pendekatan yang dapat digunakan yaitu: -
one answer per occurences, merupakan pendekatan yang paling konservatif adalah dengan mengharuskan sistem untuk dapat mengekstrak semua kemunculan nilai pada suatu atribut (one answer per occurences). Jika terdapat dua kemunculan nilai ‘2pm’ untuk field target TIME pada lokasi yang berbeda, maka sistem harus dapat mengekstrak keduanya (dianggap sebagai dua jawaban).
-
one answer per slot, merupakan pendekatan yang hanya mengharuskan sistem untuk dapat mengekstrak salah satu kemunculan yang dianggap paling benar. Dengan pendekatan ini, maka sistem cukup mengekstrak salah satu dari ‘2pm’ atau ‘2:00’.
II-13 -
one answer per different string, jika pada dokumen terdapat 2 kemunculan field target dengan string yang berbeda, misalnya untuk field TIME nilainya adalah ‘2pm’ dan ‘2:00’, maka sistem harus dapat mengekstraksi keduanya. Pada pendekatan ini, dua kemunculan nilai ‘2pm’ dianggap sebagai satu jawaban, dan ‘2:00’ merupakan jawaban lain.
2.1.5 Metrik Evaluasi Sistem Ekstraksi Informasi Di dalam mengevaluasi sebuah sistem ekstraksi informasi, metrik pengukuran yang umum digunakan adalah precision, recall, dan F-measure [SIE05a]. Adapun precision, recall, dan F-measure untuk masing-masing atribut atau tipe slot dapat dihitung dengan rumus berikut.
precision = recall =
correct correct + falsePositive
correct correct + falseNegative
F − measure =
2 × precision × recall precision + recall
(2.1) (2.2) (2.3)
dengan correct adalah jumlah slot yang terisi dan benar atau, falsePositive adalah jumlah slot yang terisi namun salah, dan falseNegative adalah jumlah slot yang tidak terisi. Untuk dataset yang memiliki beberapa tipe slot di dalam template untuk diisi (misalnya pada job postings corpus yang memiliki 17 tipe slot), terdapat beberapa cara untuk mengkombinasikan hasilnya ke dalam nilai tunggal, yaitu microaverage,
macroaverage, dan weighted average. Dengan menggunakan microaverage, semua correct, falsePositive, dan falseNegative untuk semua tipe slot dihitung dan dijumlahkan, kemudian F-measure dihitung berdasarkan nilai correct, falsePositive, dan falseNegative total hasil penjumlahan tersebut. Lain halnya pada macroaverage, yaitu menghitung rata-rata nilai F-measure yang telah dihitung untuk setiap tipe slot. Pada weighted average yang diusulkan oleh [CHI02], pertama-tama F-measure untuk setiap tipe slot dihitung, kemudian rata-rata nilai F-measure tersebut dihitung dengan mempertimbangkan bobot untuk setiap tipe slot. Yang dimaksud dengan bobot setiap
II-14 tipe slot adalah jumlah kemunculan pengisi slot untuk tipe slot tersebut pada dataset secara keseluruhan, seperti yang dapat dilihat pada Tabel III-2, pada kolom “Kemunculan”. Sehingga dapat disimpulkan bahwa rumus untuk penghitungan
weighted average adalah sebagai berikut: n
weighted _ average =
∑ F − measure × w i
i =1
i
n
∑w i =1
(2.4)
i
dimana n adalah jumlah tipe slot, dan wi adalah bobot untuk tipe slot ke- i . Mengenai penanganan partial correct, yaitu hasil prediksi ekstraksi hanya benar sebagian, di dalam rumus precision, recall, dan F-measure, terdapat 3 cara yaitu: 1. Strict, partial correct dianggap salah, yaitu baik sebagai falsePositive maupun
falseNegative. 2. Lenient, partial correct dianggap benar. 3. Average, partial correct diberi bobot ½.
2.2 Pembelajaran Mesin Pembelajaran mesin atau machine learning merupakan salah satu cabang dari ilmu intelegensia buatan (artificial intelligence). Konsep dari pembelajaran mesin adalah komputer dapat memiliki kemampuan untuk dapat beradaptasi terhadap lingkungan yang baru, dan mampu mendeteksi pola dari fakta yang ada [RUS03]. Definisi secara formalnya: Sebuah komputer dikatakan belajar dari pengalaman E dengan persoalan pembelajaran T dan metriks performansi P, jika performansinya pada persoalan T, yang diukur dengan P, meningkat dengan pengalaman E. [MIT97] Di dalam menentukan konsep pembelajaran yang akan digunakan, salah satu faktor yang paling menentukan adalah tipe umpan balik (feedback) yang disediakan. Di dalam pembelajaran mesin, terdapat 4 tipe pembelajaran berdasarkan umpan balik yang diberikan, yaitu: -
supervised learning, mempelajari sebuah fungsi dari contoh input dan outputnya.
II-15 -
unsupervised learning, mempelajari pola dari input dimana nilai output yang spesifik terhadap input tidak diberikan.
-
semi-supervised learning, menggunakan baik data berlabel kelas (memiliki nilai output) maupun data tidak berlabel kelas sebagai data pelatihan.
-
reinforcement learning, mempelajari pola kelakuan berdasarkan reward yang diberikan.
2.2.1 Support Vector Machine
Support Vector Machine (SVM), pertama kali diperkenalkan oleh Vapnik, Boser, dan Guyon pada tahun 1992, adalah metode pembelajaran mesin yang bekerja dengan prinsip Structural Risk Minimization (SRM), dengan tujuan menemukan hyperplane terbaik yang dapat memisahkan data ke dalam dua buah kelas di dalam sebuah ruang fitur (feature space) berdimensi tinggi. Yang dimaksud dengan hyperplane pada sebuah ruang vektor berdimensi d, adalah sebuah bidang berdimensi d-1 yang dapat membagi ruang vektor menjadi dua bagian, yang masing-masing berkorespondensi dengan kelas yang berbeda. Pada Gambar II-5 (kiri) dapat dilihat berbagai alternatif hyperplane atau bidang pemisah yang dapat memisahkan data ke dalam dua buah kelas. Namun, bidang pemisah terbaik tidak hanya dapat memisahkan data tetapi juga memiliki margin m paling besar seperti yang dapat terlihat pada Gambar II-5 (kanan). Data yang paling dekat dengan bidang pembatas kelas 1 dan kelas 2, pada Gambar II-5 (kanan) dilambangkan dengan garis putus-putus, dinamakan support vector. dimensi 2 dimensi 2
dimensi 1 dimensi 1
Gambar II-5 Alternatif bidang pemisah (kiri) dan bidang pemisah terbaik dengan margin m terbesar (kanan)
II-16 Pencarian bidang pemisah terbaik dengan nilai margin terbesar dapat dirumuskan menjadi masalah optimasi konstrain [SMO00], yaitu:
1 2 w 2 y i ((w ⋅ xi ) + b ) ≥ 1, for all i = 1,...,m
minimize τ (w) = subject to
(2.5)
Persoalan ini akan lebih mudah diselesaikan jika diubah ke dalam formula Lagrangian yang menggunakan Lagrange multiplier α i ≥ 0 .
L(w, b, α ) ≡
n 1 2 m w − ∑ α i ( y i (( xi ⋅ w) + b ) − 1) + ∑ α i 2 i =1 i =1
(2.6)
Lagrangian L harus diminimalkan terhadap variabel w dan b, dan harus dimaksimalkan terhadap dual variable α i . Pada Gambar II-5 terlihat bahwa terdapat bidang pemisah yang dapat memisahkan data dengan sempurna. Namun pada kenyataannya data seringkali tidak dapat dipisahkan dengan sempurna oleh bidang pemisah, seperti yang dapat terlihat pada Gambar II-6 (kiri). dimensi 2
dimensi 3
dimensi 1
Gambar II-6 Contoh data yang tidak dapat dipisah secara linear
Dengan menggunakan fungsi kernel, data (input space) yang tidak dapat dipisahkan secara linear dapat dipetakan ke dalam ruang vektor dengan dimensi yang lebih tinggi (feature space), sehingga memungkinkan untuk dilakukan pemisahan secara linear. Pada
Gambar II-6 (kiri), data yang semula berada di dalam ruang 2 dimensi,
dipetakan ke dalam ruang 3 dimensi, sehingga dapat dipisahkan secara linear, seperti yang dapat terlihat pada Gambar II-6 (kanan). Beberapa fungsi kernel yang umum digunakan antara lain [LIN07]:
II-17 -
linear: K (xi , x j ) = xiT x j
-
polynomial: K (xi , x j ) = (γ .xiT x j + r ) , γ > 0
-
radial basis function (RBF): K (xi , x j ) = exp − γ xi − x j
-
sigmoid: K (xi , x j ) = tanh (γ .xiT x j + r )
d
(
2
), γ > 0
Saat pertama kali diperkenalkan oleh Vapnik, SVM hanya dapat mengklasifikasikan data ke dalam dua kelas (klasifikasi biner) [SEM07]. Salah satu cara untuk mengimplementasikan multi class SVM adalah dengan mengkombinasikan beberapa SVM biner. Terdapat beberapa metode untuk kombinasi, antara lain [SEM07]: 1. one-against-all: dibangun sejumlah k SVM biner, dengan k adalah jumlah kelas.
Sebagai contoh, untuk persoalan klasifikasi dengan 4 buah jumlah kelas, digunakan 4 buah SVM biner seperti yang dapat dilihat pada Tabel II-3 dan penggunaannya pada pengklasifikasian data baru dapat dilihat pada Gambar II-7. Tabel II-3 Contoh kombinasi SVM biner dengan metode one-against-all [SEM07]
yi = 1
y i = −1
Kelas 1
Bukan kelas 1
Kelas 2
Bukan kelas 2
Kelas 3
Bukan kelas 3
Kelas 4
Bukan kelas 4
Hipotesis
f 1 ( x ) = (w1 )x + b1
(x ) = (w 2 )x + b 2 f 3 ( x ) = (w 3 )x + b 3 f 4 ( x ) = (w 4 )x + b 4 f
2
Gambar II-7 Contoh klasifikasi dengan metode one-against-all [SEM07]
II-18
2. one-against-one: dibangun sejumlah
k (k − 1) buah model SVM biner, dengan k 2
adalah jumlah kelas. Sebagai contoh, untuk persoalan klasifikasi dengan 4 buah jumlah kelas, digunakan 6 buah SVM biner seperti yang dapat dilihat pada Tabel II-4 dan penggunaannya pada pengklasifikasian data baru dapat dilihat pada Gambar II-8. Tabel II-4 Contoh kombinasi SVM biner dengan metode one-against-one [SEM07]
yi = 1
y i = −1
Kelas 1
Kelas 2
Hipotesis
( (x ) = (w (x ) = (w (x ) = (w (x ) = (w (x ) = (w
) )x + b )x + b )x + b )x + b )x + b
f 12 ( x ) = w12 x + b12 13
Kelas 1
Kelas 3
f
Kelas 1
Kelas 4
f 14
Kelas 2
Kelas 3
f
23
Kelas 2
Kelas 4
f
24
Kelas 3
Kelas 4
f 34
13 14 23 24 34
13 14 23 24 34
Gambar II-8 Contoh klasifikasi dengan metode one-against-one [SEM07]
3. DAGSVM: hampir sama dengan metode one-against-one, namun pada saat
klasifikasi digunakan binary directed acyclic graph. Penjelasan lebih lanjut mengenai metode kombinasi SVM biner dapat dilihat pada [SEM07]. Ketika digunakan untuk mengklasifikasikan dataset dengan rasio imbalance yang tinggi, dimana contoh positif sangat sedikit dibandingkan dengan contoh negatif, Li dan Shawe-Taylor (2003) menunjukkan bahwa SVM dengan uneven margin memiliki performansi yang lebih baik jika dibandingkan dengan SVM standar [LI05b].
II-19
Diberikan himpunan pelatihan Z = (( x1 , y1 ),..., ( x m , y m )) , dimana xi adalah vektor input n-dimensi, dan y i (= +1 atau -1) adalah label kelas, dan m adalah jumlah data pelatihan. SVM dengan uneven margin diperoleh dengan memecahkan persoalan optimisasi kuadratik: m
min w,b ,ξ w, w + C ∑ ξ i i =1
s.t w,xi + ξ i + b ≥ 1 if y i = +1 w, xi − ξ i + b ≤ −τ
(2.7)
if y i = −1
ξ i ≥ 0 for i = 1,..., m Dapat terlihat pada (2.7) terdapat penambahan parameter τ , yaitu rasio margin kelas negatif terhadap margin kelas positif, dan sama dengan 1 pada SVM standar. Pada imbalanced dataset, sebaiknya digunakan margin yang lebih besar untuk kelas positif dibandingkan untuk kelas negatif, seperti yang dapat dilihat pada Gambar II-9. Oleh karena itu, pada SVM dengan uneven margin nilai τ adalah 0 < τ < 1 .
dimensi 2
-
mpos + +
+ + +
Kelas positif
++
Kelas - negatif-
- - -- -- - - m = - neg τ- ×-mpos - Bidang pembatas kelas negatif Bidang pemisah
+
Bidang pembatas kelas positif dimensi 1
Gambar II-9 Ilustrasi SVM dengan uneven margin
2.3 Sistem Ekstraksi Informasi dengan Support Vector Machine Terdapat beberapa sistem yang memodelkan persoalan ekstraksi informasi sebagai klasifikasi token, dan menggunakan Support Vector Machine (SVM) sebagai classifier, seperti ELIEL2 [FIN04a, FIN04b, FIN06] dan GATE-SVM [LI05a].
II-20 2.3.1 ELIEL2
ELIEL2 [FIN04a, FIN04b, FIN06], yang dikembangkan oleh Aidan Finn dkk., menggunakan strategi Begin/End tagging, yaitu menggunakan dua buah classifier untuk mengklasifikasikan token awal dan token akhir dari suatu atribut. Algoritma yang digunakan untuk klasifikasi adalah algoritma Sequential Minimal Optimization (SMO), untuk lebih tepatnya WekaSMO, karena eksperimen dilakukan menggunakan Weka [FIN04a]. Algoritma pembelajaran ELIEL2 terdiri dari 2 fase atau level pembelajaran. Pada fase pertama, ELIEL2 mendeteksi awal dan akhir dari fragmen yang akan diekstrak. Akan tetapi, pada tahap pertama ini, hasil ekstraksi ternyata memiliki precision yang tinggi namun recall yang rendah. Hal ini disebabkan karena seringkali hampir terjadi false negative, yaitu bagian awal terdeteksi dengan benar namun bagian akhir salah, atau sebaliknya. Oleh karena itu dilakukan fase kedua, yaitu mendeteksi akhir dari fragmen jika diberikan bagian awal dari fragmen, dan sebaliknya. Karena terdiri dari dua fase maka ELIEL2 disebut sebagai klasifikasi dengan two-level boundary. 2.3.2 GATE-SVM
Sama seperti ELIEL2, GATE-SVM [LI05a], yang dikembangkan oleh Yaoyong Li dkk., menggunakan strategi Begin/End tagging. Akan tetapi, GATE-SVM menggunakan varian dari SVM, yaitu SVM dengan uneven margin [LI05a], yang memiliki performansi generalisasi yang lebih baik jika dibandingkan dengan SVM biasa, jika diterapkan pada dataset yang memiliki rasio imbalance yang tinggi, dimana contoh positif sangat sedikit dibandingkan dengan contoh negatif. 2.3.3 Evaluasi ELIEL2 dan GATE-SVM
Berdasarkan hasil evaluasi ELIEL2 yang terdapat pada [FIN04a] dan GATE-SVM yang terdapat pada [LI05a], dapat diketahui bahwa nilai akurasi rata-rata (weighted average) tertinggi diraih oleh ELIEL2, dengan nilai sebesar 78.8%, sementara posisi kedua ditempati oleh GATE-SVM dengan nilai akurasi rata-rata 77.9%, diikuti oleh (LP)2 dengan nilai 77.2% dan Rapier dengan nilai 72.7%. Adapun eksperimen yang dilakukan menggunakan pembagian dataset job postings corpus 50:50 untuk pelatihan dan pengujian, kemudian diulang sebanyak 10 kali.
II-21 Untuk dataset job postings corpus, ELIEL2 memang memiliki performansi yang paling baik jika dibandingkan dengan ketiga sistem lainnya (GATE-SVM, (LP)2, dan Rapier). Akan tetapi, ketika diikutsertakan pada Pascal Challenge NovemberDesember 2004 [IRE04], ELIEL2 ternyata memiliki performansi yang kurang baik. Pada Pascal Challenge tersebut, peringkat teratas diraih oleh Amilcare, yang bekerja berdasarkan algoritma (LP)2. Peringkat kedua diraih oleh sistem yang merupakan pengembangan dari GATE-SVM yang dikembangkan oleh Yaoyong Li. Sedangkan ITC-IRST, yang menempati peringkat kelima, merupakan sistem berbasis SVM satu level yang hampir sama dengan ELIEL1, namun menerapkan strategi penyaringan instance (instance filtering) yang diajukan oleh Gliozzo dkk. Salah satu penyebab mengapa ELIEL2 memiliki performansi yang kurang baik pada persoalan ini adalah karena dataset yang digunakan pada Pascal Challenge memiliki rasio imbalance yang sangat tinggi. Menurut [FIN06], dataset job postings corpus memiliki rasio imbalance 500:1, sedangkan dataset Pascal CFP memilki rasio imbalance 900:1.
