UNIVERSITAS BINA NUSANTARA ____________________________________________________________________ Program studi Ganda Teknik Informatika-Statistika Skripsi Sarjana Komputer – Sarjana Sains Semester ganjil 2005/2006
PENGGUNAAN EXPECTATION MAXIMIZATION ALGORITHM DALAM PROBABILISTIC CONTEXT FREE GRAMMARS
Wirawan Suryana NIM : 0600670215
Abstrak Expectation maximization algorithm (EM algorithm) adalah salah satu metode penduga parameter yang dikembangkan berdasarkan maximum likelihood estimation. Skripsi ini merupakan penelitian terhadap penggunaan EM algorithm dengan menggunakan beberapa contoh, serta pengaplikasiannya untuk menentukan probalilty context free grammars (PCFG) yang dapat digunakan lebih lanjut untuk memberikan informasi tentang suatu kalimat. Penelitian ini menggunakan R language dan Delphi untuk membantu dalam prosesnya. Dalam pengaplikasian EM algorithm untuk menentukan PCFG, EM algorithm memberikan nilai PCFG yang cukup baik. Dari penelitian yang dilakukan diperoleh kesimpulan bahwa EM algorithm merupakan salah satu metode yang dapat dipakai untuk menduga parameter dimana data yang diperoleh lengkap maupun tidak lengkap. Pengaplikasian dari EM algorithm sendiri dapat digunakan dalam mencari nilai dari probalilty context free grammars. Kata kunci : Maximum likelihood estimation, expectation maximization algorithm, probability context free grammars
iv
KATA PENGANTAR
Puji syukur kepada Tuhan atas kasih dan setia-Nya sehingga penulis dapat menyusun dan menyelesaikan tugas Skripsi yang berjudul : “PENGGUNAAN EXPECTATION MAXIMIZATION ALGORITHM DALAM PROBABILISTIC CONTEXT FREE GRAMMARS” sebagai syarat untuk memperoleh gelar kesarjanaan pada Program Studi Ganda, jurusan Teknik Informatika – Statistika, Jenjang Pendidikan Strata 1. Dalam proses penyusunan skripsi ini, penulis banyak sekali memperoleh bimbingan, dorongan semangat, dan fasilitas dari berbagai pihak yang mendukung penulis untuk menyelesaikan tugas tersebut tepat waktu. Ucapan terima kasih yang tulus penulis sampaikan kepada : •
Bapak Prof. Dr. Gerardus Polla, M.App.Sc., selaku Rektor Universitas Bina Nusantara, yang telah memberikan banyak kesempatan kepada mahasiswa untuk menerapkan segala sesuatu yang telah dipelajari selama mengikuti kegiatan perkuliahan dengan mengadakan program studi Skripsi.
•
Bapak Wikaria Gazali, S.Si., M.T., selaku Dekan Fakultas MIPA, atas dorongan semangatnya dan selalu memacu kreatifitas mahasiswanya.
•
Bapak Drs. Ngarap Imanuel Manik, M.kom., selaku ketua jurusan Matematika dan Statistika, yang telah memberikan persetujuan terhadap topik skripsi yang diajukan dan telah menunjuk para pembimbing terbaik untuk penulis.
•
Bapak Rojali, S.Si., selaku sekretaris jurusan Matematika dan Statistika.
v
•
Bapak Stanislaus S. Uyanto, Ph. D., selaku Dosen Pembimbing pertama, yang tiada henti-hentinya meluangkan banyak waktu, memberikan saran, ide, semangat serta dukungan moral, dan telah banyak sekali memberikan dukungan kepada penulis dari mulai persiapan pemilihan topik, penulisan skripsi sampai penyelesaian skripsi ini.
•
Bapak Siswa Trihadi, Ir., M.Sc., DR., selaku Dosen Pembimbing kedua, yang telah memberikan saran dan ide, mengajukan pertanyaan-pertanyaan yang mendorong penulis untuk menjadi lebih baik.
•
Civitas akademika Universitas Bina Nusantara yang secara langsung maupun tidak langsung memberikan dukungan kepada penulis. Ucapan terima kasih penulis haturkan juga kepada kedua orang tua yang telah membekali penulis dengan semangat juang, kepercayaan, pengertian, sehingga penulis dapat menyelesaikan Skripsi ini. Meskipun penulis telah berusaha sebaik-sebaiknya, namun penulis menyadari bahwa Skripsi ini jauh dari sempurna. Kritik dan saran akan penulis terima dengan senang hati. Kiranya Skripsi ini bermanfaat bagi para pembaca dan pihak-pihak yang membutuhkan. Terima kasih.
Jakarta, Januari 2007
Penulis
vi
DAFTAR ISI
Halaman ABSTRAK ..……………………………………………………………
iv
KATA PENGANTAR .....……………………………………………..
v
DAFTAR ISI ..…………………………………………………………
vii
DAFTAR TABEL …..…………………………………………………
x
DAFTAR GAMBAR ….………………………………………………
xi
DAFTAR LAMPIRAN .……………………………………………….
xii
BAB 1 PENDAHULUAN.......................................................................
1
1.1 Latar Belakang Masalah ………………………………………….
1
1.2 Ruang Lingkup ……………………………………………………
3
1.3 Tujuan dan Manfaat ……………………………………………….
3
1.4 Sistematika Penulisan ......................................................................
4
BAB 2 GAMBARAN UMUM OBJEK .................................................
6
2.1 Data Penelitian .................................................................................
6
BAB 3 LANDASAN TEORI ..................................................................
9
3.1 Maximum Likelihood Estimation .....................................................
9
3.2 Expectation Maximization Algorithm .............................................
11
3.2.1 Symbolic Analyzers dan Statistical Analyzers ...........................
13
3.2.2 Input, Prosedur, dan Output dari EM Agorithm ........................
14
3.2.3 Iterasi EM Algorithm .................................................................
16
3.3 Probabilistic Context Free Grammars ...........................................
17
BAB 4 METODOLOGI PENELITIAN DAN ANALISIS ..................
26
4.1 Metodologi Penelitian .....................................................................
26
4.2 Analisis EM Algorithm untuk mixnormal .......................................
27
4.3 Analisis EM Algorithm untuk Peluang Dua Dadu ..........................
27
vii
4.3.1 Proses Analisis Penginputan Data ............................................
28
4.3.2 Proses Expectation pada EM Algorithm ...................................
28
4.3.3 Proses Maximization pada EM Algorithm .................................
28
4.3.4 Proses Iterasi dan Pembandingan Hasil......................................
29
4.4 Analisis Pengaplikasian EM Algorithm untuk PCFG ......................
29
4.4.1 Analisis Penggunaan PCFG dalam Ambiguitas ........................
30
4.4.2 Maximum Likelihood Estimation dalam PCFG .........................
30
4.4.3 EM Algorithm dalam PCFG .......................................................
30
4.5 Spesifikasi Perangkat Keras (Hardware) dan Piranti Lunak (Software)........................................................................................
31
4.5.1 Spesifikasi Perangkat Keras (Hardware)...................................
31
4.5.2 Spesifikasi Piranti Lunak (Software) .........................................
31
BAB 5 HASIL DAN PEMBAHASAN ..................................................
32
5.1 Analisis EM Algorithm untuk mixnormal .......................................
32
5.2 Analisis EM Algorithm untuk Peluang Dua Mata Dadu .................
37
5.2.1 Proses Penginputan dan Analisis Data ......................................
37
5.2.2 Langkah Expectation (E-step) dari EM algorithm ....................
42
5.2.3 Langkah Maximization (M-step) dari EM algorithm ................
44
5.2.4 Iterasi dan Pembahasan Hasil ....................................................
46
5.3 Analisis Pengaplikasian EM algorithm untuk PCFG ......................
48
5.3.1 Analisis Penggunaan PCFG dalam Menyelesaikan Ambiguitas
48
5.3.2 Maximum Likelihood Estimation dalam PCFG ........................
57
5.3.3 Proses EM algorithm dalam PCFG ............................................
57
5.3.3.1 Analisis Data Awal untuk PCFG ............................................
58
5.3.3.2 Langkah Expectatioan (E-step) untuk PCFG .........................
60
5.3.3.3 Langkah Maximization (M-step) untuk PCFG .......................
62
5.3.3.4 Iterasi dan Pembahasan Hasil ................................................
63
BAB 6 SIMPULAN DAN SARAN .......................................................
65
6.1 Simpulan .........................................................................................
65
viii
6.2 Saran ...............................................................................................
65
DAFTAR ACUAN .................................................................................
xiii
DAFTAR PUSTAKA .............................................................................
xv
DAFTAR RIWAYAT HIDUP...............................................................
xvi
LAMPIRAN
ix
DAFTAR TABEL
Halaman Tabel 2.1 Tabel 4.1 Tabel 4.2 Tabel 4.3 Tabel 4.4 Tabel 4.5 Tabel 4.6 Tabel 4.7 Tabel 4.8 Tabel 4.9 Tabel 4.10 Tabel 4.11 Tabel 4.12 Tabel 4.13 Tabel 4.14 Tabel 4.15 Tabel 4.16 Tabel 4.17 Tabel 4.18 Tabel 4.19 Tabel 4.20 Tabel 4.21 Tabel 4.22 Tabel 4.23
Peluang untuk rule .............................................................. Hasil Simulasi Perhitungan EM untuk mixnormal ............. Kemungkinan Kejadian untuk Dua Mata Dadu ................. Kemungkinan Jumlah Kejadian pada Simulasi Dua Mata Dadu ................................................................... Peluang untuk Setiap Kejadian dari Simulasi Dua Mata Dadu (i) .............................................................. Frekuensi dan Peluang untuk Masing-masing Simulasi Mata Dadu ........................................................... Peluang untuk Setiap Kejadian Dari Simulasi Dua Mata Dadu (ii) ............................................................ Frekuensi untuk Setiap Jumlah Simulasi Dua Mata Dadu .................................................................. Peluang Acak untuk Masing-masing Simulasi Mata Dadu .......................................................................... Peluang Acak untuk Setiap Kejadian dari Simulasi Dua Mata Dadu ................................................... Peluang Acak Untuk Jumlah Kedua Simulasi Mata Dadu ......................................................................... Frekuensi Kejadian Pada Simulasi Dua Mata Dadu .................................................................. Frekuensi untuk Masing-masing Simulasi Mata Dadu ........................................................................ .. Peluang untuk Masing-masing Simulasi Mata Dadu .......................................................................... Peluang untuk Setiap Kejadian Dari Simulasi Dua Mata Dadu (iii) ...…………………………………… Peluang untuk Masing-masing Simulasi Mata Dadu Setelah Iterasi .................................................. Peluang untuk Setiap Kejadian dari Simulasi Dua Mata Dadu Setelah Iterasi .......................................... Contoh Perhitungan PCFG ................................................ Peluang Acak untuk Masing-masing Simulasi Rule .......... Peluang untuk Simulasi x1 , x 2 , x3 dan y1 , y 2 .................... Frekuensi Simulasi x1 , x 2 , x3 ...........……………………… Peluang untuk Masing-masing Simulasi Rule Setelah M-step Pertama ............................................. PCFG untuk Simulasi Full Parse Tree ............................. PCFG untuk Simulasi Sebagian Parse Tree.......................
x
20 33 34 35 35 36 36 37 38 39 40 40 42 42 43 44 44 53 57 57 58 59 60 61
DAFTAR GAMBAR
Halaman Gambar 2.1 Gambar 2.2 Gambar 2.3 Gambar 2.4 Gambar 2.5 Gambar 2.6 Gambar 4.1 Gambar 4.2 Gambar 4.3 Gambar 4.4 Gambar 4.5 Gambar 4.6 Gambar 4.7
CFG Parse Tree ............................................................... Tahapan dari Parse Tree................................................... Local Tree (i) .................................................................... Local Tree (i) .................................................................... Hubungan Peluang Suatu Rule Dengan Tree (i) ............... Hubungan Peluang Suatu Rule Dengan Tree (ii) .............. Ambiguitas Frase Preposisi ............................................... Ambiguitas Kata Sambung ................................................ Contoh Perhitungan pada Parse Tree (i) ........................... Contoh Perhitungan pada Parse Tree (ii) ........................... Full Parse Tree dari “the girl saw a bird on a tree” …...... Full Parse Tree untuk Contoh Perhitungan PCFG …….... Full Parse Tree untuk Simulasi y1 dan y 2 ........................
xi
15 16 17 17 18 19 45 46 48 48 50 51 56
DAFTAR LAMPIRAN
Halaman 1. Statement EM algorithm untuk mixnormal (R Language)..……...… L1 2. Statement EM algorithm untuk peluang dua buah mata dadu (Delphi) ..............................................................
L1
3. Statement EM algorithm untuk PCFG (Delphi) ......…………………
L6
xii
