bab ii tinjauan pustaka - · pdf filegrammar untuk bahasa reguler atau ekspresi reguler...
TRANSCRIPT
II-1
BAB II TINJAUAN PUSTAKA
Bab ini membahas hal-hal apa saja yang pernah dilakukan sebelumnya mengenai
model-model pola tata bahasa, pengurai (parser) untuk bahasa lain, dan
pembangkitan pola tata bahasa khususnya yang menggunakan pendekatan
probabilistik untuk bahasa lain. Penelitian mengenai pengurai dengan metode
probabilistik untuk bahasa Indonesia belum ditemukan oleh penulis. Penelitian-
penelitian yang dibahas pada bab ini dibagi menjadi tiga kelompok besar yaitu
penelitian mengenai model-model pola tata bahasa, pengurai (parser), dan
pembangkitan pola tata bahasa dengan pendekatan probabilistik. Penelitian
mengenai model-model pola tata bahasa perlu dibahas agar diketahui model pola
tata bahasa apa saja yang telah dibuat oleh orang lain. Penelitian mengenai
pengurai (parser) perlu dibahas agar diketahui model-model pengurai (parser)
yang telah dikembangkan beserta keuntungan dan kelemahannya. Penelitian
mengenai pembangkitan pola tata bahasa dengan pendekatan probabilistik disini
agar diketahui metode-metode yang digunakan.
II.1 Model-model Pola Tata Bahasa
Grammar (tata bahasa) sering dianggap sebagai sebuah jalan alternatif untuk
menspesifikasikan bahasa. Grammar secara teknis merupakan sebuah alat untuk
merepresentasikan sebuah bahasa. Grammar untuk bahasa reguler atau ekspresi
reguler disebut dengan regular grammar [19]. Sebuah regular grammar terdiri
dari empat parameter (4-tuple) yaitu kumpulan simbol non-terminal, kumpulan
simbol terminal, kumpulan aturan produksi, dan kumpulan simbol awal [19].
Grammar memiliki beberapa jenis. Grammar yang berbasis struktur frase (phrase
structure) antara lain seperti context-free grammar (CFG) beserta turunannya dan
tree-grammar, sedangkan grammar berbasis struktur kebergantungan adalah
dependency grammar. Pola tata bahasa dapat dimodelkan dengan CFG. CFG juga
terdiri dari empat parameter (4-tuple) yaitu kumpulan simbol non-terminal,
kumpulan simbol terminal, kumpulan aturan produksi, dan kumpulan simbol
II-2
awal. Perbedaan antara regular grammar dan context-free grammar terletak pada
aturan yang diterapkan pada aturan produksinya [19].
Dalam perkembangannya, CFG dikembangkan menjadi lexicalized context-free
grammar (LCFG) untuk keperluan representasi pohon pola tata bahasa. Hal ini
karena CFG tidak dapat mengakomodasi perlunya fungsi leksikal (aturan seperti
kata benda, kata kerja, kata sifat, dan lain-lain (jenis kata)) dalam membentuk
pohon pola tata bahasa. LCFG memiliki lima parameter (5-tuple) dimana tiga
parameter sama dengan CFG yaitu kumpulan simbol non-terminal, kumpulan
simbol terminal, dan kumpulan simbol awal ditambah dengan dua buah parameter
untuk merepresentasikan aturan produksi yang merepresentasikan pohon [19].
LCFG dikembangkan menjadi Stochastic Lexicalized Context-Free Grammar
(SLCFG) oleh Yves Schabes dan Richard C. Waters (1993) [23]. SLCFG
merupakan LCFG yang menambahkan komponen probabilitas untuk mengontrol
kombinasi pohon hasil dari proses penambahan simpul atau pergantian simpul.
SLCFG memilik sebelas parameter (11-tuple). Enam parameter tambahan SLCFG
merupakan probabilitas kemungkinan pertambahan dan perubahan yang dapat
terjadi pada pohon pada aturan produksi [21]. Kesimpulan dari penelitian ini
adalah bahwa SLCFG sangat bermanfaat sebagai alat pemrosesan bahasa alami
dimana perkiraan statistik atau prediksi dibutuhkan.
Pada perkembangannya, dibuat sebuah model CFG yang menambahkan
probabilitas pada aturan produksinya yang dikenal dengan Probabilistic Context-
Free Grammar (PCFG) atau dikenal juga dengan Stochastic Context-Free
Grammar (SCFG). Model PCFG memiliki lima buah parameter (5-tuple) yaitu
kumpulan simbol non-terminal, kumpulan simbol terminal, kumpulan aturan
produksi, kumpulan simbol awal, dan kumpulan probabilistik untuk aturan
produksinya. Perbedaan PCFG dengan CFG terletak pada penambahan
probabilitas pada setiap aturan produksi pada PCFG [17]. Perhitungan probabilitas
dapat menggunakan berbagai metode misalnya dengan menggunakan bigram
(keterkaitan dua buah elemen), atau trigram (keterkaitan tiga buah elemen). PCFG
(Probabilistic Context-Free Grammar)
II-3
PCFG (Probabilistic Context-Free Grammar) pada tesis ini digunakan untuk
representasi pohon. Aturan produksi pada PCFG digunakan sebagai sub pohon
(bagian-bagian yang membangun pohon). PCFG merupakan pengembangan dari
Context-Free Grammar (CFG). Sebuah CFG didefinisikan dengan empat buah
parameter (N, Σ, P, S) dimana:
N : kumpulan simbol non-terminal
Σ : kumpulan simbol terminal
P : kumpulan produksi, setiap bentuk α →β, dimana α adalah sebuah simbol
terminal dan β adalah string dari kumpulan string tak terbatas (Σ U N)*.
S : Simbol awal
Probabilistic context-free grammar menambah setiap aturan di dalam P dengan
sebuah kondisi probabilitas:
α → β [p] (II-1)
dimana [p] adalah probabilitas dari aturan produksi α → β.
Sebuah PCFG terdiri dari lima buah tuple yaitu G = (N, Σ, P, S, D), dimana D
adalah fungsi probabilitas yang dikenakan pada setiap aturan di P. Fungsi ini
merepresentasikan probabilitas p yang diberikan non-terminal α diekpansi ke β;
hal ini biasanya ditulis sebagai:
P(α→ β) atau P(α→β|α) (II-2)
Secara formal kondisi ini merupakan kondisi probabilitas yang dihasilkan dari
ekspansi di sisi kiri dari simbol non-terminal α.
Sebuah PCFG dapat digunakan untuk memperkirakan sebuah nilai probabiltas
yang berguna terkait dengan sebuah kalimat dan pohon hasil penguraian (parse-
tree). Probabilitas dari pohon hasil penguraian (parse-tree) T didefinisikan
sebagai produk probabilitas dari semua aturan r yang digunakan untuk
pembangkitan setiap simpul n dalam pohon hasil penguraian (parse-tree), S
II-4
adalah kalimat (sentence) sehingga hubungan antara pohon dan kalimat adalah
sebagai berikut:
P(T, S) = Tn
p(r(n)) (II-3)
atau
P(T,S) =
n
i 1
P(RHSi|LHSi) (II-4)
dimana n adalah jumlah aturan produksi, i adalah aturan produksi ke-i dan 1 ≤ i ≤
n, aturan produksinya adalah LHSi → RHSi [12]. Hasil dari probabilitas P(T, S)
adalah gabungan probabilitas dari hasil penguraian (parse) dan kalimat dan juga
probabilitas dari pohon P(T). Pada mulanya
P(T, S) = P(T)P(S|T) = P(T) (II-5)
karena P(S|T) bernilai 1. Setiap kalimat yang dibangkitkan pohon pola tata
bahasanya dapat diambil probabilitas pohon yang terbaik, sehingga pohon terbaik
dapat dilihat sebagai berikut:
T (S) = argmax )(ST P(T) (II-6)
Kegunaan dari PCFG untuk pemodelan bahasa adalah dapat memberikan
probabilitas pada bagian kalimat [16]. Pada tesis ini PCFG digunakan sebagai
model representasi pohon pola tata bahasa menggunakan aturan produksinya.
Glen Carroll (1995) melakukan sebuah penelitian mengenai pembelajaran tata
bahasa probabilistik untuk pemodelan bahasa [10]. Penelitian ini fokus pada
bahasa Inggris. Model yang digunakan dalam penelitian ini adalah PCFG
(probabilistic context-free grammar). Dalam penelitian ini PCFG didefinisikan
sebagai context-free grammar biasa dengan kumpulan distribusi probabilitas
II-5
aturan-aturan. Penelitian ini menggunakan trigram untuk menghitung probabilistik
setiap kata. Sistem yang dibangun pada penelitian ini diberi nama SINGER
(Single Reader) yang merefleksikan bahwa kalimat dibaca berdasarkan aturan.
Secara umum cara kerja sistem ini adalah sebagai berikut:
Didefinisikan aturan-aturan yang diterima. PCFG yang digunakan untuk
membangun aturan-aturan,
Melakukan perhitungan probabilitas per aturan PCFG dengan melihat
probabilitas simpul orang tua di atasnya.
Penelitian ini menghasilkan model grammar tambahan yang cukup besar. Perlu
adanya perbaikan lebih lanjut pada model grammar pada penelitian ini sehingga
performansi dan hasil dapat terus ditingkatkan kualitasnya.
Mark Johnson (1998) melakukan penelitian mengenai model PCFG (Probabilistic
Context-Free Grammar) untuk representasi pohon pola tata bahasa [16].
Penelitian ini mencoba menggunakan PCFG sebagai model pola tata bahasa
Inggris. Masukan dari sistem yang diimplementasikan adalah teks yang berisi
kumpulan kalimat. PCFG digunakan untuk membangkitkan pohon pola tata
bahasa per kalimat. Dalam penelitian ini model dengan PCFG dibandingkan
dengan beberapa model pola tata bahasa lainnya. Penulis penelitian ini
menyimpulkan bahwa perbedaan representasi pohon pola tata bahasa dengan
menggunakan PCFG dapat menimbulkan perbedaan performansi. PCFG cukup
baik digunakan sebagai representasi pohon pola tata bahasa untuk berbagai kasus
secara umum.
II.2 Penelitian mengenai Pengurai (parser)
Pengurai (parser) dalam tesis ini merupakan pengurai kalimat yang digunakan
dalam pemrosesan bahasa alami. Fungsi pengurai (parser) pada tesis ini adalah
sebagai pengurai kalimat untuk membuat pohon pola tata bahasanya dari teks
masukan yang berisi kumpulan kalimat (corpus) berbahasa Indonesia. Pengurai
(parser) pada tesis ini menggunakan aturan grammar untuk membangkitkan
pohon pola tata bahasa dari setiap kalimat, sedangkan proses penguraian (parsing)
II-6
merupakan proses yang mengubah kalimat menjadi model pola tata bahasa.
Pengurai (parser) yang baik harus memenuhi hal-hal berikut:
Dapat menangani ambiguitas dari parse-tree,
Dapat menangani kalimat yang keluar dari domain,
Menggunakan sumber daya (resources) seperti grammar, atau treebank,
Efisien, terutama pada kecepatan performansi,
Dapat ditelusuri hasilnya.
Pengurai (parser) memiliki beberapa jenis. Pengurai (parser) berdasarkan jenis
hasil parser-tree adalah phrase structure parser dan depedency structure parser.
Jenis pengurai (parser) jika dilihat dari penggunaan statistik atau tidak maka ada
statistical parser dan ruled-based parser.
Parse-tree merupakan struktur pohon yang dihasilkan oleh pengurai (parser).
Parser-tree dibagi menjadi dua buah jenis yaitu stuktur frase (phrase structure)
dan struktur kebergantungan (dependency structure). Parse-tree berbasis struktur
frase merupakan parse-tree yang dibangun dengan mempertimbangkan
keterkaitan kata satu dengan lainnya yang berdekatan (frase) sedangkan parse-tree
berbasis struktur kebergantungan merupakan parse-tree yang dibangun tanpa
mempertimbangakan posisi yang berdekatan dari tiap kata, tapi berdasarkan
kombinasi dua buah kata yang ada dalam kalimat.
Algoritma yang digunakan untuk proses penguraian (parsing algorithm) banyak
digunakan adalah sebagai berikut:
Algoritma top-down;
proses penguraian diawali dari akar pohon lalu diteruskan sampai ke daun,
kelemahan dari algoritma ini adalah kurang efisien untuk pembangkitan
pohon kalimat yang tidak sesuai dengan kalimat masukan (salah
membangkitkan ketika sampai pada level tertentu),
Algoritm bottom-up
proses penguraian diawali dari daun yaitu kata-kata dari kalimat kemudian
diproses sampai ke akar daun.
II-7
Algoritma kombinasi top-down dengan bottom-up;
karena masalah yang dihadapi adalah pembangkitan pohon yang kurang
efisien maka muncul algoritma kombinasi top-down dan bottom-up
dimana pohon dibangkitkan dari akar pohon, tapi dengan melihat kata-kata
(simpul daun) dari kalimat masukan (untuk filter).
Dari ketiga jenis algoritma di atas, masih ditemukan masalah yang timbul yaitu
adanya aturan produksi yang bersifat rekursif, ambiguitas, pengulangan proses
penguraian untuk sub pohon. Untuk mengatasi permasalahan yang timbul
digunakan dynamic programming. Dynamic programming membagi-bagi masalah
menjadi permasalahan yang lebih kecil untuk diselesaikan. Algoritma yang
menggunakan dynamic programming untuk proses penguraian menggunakan
CFG adalah sebagai berikut:
Algoritma Early;
menggunakan pencarian secara top-down, melakukan penelusuran dari
kanan ke kiri untuk menentukan pohon parsial,
Algoritma Cocke-Younger-Kasami (CYK);
algoritma CYK merupakan algoritma parsing yang masuk pada jenis
parsing bottom-up, algoritma CYK mengisi array probabilitas dengan
proses induksi,
Algortima Graham-Harrizon-Ruzzo (GHR);
menggunakan struktur data yang mirip dengan algoritma CYK, tapi
dengan komputasi mirip dengan algoritma Early
Salah satu penelitian mengenai pengurai dilakukan oleh Eugene Charniak.
Pengurai (parser) yang dibangun oleh Charniak (1997) [7] adalah pengurai
(parser) untuk bahasa Inggris dan menggunakan treebank (kumpulan pohon pola
tata bahasa) untuk membangun sistem pengurai (parser). Penelitian Charniak ini
sering disebut dengan parser (pengurai) menggunakan PCFG yang bersifat
leksikal (dari kamus). Algoritma yang digunakan digolongkan dengan algoritma
chart parser (pengurai) dimana setiap elemen kalimat dipilih berdasarkan chart
untuk menjadi simpul pohon. Parser (pengurai) pada penelitian ini termasuk pada
II-8
parser (pengurai) bottom-up. Setiap kata pada kalimat akan dianggap sebagai
daun pohon, dari setiap daun pohon itu akan disimpulkan apa jenis simpul orang
tuanya, demikian terus keatas sampai ditemukan kepala kalimat. Perhitungan
probabilitas setiap kata berdasarkan distribusi kata itu jika digunakan bersama
kata lain setelahnya di dalam kalimat. Dari segi performansi, parser (pengurai)
dalam penelitian ini lumayan baik.
Berikutnya Charniak melakukan penelitian mengenai parser (pengurai) dengan
Menggunakan Entropi Maksimum (2000) [8]. Ide yang digunakan pada penelitian
ini mirip dengan penggunaan algoritma pohon pengambilan keputusan (decision
tree). Algoritma parser (pengurai) yang digunakan adalah jenis top-down dimana
pada setiap simpul yang dibangkitkan dari atas ke bawah dihitung entropi
kemungkinan setiap jabatan kata dalam kalimat untuk dipilih menjadi simpul
pohon. Dari hasil kesimpulan keakurasian penelitian ini masih sekitar delapan
puluhan persen sehingga masih dibutuhkan perbaikan lebih lanjut.
Penelitian mengenai parser juga dilakukan oleh Michael Collins (1996) [11].
Penelitian ini mengenai parser (pengurai) berbasis statistik pada ketergantungan
bigram leksikal. Penelitian ini mendeskripsikan sebuah parser (pengurai) berbasis
statistik. Perhitungan probabilitas pada bigram merupakan probabilitas dari dua
buah kata yang memiliki ketergantungan dari dua buah kata. Perhitungan bigram
pada penelitian ini dihitung berdasarkan tag (jenis kata) antara dua buah kata yang
saling memiliki ketergantungan (berdekatan). Hasil perhitungan bigram akan
digunakan untuk menghitung probabilitas pohon yang dibangkitkan. Dari segi
performansi penelitian ini dianggap cukup baik karena dari eksperimen
pemrosesan 40.000 kalimat hanya memakan waktu lima belas menit. Akurasi
hasil yang dihasilkan berkisar antara delapan puluh hingga sembilan puluh persen.
Berikutnya Collins juga melakukan penelitian mengenai penguraian (parsing)
bahasa alami dengan model statistik berbasis head-driven (1999) [12]. Collins
membangun sistem penguraian (parsing) dengan membangkitkan simpul setiap
pohon menggunakan probabilitas grammar. Setiap membangkitkan simpul yang
II-9
baru maka metode head-finder akan dijalankan untuk menentukan simpul yang
baru. Metode yang digunakan adalah melakukan penelusuran untuk setiap simpul
yang akan dibangkitkan. Algoritma penguraian (parsing) yang digunakan adalah
algoritma chart. Hasil dari tesis ini dievaluasi per bagian kerja sistem, beberapa
bagian memiliki akurasi sekitar sembilan puluhan persen, tapi di lain bagian ada
yang memiliki akurasi sekitar tujuh puluhan persen. Tesis ini nantinya akan
mengambil modul-modul pada pengurai Collins dengan beberapa perubahan agar
dapat digunakan untuk bahasa Indonesia. Pengurai Collins merupakan pengurai
dengan metode statistik yang memiliki kecepatan pemrosesan yang baik dan
memiliki akurasi yang lebih baik dibandingkan pengurai dengan metode statistik
yang lainnya.
Penelitian mengenai model penguraian (parsing) menggunakan metode statistik
dengan menggunakan ruang parameter dari leksikal generatif dilakukan oleh
Daniel M. Bikel (2004) [4]. Pada penelitian ini, probabilitas yang dihitung dari
setiap kata berupa bigram, tapi menggunakan parameter-parameter tertentu yang
merupakan ekstraksi makna dan jenis kata dalam kamus dari setiap kata.
Penelitian ini merupakan pengurai (parser) untuk bahasa Inggris dan Cina. Untuk
bahasa Inggris, penelitian ini menggunakan Penn treebank untuk membangkitkan
aturan sedangkan untuk bahasa Cina menggunakan aturan-aturan yang telah
didefinisikan pada penelitian Bikel sebelumnya dengan Chiang pada tahun 2000.
Penelitian ini lebih mengarah pada pembuatan sebuah kerangka kerja (framework)
untuk mesin pengurai (parser). Hasil sistem dari penelitian ini dianggap cukup
kompleks. Beberapa parameter yang diujicobakan memberikan akurasi yang baik,
tapi beberapa parameter juga memberikan akurasi yang rendah, dari sini dapat
diambil parameter mana yang berperan baik dalam sebuah pengurai (parser).
Collins parser juga pernah digunakan untuk bahasa czech dalam penelitian yang
dilakukan oleh Michael Collins, Jan Hajic, Lance Ramshaw dan Christoph
Tillmann dengan melakukan adaptasi dengan bahasa czech dari bahasa inggris
[13]. Penelitian tersebut menggunakan Prague treebank yang merupakan treebank
berbahasa Czech. Penelitian tersebut menggunakan pengurai Collins hanya
II-10
sebatas pada model 1. Penelitian tersebut sebenarnya bertujuan sama dengan
penelitian pada tesis ini, hanya saja pada tesis ini untuk bahasa Indonesia. Oleh
karena itu perlu dilakukan adaptasi dengan bahasa Indonesia dari bahasa Inggris.
Permasalahan yang paling sering adalah bagaimana menghitung probabilitas
aturan produksi agar menghasilkan nilai akurasi yang tinggi. Secara sederhana,
probabilitas dari sebuah aturan produksi α → β dapat didefinisikan sebagai
berikut:
P( β| α) = )(
)(
jumlah
jumlah (II-7)
dimana jumlah aturan dihitung dari model tata bahasa yang dibangkitkan dari
treebank. Sebuah PCFG dapat diberi sifat leksikal dengan mengasosiasikan kata
(w) dengan sebuah part-of-speech (POS) tag t dengan setiap simbol non terminal
α di sebuah pohon. Pada Collins parser sebuah simpul pohon ditulis dengan pola
X(x) dimana x = (w, t). Misal untuk kalimat “Last week IBM bought Lotus” maka
pohonnya dapat dilihat pada Gambar II-1.
Gambar II-1 Contoh Pohon pada Collins parser
TOP
S (bought, VBD)
NP (week, NN) NP (IBM, NNP) VP (bought, VBD)
JJ (Last, JJ) NN (week, NN) NNP (IBM, NNP)
IBM Last week
VBD(bought, VBD)
bought
NP (Lotus, NNP)
NNP (Lotus, NNP)
Lotus
II-11
Maka secara sederhana perhitungan probabilitas untuk S(bought, VBD) →
NP(week, NN) NP(IBM, NNP) VP(bought, VBD) adalah
P(NP(week, NN) NP(IBM, NNP) VP(bought, VBD) | S(bought, VBD)) =
jumlah S(bought, VBD) → NP(week, NN) NP(IBM, NNP) VP(bought, VBD) jumlah S(bought, VBD) (II-8)
Namun hasil perhitungan probabilitas di atas akan menyebabkan statistik bersifat
jarang; karena yang menjadi pembilang dapat bernilai sangat kecil atau bahkan
nol dan penyebutnya bisa jadi bernilai rendah. Oleh karena itu Collins
memaparkan tiga buah model perhitungan probabilitas aturan produksi yang telah
diperkenalkan sebelumnya oleh beberapa peneliti dan melakukan beberapa
perbaikan terhadap model yang ada [12]. Pengurai Collin mengakomodasi semua
model pada aplikasi yang dibuatnya sebagai perbandingan antar model dengan
variasi kumpulan dokumen (corpus) yang digunakan.
II.2.1 Perhitungan Probabilitas Aturan Produksi
Pada disertasi Michael Collins (1999) [12] membahas tiga buah model
probabilistik untuk penguraian (parsing) yang telah diperkenalkan sebelum
Collins melakukan disertasi. Pada disertasinya, Collins melakukan beberapa
perbaikan pada ketiga model yang sudah ada itu. Collins mengimplementasikan
semua model sebagai perbandingan. Dari hasil penelitian yang dilakukan Collins,
model 2 dan model 3 masih menghasilkan beberapa kalimat yang gagal diuraikan.
Hal tersebut kemungkinan karena kurangnya kalimat pada treebank yang
menggunakan tag khusus untuk model 2 dan 3. Dalam tesis ini hanya
mengimplementasikan model 1 dari pengurai Collins karena keterbatasan
treebank.
II-12
II.2.1.1 Model 1
Model 1 membagi pembuatan aturan produksi sisi kanan menjadi urutan langkah
yang sederhana. Pada PCFG yang memiliki pola standar maka aturan produksinya
memiliki pola sebagai berikut:
P(h) → Ln(ln)...L1(l1)H(h)R1(r1)...Rm(rm) (II-9)
H adalah kepala (head-child) dari anak aturan P (aturan produksi sisi kanan).
Ln(ln)...L1(l1) dan R1(r1)...Rm(rm) adalah sisi kiri dan kanan dari H. Simbol n dan m
dapat bernilai nol, dan n = m = 0 untuk aturan yang bersifat tunggal (hanya
memiliki kepala H). Pada model ini ditambahkan simbol terminasi yaitu STOP
dimana Ln+1 = Rm+1 = STOP. Sebagai contoh adalah aturan S(bought, VBD) ->
NP(week, NN) NP(IBM, NNP) VP(bought, VBD) maka:
n = 2 m = 0 P = S
H = VP L1 = NP L2 = NP
L3 = STOP R1 = STOP h = (bought, VBD)
l1 = (IBM, NNP) l2 = (week, NN)
Simbol STOP ini hanya akan masuk pada file events sebagai penanda bahwa
sebuah kalimat atau bagian kalimat telah diuraikan dengan benar, tapi tidak
dimasukkan sebagai model pola tata bahasa (grammar).
Pembangkitan aturan sisi kanan (child) dari aturan sisi kiri (parent) yang
diberikan dibagi menjadi tiga langkah berikut:
1. Membuat pilihan label kepala frase dengan probabilitas
Ph(H|P, h), (II-10)
2. Membuat sisi kiri kepala dengan probabilitas
1...1 ni
Pl(Li(li)| P, h, H) (II-11)
II-13
dimana Ln+1(ln+1) = STOP, model akan berhenti membangkitkan sisi kiri
ketika simbol STOP dibangkitkan,
3. Membuat sisi kanan kepala dengan probabilitas
1...1 ni
Pr(Ri(ri)| P, h, H) (II-12)
dimana Rm+1(rm+1) = STOP.
Sebagai contoh untuk aturan S(bought, VBD) → NP(week, NN) NP(IBM, NNP)
VP(bought, VBD) maka probabilitasnya adalah:
Ph(VP | S, bought) × Pl(NP(IBM) | S, VP, bought) × Pl(NP(week) | S, VP, bought)
× Pl(STOP | S, VP, bought) × Pr(STOP | S, V, bought) (II-13)
Collins memberikan tambahan parameter jarak pada model 1 yang secara opsional
dapat digunakan atau tidak. Jarak ditambahkan agar tidak terjadi dominasi oleh
bagian aturan (kepala, bagian kiri, atau bagian kanan). Jarak digunakan untuk
memperhatikan tata letak simbol terminal atau non-terminal pada aturan sisi
kanan. Jarak dapat dilihat pada Gambar II-2.
Gambar II-2 Parameter Jarak
P(h)
H(h) R1(r1) R2(r2) R3(r3)
h jarak
II-14
Parameter jarak dapat dimasukkan pada model dengan memodifikasi asumsi
saling lepas sehingga setiap sisi memiliki keterkaitan yang terbatas. Maka
persamaannya akan menjadi sebagai berikut:
Pl(Li(li) | H, P, h, Li(li)...Li-1(li-1)) = Pl(Li(li) | H, P, h, distancel(i-1)) (II-14)
dan
Pr(Ri(ri) | H, P, h, Ri(ri)...Ri-1(ri-1)) = Pr(Ri(ri) | H, P, h, distancer(i-1)) (II-15)
Perkiraan jarak adalah sebuah vektor yang memiliki dua elemen yaitu:
1. Banyaknya string yang digunakan (posisi string),
2. Ada atau tidaknya kata kerja yang digunakan untuk pembelajaran memilih
kata kerja yang paling banyak digunakan [12].
II.2.1.2 Model 2
Adanya pembedaan pelengkap/keterangan dan pengkategorian sub kalimat yang
menjadi pelengkap/keterangan sangat diperlukan. Namun pembedaan ini tidak
ditampilkan secara eksplisit pada pohon, hanya digunakan pada mesin pengurai
(parsing). Model ini mengakomodasi aturan-aturan pembedaan
pelengkap/keterangan pada kaidah tata bahasa yang digunakan. Untuk bahasa
Indonesia pelengkap dan keterangan bisa menjadi sebuah sub kalimat. Untuk
membedakan sub kalimat pelengkap/keterangan maka perlu adanya pembedaan
simbol non terminal untuk merepresentasikan sub kalimat dan komponen-
komponen di dalamnya. Pada pengurai Collins sebuah sub kalimat disimbolkan
dengan SBAR dan komponen-komponen di dalamnya diberi tambahan –C pada
simbol non terminalnya (hanya untuk keperluan history/events dan pemrosesan),
misalnya NP maka akan menjadi NP-C. Penambahan penanda ini dimaksudkan
agar sebuah simbol non terminal yang sudah ada di sisi kiri aturan tidak boleh
muncul lagi di sisi kanan aturan, misal S → S CC S maka kedua S tidak dapat
II-15
dianggap sebagai pelengkap/keterangan/sub kalimat dan dapat menyebabkan
perulangan tanpa henti.
Probabilitas dari model 1 dapat diubah sebagai berikut pada model 2:
1. Pilih kepala H dengan probabilitas Ph(H | P, h),
2. Pilih lingkup kategori kiri (LC) dan lingkup kategori kanan (RC) dengan
probabilitas Plc(LC | P, H, h) dan Prc(RC | P, H, h). Setiap sub kategori
adalah kumpulan aturan yang mungkin memiliki simbol non terminal yang
sama dan mespesifikasikan pelengkap.
3. Buat sisi kiri dan kanan dengan probabilitas Pi(Li(li) | H, P, h, jarak(i-1),
LC) dan Pi(Ri(ri) | H, P, h, jarak(i-1), RC).
Aturan yang ada di dalam kumpulan aturan pada langkah 2 akan dihapus begitu
diidentifikasi dan dijadikan aturan kategori pelengkap. Sebagai contoh
probabilitas dari aturan S(bought, VBD) → NP(week, NN) NP(IBM, NNP)
VP(bought, VBD) akan menjadi:
Ph(VP | S, bought) × Plc(NP-C(IBM) | S, VP, bought) × Prc({}|S, VP, bought) ×
Pl(NP-C(IBM) | S, VP, bought, {NP-C}) × Pl(NP(week) | S, VP, bought, {}) ×
Pl(STOP | S, VP, bought, {}) × Pr(STOP | S, V, bought, {}) (II-16)
Kepala akan diputuskan dari NP-C (subyek) tunggal pada bagian kiri dan tidak
ada pelengkap/keterangan pada bagian kanan. NP-C(IBM) dibangkitkan sebagai
subyek dan NP-C dihapus dari LC, kemudian NP(week) dibangkitkan.
II.2.1.3 Model 3
Model ini menghitung probabilitas dengan mempertimbangkan adanya lebih dari
satu sub kalimat dalam sebuah kalimat. Dalam bahasa Indonesia, pengkategorian
sub kalimat juga perlu dilakukan pada kalimat majemuk yang dipisahkan oleh
kata penghubung atau tanda koma. Permasalahan yang timbul adalah tidak semua
tanda koma memisahkan sub kalimat dan tidak semua kata hubung memisahkan
II-16
dua buah kalimat. Oleh karena itu, jika yang dipisahkan oleh koma atau kata
hubung hanya terdiri dari satu kata maka tidak dianggap sebagai sebuah sub
kalimat pada bagian yang memiliki satu kata.
Kalimat yang di dalamnya terdapat sekurang-kurangnya dua kalimat dasar dan
masing-masing dapat berdiri sebagai kalimat tunggal disebut kalimat majemuk
setara (koordinatif). Kalimat yang terdiri atas dua kalimat dasar dimana jika
kalimat dasar pertama ditiadakan, maka kalimat yang kedua masih bisa berdiri
sendiri sebagai kalimat mandiri. Demikian pula sebaliknya. Keduanya mempunyai
kedudukan yang sama. Itulah sebabnya kalimat itu disebut kalimat majemuk
setara [24]. Kalimat yang mengandung satu kalimat dasar yang merupakan inti
(utama) dan satu atau beberapa kalimat dasar yang berfungsi sebagai pengisi salah
satu unsur kalimat inti itu misalnya keterangan, subyek, atau obyek dapat disebut
sebagai kalimat majemuk bertingkat jika diantara kedua unsur itu digunakan
konjungtor. Konjungtor inilah yang membedakan kalimat majemuk bertingkat
dari kalimat majemuk setara. Kalimat majemuk bertingkat juga dapat berupa
kalimat tunggal yang mengalami perluasan sekurang-kurangnya pada salah satu
unsurnya misalnya pada unsur keterangan, subyek atau obyek. Elemen yang
berperan memperluas salah satu unsur kalimat ini merupakan anak kalimat dan
diawali oleh konjungtor yang atau kata penunjuk itu [24].
Model ini juga dapat digunakan untuk penanganan wh-movement dimana sebuah
kalimat dipisahkan oleh kata tanya, misal dalam bahasa Inggris sebagai berikut:
They didn't know which model that we had discussed
atau misal dalam bahasa Indonesia sebagai berikut:
Mereka tidak tahu model mana yang sedang kita diskusikan.
Model ini juga digunakan untuk menangani kalimat tanya sebagai salah satu
bagian dari wh-movement misal,
What does she believe?
maka kalimat di atas memiliki inti she believe dengan penambahan kata tanya
what.
II-17
Pengurai Collins menambahkan sebuah simbol TRACE yang merupakan tanda
berhenti melakukan pembagian sub pohon. Sebuah SBAR akan diberi penanda
+gap untuk menandakan orang tua dari TRACE (hanya akan disimpan sebagai
history agar kalimat diuraikan dengan benar). Misal untuk contoh kalimat “The
Store that IBM bought last week” maka pohon pola tata bahasanya akan mejadi
seperti pada Gambar II-3.
Gambar II-3 Pohon Model 3
Probabilitas untuk aturan VP(bought)(+gap) → VB(bought) TRACE NP(week)
adalah:
Ph(VB | VP, bought) × Pg(Right | VP, bought, VB) × Plc({}|VP, bought, VB) ×
Prc({NP-C}|VP, bought, VB) × Pr(TRACE | VP, bought, VB, {NP-C, +gap}) ×
Pr(NP(week) | VP, bought, VB, {}) × Pl(STOP | VP, bought, VB, {}) × Pr(STOP |
VP, bought, VB, {}) (II-17)
NP(Store)
NP(Store) SBAR(that)(+gap)
The store WHNP(that) S(bought)(+gap)
NP-C(IBM) VP(bought)(+gap)
TRACEVBD NP(week)
WDT
that
IBM
bought last week
II-18
II.2.2 Perhitungan Probabilitas Setiap Pohon
Sebuah kalimat sangat dimungkinkan memiliki model pola tata bahasa lebih dari
satu dan hal ini menyebabkan terjadinya ambigu. Oleh karena itu setiap model
pohon pola tata bahasa harus dihitung probabilitasnya untuk memilih pohon mana
yang terbaik. Sama dengan hasil penelitian yang dilakukan Daniel Jurafsky dan
James H. Martin, pada pengurai Collins pohon yang terbaik diambil dari
perhitungan berikut:
T (S) = argmax )(ST P(T) (II-18)
dimana
P(T) = P(T)P(S|T) = P(T, S) (II-19)
dan
P(T, S) = Tn
p(r(n)) (II-20)
p(r(n)) adalah nilai probabilitas yang didapatkan dari model probabilitas pengurai
Collins [12].
II.3 Penelitian Mengenai Pembangkitan Pola Tata Bahasa dengan
Pendekatan Probabilistik (Probabilistic Parsing)
Penelitian mengenai teknik pembangkitan pola tata bahasa untuk ekstraksi relasi
pada bahasa Malaysia dilakukan oleh Mohd Juzaiddin Ab Aziz dkk (2006) [3].
Penelitian ini membahas mengenai pembangkitan pola tata bahasa melayu
Malaysia dari kalimat masukan berbahasa melayu Malaysia. Pada awalnya pola
tata bahasa didefinisikan dengan menggunakan aturan produksi CFG (Context-
Free Grammar). Pohon pola tata bahasa dibangkitkan dari kalimat masukan
berdasarkan aturan produksi CFG yang telah didefinisikan sebelumnya.
II-19
Permasalahan yang timbul adalah ambiguitas pohon yang dibangkitkan karena
pada penelitian ini tidak melibatkan komponen probabilitas. Keakurasian dalam
penelitian ini mencapai sekitar delapan puluhan persen. Jabatan kata bahasa
melayu Malaysia memiliki perbedaan dengan bahasa Indonesia. Beberapa arti
kata dalam bahasa melayu Malaysia juga berbeda dengan bahasa Indonesia
sehingga jabatan kata dalam kalimat pun menjadi berbeda. Oleh karena itu bahasa
melayu Malaysia tidak sama dengan bahasa Indonesia walaupun dikatakan
sebagai bahasa yang serumpun.
Penguraian (parsing) probabilistik adalah penguraian elemen pada pemrosesan
bahasa alami dengan menggunakan pendekatan probabilistik. Penelitian mengenai
penguraian (parsing) probabilistik dilakukan oleh Daniel Jurafsky dan James H.
Martin (2000) [17]. Penelitian ini juga menggunakan PCFG. Aturan produksi
PCFG didefinisikan terlebih dahulu. Setiap kalimat yang masuk ke sistem akan
dihitung probabilitas katanya berdasarkan distribusi kata. Nilai probabilitas ini
nanti digunakan untuk menghitung probabilitas pohon yang dibangkitkan
sehingga dapat dipilih pohon yang terbaik. Penelitian ini menggunakan algoritma
CYK (Cocke, Younger, Kasami). Algoritma CYK merupakan algoitma yang
efisien ketika digunakan untuk memproses struktur leksikal bahasa. Algoritma
CYK merupakan algoritma parsing yang masuk pada jenis parsing bottom-up.
Hasil penelitian ini cukup baik dan masih memerlukan perbaikan di masa
mendatang untuk mengurangi kesalahan yang ditimbulkan misal jika pemilihan
pohon dengan probabilitas menghasilkan nilai probabilitas yang sama untuk dua
atau lebih pohon, harus didefinisikan justifikasi lebih lanjut.
Penelitian yang dilakukan Ramon Lefuel dan Brian J. Ross (2004)
menggabungkan penguraian (parsing) probabilistik dengan algoritma genetik
[18]. Algoritma genetik digunakan untuk membangkitkan pohon pola tata bahasa
dari kalimat masukan. Model yang digunakan pada penelitian ini adalah PCFG.
Kromoson dalam penelitian ini merepresentasikan parse-tree. Fungsi fitness yang
digunakan adalah perhitungan probabilitas setiap parse-tree. Penelitian ini
membuktikan bahwa algoritma genetik juga dapat digunakan untuk melakukan
II-20
penguraian (parsing) probabilistik pada kalimat walaupun dari segi performansi
dianggap masih kurang efisien.
Penelitian yang sama dengan tesis ini juga pernah dilakukan oleh Ria Hari
Gusmita dan Ruli Manurung (2008) [14]. Penelitian tersebut menggunakan
perangkat PC-PATR. Penelitian tersebut juga melakukan adaptasi terhadap file
masukan perangkat PC-PATR agar dapat digunakan untuk bahasa Indonesia. PC-
PATR adalah perangkat membangkitkan pohon pola tata bahasa berdasarkan
aturan-aturan yang didefinisikan (rule based). PC-PATR dibuat untuk bahasa
Inggris. Kalimat berbahasa Indonesia yang berhasil diuraikan dari penelitian ini
adalah sekitar 58%.
II.4 Rangkuman Tinjauan Pustaka
Berbagai penelitian mengenai pemodelan pohon pola tata bahasa, parser
(pengurai), dan parsing probabilistik telah banyak dilakukan. Dalam bab ini
penulis hanya membahas penelitian-penelitian yang sekiranya dapat menjadi
acuan dalam tesis ini. Penelitian yang dibahas mengenai model pola tata bahasa
diawali dengan penelitian dari Yves Schabes dan Richard C. Waters (1993) [23].
Penelitian tersebut membahas Stochastic Lexicalized Contex-Free Grammar
(SLCFG) yang juga dikenal dengan Probabilistic Lexicalized Context-Free
Grammar (PLCFG). PLCFG merupakan model turunan PCFG. Glen Carrol
(1995) [10] melakukan penelitian mengenai pembelajaran tata bahasa
probabilistik untuk pemodelan bahasa dimana digunakan treebank untuk
membangkitkan aturan dan akan ditambah dengan aturan-aturan baru hasil dari
pembelajaran yang dilakukannya. Mark Johnson (1998) [16] mencoba membuat
model pola tata bahasa dengan menggunakan PCFG dan melakukan evaluasi
dengan model-model pohon pola tata bahasa yang telah ada saat itu.
Penelitian mengenai pengurai (parser) yang dibahas pada tesis ini dimulai dengan
penelitian yang dilakukan Eugene Charniak (1997) [7] yang membangkitkan pola
tata bahasa dengan model PCFG dan kamus leksikal. Charniak juga melakukan
penelitian mengenai sistem pengurai (parser) yang menggunakan perhitungan
II-21
entropi (2000) [8]. Penelitian selanjutnya yang dibahas adalah penelitian dari
Michael Collins (1996) [11] yang membuat sistem pengurai (parser) berbasis
statistik dengan menghitung ketergantungan kata menggunakan metode bigram.
Collins (1999) [12] juga melakukan penelitian membuat sebuah pengurai (parser)
berbasis head-driven. Daniel M. Bikel (2004) [4] melakukan penelitian mengenai
sebuah kerangka kerja pengurai (parser framework) yang menggunakan
parameter-parameter leksikal. Michael Collins juga melakukan penelitian
menggunakan pengurai hasil disertasinya [12] untuk bahasa Czech [13]. Tesis ini
juga melakukan adaptasi bahasa Indonesia untuk pengurai Collins seperti halnya
pengurai Collins untuk bahasa Czech.
Penelitian mengenai pembangkitan pola tata bahasa yang dibahas pada tesis ini
dimulai dengan penelitian mengenai pembangkitan pola tata bahasa yang
dilakukan oleh Ab Aziz dan kawan-kawan (2006) [3] untuk bahasa Malaysia.
Penelitian mengenai pembangkitan pola tata bahasa dengan pendekatan
probabilistik dilakukan oleh Daniel Jurafsky dan James H. Martin (2000) [17]
dimana penguraian (parsing) probabilistik digunakan untuk menangani
ambiguitas pohon-pohon yang dibangkitkan. Penelitian tersebut menggunakan
tata bahasa Inggris. Penelitian mengenai parsing probabilistik juga dilakukan oleh
Ramon Lefuel dan Brian J. Ross (2004) [18]. Penelitian tersebut menggunakan
algoritma genetik untuk penguraian (parsing) probabilistik pada kalimat.
Penelitian mengenai pengurai menggunakan metode statistik juga pernah
dilakukan oleh Ria Hari Gusmita dan Ruli Manurung (2008) [14]. Penelitian ini
menggunakan perangkat PC-PATR dengan mengadaptasi kumpulan file
masukannya. Kalimat berbahasa Indonesia yang berhasil diuraikan dari penelitian
ini adalah sekitar 58%.