BAB IV IMPLEMENTASI DAN PENGUJIAN Bab ini menjabarkan bagaimana implementasi hasil perancangan tersebut ke dalam kode program yang dilakukan selama pengerjaan Tesis. Selain itu dijabarkan pula pengujian yang dilakukan terhadap sistem berbasis pengetahuan yang dibangun. Pada bab ini dijabarkan metode pengujian yang digunakan, skenario pengujian, hasil, dan analisis hasil pengujian.
4.1 Implementasi Pada sub bab ini dijelaskan proses implementasi perangkat lunak Genetsim. Hal-hal yang dijabarkan meliputi lingkungan implementasi, implementasi kelas perancangan, dan implementasi user interface.
4.1.1 Lingkungan Implementasi Aplikasi Genetsim kebanyakan diimplementasikan dengan menggunakan bahasa pemrograman Java. Bahasa pemrograman ini dipilih karena: 1. Bahasa pemrograman Java merupakan bahasa pemrograman yang bersifat freeware sehingga mudah untuk didapatkan. 2. Aplikasi dalam bahasa Java di-compile ke dalam byte code yang kemudian diinterpretasikan oleh Java Virtual Machine. Dengan demikian, aplikasi tersebut dapat dijalankan pada komputer dengan arsitektur apapun asal terdapat Java Virtual Machine. 3. Bahasa pemrograman Java memiliki library yang lengkap. Selain library standar, telah banyak pula tersedia library bahasa Java lainnya yang dapat diperoleh secara free. 4. Subsistem yang digunakan untuk melakukan inferensi dan memvisualisasikan graf dikembangkan dengan bahasa Java. Secara umum, engine untuk rekonstruksi model dan inferensi dibangun sebagai kelaskelas dalam bahasa Java. Untuk user interface, digunakan Java Server Pages (JSP) selain script
HTML
dan
Javascript.
JSP
IV-1
memungkinkan
script
HTML
IV-2
disertai dengan kode bahasa Java yang di-embbed untuk menciptakan konten yang dinamik. Dengan demikian, halaman web yang dibuat dapat memanggil kelas-kelas bahasa Java yang telah dibuat. Pada sistem berbasis pengetahuan yang dibangun, JSP digunakan untuk proses rekonstruksi model dan pembentukan treeview. Selain itu, untuk menjembatani user interface web dan engine inferensi yang telah dibangun dengan bahasa Java, digunakan Java Servlet. Java Servlet dipilih karena: 1. Java servlet dijalankan pada Java Virtual Machine yang ada di server sehingga lebih aman dan portable. Aplikasi dijamin dapat dijalankan sebagaimana mestinya. 2. Java servlet dijalankan sepenuhnya pada domain yang ada di server, tidak seperti applet. Dengan demikian, untuk menjalankan aplikasi, tidak diperlukan adanya dukungan Java pada web browser. 3. Java servlet lebih efisien dan bersifat scalable. Servlet dapat menjalankan request yang berbeda sebagai sejumlah thread dalam satu proses atau sebagai sejumlah thread dalam sejumlah proses yang disebar dalam sejumlah backend servers. Hal ini memudahkan pengembangan Genetsim selanjutnya. Implementasi dilakukan pada notebook dengan spesifikasi sebagai berikut: 1. Processor Intel Core Duo T2250 1.73 GHz 2. RAM 1 GB Perangkat lunak dan kakas pengembangan yang digunakan untuk mengimplementasikan Genetsim antara lain: 1. Bayesian Network Tools in Java 2.7 2. JGraphLayout 3. Microsoft Windows XP Home Edition 4. Apache Tomcat 6.0 5. phpMyAdmin 2.7.0 6. Eclipse Europa SDK 3.4.1 7. Mozilla Firefox 3.0.5
IV-3
4.1.2 Implementasi Kelas Perancangan Implementasi kelas-kelas yang telah didefinisikan pada tahap perancangan selain kelas pada subsistem dapat dilihat pada Tabel IV-1. Tabel IV-1 Implementasi Kelas Perancangan No 1 2 3 4 5 6
Kelas Gene DBConfiguration DBConnection Model Parser EngineServlet
Package core database database generator generator inference
Implementasi Fisik src/core/Gene.java src/database/DBConfiguration.java src/database/DBConnection.java src/generator/Model.java src/generator/Parser.java src/inference/EngineServlet.java
Untuk meningkatkan performansi, pembangunan Bayesian network dari model pada basis data hanya dilakukan sekali pada saat start-up. Bayesian network yang direkonstruksi kemudian disimpan dalam file XML untuk kemudian digunakan pada pengaksesan aplikasi selanjutnya. Selain itu, pembangkitan graf visual yang menggambarkan graf Bayesian network juga hanya dilakukan sekali pada saat start-up. Graf yang telah dibangkitkan kemudian disimpan sebagai file image berekstensi png. Map HTML yang digunakan agar simpul pada graf dapat diklik juga hanya dibangkitkan sekali dan kemudian disimpan pada file untuk digunakan pada pengaksesan selanjutnya.
4.1.3 Implementasi User Interface Berdasarkan hasil perancangan, user interface diimplementasikan sebagai halaman web. Untuk menampilkan tree view yang digunakan untuk memasukkan evidences dan menampilkan hasil inferensi, dibuat script JSP dalam file bbntreeview.jsp. Sedangkan, user interface utama diimplementasikan dalam file bbnnetwork.jsp yang merupakan welcome file dari aplikasi web Genetsim. Script Javascript yang digunakan berada pada file script.js. Screenshot halaman utama aplikasi Genetsim dapat dilihat pada Gambar IV-1.
IV-4
Gambar IV-1 User Interface Genetsim
4.2 Pengujian Pada sub bab ini dijelaskan pengujian yang dilakukan terhadap sistem berbasis pengetahuan yang dibangun. Sistem berbasis pengetahuan yang dikerjakan dibangun dengan mengimplementasikan tiga buah algoritma inferensi yaitu algoritma exact inference Lauritzen-Spiegelhalter dan dua algoritma approximate inference, likelihood weighting dan Markov Chain Monte Carlo. Berdasarkan hasil analisis, diperoleh hipotesis bahwa inferensi dengan teknik exact inference tidak dapat dilakukan untuk ranah permasalahan jaringan regulatori genetik karena kompleksitasnya yang eksponensial. Sedangkan, teknik approximate inference dapat digunakan untuk graf dengan kompleksitas tinggi. Namun, dari proses analisis saja, hanya dapat diketahui dua algoritma yang memberikan performansi paling baik, tidak berhasil disimpulkan algoritma yang terbaik dari kedua algoritma yang digunakan. Oleh karena itu, pengujian dilakukan untuk membuktikan hipotesis dan mencari algoritma approximate mana yang memberikan performansi paling baik untuk ranah permasalahan jaringan regulatori genetik. Pada sub bab ini dijelaskan skenario pengujian, hasil pengujian, dan analisis hasil pengujian.
IV-5
4.2.1 Skenario Pengujian Pengujian performansi sistem berbasis pengetahuan pada dasarnya dilakukan dengan mengukur dua hal yaitu: 1. Kebenaran hasil inferensi Kebenaran hasil inferensi diukur dengan menguji apakah sistem sudah memberikan hasil inferensi yang benar sesuai dengan permasalahan yang ada. Dalam topik ini, pengujian kebenaran hasil inferensi berarti menilai apakah level ekspresi gen hasil inferensi sesuai dengan level ekspresi gen pada kasus sebenarnya. Kebenaran hasil inferensi sangat bergantung pada kebenaran pengetahuan yang tersimpan pada basis pengetahuan. Pada Tesis ini, pengetahuan yang ada pada basis pengetahuan bukan merupakan hasil pekerjaan melainkan menggunakan pengetahuan yang sudah ada. Pekerjaan yang dilakukan dimulai dengan merepresentasikan pengetahuan yang sudah ada tersebut ke dalam representasi Bayesian network. Karena basis pengetahuan yang digunakan bukan merupakan hasil pekerjaan Tesis, dalam Tesis ini tidak dapat dilakukan pengujian kebenaran hasil inferensi. 2. Performansi algoritma inferensi Karena terdapat lebih dari satu algoritma inferensi yang dapat digunakan untuk melakukan inferensi pada sistem berbasis pengetahuan, perlu diukur pula performansi berbagai algoritma tersebut untuk mengetahui algoritma mana yang memberikan performansi paling baik. Pengujian performansi algoritma inferensi dilakukan dengan menghitung kebutuhan resources untuk melakukan inferensi. Kebutuhan resources didefinisikan sebagai kebutuhan waktu dan memori proses inferensi. Secara khusus, pengujian pekerjaan Tesis ini dilakukan untuk membuktikan hipotesis dan mencari algoritma approximate yang paling tepat digunakan untuk ranah permasalahan jaringan regulatori genetik. Untuk menguji hal-hal tersebut dapat digunakan pengujian performansi algoritma inferensi. Pengujian yang dilakukan pada Tesis ini dilakukan melalui dua tahap: 1. Load test Load test dilakukan untuk membuktikan hipotesis tahap analisis bahwa teknik exact inference tidak dapat digunakan untuk ranah permasalahan jaringan regulatori genetik. Untuk melakukan pengujian ini, digunakan data jaringan
IV-6
regulatori
genetik
yang
divariasikan
kompleksitasnya.
Kompleksitas
didefinisikan sebagai jumlah gen dan relasi yang ada pada jaringan regulatori genetik. Bila kompleksitas Bayesian network didefinisikan sebagai jumlah simpul dan jumlah relasi yang ada pada graf, dari hasil analisis dapat disimpulkan bahwa untuk sejumlah n gen dan m relasi regulasi, graf Bayesian network yang terbentuk memiliki 2n simpul dan paling sedikit m+n relasi. Dari hasil load test ini, dapat diketahui apakah teknik exact inference dapat digunakan pada data yang kompleks. Bila ternyata teknik tidak dapat digunakan, pada data jaringan regulatori genetik dengan kompleksitas seperti apa exact inference masih mungkin dilakukan. Selain itu, dari pengujian ini, dapat diketahui pula apakah sesuai dengan hasil analisis, teknik approximate inference dapat digunakan pada data jaringan yang lebih kompleks daripada data paling kompleks yang dapat diinferensi dengan teknik exact inference. 2. Pengujian performansi algoritma approximate inference Pengujian ini dilakukan untuk mencari algoritma approximate mana yang paling tepat digunakan untuk ranah permasalahan jaringan regulatori genetik. Dari hasil analisis, tidak berhasil diperoleh kesimpulan mana diantara kedua algoritma approximate inference yang lebih baik. Oleh karena itu, dilakukan pengujian dengan membandingkan kebutuhan resources kedua algoritma. Pembandingan dilakukan juga dengan mengukur seberapa jauh perkiraan distribusi probabilitas yang dihasilkan kedua algoritma dengan nilai distribusi probabilitas yang sebenarnya yang diperoleh melalui teknik exact inference. Pengujian dilakukan dengan memvariasikan variabel-variabel proses sampling selain input berupa graf Bayesian network yang mempengaruhi proses inferensi. Dari hasil tinjauan pustaka, diketahui bahwa performansi teknik approximate inference pada dasarnya berbasis pada proses sampling yang dilakukan. Performansi inferensi yang dilakukan dengan demikian mungkin dipengaruhi oleh jumlah evidences dan sampel yang digunakan. Oleh karena itu, pengujian dilakukan dengan memvariasikan jumlah evidences dan jumlah sampel yang digunakan.
IV-7
4.2.2 Hasil Pengujian Pada sub bab ini dijelaskan hasil pengujian yang dilakukan terhadap sistem berbasis pengetahuan yang dibangun. Sesuai dengan skenario pengujian, dijabarkan hasil yang diperoleh dalam dua tahap pengujian yaitu load test dan pengujian performansi algoritma approximate inference. 4.2.2.1 Load Test Load test dilakukan dengan memvariasikan kompleksitas data jaringan regulatori genetik yang digunakan. Kompleksitas didefinisikan sebagai jumlah gen dan jumlah relasi regulasi yang terlibat dalam jaringan regulatori genetik. Dari grafik pada Gambar IV-2 diketahui bahwa jumlah gen dan jumlah relasi regulasi yang ada pada jaringan regulatori genetik berbanding lurus. Bertambahnya jumlah gen yang terlibat menyebabkan bertambah pulanya jumlah relasi. Dengan demikian, variasi dapat dilakukan dengan memvariasikan salah satu dari jumlah gen ataupun jumlah relasi. Pada pengujian ini, dilakukan variasi dengan basis jumlah gen yang terlibat. 160 Jumlah Relasi
140 120 100 80 60 40 20 0 4
6
8 10 12 14 16 18 20 22 24 26 28 30 32 34 36 38 40 42 44 46 48 50 Jum lah Sim pul
Gambar IV-2 Perbandingan Jumlah Simpul dan Jumlah Relasi
Sebagai data awal, digunakan data jaringan regulatori genetik yang melibatkan dua puluh lima buah gen. Bayesian network yang direkonstruksi dari data ini memiliki 50 buah simpul dan 146 buah relasi. Dari data awal ini, kemudian dilakukan pengurangan jumlah gen dengan mengeliminasi gen yang paling sedikit memberikan pengaruh terhadap kompleksitas graf. Pengurangan jumlah gen dilakukan hingga jaringan regulatori genetik hanya terdiri dari dua buah gen. Eliminasi sebuah gen mengakibatkan berkurangnya dua simpul dan sejumlah relasi pada graf Bayesian network. Oleh karena itu, untuk menentukan pengaruh eliminasi suatu gen terhadap kompleksitas graf Bayesian network,
IV-8
dilakukan perbandingan jumlah relasi yang tereliminasi dengan eliminasi gen tersebut. Jumlah relasi yang tereliminasi didefinisikan sebagai jumlah panah masuk (vent-in) dan panah keluar (vent-out) dari suatu gen. Gen dengan jumlah panah masuk dan panah keluar yang paling sedikit adalah gen yang paling sedikit mempengaruhi jumlah relasi pada graf keseluruhan. Oleh karena itu, gen inilah yang dieliminasi untuk memperoleh data pengujian selanjutnya. Urutan eliminasi jumlah gen tidak dapat diperoleh dalam satu kali iterasi. Hal ini disebabkan pengurangan suatu gen juga mempengaruhi jumlah relasi pada gen-gen lain. Oleh karena itu, setiap kali dilakukan eliminasi gen, dilakukan pendataan ulang jumlah panah masuk dan panah keluar dari setiap gen yang tersisa untuk mengetahui gen mana yang harus dieliminasi selanjutnya. Urutan eliminasi gen dapat dilihat pada Tabel IV-2. Tabel IV-2 Data Load Test Nama File gen2.xml gen3.xml gen4.xml gen5.xml gen6.xml gen7.xml gen8.xml gen9.xml gen10.xml gen11.xml gen12.xml gen13.xml gen14.xml gen15.xml gen16.xml gen17.xml gen18.xml gen19.xml gen20.xml gen21.xml gen22.xml gen23.xml gen24.xml gen25.xml
Jumlah Gen 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25
Gen Tereliminasi MBP1 SWI4 MCM1 CDC6 CDC20 SWI5 NDD1 FKH1 PCL2 CDC5 ACE2 SIC1 FAR1 ASH1 CTS1 CLN2 CDC21 EGT2 STB1 HTA1 ALG7 CLB5 CLB2 -
Jumlah Simpul 4 6 8 10 12 14 16 18 20 22 24 26 28 30 32 34 36 38 40 42 44 46 48 50
Jumlah Relasi 5 9 15 21 28 34 38 45 54 61 67 74 79 84 91 98 105 112 117 124 129 134 139 146
Pada setiap kasus uji, tidak diberikan input berupa evidences. Proses yang dilakukan murni merupakan penghitungan nilai probabilitas marginal dari conditional probability yang ada. Hal ini dimaksudkan untuk menghilangkan pengaruh evidences terhadap
IV-9
performansi sistem sehingga pengujian dapat difokuskan untuk menguji faktor kompleksitas data. Dari pengujian yang dilakukan, diperoleh bahwa teknik exact inference hanya mampu melakukan inferensi maksimal pada data yang melibatkan sembilan buah gen. Bila direkonstruksi menjadi Bayesian network, data tersebut direkonstruksi sebagai graf dengan 18 simpul dan 45 relasi. Dari grafik pada Gambar IV-3, diketahui bahwa seiring dengan pertambahan jumlah gen yang terlibat dalam jaringan regulatori genetik, algoritma Lauritzen-Spiegelhalter dan Markov Chain Monte Carlo membutuhkan waktu inferensi yang lebih lama. Sedangkan, algoritma likelihood weighting relatif memiliki waktu inferensi yang konstan. Waktu inferensi yang dibutuhkan algoritma ini juga lebih kecil daripada kedua algoritma lainnya. Dari grafik tersebut dapat dilihat pula bahwa kebutuhan waktu algoritma Lauritzen-Spiegelhalter sebenarnya tidak jauh berbeda dengan kebutuhan waktu inferensi algoritma Markov Chain Monte Carlo untuk jumlah gen yang sama. Dari proses peratarataan, diketahui bahwa kebutuhan waktu algoritma likelihood weighting mendekati 5% dari kebutuhan waktu algoritma Lauritzen-Spiegelhalter dan Markov Chain Monte Carlo. Pada Gambar IV-4, dapat dilihat bahwa pertambahan jumlah relasi juga memberikan pengaruh yang sama terhadap kebutuhan waktu inferensi ketiga algoritma. Dari grafik, dapat dilihat bahwa dari ketiga algoritma, yang memiliki waktu inferensi yang paling kecil dan relatif konstan adalah likelihood weighting. Kedua algoritma yang lain memiliki waktu inferensi yang tidak jauh berbeda dan terus menaik seiring dengan pertambahan jumlah relasi. Dilihat dari sisi kebutuhan memori, pada grafik dalam Gambar IV-5 dapat dilihat bahwa kedua algoritma approximate inference memiliki kebutuhan memori yang relatif sama. Kebutuhan memori ini jauh lebih kecil bila dibandingkan dengan algoritma LauritzenSpiegelhalter. Perbandingan rata-rata kebutuhan memori kedua algoritma approximate inference tidak terlalu signifikan, hanya sekitar 9 : 10. Jumlah memori yang dibutuhkan untuk melakukan inferensi juga dapat dikatakan relatif konstan dan tidak terpengaruh oleh pertambahan jumlah gen yang terlibat. Namun, dapat dilihat bahwa pada algoritma Lauritzen-Spiegelhalter, memori yang dibutuhkan meningkat dengan pesat seiring dengan pertambahan jumlah gen.
Waktu (ms)
IV-10
16000 14000 12000 10000 8000 6000 4000 2000 0 2
3
4
5
6
7
8
9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 Jumlah Gen
Lauritzen-Spiegelhalter
Likelihood Weighting
Markov Chain Monte Carlo
13 9
12 9
11 7
10 5
91
79
67
54
15
28
38
16000 14000 12000 10000 8000 6000 4000 2000 0
5
Waktu (ms)
Gambar IV-3 Kebutuhan Waktu Inferensi terhadap Jumlah Gen
Jumlah Relasi Lauritzen-Spiegelhalter
Likelihood Weighting
Markov Chain Monte Carlo
Gambar IV-4 Kebutuhan Waktu Inferensi terhadap Jumlah Relasi
Memori (KB)
25000 20000 15000 10000 5000 0 2
3
4
5
6
7
8
9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 Jumlah Gen
Lauritzen-Spiegelhalter
Likelihood Weighting
Markov Chain Monte Carlo
Gambar IV-5 Kebutuhan Memori Inferensi terhadap Jumlah Gen
IV-11
Memori (KB)
25000 20000 15000 10000 5000
13 9
12 9
11 7
10 5
91
79
67
54
38
28
15
5
0
Jumlah Relasi Lauritzen-Spiegelhalter
Likelihood Weighting
Markov Chain Monte Carlo
Gambar IV-6 Kebutuhan Memori Inferensi terhadap Jumlah Relasi
Dari Gambar IV-6, dapat dilihat pula bahwa dari sisi kebutuhan memori, pertambahan jumlah relasi memberikan pengaruh yang sama bagi kebutuhan memori ketiga algoritma dengan pertambahan jumlah gen. Kebutuhan memori untuk melakukan inferensi pada kedua algoritma approximate inference relatif tidak terpengaruh oleh pertambahan jumlah relasi. Memori yang dibutuhkan juga jauh lebih kecil bila dibandingkan dengan teknik exact inference. Pada algoritma Lauritzen-Spiegelhalter, pertambahan jumlah relasi mengakibatkan pertambahan kebutuhan memori yang pesat. Hasil pengujian load test secara rinci dapat dilihat pada lampiran. 4.2.2.2 Pengujian Performansi Algoritma Approximate Inference Pada sistem berbasis pengetahuan, diimplementasikan dua algoritma approximate inference yaitu likelihood weighting dan Markov Chain Monte Carlo. Untuk melakukan pembandingan performansi kedua algoritma dilakukan pengukuran kebutuhan resources berupa waktu dan memori yang dibutuhkan saat inferensi serta bagaimana distribusi probabilitas perkiraan yang dihasilkan bila dibandingkan dengan distribusi sebenarnya. Untuk melakukan pengukuran perbedaan distribusi probabilitas ini, distribusi dibandingkan dengan menggunakan nilai distribusi sebenarnya yang diperoleh melalui teknik exact inference. Pada pengujian ini, ingin dilihat pula pengaruh jumlah evidences dan sampel terhadap performansi algoritma. Dari kasus uji pada load test, telah dilakukan pula pengujian untuk melihat sejauh mana pengaruh pertambahan jumlah gen dan relasi terhadap bagaimana kedua algoritma mendekati nilai probabilitas sebenarnya. Dalam grafik pada Gambar IV-7 dan Gambar IV-8, dapat dilihat bahwa algoritma likelihood weighting memiliki nilai KL distance yang konstan terhadap pertambahan jumlah gen dan relasi. Sedangkan, algoritma Markov
IV-12
Chain Monte Carlo pada jumlah gen dan relasi yang sedikit belum menghasilkan distribusi yang mendekati distribusi sebenarnya sebaik likelihood weighting. Kedekatan distribusi meningkat seiring dengan pertambahan jumlah gen dan relasi. Ketika distribusi yang dihasilkan sudah mendekati distribusi sebenarnya pun, nilai KL distance yang dihasilkan masih lebih besar dari nilai KL distance likelihood weighting. Nilai KL distance algoritma likelihood weighting berkisar antara 0.0008 hingga 0.0036. Sedangkan nilai KL distance untuk Markov Chain Monte Carlo berkisar antara 0.0357 hingga 0.1334. Dari grafik pada Gambar IV-9 dan Gambar IV-10, dapat dilihat bahwa perubahan jumlah gen dan relasi memberikan pengaruh yang sama pada nilai symmetric KL distance kedua algoritma. Secara umum, dapat dilihat bahwa nilai symmetric KL distance yang dimiliki algoritma likelihood weighting masih jauh lebih baik dari algoritma Markov Chain Monte
KL Distance
Carlo.
0,1600 0,1400 0,1200 0,1000 0,0800 0,0600 0,0400 0,0200 0,0000 4
6
8
10
12
14
16
18
Jumlah Node Likelihood Weighting
Markov Chain Monte Carlo
KL Distance
Gambar IV-7 Nilai KL Distance terhadap Pertambahan Jumlah Simpul
0,1600 0,1400 0,1200 0,1000 0,0800 0,0600 0,0400 0,0200 0,0000 5
9
15
21
28
34
38
Jumlah Relasi Likelihood Weighting
Markov Chain Monte Carlo
Gambar IV-8 Nilai KL Distance terhadap Pertambahan Jumlah Relasi
45
Symmetric KL Distance
IV-13
0,3000 0,2500 0,2000 0,1500 0,1000 0,0500 0,0000 4
6
8
10
12
14
16
18
Jumlah Simpul Likelihood Weighting
Markov Chain Monte Carlo
Symmetric KL Distance
Gambar IV-9 Nilai Symmetric KL Distance terhadap Pertambahan Jumlah Simpul
0,3000 0,2500 0,2000 0,1500 0,1000 0,0500 0,0000 5
9
15
21
28
34
38
45
Jumlah Relasi Likelihood Weighting
Markov Chain Monte Carlo
Gambar IV-10 Nilai Symmetric KL Distance terhadap Pertambahan Jumlah Relasi
Pengujian yang terlebih dahulu dilakukan adalah menguji bagaimana pengaruh evidences terhadap performansi sistem. Sebagai kasus uji, digunakan data jaringan regulatori genetik paling kompleks yang masih dapat diinferensi dengan teknik exact inference. Dari tahap pengujian sebelumnya, diketahui bahwa data tersebut adalah data jaringan regulatori genetik yang melibatkan 9 buah gen dan 45 buah relasi yang bila direkonstruksi menjadi Bayesian network, graf yang terbentuk melibatkan 18 buah simpul. Setiap simpul yang ada dapat merupakan simpul evidences atau simpul query. Oleh karena itu, dengan kasus uji awal ini, untuk menguji proses inferensi terhadap query, dapat divariasikan jumlah evidences dari nol hingga 17 evidences. Kasus-kasus uji tersebut ekivalen dengan jumlah simpul query sebanyak 18 hingga satu simpul. Gambar IV-11 menggambarkan grafik antara kebutuhan memori ketiga algoritma dengan pertambahan jumlah evidences. Secara umum, sesuai hasil load test, dapat dilihat bahwa kedua algoritma approximate inference membutuhkan memori yang lebih kecil
IV-14
dibandingkan dengan algoritma exact inference. Diantara kedua algoritma approximate inference, dapat dikatakan bahwa jumlah memori yang dibutuhkan relatif konstan terhadap jumlah evidences. Namun, dari grafik, pada suatu kasus uji, algoritma yang memberikan performansi yang lebih baik tidak selalu sama. Dengan proses perata-rataan, dari hasil pengujian, diketahui bahwa kebutuhan memori algoritma likelihood weighting adalah 80% kebutuhan memori algoritma Markov Chain Monte Carlo. Hal ini mendukung hasil pengujian pada tahap sebelumnya yang menyatakan bahwa perbedaan kebutuhan memori antara kedua algoritma approximate inference yang digunakan tidak
Memori (KB)
terlalu signifikan.
8000 7000 6000 5000 4000 3000 2000 1000 0 0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
Jumlah Evidences Lauritzen-Spiegelhalter
Likelihood Weighting
Markov Chain Monte Carlo
Gambar IV-11 Kebutuhan Memori terhadap Pertambahan Jumlah Evidences
3000 Waktu (ms)
2500 2000 1500 1000 500 0 0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
Jumlah Evidences Lauritzen-Spiegelhalter
Likelihood Weighting
Markov Chain Monte Carlo
Gambar IV-12 Kebutuhan Waktu terhadap Pertambahan Jumlah Evidences
Dari Gambar IV-12, dapat dilihat bahwa waktu inferensi algoritma likelihood weighting relatif konstan terhadap pertambahan jumlah evidences. Sedangkan, untuk kedua algoritma lainnya, kebutuhan waktu menurun seiring dengan pertambahan jumlah evidences. Walaupun kebutuhan waktu inferensi untuk algoritma Markov Chain Monte
IV-15
Carlo menurun, namun waktu inferensi untuk kasus-kasus uji yang diberikan masih lebih lama dibandingkan dengan algoritma likelihood weighting. Kebutuhan waktu algoritma likelihood weighting untuk melakukan inferensi hanya sekitar 7% dari kebutuhan waktu algoritma Markov Chain Monte Carlo. Pada pembandingan distribusi probabilitas, dari grafik pada Gambar IV-13, dapat dilihat bahwa nilai KL distance untuk algoritma likelihood weighting relatif konstan terhadap pertambahan jumlah evidences. Sedangkan, untuk algoritma Markov Chain Monte Carlo, nilai KL distance lebih bervariasi dan tidak dapat ditemukan keteraturannya terhadap jumlah evidences yang diberikan. Secara umum, diketahui bahwa nilai KL distance untuk algoritma likelihood weighting berkisar antara 0.001 hingga 0.009. Sedangkan, nilai KL distance untuk algoritma Markov Chain Monte Carlo memiliki jangkauan yang jauh lebih besar karena bervariasi antara 0.026 hingga 0.26. Dari grafik pada Gambar IV-14, dapat dilihat pula bahwa pertambahan jumlah evidences juga memberikan pengaruh yang sama terhadap nilai symmetric KL distance.
0,3 KL Distance
0,25 0,2 0,15 0,1 0,05 0 0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
Jumlah Evidences Likelihood Weighting
Markov Chain Monte Carlo
Symmetric KL Distance
Gambar IV-13 Nilai KL Distance terhadap Pertambahan Jumlah Evidences
0,8 0,7 0,6 0,5 0,4 0,3 0,2 0,1 0 0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
Jumlah Evidences Likelihood Weighting
Markov Chain Monte Carlo
Gambar IV-14 Nilai Symmetric KL Distance terhadap Pertambahan Jumlah Evidences
IV-16
Setelah dilakukan pengujian untuk melihat pengaruh jumlah evidences, dilakukan pengujian untuk melihat bagaimana pengaruh jumlah sampel terhadap performansi kedua algoritma approximate. Untuk melakukan pengujian ini, dipilih satu kasus uji dari pengujian pengaruh evidences dimana kedua algoritma memberikan performansi yang paling mendekati dari sisi perbedaan distribusi probabilitas. Dari grafik pada Gambar IV-13, dapat dilihat bahwa kedua algoritma memberikan nilai KL distance yang paling dekat perbedaannya pada kasus uji dimana terdapat lima evidences untuk 18 simpul yang ada. Oleh karena itu, kasus uji ini dipilih sebagai kasus uji dasar untuk melakukan pengujian pengaruh jumlah sampel. Pada pengujian pengaruh jumlah sampel, divariasikan jumlah sampel yang dibangkitkan dari 50 sampel hingga nampak keteraturan dari besaran-besaran yang diukur. Dari Gambar IV-15, dapat dilihat bahwa kebutuhan memori kedua algoritma relatif tidak terpengaruh terhadap pertambahan jumlah sampel yang dibangkitkan. Dari grafik tersebut, dapat dilihat pula bahwa algoritma likelihood weighting memiliki kebutuhan memori yang lebih sedikit bila dibandingkan dengan algoritma Markov Chain Monte Carlo. Bila dirata-rata, algoritma likelihood weighting menggunakan memori sekitar 75% dari kebutuhan memori algoritma Markov Chain Monte Carlo. Waktu yang dibutuhkan untuk melakukan inferensi dengan kedua algoritma juga relatif konstan terhadap pertambahan jumlah sampel. Dari Gambar IV-16 dapat dilihat bahwa meskipun kedua algoritma memiliki kebutuhan waktu yang konstan terhadap pertambahan
jumlah
sampel
yang
dilakukan,
algoritma
likelihood
weighting
membutuhkan waktu inferensi yang jauh lebih kecil bila dibandingkan dengan algoritma Markov Chain Monte Carlo. Kebutuhan waktu algoritma likelihood weighting hanya sekitar 6% dari kebutuhan waktu inferensi algoritma Markov Chain Monte Carlo.
500 400 300 200 100
95 0 10 00
90 0
85 0
80 0
75 0
70 0
65 0
60 0
55 0
50 0
45 0
40 0
35 0
30 0
25 0
20 0
15 0
0 50 10 0
Memori (KB)
600
Jumlah Sampel Likelihood Weighting
Markov Chain Monte Carlo
Gambar IV-15 Kebutuhan Memori terhadap Pertambahan Jumlah Sampel
IV-17
Waktu (ms)
2500 2000 1500 1000 500
50 10 0 15 0 20 0 25 0 30 0 35 0 40 0 45 0 50 0 55 0 60 0 65 0 70 0 75 0 80 0 85 0 90 0 95 0 10 00
0
Jumlah Sampel Likelihood Weighting
Markov Chain Monte Carlo
0,07 0,06 0,05 0,04 0,03 0,02 0,01 0 50 10 0 15 0 20 0 25 0 30 0 35 0 40 0 45 0 50 0 55 0 60 0 65 0 70 0 75 0 80 0 85 0 90 0 95 0 10 00
KL Distance
Gambar IV-16 Kebutuhan Waktu terhadap Pertambahan Jumlah Sampel
Jumlah Sampel Likelihood Weighting
Markov Chain Monte Carlo
0,16 0,14 0,12 0,1 0,08 0,06 0,04 0,02 0 50 10 0 15 0 20 0 25 0 30 0 35 0 40 0 45 0 50 0 55 0 60 0 65 0 70 0 75 0 80 0 85 0 90 0 95 0 10 00
Symmetric KL Distance
Gambar IV-17 Nilai KL Distance terhadap Pertambahan Jumlah Sampel
Jumlah Sampel Likelihood Weighting
Markov Chain Monte Carlo
Gambar IV-18 Nilai Symmetric KL Distance terhadap Pertambahan Jumlah Sampel
Dari sisi perbandingan distribusi probabilitas dengan distribusi sebenarnya, dapat dilihat dari Gambar IV-17 dan Gambar IV-18 bahwa kedua algoritma memiliki nilai KL distance dan symmetric KL distance yang relatif konstan terhadap pertambahan jumlah
IV-18
sampel. Dari grafik tersebut dapat dilihat pula bahwa nilai KL distance dan symmetric KL distance untuk algoritma likelihood weighting lebih kecil dan lebih stabil dibanding algoritma Markov Chain Monte Carlo. Hasil pengujian secara rinci dapat dilihat pada lampiran.
4.2.3 Analisis Hasil Pengujian Pada sub bab ini dijelaskan analisis dari hasil pengujian yang telah dilakukan. Pertama, analisis dilakukan terhadap hasil pengujian load test untuk mengetahui apakah hipotesis bahwa teknik exact inference tidak dapat digunakan untuk ranah permasalahan jaringan regulatori genetik benar. Setelah itu, dilakukan analisis pengujian performansi algoritma approximate inference untuk menyimpulkan algoritma mana yang lebih sesuai untuk ranah permasalahan jaringan regulatori genetik. 4.2.3.1 Load Test Diketahui bahwa pertambahan jumlah gen dan jumlah relasi memberikan pengaruh yang sama terhadap kebutuhan resources algoritma untuk melakukan inferensi. Hal ini disebabkan pertambahan jumlah gen yang berbanding lurus dengan pertambahan jumlah relasi regulasi yang terlibat pada jaringan regulatori genetik. Karena gen menjadi simpul pada Bayesian network dan relasi regulasi menjadi relasi antar simpulnya, bertambahnya simpul juga mengakibatkan bertambahnya jumlah relasi pada graf Bayesian network seperti terlihat pada Gambar IV-2. Pada pengujian, diketahui bahwa dari sisi kebutuhan waktu inferensi, pertambahan jumlah gen dan relasi relatif tidak berpengaruh pada algoritma likelihood weighting. Algoritma ini juga memiliki kebutuhan waktu yang lebih kecil dari kedua algoritma yang lain. Dari hasil pengujian, diketahui bahwa algoritma Lauritzen-Spiegelhalter maksimal dapat digunakan pada graf yang melibatkan 9 buah gen. Sedangkan, algoritma Markov Chain Monte Carlo masih dapat terus digunakan untuk graf-graf yang lebih kompleks. Padahal, algoritma Markov Chain Monte Carlo dan Lauritzen-Spiegelhalter memiliki kebutuhan waktu yang menaik dan berdekatan seiring dengan pertambahan jumlah gen dan relasi. Oleh karena itu, dapat disimpulkan bahwa kegagalan algoritma LauritzenSpiegelhalter melakukan inferensi bukan disebabkan oleh kebutuhan waktu algoritma tersebut. Dari hasil pengujian terhadap kebutuhan memori, dapat disimpulkan bahwa faktor inilah yang membedakan algoritma Lauritzen-Spiegelhalter dengan algoritma Markov Chain
IV-19
Monte Carlo. Algoritma Markov Chain Monte Carlo dan likelihood weighting memiliki kebutuhan memori untuk inferensi yang relatif konstan terhadap pertambahan kompleksitas graf. Sedangkan, kebutuhan memori inferensi Lauritzen-Spiegelhalter terus menaik secara eksponensial seiring dengan pertambahan kompleksitas graf. Peningkatan secara eksponensial ini berkaitan dengan bertambahnya nilai conditional probability yang harus dihitung. Teknik exact inference melakukan penghitungan secara tepat nilai-nilai probabilitas berdasarkan teorema Bayes. Hal inilah yang menyebabkan algoritma exact inference seperti Lauritzen-Spiegelhalter tidak dapat digunakan untuk graf yang kompleks. Secara keseluruhan, dapat disimpulkan bahwa hasil pengujian load test telah membuktikan bahwa hipotesis yang diambil benar. Dari tahap analisis, diperoleh hipotesis bahwa teknik exact inference tidak dapat digunakan untuk ranah permasalahan jaringan regulatori genetik karena besarnya kompleksitas Bayesian network yang dihasilkan dari data jaringan regulatori genetik. Secara lebih spesifik, dapat disimpulkan bahwa faktor yang menyebabkan teknik exact inference tidak dapat digunakan untuk ranah permasalahan jaringan regulatori genetik adalah kebutuhan memori yang meningkat secara eksponensial seiring dengan pertambahan kompleksitas data. 4.2.3.2 Pengujian Performansi Algoritma Approximate Inference Dari hasil load test, diketahui bahwa kebutuhan waktu inferensi algoritma likelihood weighting relatif konstan terhadap pertambahan jumlah gen dan relasi. Secara umum, algoritma ini lebih unggul dari algoritma Markov Chain Monte Carlo dari sisi kebutuhan waktu inferensi. Dari proses perata-rataan, diketahui bahwa algoritma ini hanya membutuhkan 5% waktu yang dibutuhkan algoritma Markov Chain Monte Carlo. Algoritma Markov Chain Monte Carlo membutuhkan waktu yang menaik seiring dengan pertambahan kompleksitas data. Perbedaan ini disebabkan adanya perbedaan dalam proses sampling yang dilakukan kedua algoritma. Pada algoritma likelihood weighting, proses sampling dilakukan untuk variabel-variabel non-evidences.
Proses
sampling
dilakukan
sesuai
urutan
topologi
dengan
mempertimbangkan nilai sampel variabel parents. Dengan demikian, jumlah variabel yang harus diperhatikan untuk menentukan state sampel suatu variabel hanya sejumlah parents yang dimiliki variabel tersebut. Sedangkan, pada algoritma Markov Chain Monte Carlo, proses sampling juga dilakukan untuk variabel-variabel non-evidences saja. Namun, untuk menentukan sampel suatu variabel, perlu diperhatikan state sampel variabel-variabel yang menjadi Markov blanket variabel tersebut. Markov blanket
IV-20
merupakan himpunan simpul parents, children dan parents dari children variabel. Dengan demikian, jumlah variabel yang harus dipertimbangkan untuk melakukan sampel lebih banyak daripada jumlah variabel pada proses sampling likelihood weighting. Dengan lebih banyaknya jumlah variabel yang harus diperhatikan, waktu yang dibutuhkan untuk menentukan state sampel juga semakin besar. Jumlah variabel yang harus diperhatikan ini juga semakin banyak seiring dengan pertambahan jumlah gen dan relasi yang terlibat. Pada kasus-kasus uji yang diberikan untuk melihat pengaruh pertambahan kompleksitas data, dapat dilihat bahwa jumlah parents maksimal yang dimiliki simpul relatif tidak berubah banyak seiring dengan pertambahan jumlah gen. Namun, jumlah children suatu simpul mengalami perubahan yang lebih signifikan. Hal ini mengakibatkan ukuran Markov blanket meningkat seiring dengan pertumbuhan gen dan relasi. Dengan demikian, proses sampling untuk algoritma Markov Chain Monte Carlo juga semakin kompleks seiring dengan pertambahan jumlah gen. Sementara, proses sampling algoritma likelihood weighting tidak terlalu terpengaruh. Dari hasil pengujian load test, diketahui pula bahwa pertambahan jumlah gen dan relasi tidak berpengaruh pada kebutuhan memori algoritma likelihood weighting dan Markov Chain Monte Carlo. Secara rata-rata, perbandingan kebutuhan memori algoritma likelihood weighting dan Markov Chain Monte Carlo juga hanya sekitar 9:10. Secara umum, proses penentuan state sampel pada proses sampling kedua algoritma sama-sama melibatkan operasi penghitungan yang sederhana sehingga tidak membutuhkan memori yang besar. Perbedaan kedua proses sampling hanya terletak pada jumlah state yang harus di-lookup sehingga hanya memunculkan perbedaan dari sisi waktu. Bagaimana kedua algoritma mendekati nilai distribusi sebenarnya juga dipengaruhi oleh jumlah gen dan relasi. Dari kasus uji-kasus uji pada load test, diketahui bahwa nilai KL distance algoritma likelihood weighting relatif konstan terhadap pertambahan jumlah gen dan relasi. Nilai KL distance algoritma ini juga jauh lebih kecil dari nilai KL distance algoritma Markov Chain Monte Carlo. Hal ini disebabkan karena pada proses sampling yang dilakukan likelihood weighting, setiap sampel diberi bobot sebanding dengan kemungkinan sampel tersebut muncul bersama evidences. Selain itu, proses sampling dilakukan sesuai urutan topologi graf. Dengan demikian, dapat dijamin bahwa distribusi sampel yang dihasilkan benar-benar mendekati distribusi yang sebenarnya, berapa pun jumlah simpul dan relasi yang ada. Nilai KL distance algoritma Markov Chain Monte Carlo jauh lebih besar daripada algoritma likelihood weighting. Selain itu, distribusi yang dihasilkan pada jumlah gen dan
IV-21
relasi yang sedikit cukup jauh dari distribusi sebenarnya. Kedekatan distribusi yang dihasilkan bertambah seiring dengan pertambahan jumlah gen dan relasi. Proses sampling yang dilakukan pada algoritma Markov Chain Monte Carlo menggunakan metode sampling Markov blanket. Perpindahan state dilakukan berdasarkan nilai yang dibangkitkan secara acak. Setiap sampel tidak diberi bobot sesuai dengan kemungkinan sampel tersebut muncul bersama evidences. Dengan demikian, tidak dapat ditentukan apakah distribusi sampel yang sudah dihasilkan sudah sesuai dengan distribusi sebenarnya. Pada jumlah simpul dan relasi yang sedikit, hanya terdapat sedikit kemungkinan state suatu graf. Kemungkinan distribusi sampel yang dihasilkan sesuai dengan distribusi sebenarnya lebih kecil dibandingkan pada graf dengan jumlah simpul dan relasi yang banyak. Berdasarkan pengukuran nilai symmetric KL distance kedua algoritma, dapat dilihat bahwa jarak distribusi hasil perkiraan algoritma likelihood weighting lebih dekat dengan distribusi sebenarnya bila dibandingkan dengan distribusi hasil algoritma Markov Chain Monte Carlo. Dengan demikian, dapat disimpulkan bahwa algoritma likelihood weighting memberikan performansi yang lebih baik daripada algoritma Markov Chain Monte Carlo dari sisi kedekatan distribusi. Selain itu, algoritma likelihood weighting juga memiliki performansi yang lebih stabil untuk berbagai variasi kompleksitas data. Dari analisis yang dilakukan, dapat disimpulkan bahwa dengan mempertimbangkan kompleksitas data, secara keseluruhan performansi algoritma likelihood weighting lebih baik dibandingkan Markov Chain Monte Carlo. Algoritma likelihood weighting selain memberikan kebutuhan memori konstan juga lebih cepat dan menghasilkan distribusi yang lebih dekat dengan distribusi sebenarnya pada berbagai kompleksitas data. Pertambahan jumlah evidences tidak mempengaruhi kebutuhan memori kedua algoritma. Tidak terdapat pula perbedaan yang signifikan antara kebutuhan memori algoritma likelihood weighting dan Markov Chain Monte Carlo. Pertambahan jumlah evidences mengakibatkan semakin sedikitnya jumlah variabel yang harus disampel. Hal ini berpengaruh pada operasi penghitungan yang harus dilakukan. Namun, operasi penghitungan yang harus dilakukan pada kedua algoritma bukan merupakan perhitungan yang membutuhkan banyak memori. Hal inilah yang menyebabkan pertambahan jumlah evidences tidak berpengaruh. Secara umum, dari sisi pengaruh pertumbuhan jumlah evidences terhadap kebutuhan memori, kedua algoritma memiliki performansi yang sebanding.
IV-22
Sesuai dengan analisis sebelumnya, perbedaan proses sampling kedua algoritma terletak pada jumlah state yang harus di-lookup sehingga hanya memunculkan perbedaan dari sisi waktu. Hal ini sesuai dengan hasil pengujian pengaruh pertambahan evidences. Untuk algoritma likelihood weighting, pertambahan evidences tidak mengakibatkan perubahan pada kebutuhan waktu. Dalam sampling algoritma likelihood weighting, pertambahan jumlah evidences hanya berpengaruh pada bobot tiap sampel, proses yang dilakukan masih tetap sama berapapun jumlah evidences yang ada. Pada algoritma Markov Chain Monte Carlo, pertambahan jumlah evidences berpengaruh pada jumlah kemungkinan state untuk graf. Semakin banyak evidences, semakin sedikit kemungkinan state untuk graf. Hasil operasi penghitungan yang harus dikelola sebanding dengan jumlah kemungkinan state. Dengan demikian, seiring dengan bertambahnya evidences, waktu yang dibutuhkan untuk melakukan proses sampling semakin menurun. Secara umum, dilihat dari sisi pengaruh pertambahan evidences terhadap kebutuhan waktu, algoritma likelihood weighting lebih unggul dibandingkan algoritma Markov Chain Monte Carlo. Algoritma ini memiliki kebutuhan waktu yang stabil terhadap peningkatan jumlah evidences. Selain itu, waktu yang dibutuhkan juga baru dapat disamai oleh algoritma Markov Chain Monte Carlo pada jumlah evidences yang besar. Pertambahan evidences tidak terlalu berpengaruh pada distribusi perkiraan yang dihasilkan algoritma likelihood weighting. Secara umum, distribusi yang dihasilkan algoritma likelihood weighting dapat dijamin kesesuaiannya dengan distribusi sebenarnya karena metode pembobotan sampel yang digunakan. Bobot yang dikenakan dijamin sesuai dengan kemungkinan sampel tersebut muncul bersama evidences. Pertambahan jumlah evidences mengakibatkan sampel yang sama diberi bobot yang berbeda. Namun, perbedaaan bobot ini tidak berpengaruh pada distribusi karena dilakukan proses normalisasi untuk memperoleh distribusi perkiraan. Pada algoritma Markov Chain Monte Carlo, tidak diperoleh distribusi yang stabil seperti halnya pada likelihood weighting seiring dengan pertumbuhan jumlah evidences. Tidak dapat ditemukan keteraturan antara pertambahan jumlah evidences dengan distribusi yang dihasilkan. Sesuai dengan analisis sebelumnya, pertambahan jumlah evidences mengurangi kemungkinan state yang dimiliki graf dan mengurangi operasi penghitungan yang harus dikelola. Namun, kualitas distribusi tetap tidak dapat dijamin karena masih bergantung pada perpindahan state yang dipilih. Dari analisis yang telah dilakukan, dapat disimpulkan bahwa dengan mempertimbangkan pengaruh jumlah evidences, algoritma likelihood weighting memiliki performansi yang
IV-23
lebih baik daripada algoritma Markov Chain Monte Carlo. Meskipun sebanding dari sisi kebutuhan memori, likelihood weighting memiliki kebutuhan waktu dan kualitas distribusi yang lebih stabil terhadap pertambahan jumlah evidences. Pertambahan jumlah sampel tidak berpengaruh terhadap kebutuhan memori dan waktu inferensi kedua algoritma. Distribusi yang dihasilkan juga tidak mengalami perubahan yang berarti seiring dengan pertambahan jumlah sampel. Hal ini mungkin disebabkan oleh data yang digunakan. Secara teori, pertambahan jumlah sampel mengakibatkan semakin baiknya distribusi yang dihasilkan oleh algoritma approximate inference. Namun, apabila distribusi yang ingin diperkirakan adalah distribusi yang mudah disampel, pertambahan jumlah sampel yang dihasilkan tidak mengakibatkan perubahan kualitas yang signifikan.
