BAB 5 HASIL DAN PEMBAHASAN

32

BAB 5 HASIL DAN PEMBAHASAN

Dalam bagian hasil dan pembahasan ini akan ditampilkan proses analisis dan pengolahan data, dalam bentuk deskriptif, tabel-tabel yang digunakan, gambar-gambar beserta hasil dan pembahasannya. Dengan memperhatikan segi efisiensi dalam penelitian ini, maka tidak semua hasil proses penelitian data yang diolah akan ditampilkan tetapi hanya sebagian saja yang dianggap oleh peneliti dapat mewakili keseluruhan proses yang dilakukan. Proses pengolahan yang tidak diuraikan dalam proses dan pembahasan ini akan ditampilkan hasil akhir pengolahannya saja.

5.1

Analisis EM Algorithm untuk mixnormal Selain digunakan untuk menentukan parameter dari suatu data di mana informasi yang diperoleh tidak lengkap, EM algorithm juga dapat digunakan untuk kasus di mana terdapat gabungan antara dua fungsi persamaan atau lebih. Pada bagian ini akan dibahas salah satu penggunaan EM algorithm dalam menentukan parameter bagi data yang menyebar berdasarkan fungsi persamaan gabungan dari dua fungsi normal. Pembahasan akan diberikan secara teoritis disertai dengan contoh, serta statement dalam R Language. (Introduction to Mathematical Statistics). Penulis mengambil contoh persamaan gabungan yang terdiri dari persamaan distribusi normal. Y1 menyebar secara normal dengan distribusi

N ( μ1 , σ 1 ) dan Y2 menyebar secara normal dengan distribusi N ( μ 2 , σ 2 ) . W 2

2

33 merupakan variabel acak independen Bernoulli untuk Y1 dan Y2 , dengan peluang sukses π = P(W = 1) . Variabel acak yang diamati adalah X = (1 − W )Y1 + WY2 . Parameternya antara lain θ ′ = ( μ1 , μ 2 , σ 1 , σ 2 , π ) .

Pdf dari variable acak

gabungan X adalah : f ( x) = (1 − π ) f 1 ( x) + πf 2 ( x),

− ∞ < x < ∞,

(4.1)

−1

di mana f j ( x) = σ j φ (( x − μ j ) / σ j )), j = 1,2 dan φ (z ) adalah pdf dari variabel

acak standar normal. Sampel acak X ′ = ( X 1 , X 2 ,..., X n ) dari distribusi gabungan dengan pdf f (x) . Maka fungsi log likelihood dari fungsi tersebut adalah : n

l (θ | x) = ∑ log[(1 − π ) f 1 ( xi ) + πf 2 ( xi )]

(4.2)

i =1

Pada kasus ini, data yang tidak diamati adalah variabel acak yang mengidentifikasikan

anggota

dari

distribusi.

Untuk

i

=

1,2,...,n,

mengidentifikasikan variabel acak Wi = 0 jika xi memiliki pdf f1 ( x) 1 jika xi memiliki pdf f 2 ( x)

(4.3)

Variabel-variabel ini merupakan sampel acak dari variabel acak Bernoulli W. Dengan mengasumsikan W1 ,W2 ,...,Wn adalah variabel acak Bernoulli dengan peluang sukses π . Fungsi lengkap likelihoodnya adalah : Lc (θ | x, w) = ∏ f1 ( xi )∏ f 2 ( xi ) wi = 0

Wi =1

maka fungsi log likelihood lengkapnya adalah : l c (θ | x, w) =

∑ log f ( x ) + ∑ log f

Wi = 0

1

i

Wi =1

2

( xi )

(4.4)

34 n

= ∑ [(1 − wi ) log f 1 ( xi ) + wi log f 2 ( xi )]

(4.5)

i =1

Untuk E-step dari EM algorithm, kondisi harapan dari Wi yang diberikan x berdasarkan θ 0 perlu ditentukan, yaitu :

Eθ 0 [Wi | θ 0 , x] = P[Wi = 1 | θ 0 , x ]

(4.6)

Pendugaan dari E-step merupakan likelihood dari xi yang digambarkan dari sebaran :

γi =

πˆf 2,0 ( xi ) (1 − πˆ ) f1,0 ( xi ) + πˆf 2,0 ( xi )

(4.7)

di mana subscript 0 menandakan bahwa parameter-paramater pada θ 0 juga dipakai. Dengan mengganti wi dengan γ i pada perhitungan (4.5), maka langkah maximization (M-step) dari EM algorithm adalah untuk memaksimumkan n

Q(θ | θ 0 , x) = ∑ [(1 − γ i ) log f1 ( xi ) + γ i log f 2 ( xi )]

(4.8)

i =1

Nilai maksimum dapat diperoleh dengan menghitung turunan dari Q(θ | θ 0 , x ) berdasarkan parameternya. Contohnya : n ∂Q 2 = ∑ (1 − γ i )(−1 / 2σ 1 )(−2)( xi − μ1 ) = 0 ∂μ1 i =1

n ∂Q 2 = ∑ (1 − γ i )(−1 / 2σ 1 )(−2)( xi − μ1 ) = 0 ∂σ 1 i =1 n ∂Q 2 = ∑ (1 − γ i )(−1 / 2σ 1 )(−2)( xi − μ1 ) = 0 ∂μ 2 i =1 n ∂Q 2 = ∑ (1 − γ i )(−1 / 2σ 1 )(−2)( xi − μ1 ) = 0 ∂σ 2 i =1

(4.9)

35 Dengan menyatakan turunannya sama dengan nol (0) berarti mendapatkan hasil pendugaan nilai μ1 . Untuk parameter yang lainnya diperoleh dengan cara yang sama, hasil pendugaan untuk parameter adalah : n

μˆ 1 =

∑ (1 − γ )x i

i =1 n

i

∑ (1 − γ ) i

i =1

n

σˆ 1 2 =

∑ (1 − γ )(x i

i =1

i

2 − μˆ 1 )

n

∑ (1 − γ ) i

i =1

n

μˆ 2 =

∑γ i =1 n

i

∑γ i =1

xi i

n

σˆ 2 =

∑ γ (x i =1

i

i

γi

adalah

2

(4.10)

n

∑γ i =1

Karena

− μˆ 2 ) i

penduga

dari

P (Wi = 1 | θ 0 , x) ,

rata-rata

dari

n

n −1 ∑ γ i merupakan penduga dari π = P[Wi = 1] . Rata-rata ini merupakan i =1

penduga untuk πˆ . Sebagai contoh jika ada data yang diobservasi yang merupakan variabel acak X = (1 − W )Y1 + WY2 di mana W menyebar secara Bernoulli dengan peluang sukses 0.7. Y1 menyebar secara normal dengan fungsi N (100,20 2 ) dan Y2

36 menyebar secara normal dengan fungsi N (120,25 2 ) . W dan Y1 independent, W dan Y2 juga independent. Data yang dipakai : 119.0 96.0

146.2 138.6 143.4 98.2

114.1 136.2 136.4 184.8 79.8 145.7 95.9

97.3

124.5

151.9 114.2

136.4 109.2 103.2

Maka dengan bantuan R Language, dapat dibuat sebuah fungsi untuk menyelesaikan persoalan diatas. > + + + + + + + + + + + + +

mixnormal = function(x,theta0){ part1=(1-theta0[5])*dnorm(x,theta0[1],theta0[3]) part2=theta0[5]*dnorm(x,theta0[2],theta0[4]) gam=part2/(part1+part2) denom1=sum(1-gam) denom2=sum(gam) mu1=sum((1-gam)*x)/denom1 sig1=sqrt(sum((1-gam)*((x-mu1)^2))/denom1) mu2=sum(gam*x)/denom2 sig2=sqrt(sum(gam*((x-mu2)^2))/denom2) p=mean(gam) mixnormal = c(mu1,mu2,sig1,sig2,p) mixnormal }

Sintaks untuk memanggil fungsinya adalah: > mixnormal(c(119.0,96.0,146.2,138.6,143.4,98.2,124.5, + 114.1,136.2,136.4,184.8,79.8,151.9,114.2, + 145.7,95.9,97.3,136.4,109.2,103.2),c(100,120,20,25,0.7))

Hasil prediksi parameternya adalah baris pertama merupakan hasil pada proses pertama kali, sedangkan baris kedua adalah hasil setelah iterasi 500 kali. Tabel 4.1 Hasil Simulasi Perhitungan EM untuk mixnormal

μ1

σ1

μ2

σ2

π

106.94 98.76

128.81 133.96

17.59 9.88

24.37 21.51

0.75 0.70

37 5.2

Analisis EM Algorithm untuk Peluang Dua Mata Dadu

Pada bagian ini dijelaskan tentang pemakaian EM algorithm dibidang statistika, yaitu menduga peluang untuk setiap kejadian pada dua buah mata dadu. (http://[email protected]). Pada kasus ini merupakan salah satu contoh kasus data yang tidak lengkap. Data yang tidak lengkap ini akan dijelaskan pada sub bab yaitu proses penginputan dan analisis data. 5.2.1

Proses Penginputan dan Analisis Data

Percobaan yang dipilih oleh penulis adalah dua buah mata dadu yang dilempar, peneliti ingin mengetahui berapa peluang setiap kejadian pada masingmasing mata dadu, misalnya peluang untuk mata dadu pertama keluar angka 1, angka 2, dst. Jika data yang dimiliki lengkap, maka tidak diperlukan teori yang rumit untuk menentukan berapa peluang untuk setiap kejadian. Jika setiap kejadian bisa dilambangkan dengan pasangan angka yaitu ( x1 , x 2 ) , dengan x1 merupakan angka yang keluar pada dadu pertama dan x 2 merupakan angka yang keluar pada dadu kedua. Maka ada 36 kemungkinan yang bisa terjadi. Tabel 4.2 Kemungkinan Kejadian untuk Dua Mata Dadu ( x1 , x 2 ) x1 = 1 x1 = 2 x1 = 3 x1 = 4 x1 = 5 x1 = 6

x2 = 1

x2 = 2

x2 = 3

x2 = 4

x2 = 5

x2 = 6

(1,1) (2,1) (3,1) (4,1) (5,1) (6,1)

(1,2) (2,2) (3,2) (4,2) (5,2) (6,2)

(1,3) (2,3) (3,3) (4,3) (5,3) (6,3)

(1,4) (2,4) (3,4) (4,4) (5,4) (6,4)

(1,5) (2,5) (3,5) (4,5) (5,5) (6,5)

(1,6) (2,6) (3,6) (4,6) (5,6) (6,6)

38 Jika kedua dadu dilempar bersamaan sebanyak 10000 kali, maka dapat diperoleh tabel frekuensi seperti berikut : Tabel 4.3 Kemungkinan Jumlah Kejadian pada Simulasi Dua Mata Dadu f ( x1 , x 2 ) x1 = 1 x1 = 2 x1 = 3 x1 = 4 x1 = 5 x1 = 6

x2 = 1

x2 = 2

x2 = 3

x2 = 4

x2 = 5

x2 = 6

2436 4773 2520 2498 3233 3298

4773 3794 2497 2462 2269 3184

2520 2497 2969 2035 2883 3010

2498 2462 2035 1049 2487 2451

3233 2269 2883 2487 2276 2191

3298 3184 3010 2451 2191 3673

Data diatas merupakan sampel. Jika data yang diperoleh adalah data yang lengkap seperti tabel 4.3, maka peluang kejadian untuk setiap mata dadu dapat langsung dihitung. Tabel 4.4 Peluang untuk Setiap Kejadian dari Simulasi Dua Mata Dadu (i) ~ p ( x1 , x 2 ) x1 = 1 x1 = 2 x1 = 3 x1 = 4 x1 = 5 x1 = 6

x2 = 1

x2 = 2

x2 = 3

x2 = 4

x2 = 5

x2 = 6

0.02436 0.04773 0.02520 0.02498 0.03233 0.03298

0.04773 0.03794 0.02497 0.02462 0.02269 0.03184

0.02520 0.02497 0.01969 0.02035 0.02883 0.03010

0.02498 0.02462 0.02035 0.01049 0.02487 0.02451

0.03233 0.02269 0.02883 0.02487 0.02276 0.02191

0.03298 0.03184 0.03010 0.01451 0.02191 0.03673

Jika data yang diperoleh berbeda, akan tetapi tetap merupakan data yang lengkap. Sebagai contoh data yang diperoleh merupakan frekuensi untuk masingmasing mata dadu secara terpisah. Maka proses menghitung peluang untuk masing-masing mata dadu dapat dilakukan terlebih dahulu untuk menentukan peluang dari setiap kejadian yang memungkinkan.

39 Tabel 4.5 Frekuensi dan Peluang untuk Masing-masing Simulasi Mata Dadu f1 ( x1 ) 15112 14941 19756 10027 15037 25127

x1 1 2 3 4 5 6

~ p1 ( x1 ) 0.15112 0.14941 0.19756 0.10027 0.15037 0.25127

x1 1 2 3 4 5 6

f 2 ( x2 ) 25112 25067 10129 10052 14833 14807

x2 1 2 3 4 5 6

~ p2 ( x2 ) 0.25112 0.25067 0.10129 0.10052 0.14833 0.14807

x2 1 2 3 4 5 6

Maka peluang untuk setiap kejadian untuk kedua mata dadu, dengan asumsi kedua mata dadu independen adalah p ( x1 , x 2 ) = p ( x1 ). p ( x 2 )

(4.11)

Proses perhitungan akan menghasilkan : Tabel 4.6 Peluang untuk Setiap Kejadian Dari Simulasi Dua Mata Dadu (ii) ~ p ( x1 , x 2 ) x1 = 1 x1 = 2 x1 = 3 x1 = 4 x1 = 5 x1 = 6

x2 = 1

x2 = 2

x2 = 3

x2 = 4

x2 = 5

x2 = 6

0.037949 0.037519 0.049611 0.025179 0.037760 0.063098

0.037881 0.037452 0.049522 0.025134 0.037693 0.062985

0.015306 0.015133 0.020010 0.010156 0.015231 0.025451

0.015190 0.015018 0.019858 0.010079 0.015115 0.025257

0.022415 0.022162 0.029304 0.014873 0.022304 0.037270

0.022376 0.022123 0.029252 0.014847 0.022265 0.037205

40 Dapat dilihat bahwa tabel 4.4 dan tabel 4.6 sebenarnya mewakili pendugaan untuk parameter yang sama, akan tetapi terdapat sedikit perbedaan karena data yang diperoleh berbeda. Secara garis besar kedua tabel memberikan nilai yang relatif sama. Kasus yang terakhir menggunakan data tidak lengkap. Data yang diketahui adalah jumlah penambahan dari kedua angka pada mata dadu pertama dan kedua. Berarti y sebagai kejadian jumlah kedua mata dadu. Maka berdasarkan contoh sampel, y dapat dihitung dengan persamaan : f ( y) =

∑ f (x , x

x1 + x2 = y

1

2

(4.12)

)

Jumlah frekuensi dari masing-masing kejadian y adalah : Tabel 4.7 Frekuensi untuk Setiap Jumlah Simulasi Dua Mata Dadu

f ( y) 3790 7508 10217 10446 12003 17732 13923 8595 6237 5876 3673 Data

diatas

dihasilkan

y 2 3 4 5 6 7 8 9 10 11 12

berdasarkan

data

sebelumnya,

yaitu

menjumlahkan data yang ada pada tabel 4.3. Sebagai contoh : f (4) = f (1,3) + f (2,2) + f (3,1) = 1520 + 3794 + 4903 = 10217

dengan

41 Tipe data yang tidak lengkap adalah : Y = {2,3,4,5,6,7,8,9,10,11,12}

di mana himpunan tipe data yang lengkap adalah X, dengan y ∈ Y A( y ) = {( x1 , x 2 ) ∈ X | x1 + x 2 = y}

(4.13)

Berdasarkan definisi 4.11, maka dengan EM algorithm dicari nilai peluang p 0 ( x1 , x 2 ) untuk data

sebagai nilai awal. Yang berarti nilai awal peluang

lengkap yang dihasilkan secara acak dari peluang sebaran p 01 ( x1 ) sebagai angka yang muncul pada dadu pertama dan angka acak dari peluang sebaran p 02 ( x 2 ) sebagai angka yang muncul pada dadu kedua. p o ( x1 , x 2 ) = p01 ( x1 ). p 02 ( x 2 )

(4.14)

Tabel berikut memberikan nilai acak untuk kedua mata dadu yaitu p 01 ( x1 ) dan p 02 ( x 2 ) . Tabel 4.8 Peluang Acak untuk Masing-masing Simulasi Mata Dadu p 01 ( x1 ) 0.18 0.19 0.16 0.13 0.17 0.17

x1 1 2 3 4 5 6

p 02 ( x 2 ) 0.22 0.23 0.13 0.16 0.14 0.12

x2 1 2 3 4 5 6

Berdasarkan

angka acak yang telah dihasilkan pada tabel 4.8 maka dapat dihitung peluang untuk data yang lengkap, berdasarkan definisi 4.11.

42 Tabel 4.9 Peluang Acak untuk Setiap Kejadian dari Simulasi Dua Mata Dadu p 0 ( x1 , x 2 ) x1 x1 x1 x1 x1 x1

=1 =2 =3 =4 =5 =6

x2 = 1

x2 = 2

x2 = 3

x2 = 4

x2 = 5

x2 = 6

0.0396 0.0418 0.0352 0.0286 0.0374 0.0374

0.0414 0.0437 0.0368 0.0299 0.0391 0.0391

0.0234 0.0247 0.0208 0.0169 0.0221 0.0221

0.0288 0.0304 0.0256 0.0208 0.0272 0.0272

0.0252 0.0266 0.0224 0.0182 0.0238 0.0238

0.0216 0.0228 0.0192 0.0156 0.0204 0.0204

Contoh perhitungannya adalah : p 0 (1,3) = p 01 (1). p 02 (3) = 0.18 * 0.13 = 0.0234 p 0 (2,2) = p 01 (2). p 02 (2) = 0.19 * 0.23 = 0.0437 p 0 (3,1) = p 01 (3). p 02 (1) = 0.16 * 0.22 = 0.0352 Data pada tabel 4.9 dianggap sebagai data dugaan pertama untuk peluang dari setiap kejadian yang mungkin, yang akan dipakai pada proses E-step yang pertama kali. Bagian analisis data ini juga nantinya akan dijadikan sebagai pembanding hasil untuk pendugaan parameter menggunakan EM algorithm untuk data yang tidak lengkap dengan data yang lengkap.

5.2.2

Langkah Expectation (E-step) dari EM algorithm

Pada langkah E (E-step) ini akan dilakukan perhitungan berdasarkan data yang diperoleh sebelumnya. Pertama-tama perhitungan untuk menentukan nilai peluang setiap kejadian y yang merupakan data tidak lengkap berdasarkan data lengkap pada tabel 4.9 dilakukan. Rumusnya adalah : p0 ( y) =

∑p

x1 + x2 = y

0

( x1 , x 2 )

(4.15)

43 Berdasarkan definisi 4.15 maka akan dihasilkan peluang untuk setiap kejadian y : Tabel 4.10 Peluang Acak Untuk Jumlah Kedua Simulasi Mata Dadu

p0 ( y) 0.0396 0.0832 0.1023 0.1189 0.1437 0.1672 0.1272 0.0867 0.0666 0.0442 0.0204

y 2 3 4 5 6 7 8 9 10 11 12

Contoh perhitungannya : p 0 (4) = p 0 (1,3) + p 0 (2,2) + p 0 (3,1) = 0.0234 + 0.0437 + 0.0352 = 0.1023 Berdasarkan data yang diperoleh dari tabel 4.10 maka frekuensi dari setiap kemungkinan dari kedua mata dadu dihitung. Frekuensi dari setiap kemungkinan yang terjadi adalah : Tabel 4.11 Frekuensi Kejadian Pada Simulasi Dua Mata Dadu f q ( x1 , x 2 ) x1 x1 x1 x1 x1 x1

=1 =2 =3 =4 =5 =6

x2 = 1

x2 = 2

x2 = 3

x2 = 4

x2 = 5

x2 = 6

3790 3772.05 3515.53 2512.66 3123.95 3966.37

3735.95 4364.45 3233.08 2497.49 4146.66 4279.79

2337.03 2170.03 1737.39 1792.29 2419.01 2190.88

2530.23 2539.26 2714.95 2276.72 2696.47 2547.24

2104.91 2821 2451.85 1804.26 2228.84 3164

2290.74 2495.63 1903.39 1460.92 2712 3673

44 Contoh perhitungannya : f q (1,3) = f (4).

p 0 (1,3) 0.0234 = 10217. = 2337.03 p 0 ( 4) 0.1023

f q (2,2) = f (4).

p 0 (2,2) 0.0437 = 10217. = 4364.45 p 0 ( 4) 0.1023

f q (3,1) = f (4).

p 0 (3,1) 0.0352 = 10217. = 3515.53 p 0 ( 4) 0.1023

Hasil yang diperoleh pada tabel 4.11 akan digunakan dalam proses M-step nantinya. Hasil ini digunakan untuk memperoleh peluang untuk masing-masing simulasi mata dadu.

5.2.3

Langkah Maximization (M-step) dari EM Algorithm

Pada langkah maximization ini, akan dihitung berdasarkan MLE. Proses pertama adalah menghitung frekuensi untuk setiap mata dadu menghasilkan suatu angka, yaitu jumlah kejadian keluar pada mata dadu pertama : f q1 ( x1 ) = ∑ f q ( x1 , x 2 ) ,

(4.16)

x2

dan jumlah kejadian keluar pada mata dadu kedua : f q 2 ( x 2 ) = ∑ f q ( x1 , x 2 ) .

(4.17)

x1

Hasil perhitungan untuk frekuensi kedua buah mata dadu berdasarkan tabel 4.11 adalah :

45 Tabel 4.12 Frekuensi untuk Masing-masing Simulasi Mata Dadu f q1 ( x1 )

x1 1 2 3 4 5 6

16788.86 18162.42 15556.19 12344.34 17326.93 19821.28

f q 2 ( x2 ) 20680.56 22257.42 12646.63 15304.87 14574.86 14535.68

x2 1 2 3 4 5 6

Contoh perhitungannya : f q1 (1) = f q (1,1) + f q (1,2) + f q (1,3) + f q (1,4) + f q (1,5) + f q (1,6) = 3790 + 3735.95 + 2337.03 + 2530.23 + 2104.91 + 2290.74 = 16788.86

f q 2 (1) = f q (1,1) + f q (2,1) + f q (3,1) + f q (4,1) + f q (5,1) + f q (6,1) = 3790 + 3772.05 + 3515.53 + 2512.66 + 3123.95 + 3966.37 = 20680.56

Lalu dilakukan proses menghitung peluang untuk setiap kejadian pada masingmasing mata dadu. Jumlah pelemparan mata dadu dilakukan sebanyak 10000 kali maka peluang masing-masing mata dadu adalah :

Tabel 4.13 Peluang untuk Masing-masing Simulasi Mata Dadu p11 ( x1 ) 0.167889 0.181624 0.155561 0.123443 0.173269 0.198213

x1 1 2 3 4 5 6

p12 ( x 2 ) 0.206806 0.222574 0.126466 0.153049 0.145749 0.145357

x2 1 2 3 4 5 6

46 Contoh perhitungannya : p11 =

f11 ( x1 ) 16788.86 = = 0.16789 100000 100000

Proses selanjutnya adalah menghitung peluang dari setiap kejadian yang muncul dari kedua mata dadu, berdasarkan definisi 4.11. Tabel 4.14 Peluang untuk Setiap Kejadian Dari Simulasi Dua Mata Dadu (iii) p1 ( x1 , x 2 ) x1 = 1 x1 = 2 x1 = 3 x1 = 4 x1 = 5 x1 = 6

x2 = 1

x2 = 2

x2 = 3

x2 = 4

x2 = 5

x2 = 6

0.034720 0.037560 0.032171 0.025528 0.035833 0.040991

0.037367 0.040424 0.034624 0.027475 0.038565 0.044117

0.021232 0.022969 0.019673 0.015611 0.021912 0.025067

0.025695 0.027797 0.023808 0.018892 0.026518 0.030336

0.024469 0.026471 0.022673 0.017991 0.025253 0.028889

0.024403 0.026400 0.022612 0.017943 0.025185 0.028811

Contoh perhitungannya : p1 (1,1) = p11 (1). p12 (1) = 0.167889 * 0.206806 = 0.0347204 p1 (1,2) = p11 (1). p12 (2) = 0.167889 * 0.222674 = 0.0373677

Maka proses perhitungan EM algorithm yang dilakukan pada iterasi pertama menghasilkan pendugaan nilai peluang untuk masing-masing kombinasi antara dua mata dadu, seperti pada tabel 4.14. Selanjutnya dilakukan kembali proses EM algorithm untuk iterasi kedua.

5.2.4

Iterasi dan Pembahasan Hasil

Proses EM algorithm merupakan proses yang melakukan iterasi. Semakin banyak iterasi yang dilakukan maka semakin akurat pendugaan parameter yang dihasilkan. Iterasi dapat dihentikan bila nilai parameter yang dihasilkan pada

47 proses ke-i mendekati nilai parameter pada proses ke-i-1. Pada penelitian ini iterasi dilakukan sebanyak 2000 kali, dan hasilnya adalah : Tabel 4.15 Peluang untuk Masing-masing Simulasi Mata Dadu Setelah Iterasi p 2000,1 ( x1 ) 0.158425 0.141255 0.204329 0.078494 0.172283 0.245213

x1 1 2 3 4 5 6

p 2000, 2 ( x 2 ) 0.239230 0.260611 0.103999 0.111984 0.134388 0.149788

x2 1 2 3 4 5 6

Tabel 4.16 Peluang untuk Setiap Kejadian dari Simulasi Dua Mata Dadu Setelah Iterasi

Tabel 4.16 merupakan hasil dari proses EM algorithm setelah melakukan proses iterasi sebanyak 2000 kali dengan menggunakan bantuan Delphi. Proses iterasi dilakukan sebanyak 2000 kali karena hasil dari proses ke-2001 dengan hasil dari proses ke-2000 tidak jauh berbeda. Dengan membandingkan hasil pada tabel 4.16 dengan peluang dari dua mata dadu berdasarkan data yang lengkap, yaitu pada tabel 4.6. Maka dapat

48 disimpukan bahwa EM algorithm merupakan salah satu metode pendugaan yang baik.

5.3

Analisis Pengaplikasian EM algorithm untuk PCFG

Pada sub bab ini, peneliti menjelaskan tentang salah satu pengaplikasian EM

algorithm

dalam

bidang

context

free

grammars

(CFG).

(http://[email protected]). Proses penelitian ini dibagi menjadi beberapa bagian yaitu :

5.3.1

•

Analisis penggunaan PCFG dalam menyelesaikan masalah ambiguitas

•

Penggunaan Maximum Likelihood dalam PCFG

•

Proses EM algorithm dalam PCFG

Analisis Penggunaan PCFG dalam Menyelesaikan Ambiguitas

Hal yang umum dalam hal CFG adalah munculnya ambiguitas. Hal ini dikarenakan pada kenyataannya sebuah kalimat dapat mempunyai struktur frase yang lebih dari satu. Yang berarti bisa mengakibatkan lebih dari satu arti. Salah satu jenis ambiguitas antara lain : Ambiguitas yang disebabkan penambahan frase preposisi :

49

Gambar 4.1

Ambiguitas Frase Preposisi

Ambiguitas yang disebabkan kata sambung :

50

Gambar 4.2

Ambiguitas Kata Sambung

Dalam komputasi , beberapa struktur frase ditampilkan dengan disingkat.

Sebagai contoh bentuk

yang merupakan bentuk singkat dari

parse tree

. Dalam contoh, ambiguitas terjadi karena CFG menggunakan prinsip rekursif. Bagian rule NP → NP CONJ NP dan NP → NP PP merupakan bagian dari rekursif karena dapat digunakan untuk menghasilkan frase nominal. Rules VP → V NP dan PP → P NP, bisa disebut sebagai rekursif tidak langsung, karena dapat menghasilkan verbal dan frase preposisi. Pada umumnya PCFG dapat menyelesaikan ambiguitas (i)

dengan memproses semua full parse tree yang terdapat dalam suatu kalimat (menggunakan simbol backbone dari CFG),

51 (ii)

dengan menghitung peluang untuk semua tree (menggunakan aturan peluang dari PCFG),

(iii)

memilih parse yang paling cocok sebagai analis dari kalimat yang diberikan.

Proses perhitungan dari full parse tree :

⎛ NP ⎞ p(S → NP VP) . p⎜ Δ ⎟ . p(VP → V NP PP) . p(V → saw) . ⎝ Peter ⎠ PP ⎛ NP ⎞ ⎛ ⎞ ⎟⎟ p⎜⎜ Δ ⎟⎟ . p⎜⎜ Δ . . Mary with the telescope ⎝ ⎠ ⎝ ⎠

Gambar 4.3 Contoh Perhitungan pada Parse Tree (i)

52

⎛ NP ⎞ p(S → NP VP) . p⎜ Δ ⎟ . p(VP → V NP) . p( NP → NP PP) . ⎝ Peter ⎠ PP ⎛ NP ⎞ ⎛ ⎞ ⎟⎟ p(V → saw). p⎜⎜ Δ ⎟⎟. p⎜⎜ Δ . . Mary with a telescope ⎝ ⎠ ⎝ ⎠

Gambar 4.4 Contoh Perhitungan pada Parse Tree (ii)

Dengan membandingkan peluang untuk kedua analisis diatas, maka dipilih analisis yang pertama, jika : p(VP → V NP PP) > p(VP → V NP) . p(NP → NP PP) Pada prinsipnya, ambiguitas pada CFG dapat diselesaikan dengan model probabilistic. Ambiguitas pada CFG dapat diselesaikan hanya dengan melihat dari rule CFG, yang disebabkan oleh penambahan PP. PCFG juga memiliki keterbatasan dalam menghilangkan ambiguitas. PCFG dapat digunakan untuk memilih kalimat dengan menganalisis kalimat tersebut, namun contoh kedua di mana ambiguitasnya disebabkan oleh kata hubung, tidak dapat diselesaikan dengan PCFG. Walaupun kedua tree memiliki struktur yang berbeda tetapi keduanya memiliki probalistic yang sama. Beberapa contoh lain tentang penggunaan PCFG adalah pada kalimat “the girl saw a bird on a tree”. Kalimat ini memiliki dua parse tree.

53

Gambar 4.5 Full Parse Tree dari “the girl saw a bird on a tree”

Dengan membandingkan peluang dari kedua analisis, dipilih analisis yang pertama jika : p(VP → V NP). p(NP → NP PP) > p(VP → V NP PP) Jika hasil yang diperoleh ini dibandingkan dengan hasil yang diperoleh untuk kalimat “John saw Mary with the telescope” pada percobaan pertama, tampak frase proposional ditambahkan pada kedua contoh frase verbal ataupun frase nominal. PP “with the telescope” ditambahkan pada frase verbal, sedang PP “on the tree” ditambahkan pada frase kata benda, maka hanya ada satu solusi untuk masalah diatas, CFG harus ditulis agar model peluang dapat dipakai untuk peluang yang berbeda untuk analisis yang berbeda.

54 p(VP → V NP PP-ON) < p(VP → V NP) . p(NP → NP PP-ON) p(VP → V NP PP-WITH) > p(VP → V NP) . p(NP → NP PP-WITH) Dalam menghitung besarnya nilai peluang suatu rule maka digunakan treebank grammars, yang dapat memberikan informasi untuk PCFG yang terbentuk dari full parse tree (Charniak, 1996). Ttreebank grammars G, p adalah PCFG didefinisikan sebagai (i)

G adalah context free grammars yang dibaca dari treebank, dan

(ii)

p adalah distribusi peluang pada himpunan full parse tree dari G, dengan peluang distribusi pada fragmen grammar G A : p(r ) =

f (r ) ∑ f (r )

untuk semua r ∈ G A

(4.18)

r∈G A

Dengan f (r ) adalah jumlah rule r ∈ G A muncul pada treebank Berikut merupakan contoh perhitungan PCFG untuk treebank di mana terdapat 210 full parse tree : 100 * t1

55

5 * t2

100 * t 3

5 * t4

Gambar 4.6 Full Parse Tree untuk Contoh Perhitungan PCFG

Berdasarkan aturan dari CFG, treebank grammars akan dihasilkan, dengan frekuensi rule f (r ) merupakan jumlah kejadian dari suatu rule terjadi pada treebank, sedang peluang rule p(r ) merupakan peluang kejadiannya.

56 Tabel 4.17 Contoh Perhitungan PCFG CFG rule S → NP VP VP → V NP PP-WITH VP → V NP PP-ON VP → V NP NP → Peter NP → Mary NP → a bird NP → NP PP-WITH NP → NP PP-ON PP-WITH → with a telescope PP-ON → on a tree V → saw

Frekuensi Rule 100 + 5 + 100 + 5 100 5 5 + 100 100 + 5 100 + 5 + 100 + 5 100 + 5 5 100

Probability Rule 210 / 210 = 1.000 100 / 210 ≈ 0.476 5 / 210 ≈ 0.024 105 / 210 = 0.500 105 / 525 = 0.200 210 / 525 = 0.400 105 / 525 = 0.200 5 / 525 ≈ 0.010 100 / 525 ≈ 0.190

100 + 5 100 + 5 100 + 5 + 100 + 5

105/ 105 = 1.000 105 / 105 = 1.000 210 / 210 = 1.000

Full parse tree t1 dari kalimat “Peter saw Mary with the telescope” akan dipilih jika : p(VP → V NP PP-WITH) > p(VP → V NP) . p(NP → NP PP-WITH) Dengan melihat nilai peluang dari PCFG untuk semua rule, maka dipilih t1 karena : 0.476 > 0.500 * 0.010 Untuk kalimat yang kedua pada treebank grammar “Mary saw a bird on the tree”, dipilih full parse tree t 3 jika : (VP → V NP PP-ON) < p(VP → V NP) . p(NP → NP PP-ON) Dan peluang dari PCFG memberikan nilai bahwa 0.024 < 0.500 * 0.190. Hal ini membuktikan bahwa PCFG bisa menyelesaikan ambiguitas dari kalimatkalimat tersebut.

57 5.3.2

Maximum Likelihood Estimation dalam PCFG

Dengan mengasumsikan G sebagai context free grammar, dan X merupakan himpunan full parse tree dari G. Maka model peluang dari G didefinisikan sebagai:

⎫ ⎧ M G = ⎨ p ∈ M ( X ) | p( x) = ∏ p(r ) f r ( x ) dengan ∑ p(r ) = 1⎬ r∈G! r∈G ⎭ ⎩

(4.19)

untuk semua pecahan grammar G A Dengan mengasumsikan

f T : X → R merupakan bagian dari tidak

kosong dan full parse tree yang terbatas, dan G, pT adalah treebank grammar dari f T , maka pT merupakan MLE dari M G pada f T .

L( f T ; pT ) = max L( f T ; p)

(4.20)

p∈M G

MLE dari M G pada f T merupakan penduga yang unik.

5.3.3

Proses EM Algorithm dalam PCFG

Pada bagian ini dijelaskan tentang penggunaan EM algorithm dalam penentukan probability context free grammars (PCFG). Dengan mengasumsikan G, p

sebuah PCFG, di mana p 0 merupakan starting instance dari model

peluang M G , f : Y → R yang merupakan bagian dari kalimat G. ⎧ ⎫ * M G = ⎨ p ∈ M ( X ) | p( x) = ∏ p(r ) f r ( x ) ⎬ r∈G ⎩ ⎭ Dengan mengaplikasikan PCFG G, p 0 dari EM algorithm adalah sebagai berikut :

(4.21)

dan kalimat utama f, maka prosedur

58 (1) untuk setiap i = 1,2,3 ... do (2)

q := pi − 1

(3)

Langkah E (PCFG) : generate treebank f Tq : X → R yang didefinisikan : f Tq ( x) := f ( y ).q( x | y ) dengan y = yield (x)

(4)

Langkah M (PCFG) : membuat treebank grammar G, PTq

(5)

pi := pTq ss

(6) End (7) Cetak p 0 , p1 , p 2 ,...

(4.22)

Pendugaan dari EM algorithm ini menghasilkan nilai peluang dari suatu fungsi f dengan urutan yang secara monoton menaik. L( f ; p 0 ) ≤ L( f ; p1 ) ≤ L( f ; p 2 ) ≤ ...

(4.23)

5.3.3.1 Analisis Data Awal untuk PCFG

Data yang dipakai merupakan contoh yang sederhana sehingga proses dapat dimengerti dan proses dari EM algorithm yang dilakukan tidak terlalu banyak. Contoh terdiri dari dua kalimat dengan kalimat pertama merupakan kalimat yang ambigu sedangkan kalimat kedua tidak ambigu. Contoh yang dipakai adalah 15 kalimat berikut : f(y) 5 10

y y1 y2

59 y1 = “Mary saw a bird on a tree” y 2 = “a bird on the tree saw a worm”

Berdasarkan kedua kalimat tersebut maka dapat dibuat full parse tree nya. x1

x2

x3

Gambar 4.7 Full Parse Tree untuk Simulasi y1 dan y 2 Dengan pendugaan dari EM algorithm maka ditentukan nilai peluang awal acak dari rule yang ada yang mewakili semua parse dari kalimat.

60 Tabel 4.18 Peluang Acak untuk Masing-masing Simulasi Rule S → NP VP VP → V NP VP → V NP PP NP → NP PP NP → Mary NP → a bird NP → a worm PP → on the tree V → saw

1.00 0.5 0.5 0.25 0.25 0.25 0.25 1.00 1.00

Nilai-nilai peluang awal yang tertulis, berdasarkan sebaran uniform untuk fragmen grammar. EM algorithm memberikan kebebasan dalam menentukan nilai awalnya oleh sebab itu nilai pada tabel tidak harus sama.

5.3.3.2 Langkah Expectation (E-step) untuk PCFG

Pada langkah E dari EM algorithm untuk PCFG, nilai untuk treebank f Tq akan dihasilkan dari starting intance q := p 0 . Starting instance untuk full parse tree x1 , x 2 , x3 , dan y1 , y 2 adalah : Tabel 4.19 Peluang untuk Simulasi x1 , x 2 , x3 dan y1 , y 2

p 0 ( x) 0.0078125 0.0312500 0.0078125

x x1 x2 x3

p0 ( y) 0.0390625 0.0078125

y y1 y2

61 Contoh perhitungannya : p 0 ( x1 ) = ∏ p(r ) f r ( x1 )` r∈G

⎛ NP ⎞ = p(S → NP VP) . p⎜ Δ ⎟ . p(VP → V NP) . p(V → saw) . ⎝ Mary ⎠ ⎛ NP ⎞ ⎛ NP ⎞ p(NP → NP PP) . p⎜ Δ ⎟ . p⎜ Δ ⎟ ⎝ abird ⎠ ⎝ on.a.tree ⎠ = 1.00 * 0.25 * 0.50 * 1.00 * 0.25 * 0.25 * 1.00 = 0.0078125 p0 ( y) =

∑ p( x)

yield ( x ) = y1

= p ( x1 ) + p ( x 2 ) = 0.0078125 + 0.0312500 = 0.0390625 Dengan adanya nilai sebaran peluang q := p 0 , maka proses selanjutnya adalah menghasilkan treebank f Tq dengan menghitung frekuensi untuk masing-masing full parse tree. Tabel 4.20 Frekuensi Simulasi x1 , x 2 , x3

f Tq (x) 1 4 10

x x1 x2 x3

Contoh perhitungannya : f Tq ( x1 ) = f ( yield ( x1 )).q ( x1 | yield ( x1 ))

62 = f ( y1 ).q ( x1 | y1 ) = f ( y1 ).

= 5.

q ( x1 ) q ( y1 )

0.0078125 0.0390625

=1 Hasil perhitungan pada tabel 4.20 akan digunakan untuk membuat treebank grammar

. 5.3.3.3 Langkah Maximization (M-step) untuk PCFG

Pada proses maximization dari EM algorithm yang dilakukan adalah membuat treebank grammar G, pTq dari treebank f Tq . Tabel 4.21 Peluang untuk Masing-masing Simulasi Rule Setelah M-step Pertama S → NP VP VP → V NP VP → V NP PP NP → NP PP NP → Mary NP → a bird NP → a worm PP → on the tree V → saw

1.00 1 + 10 0.733 ≈ 15 4 0.267 ≈ 15 1 + 10 0.268 ≈ 41 1+ 4 0.122 ≈ 41 1 + 4 + 10 0.366 ≈ 41 10 0.244 ≈ 41 1.00 1.00

63 Contoh perhitungan untuk tabel 4.21 sama seperti yang dilakukan pada tabel 4.17. Peluang diatas merupakan hasil dari proses EM algoritm pada iterasi pertama. Dilanjutkan iterasi kedua dengan data input bagi langkah E adalah data yang telah dihasilkan pada langkah M sebelumnya.

5.3.3.4 Iterasi dan Pembahasan Hasil

Perulangan dilakukan sampai hasil akhir dari suatu proses tidak jauh berbeda dengan proses sebelumnya. Tabel 4.22 PCFG untuk Simulasi Full Parse Tree CFG rule S → NP VP VP → V NP VP → V NP PP NP → NP PP NP → Mary NP → a bird NP → a worm PP → on the tree V → saw

p0

p1

p2

p3

1.000 0.500 0.500 0.250 0.250 0.250 0.250 1.000 1.000

1.000 0.733 0.267 0.268 0.122 0.366 0.244 1.000 1.000

1.000 0.808 0.192 0.288 0.119 0.356 0.237 1.000 1.000

1.000 0.849 0.151 0.298 0.117 0.351 0.234 1.000 1.000

…

p 27 1.000 0.975 0.025 0.328 0.112 0.336 0.224 1.000 1.000

Hasil pada table 4.22 merupakan hasil iterasi sebanyak 27 kali. Proses berhenti pada iterasi ke-27, karena pada iterasi ke-28 data yang dihasilkan tidak berbeda dengan sebelumnya. Maka proses EM algorithm dapat dihentikan dan dilakukan pembahasan hasilnya. Berdasarkan pembahasan PCFG dalam mengatasi ambiguitas, maka dari data yang diperoleh akan dipilih x1 dibandingkan x 2 karena:

64

p(VP → V NP). p(NP → NP PP) > p(VP → V NP PP) Nilai peluang yang diperhatikan adalah p(VP → V NP) , p(NP → NP PP), dan

p(VP → V NP PP).

Tabel 4.23 PCFG untuk Simulasi Sebagian Parse Tree

p p0 p1 p2 p3

… p 27

p(VP → V NP) . p(NP → NP PP)

p(VP → V NP PP)

0.500 * 0.250 = 0.125 0.733 * 0.268 = 0.196 0.808 * 0.288 = 0.233

0.500 0.267 0.192

0.849 * 0.298 = 0.253

0.151

0.975 * 0.328 = 0.320

0.025

Dilihat dari perhitungan EM algorithm tampak bahwa pernyataan yang memberikan alasan untuk

memilih x1 dibandingkan x 2 dimulai dari iterasi

kedua dari EM algorithm. Terlihat dari tabel 4.23 bahwa nilai dari p(VP → V NP) . p(NP → NP PP) secara monoton menaik (0.125 sampai 0.320) dan nilai dari p(VP → V NP PP) secara monoton menurun (0.500 sampai 0.025). Hal ini memberikan alasan yang kuat yang menyatakan bahwa PCFG yang dihasilkan

EM algorithm cukup baik.