BAB II TINJAUAN PUSTAKA

Pada bab ini dijelaskan dasar teori yang digunakan dalam pengerjaan Tesis ini. Dasar

teori yang dijelaskan meliputi dasar teori mengenai sistem berbasis pengetahuan,

penalaran, Bayesian network, dan jaringan regulatori genetik. Selain itu dijelaskan pula

beberapa penelitian terdahulu mengenai penggunaan Bayesian network untuk jaringan

regulatori genetik.

2.1 Sistem Berbasis Pengetahuan

Sistem berbasis pengetahuan adalah suatu sistem yang memberikan solusi dari

permasalahan masukan pengguna dengan melakukan penalaran berdasarkan pengetahuan

yang direpresentasikan didalamnya [PUP94]. Komponen utama dari sistem berbasis

pengetahuan adalah basis pengetahuan dan mesin inferensi. Basis pengetahuan

merupakan kumpulan pengetahuan. Pengetahuan yang ada dalam basis pengetahuan

direpresentasikan dengan representasi pengetahuan tertentu. Beberapa representasi

pengetahuan yang sering digunakan adalah logika proposisi, rule, graf, dan tree.

Pengetahuan yang ada pada basis pengetahuan digunakan oleh mesin inferensi untuk

membentuk solusi dari permasalahan masukan pengguna.

Tidak semua ranah permasalahan cocok untuk diselesaikan dengan sistem berbasis

pengetahuan. Ranah permasalahan yang cocok untuk diselesaikan dengan sistem berbasis

pengetahuan adalah ranah permasalahan yang ill-structured sehingga tidak dapat

diselesaikan dengan metode prosedural. Selain itu, ranah permasalahan tersebut juga

biasanya memiliki pengetahuan yang masih dapat berubah atau masih mengandung

uncertainty.

Pembangunan sistem berbasis pengetahuan sangat bergantung pada permasalahan yang

ditangani. Kelas masalah menentukan metode pemecahan masalah yang selanjutnya

berpengaruh pada pemilihan representasi pengetahuan dan inferensi yang digunakan.

II-1

II-2

Menurut Stefik dan Hayes-Roth, permasalahan dapat diklasifikasikan kedalam kelas-

kelas sebagai berikut:

1. Interpretation: diberikan input observasi atau data dari sensor untuk

menyimpulkan deskripsi dari situasi.

2. Monitoring: diberikan hasil observasi untuk menentukan penanganan masalah.

Penanganan masalah dibangun melalui pembandingan observasi dengan

sekumpulan hasil observasi sebelumnya.

3. Diagnosis: diberikan hasil observasi/gejala untuk menentukan system

malfunction.

4. Prediction: diberikan observasi berupa suatu kondisi untuk memprediksi akibat

dari kondisi tersebut.

5. Design: diberikan batasan-batasan yang digunakan untuk merancang solusi.

6. Planning: diberikan tujuan yang dicapai untuk merencanakan aksi yang harus

dilakukan untuk mencapai tujuan tersebut.

7. Debugging: diberikan system malfunction untuk membentuk solusi berupa cara

memperbaikinya.

8. Repair: dilakukan eksekusi rencana untuk melakukan perawatan sistem.

9. Instruction: gabungan dari diagnosis, debugging, dan repair.

10. Control: gabungan dari interpretation, prediction, repair, dan monitoring.

Sedangkan, menurut Clancey, permasalahan dapat dikalsifikasikan kedalam kelas-kelas

sebagai berikut:

1. Interpret: melakukan analisa/interpretasi terhadap sistem

a. Identify: mengenali state sistem berdasarkan input dan output sistem.

i. Monitor: melakukan pemeriksaaan untuk menemukan defek dari

sistem.

ii. Diagnose: melakukan debugging berdasarkan error yang

ditemukan untuk menemukan penyebabnya.

b. Predict: mensimulasikan output sistem berdasarkan input dan deskripsi

sistem.

II-3

c. Control: melakukan hindsight dengan mendefinisikan input sistem

berdasarkan output dan deskripsi sistem.

2. Construct: membangun atau memodifikasi sistem.

a. Specify: menentukan batasan-batasan state berdasarkan rancangan sistem.

b. Design: melakukan perancangan sistem berdasarkan batasan-batasan

sistem yang diberikan.

i. Plan: membuat perencanaan pembangunan struktur.

ii. Configure: melakukan pembangunan struktur.

c. Assemble: merealisasikan rancangan dengan melakukan assembling.

i. Modify: melakukan perbaikan berdasarkan instruksi.

Selain klasifikasi masalah, pemecahan masalah pun dibagi kedalam kelas-kelas sebagai

berikut:

1. Classification: Solusi dipilih dari himpunan solusi dari domain berupa himpunan

observasi dan himpunan solusi. Masalah yang diselesaikan merupakan subset

observasi yang dapat bersifat tidak lengkap. Hasil yang diberikan berupa satu

atau lebih solusi.

2. Construction: Solusi dibangun dari komponen-komponen yang diberikan.

3. Simulation: Solusi dibangun dengan melakukan simulasi bagaimana reaksi sistem

terhadap input tertentu.

2.2 Penalaran

Penalaran (reasoning) merupakan proses penarikan kesimpulan terhadap suatu ranah

permasalahan. Dua metode reasoning yang sering digunakan yaitu penalaran secara

induktif dan deduktif. Penalaran induktif dilakukan dengan menarik kesimpulan melalui

penelitian sejumlah observasi Sedangkan penalaran deduktif dilakukan dengan menarik

kesimpulan berdasarkan premis-premis yang sudah tersedia. Dalam intelejensia buatan,

penalaran deduktif dan induktif digunakan untuk dua task utama yaitu pembelajaran

(learning) dan inferensi. Pembelajaran dapat dilakukan dengan menggunakan penalaran

deduktif dan induktif. Sedangkan inferensi dilakukan dengan melakukan penalaran

deduktif.

II-4

2.2.1 Pembelajaran

Suatu agen dikatakan belajar dari experience E berdasarkan performance measure E

untuk task T bila performansinya untuk melakukan task T tersebut meningkat dengan

experience E bila diukur dengan performance measure P [MIT97]. Pembelajaran dapat

dilakukan dengan menggunakan penalaran deduktif maupun induktif.

Pembelajaran yang dilakukan dengan menggunakan penalaran induktif disebut sebagai

inductive learning. Pada inductive learning dilakukan pencarian hipotesis yang sesuai

dengan training data dengan melakukan generalisasi berdasarkan pola-pola yang terdapat

pada training data. Dengan kata lain, hipotesis dilakukan melalui penalaran induktif.

Pembelajaran dapat pula dilakukan dengan menggunakan penalaran deduktif berdasarkan

prior knowledge. Pembelajaran ini disebut sebagai analytical learning. Pada analytical

learning, prior knowledge digunakan sebagai premis dan setiap training data merupakan

fakta pada penalaran deduktif yang dilakukan. Hasil dari penalaran deduktif merupakan

explanation. Explanation dari semua training data kemudian digeneralisasi untuk

memperoleh hipotesis. Hipotesis ini berupa penghilangan faktor yang tidak relevan pada

prior-knowledge. Tidak seperti inferensi, hasil dari proses pembelajaran tidak dapat

dipastikan kebenarannya.

2.2.2 Inferensi

Inferensi merupakan penarikan kesimpulan terhadap suatu fakta dari pengetahuan yang

dimiliki. Inferensi digunakan pada sistem berbasis pengetahuan untuk memperoleh solusi.

Inferensi dilakukan dengan melakukan penalaran secara deduktif. Kesimpulan diperoleh

secara logika dengan menggunakan premis-premis tertentu. Inferensi diawali dengan

mendefinisikan premis-premis yang digunakan untuk mengambil kesimpulan.

Kesimpulan ditentukan dengan mengaplikasikan premis-premis tersebut terhadap fakta

yang ada di lingkungan. Hasil inferensi dipastikan sesuai dengan pengetahuan yang

direpresentasikan sebagai premis-premis.

Proses deduksi terdiri dari tiga tahap. Pertama, pelaku deduksi harus memahami arti dari

premis-premis yang ada. Kemudian, pelaku harus membuat kesimpulan yang valid

berdasarkan premis tersebut. Terakhir, pelaku harus melakukan evaluasi kesimpulan

untuk memeriksa validitas kesimpulannya. Hasil inferensi dipastikan sesuai dengan

pengetahuan yang direpresentasikan sebagai premis-premis. Hasil inferensi ini dapat

digunakan untuk menambah informasi yang sudah dimiliki dan dinyatakan sebagai

premis melalui proses pembelajaran.

II-5

2.3 Bayesian Network

Bayesian network merupakan representasi pengetahuan yang digunakan untuk melakukan

probabilistic reasoning. Probabilistic reasoning merupakan proses inferensi yang

dilakukan pada kondisi dimana terdapat uncertainty [RUS03]. Untuk melakukan

inferensi, dibangun sebuah model jaringan yang menggambarkan relasi antara variabel-

variabel yang ada. Proses inferensi dilakukan berdasarkan hukum-hukum yang ada pada

teori probabilitas.

2.3.1 Uncertainty dan Probabilistic Reasoning

Uncertainty adalah kondisi dimana suatu agen tidak dapat mengetahui seluruh informasi

yang dibutuhkan dari lingkungannya untuk dapat mengambil keputusan secara rasional.

Pada ranah permasalahan dimana terdapat uncertainty, pengetahuan yang dimiliki agen

hanya mampu memberikan nilai degree of belief pada suatu sentence. Degree of belief ini

menyatakan apa yang agen percaya mengenai kebenaran sentence tersebut dan bukan

nilai kebenaran sentence yang sebenarnya pada world. Kepercayaan agen tersebut

berdasarkan pada persepsi berupa evidences/observasi yang telah diterima agen. Degree

of belief dinyatakan sebagai nilai probabilitas.

Dalam probabilistic reasoning, setiap elemen dasar yang terlibat dan diberi nilai degree

of belief dinyatakan sebagai random variable. Random variable dapat dianggap sebagai

anggota dari world yang memiliki status awal tidak diketahui (unknown). Sentence

dinyatakan sebagai random variable yang sudah memiliki nilai tertentu. Random variable

dapat dibedakan menjadi tiga jenis berdasarkan ranah nilainya yaitu boolean random

variable yang memiliki nilai true dan false, discrete random variable dengan ranah nilai

diskrit, dan continuous random variable dengan ranah nilai kontinu.

Dalam probabilistic inference, terdapat dua jenis probabilitas yang digunakan yaitu prior

probability dan conditional probability. Prior probability disebut juga sebagai

unconditional probability atau marginal probability. Nilai probabilitas ini menyatakan

degree of belief agen terhadap suatu sentence pada saat tidak diketahui informasi lainnya.

Prior probability hanya berlaku pada saat agen belum memiliki persepsi berupa

evidence/observasi apapun.

Probabilitas semua kemungkinan nilai dari random variable disebut sebagai prior

probability distribution dari random variable tersebut. Join probability distribution

merupakan distribusi probabilitas yang dibentuk dengan melibatkan kombinasi nilai

probabilitas dari lebih dari satu random variables. Bila join probability distribution

II-6

dibentuk dengan melibatkan seluruh variabel yang ada di world, maka distribusinya

disebut sebagai full join probability distribution. Distribusi ini mendefinisikan

probabilitas dari setiap atomic event yang ada sehingga merupakan spesifikasi yang

lengkap tentang uncertainty agen pada world.

Untuk variabel yang kontinu, tidak mungkin dibangun tabel distribusi probabilitasnya

karena tidak terbatasnya nilai yang mungkin pada ranah nilai variabel tersebut. Sebagai

penggantinya, biasanya didefinisikan probabilitas random variable tersebut mengambil

suatu nilai x sebagai masukan fungsi parameter tertentu. Distribusi probabilitas untuk

variabel kontinu disebut sebagai probability density function.

Bila agen telah mendapatkan evidence berkaitan dengan random variable yang

sebelumnya tidak diketahui nilainya, prior probability tidak dapat lagi diterapkan dalam

probabilistic inference. Probabilitas yang dipakai untuk melakukan penalaran harus

berupa conditional probability. Probabilitas ini dinotasikan dengan dengan

dan b adalah sentence. Notasi tersebut menyatakan nilai probabilitas bila semua yang

diketahui (evidence) adalah b . Nilai conditional probability dihitung berdasarkan

teorema Bayes.

)|( baP a

a

2.3.2 Teorema Bayes

Teorema Bayes merupakan teorema yang menghubungkan conditional probability

dengan unconditional probability. Teorema ini digunakan untuk menghitung nilai

conditional/posterior probability bila diketahui observasi. Conditional probability dapat

didefinisikan sebagai formula dari unconditional probability dengan persamaan ( II-1).

)()()|(

BPBAPBAP ∧

=

( II-1)

Persamaan ( II-1) berlaku bila 0)( >= bBP . Selain itu, persamaan tersebut juga dapat

dituliskan dalam bentuk product rule sebagai berikut:

)()|()( BPBAPBAP =∧

( II-2)

Bentuk penulisan ini berdasarkan pada fakta bahwa agar A= dan B= b benar, B=

harus benar dan A= harus benar bila diketahui B= b benar. Hal ini ekivalen dengan:

a b

a

II-7

)()|()( APABPBAP =∧

( II-3)

Teorema Bayes menggabungkan kedua persamaan tersebut menjadi:

)()()|()|(

BPAPABPBAP =

( II-4)

Setiap term pada teorema Bayes memiliki nama konvensional sebagai berikut:

1. merupakan prior/marginal probability dari random variable A. )(AP

2. merupakan conditional probability variabel A bila terdapat evidence

mengenai variabel B.

)|( BAP

3. adalah conditional probability variabel B bila terdapat evidence

mengenai variabel A.

)|( ABP

4. adalah prior/marginal probability dari variabel B yang berfungsi sebagai

konstanta normalisasi untuk menjamin nilai probabilitas maksimal satu.

)(BP

Pernyataan hanya berlaku bila )|( BAP B adalah satu-satunya evidence yang ada. Bila

terdapat evidence tambahan C , maka degree of belief A adalah . )|( CBAP ∧

Teorema Bayes merupakan dasar dari probabilistic reasoning. Pembaharuan nilai

probabilistik bila diketahui evidence/observasi dilakukan dengan menggunakan teorema

ini.

2.3.3 Relasi Independensi dan Conditional Independence

Konsep lain yang digunakan dalam probabilistic reasoning adalah relasi independensi.

Dalam suatu ranah permasalahan, random variables yang terdefinisi di dalamnya, tidak

seluruhnya memiliki keterkaitan satu sama lain. Dua variabel yang tidak saling terkait

tidak saling mempengaruhi satu sama lainnya. Bila diketahui random variables X dan

saling tidak terkait, maka bila salah satu variabel tersebut menjadi evidence, nilai

probabilitas variabel yang lainnya tidak terpengaruh. Kondisi ini disebut sebagai

independensi.

Y

Independensi antara dua variabel X dan Y dapat dituliskan dalam persamaaan ( II-5).

II-8

)()(),()()|()()|(

YXYXYXYXYX

ΡΡ=ΡΡ=ΡΡ=Ρ

( II-5)

Asersi independensi biasanya berasal dari pengetahuan mengenai ranah permasalahan.

Independensi dapat mengurangi jumlah informasi yang dibutuhkan untuk membentuk full

join distribution secara signifikan.

Selain relasi independensi, dalam probabilistic inference terdapat pula relasi conditional

independence. Dua variabel memiliki relasi conditional independence bila kedua variabel

tersebut memiliki relasi independensi tetapi juga dipengaruhi oleh sebuah variabel yang

sama. Dengan demikian, ada tidaknya relasi independensi antar kedua variabel tersebut

bergantung pada ada tidaknya evidence mengenai variabel ketiga. Bila terdapat evidence

mengenai variabel ketiga, kedua variabel pertama tidak lagi bersifat independen. Sama

seperti relasi independensi, relasi conditional independence juga dapat membantu

mengurangi jumlah informasi yang dibutuhkan untuk membentuk full join distribution.

2.3.4 Konsep Bayesian Network

Untuk merepresentasikan ketergantungan antar variabel dan memberikan spesifikasi yang

singkat tentang full join probability distribution, digunakan struktur data yang disebut

sebagai Bayesian network.

Bayesian network merupakan sebuah graf berarah dimana setiap simpulnya memiliki

informasi nilai probabilitas. Bayesian network terdiri dari:

1. Himpunan random variables yang masing-masing direpresentasikan sebagai

simpul. Random variable dapat bersifat diskrit maupun kontinu.

2. Himpunan sisi berarah yang menghubungkan sepasang simpul. Sisi berarah dari

simpul X ke simpul Y , maka X disebut sebagai parent dari Y .

3. Setiap simpul memiliki conditional probability distribution

yang mengkuantisasi pengaruh dari parents simpul

tersebut.

iX

))(|( ii XParentsXP

4. Graf tidak memiliki siklus berarah sehingga harus merupakan directed acyclic

graph (DAG).

II-9

Topologi jaringan yang dibentuk oleh himpunan simpul dan sisi menggambarkan relasi

conditional independence yang ada pada ranah permasalahan. Sisi berarah yang ada

memiliki makna intuitif bahwa X memiliki pengaruh langsung pada Y . Pengaruh

langsung ini dengan mudah ditentukan oleh pakar pada ranah permasalahan tersebut.

Bila suatu variabel X memiliki relasi conditional independence dengan variabel Y bila

terdapat variabel Z , dalam topologi jaringan, relasi ini digambarkan dengan sisi berarah

dari variabel Z ke variabel X , serta dari variabel Z ke variabel Y . Kedua sisi berarah

tersebut menggambarkan pengaruh langsung variabel Z ke masing-masing variabel X

dan Y . Relasi conditional independence antara variabel X dan Y digambarkan dengan

tidak adanya sisi berarah diantara kedua variabel.

Setelah topologi jaringan terbentuk, data yang dibutuhkan untuk melalukan proses

inferensi hanyalah conditional probability distribution untuk setiap simpul bila terdapat

parents-nya. Kombinasi topologi jaringan dan conditional probability distributions ini

telah cukup untuk menentukan full join probability distributions pada ranah

permasalahan. Distribusi pada setiap simpul digambarkan dengan conditional probability

table (CPT). Untuk variabel yang tidak memiliki parent, CPT berisi prior probability

distribution. CPT hanya dapat digunakan untuk variabel diskrit. Setiap baris pada CPT

mengandung conditional probability untuk setiap nilai simpul untuk suatu conditioning

case. Conditioning case merupakan kombinasi nilai yang mungkin dari parents simpul

tersebut. Nilai probabilitas yang ada pada tiap baris harus bernilai satu bila dijumlahkan

karena entri-entri yang ada merepresentasikan himpunan kasus untuk variabel tersebut

secara exhaustive.

2.3.5 Dynamic Bayesian Network

Dynamic Bayesian network adalah salah satu perluasan dari Bayesian network yang

digunakan untuk merepresentasikan model probabilitas temporal. Pada model probabilitas

temporal, aspek dinamis dari permasalahan yang dimodelkan menjadi suatu aspek yang

diperhatikan. Aspek dinamis sendiri merupakan perubahan state dari suatu variabel.

Proses perubahan state dapat dilihat sebagai sekumpulan snapshots yang masing-masing

mendeskripsikan state permasalahan pada waktu tertentu. Tiap snapshot disebut sebagai

time slice yang terdiri dari sekumpulan random variable.

Pada dynamic Bayesian network, variabel dan relasi yang ada diantaranya direplikasi

pada tiap time slice-nya sedemikian sehingga merepresentasikan first-order Markov

process. Dalam first-order Markov process, tiap variabel hanya mungkin memiliki

II-10

parents dari time slice-nya atau time slice tepat sebelumnya. Dengan kata lain, kondisi

suatu variabel hanya dipengaruhi oleh variabel-variabel yang ada pada time slice

sebelumnya atau setelahnya.

Dynamic Bayesian network direpresentasikan sebagai Bayesian network yang direplikasi

setiap time slice-nya. Dari suatu time slice ke time slice selanjutnya terdapat model

transisi yang menggambarkan bagaimana nilai probabilitas suatu variabel berubah.

Bayesian network pada dynamic Bayesian network direplikasi hingga diperoleh snapshot

yang mencukupi observasi. Hasil dari replikasi tersebut membentuk suatu Bayesian

network sehingga proses inferensinya dapat dilakukan dengan inferensi Bayesian network

biasa.

2.4 Inferensi pada Bayesian Network

Untuk melakukan inferensi dengan Bayesian network, terdapat dua teknik yang dapat

digunakan yaitu exact inference dan approximate inference. Pada exact inference,

dilakukan perhitungan nilai-nilai probabilistik secara tepat berdasarkan hasil observasi.

Sedangkan, approximate inference tidak melakukan perhitungan nilai probabilistik secara

tepat.

2.4.1 Exact Inference pada Bayesian Network

Dalam probabilistic reasoning dilakukan penghitungan distribusi probabilitas posterior

untuk himpunan variabel query bila terdapat suatu event. Event didefinisikan sebagai

assignment nilai-nilai untuk himpunan variabel evidence. Bila X menyatakan variabel

query, menyatakan himpunan variabel evidence , menyatakan suatu event

tertentu yang diobservasi, dan

Ε mEE ,...,1 e

Υ adalah himpunan variabel nonevidence , maka

himpunan variabel yang lengkap dapat dinyatakan sebagai

lYY ,..,1

Υ∪Ε∪=Χ }{X .

Pemrosesan query merupakan penghitungan distribusi probabilitas posterior untuk

. )|( eXΡ

2.4.1.1 Inferensi dengan Enumerasi

),,( yeXΡ pada join probability distribution dapat dituliskan sebagai hasil kali dari

conditional probability yang ada pada jaringan. Dengan demikian, sebuah query dapat

dijawab dengan menggunakan Bayesian network melalui perhitungan sum of products

dari conditional probabilities pada jaringan.

II-11

Proses inferensi dengan enumerasi dilakukan dengan penelusuran depth first recursion

pada expression tree. Dengan demikian, kompleksitas ruang untuk algoritma ini adalah

atau linear terhadap jumlah variabel. Namun, kompleksitas waktu algoritma adalah

dengan d adalah arity dari variabel. Dengan demikian, kompleksitas waktu

algoritma masih bersifat eksponensial sehingga tidak memungkinkan diterapkan untuk

jaringan dengan jumlah variabel yang banyak. Selain itu, dengan penelusuran depth first

recursion pada expression tree banyak terdapat subekspresi yang diulangi

penghitungannya sehingga memperumit komputasi.

)(nO

)( ndO

2.4.1.2 Algoritma Variable Elimination

Algoritma untuk melakukan inferensi dengan enumerasi dapat disempurnakan dengan

mengeliminasi penghitungan ulang subekspresi pada expression tree. Hal ini dilakukan

dengan melakukan penghitungan satu kali saja dan menyimpan hasilnya untuk digunakan

kemudian. Salah satu algoritma yang mengaplikasikan ide ini adalah algoritma variable

elimination.

Algoritma variable elimination mengolah ekspresi perhitungan query dengan urutan dari

kanan ke kiri (bottom up pada expression tree). Hasil antara disimpan dan penghitungan

notasi sigma untuk suatu variabel dilakukan hanya untuk bagian ekspresi yang

bergantung pada variabel tersebut.. Setiap bagian ekspresi yang berupa conditional

probability ditandai dengan nama variabel yang berasosiasi dan disebut sebagai faktor.

Setiap vektor dinyatakan sebagai matriks conditional probability berukuran sesuai dengan

kemungkinan nilai variabel-variabel yang mempengaruhi ekspresi tersebut.

Pada algoritma variable elimination, setiap simpul daun pada expression tree yang bukan

merupakan variabel query atau evidence dapat dihilangkan. Secara umum, setiap variabel

yang bukan merupakan ancestor dari variabel query atau evidence tidak relevan terhadap

query sehingga dapat dihilangkan dalam penghitungan.

Algoritma variable elimination lebih efisien dibandingkan inferensi dengan enumerasi

karena mampu menghindari penghitungan berulang dari subekspresi dan menghilangkan

variabel yang tidak relevan. Kebutuhan waktu dan ruang untuk algoritma ini sangat

ditentukan oleh urutan eliminasi variabel dan struktur jaringan.

Untuk singly connected network/polytree dimana terdapat paling banyak satu path tidak

langsung antara dua simpul, kompleksitas waktu dan ruang algoritma variable

elimination adalah , linear terhadap ukuran jaringan. Ukuran jaringan dinyatakan )(nO

II-12

sebagai jumlah entri pada CPT. Sebaliknya, untuk multiply connected network, algoritma

ini memiliki kompleksitas waktu dan ruang . )( kndO

2.4.1.3 Algoritma Clustering

Algoritma variable elimination sederhana dan efisien bila digunakan untuk menjawab

query individual. Namun, algoritma ini tidak efisien bila digunakan untuk menghitung

probabilitas posterior seluruh variabel yang ada pada jaringan. Pada jaringan polytree,

dibutuhkan queries dengan cost untuk setiap query. Dengan demikian,

waktu yang dibutuhkan adalah . Untuk menghindarinya, dapat digunakan

algoritma clustering. Algoritma ini disebut juga sebagai algoritma junction tree dan dapat

mengurangi kompleksitas waktu hingga mencapai . Karena itu, algoritma ini

banyak digunakan pada kakas Bayesian network.

)(nO )(nO

)( 2nO

)(nO

Ide dasar dari clustering adalah menggabungkan simpul individual pada jaringan untuk

membentuk simpul cluster sedemikian sehingga jaringan yang ada berbentuk polytree.

Sebagai contoh, dua variabel Boolean digabungkan menjadi suatu simpul besar yang

memiliki nilai . FFFTTFTT ,,,

Untuk melakukan clustering dari directed acyclic graph, langkah-langkah yang harus

dilakukan adalah melakukan moralisasi graf, memasukkan evidences, melakukan

triangulasi, membentuk junction tree, dan mempropagasikan evidences yang ada.

Moralisasi graf dilakukan dengan menambahkan sisi diantara dua variabel yang memiliki

anak yang sama. Setelah itu, dilakukan penghilangan arah pada sisi untuk memperoleh

graf tak berarah. Triangulasi dilakukan untuk mengubah graf menjadi graf chordal. Pada

graf chordal, tiap cycle yang terdiri dari empat atau lebih simpul harus memiliki chord.

Chord merupakan sisi yang menghubungkan dua simpul yang tidak saling bersisian pada

suatu cycle. Setelah graf ditriangulasi, maximum spanning tree dari graf merupakan

junction tree. Evidences yang telah diperoleh kemudian dipropagasikan dengan

melakukan message passing.

Message passing pada junction tree dilakukan dari simpul daun ke akar. Untuk

melakukan message passing, hal pertama yang harus dilakukan adalah menginisialisasi

potensial untuk setiap cluster dan separator. Setelah potensial diinisialisasi, barulah

dilakukan message passing. Algoritma untuk melakukan message passing yang paling

efisien adalah algoritma clustering Lauritzen-Spiegelhalter versi Jensen [JIT96]. Pada

algoritma ini, tiap cluster mengelola degree of belief yang telah diperbaharui hingga saat

II-13

ini. Sedangkan, tiap separator mengelola message sebelumnya yang di-passing antara

cluster yang dipisahkan oleh separator tersebut. Setiap message baru yang di-passing

antar dua cluster yang dipisahkan oleh separator dibagi dengan nilai yang dikelola oleh

separator tersebut. Dalam implementasinya, algoritma Lauritzen-Spiegelhalter masih

membutuhkan komputasi yang intensif dan kadang tidak dapat diterapkan untuk

mengevaluasi jaringan yang berukuran besar [JIT96]

Algoritma clustering mengaplikasikan constraint propagation dimana constraints

meyakinkan bahwa cluster yang bertetangga tidak bertentangan dengan probabilitas

posterior dari variabel yang dimiliki oleh keduanya. Dengan bookkeeping yang baik,

algoritma ini dapat menghitung probabilitas posterior untuk semua variabel nonevidence

pada jaringan dalam waktu , dengan n adalah ukuran dari jaringan yang telah

dimodifikasi. Bila jaringan membutuhkan waktu dan ruang eksponensial dengan

algoritma variable elimination, maka CPT yang dibutuhkan pada jaringan yang di-cluster

juga dibangun dengan kompleksitas waktu dan ruang yang eksponensial yaitu .

)(nO

)( kndO

2.4.2 Approximate Inference pada Bayesian Network

Metode approximate inference muncul karena tidak mungkin dilakukan exact inference

pada Bayesian network yang besar atau memiliki struktur multiply connected network.

Algoritma-algoritma yang digunakan untuk melakukan approximate inference salah

satunya merupakan varian dari algoritma Monte Carlo. Algoritma Monte Carlo banyak

digunakan untuk memperkirakan kuantitas yang sulit untuk dihitung secara tepat.

Algoritma ini menggunakan metode sampling secara acak Oleh karena itu, akurasi

algoritma ini bergantung pada jumlah sampel yang dibangkitkan. Pada probabilistic

reasoning, sampling digunakan dalam perhitungan probabilitas posterior. Terdapat dua

kelompok algoritma Monte Carlo yaitu direct sampling dan Markov chain sampling.

2.4.2.1 Metode Direct Sampling

Elemen dasar dari algoritma sampling adalah pembangkitan sampel dari distribusi

probabilitas yang diketahui. Proses sampling acak yang paling sederhana pada Bayesian

network adalah membangkitkan event dari jaringan dimana tidak terdapat evidence yang

berkaitan dengan event tersebut hingga saat ini (empty network). Sampling dilakukan

pada setiap variabel secara bergantian sesuai urutan topologinya. Nilai distribusi

probabilitas sampel bergantung pada nilai yang telah diberikan pada variabel parent.

Kompleksitas ruang proses sampling ini sebanding dengan jumlah variabel pada Bayesian

II-14

network yaitu . Sedangkan, kompleksitas waktu proses sampling ini adalah

dengan k adalah jumlah parents.

)(nO )(knO

Dengan teknik pembangkitan sampel tersebut, setiap langkah sampling hanya bergantung

pada nilai yang telah diberikan untuk variabel parent, sehingga probabilitas suatu event

dibangkitkan dapat dinyatakan sebagai:

∏=

=n

iiinPS XparentsxPxxS

11 ))(|(),...,(

( II-6)

Ruas kanan persamaan ( II-6) sama dengan ruas kanan pada persamaan representasi join

probability distribution pada Bayesian network. Dengan demikian, query dapat dijawab

dengan menggunakan sampel.

Pada algoritma sampling, jawaban query dibuat dengan memperhitungkan sampel aktual

yang dibangkitkan. Nilai perkiraan probabilitas dihitung sebagai fraksi jumlah sampel

yang sesuai dengan query dari keseluruhan sampel.

Gambar II-1 Contoh Bayesian Network

Sebagai contoh, pada Gambar II-1, sampling dilakukan pertama kali pada variabel

Cloudy. Karena nilai probabilitas untuk Cloudy = true dan Cloudy = false sama, maka

variabel ini dapat disampel dengan nilai true atau false. Misalkan, nilai yang dipilih

adalah Cloudy = true. Sampling kemudian dilanjutkan ke variabel Sprinkler dengan

memperhitungkan nilai parent-nya yaitu Cloudy = true. Nilai probabilitas Sprinkler =

II-15

true, bila diketahui Cloudy = true adalah 0.1. Dengan demikian variabel Sprinkler di-

sampling dengan nilai false, begitu seterusnya. Untuk menghitung nilai probabilitas

query, misal Rain = true, dari seluruh sampel dihitung fraksi sampel yang memenuhi

Rain = true. Misal dari 100 sampel, terdapat 25 sampel dimana Rain = true. Dengan

demikian, nilai probabilitas Rain = true adalah 0.25.

2.4.2.2 Rejection Sampling

Rejection sampling adalah metode umum yang digunakan untuk menghasilkan sampel

dari distribusi yang sulit di-sampling. Metode ini dapat digunakan untuk menghitung

conditional probability . Algoritma rejection sampling pertama membangkitkan

sampel-sampel dari distribusi prior yang ada pada jaringan. Kemudian, algoritma

mengeliminasi sampel-sampel yang tidak sesuai dengan evidence. Terakhir, estimasi dari

diperoleh dengan menghitung seberapa sering

)|( eXP

)|( exXP = xX = muncul pada sampel-

sampel yang tersisa.

Misalkan pada Gambar II-1, ingin dilakukan inferensi untuk mengetahui nilai

probabilitas Rain = true, bila diketahui Sprinkler = true. Dari 100 sampel yang

dibangkitkan 50 memiliki nilai Sprinkler = true. Dari 50 tersebut, diketahui 20 sampel

memiliki nilai Rain = true. Dengan demikian, dapat disimpulkan probabilitas query

sebagai hasil normalisasi dari <20,30>. Sehingga, nilai probabilitas Rain = true bila

diketahui Sprinkler = true adalah 0.4.

Rejection sampling mampu memberikan estimasi yang konsisten terhadap nilai

probabilitas sebenarnya. Semakin banyak sampel yang sesuai, nilai estimasi probabilitas

semakin mendekati nilai probabilitas sebenarnya. Permasalahan utama rejection sampling

adalah algoritma ini mengeliminasi terlalu banyak sampel. Fraksi dari sampel yang

konsisten dengan evidence menurun secara eksponensial seiring dengan pertambahan

variabel evidence. Dengan demikian, metode ini tidak dapat digunakan untuk

permasalahan yang kompleks.

Kompleksitas waktu algoritma rejection sampling adalah untuk s jumlah sampel.

Sedangkan, kompleksitas ruangnya adalah .

)(sknO

)(snO

2.4.2.3 Likelihood Weighting

Likelihood weighting mampu mengeliminasi kelemahan rejection sampling dengan hanya

membangkitkan events yang konsisten dengan evidence. Algoritma ini pertama

II-16

menetapkan nilai untuk variabel evidence Ε . Kemudian, proses sampling dilakukan

hanya untuk variabel-variabel lainnya, yaitu variabel query X dan variabel nonevidence

. Dengan demikian, setiap event yang dibangkitkan konsisten dengan evidence. Setiap

event diberi bobot berdasarkan kemungkinan event tersebut muncul bersama dengan

evidence. Bobot ini dihitung sebagai hasil kali dari conditional probability dari setiap

variabel evidence bila diberikan parents-nya. Pada awal pembangkitan sampel, bobot

diberi nilai satu. Events dimana evidence sebenarnya jarang muncul memiliki bobot yang

kecil. Estimasi jawaban query dihitung dengan membentuk distribusi dimana setiap

elemennya diberi bobot dengan menjumlahkan bobot event yang sesuai dengan setiap

kemungkinan nilai variabel query dan dinormalisasi.

Υ

Sebagai contoh, misalkan pada Gambar II-1, ingin dilakukan inferensi untuk mengetahui

probabilitas variabel Rain bila diketahui Sprinkler = true, dan WetGrass = true. Pada saat

proses sampling, bobot pertama kali diset dengan nilai satu. Kemudian, dilakukan

sampling terhadap variabel Cloudy yang menghasilkan nilai Cloudy = true. Proses

kemudian dilanjutkan ke variabel Sprinkler. Variabel ini merupakan variabel evidence

sehingga bobot diset dengan nilai bobot sebelumnya dikalikan nilai probabilitas

Sprinkler=true bila diketahui Cloudy = true. Bobot menjadi bernilai 1 x 0.1 = 0.1.

Kemudian, proses dilanjutkan ke variabel Rain, dan menghasilkan nilai Rain = true.

Setelah itu, variabel WetGrass merupakan variabel evidence sehingga nilai bobot menjadi

0.1 x 0.99 = 0.099. Dengan demikian, diperoleh sampel [true,true,true,true] dengan bobot

0.099.

Sama seperti rejection sampling, likelihood weighting juga memberikan estimasi yang

konsisten terhadap distribusi probabilitas sebenarnya. Bobot yang ada menyatakan

perbedaan antara distribusi probabilitas estimasi dan sebenarnya. Kompleksitas waktu

algoritma ini adalah untuk s jumlah sampel. Sedangkan, kompleksitas ruangnya

adalah . Karena likelihood weighting menggunakan seluruh sampel yang

dibangkitkan, algoritma ini jauh lebih efisien dibandingkan dengan rejection sampling.

Namun, performansi algoritma menurun seiring dengan pertambahan jumlah variabel

evidence. Hal ini dapat dihindari bila variabel evidence muncul pada urutan bawah pada

urutan variabel.

)(sknO

)(snO

2.4.2.4 Markov Chain Monte Carlo

Teknik lain yang digunakan untuk melakukan approximate inference adalah Markov

Chain Monte Carlo (MCMC). Pada MCMC, suatu network dengan assignment nilai

II-17

semua variabelnya disebut sebagai state. State selanjutnya dibangkitkan dengan

melakukan sampling pada suatu variabel berdasarkan nilai Markov blanket-nya. Markov

blanket untuk suatu simpul didefinisikan sebagai variabel parent, child, dan child dari

parent-nya. Suatu simpul memiliki relasi conditional independence dengan variabel

lainya bila diberikan Markov blanket-nya. Pada MCMC, dilakukan proses sampling

setiap variabel secara bergantian, dengan nilai variabel evidences yang tetap. Pemilihan

variabel yang disampling dilakukan secara acak.

Sebagai contoh, untuk Bayesian network pada Gambar II-1 dengan evidences Sprinkler =

true, WetGrass = true, dapat didefinisikan empat state dalam MCMC seperti terlihat pada

Gambar II-2.

Gambar II-2 Contoh State Network pada MCMC

Untuk mengestimasi nilai peluang terjadinya hujan bila diketahui Sprinkler = true dan

WetGrass = true, dilakukan proses sampling untuk variabel Cloudy dan Rain berdasarkan

Markov blanket-nya dengan initial state tertentu. Misalkan , dari 100 state yang

dibangkitkan, terdapat 31 state dimana Rain = true, dan 69 state dimana Rain = false,

maka peluang terjadinya hujan bila diketahui Sprinkler = true dan WetGrass = true

adalah 0,31. Berdasarkan teorema, diketahui bahwa fraksi sampel yang dibangkitkan

tersebut sebanding dengan probabilitas posterior. Nilai probabilitas suatu state simpul bila

diberikan Markov blanket-nya diformulasikan dalam persamaan ( II-7).

II-18

∏∈

=)(

))(|())(|'())(|'(ij XChildrenz

jjiiii ZParentszPXParentsxPXmbxP

( II-7)

Kompleksitas waktu algoritma ini adalah untuk s jumlah sampel dan m jumlah

variabel pada Markov blanket. Sedangkan, kompleksitas ruangnya adalah .

)(smnO

)(snO

2.5 Jaringan Regulatori Genetik

Pada sub bab ini dijelaskan mengenai jaringan regulatori genetik yang ada pada

organisme. Konsep dasar jaringan regulatori genetik dijelaskan diikuti representasinya.

Pemodelan jaringan regulatori genetik dan fungsinya juga dijelaskan.

2.5.1 Konsep Dasar

Jaringan regulatori genetik adalah sekumpulan segmen DNA dalam sel yang berinteraksi

satu sama lain secara tidak langsung melalui RNA dan produk ekspresi berupa protein.

Selain itu, dalam jaringan regulatori genetik, sekumpulan segmen DNA ini juga

berinteraksi dengan substansi lain yang ada dalam sel. Interaksi yang terjadi mengatur

bagaimana tingkat suatu gen ditranskripsikan menjadi mRNA. Secara umum, tiap

molekul mRNA menjadi template dalam pembentukan protein. Pada beberapa kasus,

protein ini menjadi molekul pembentuk struktur yang berkumpul di dinding sel atau di

dalam sel dan membentuk struktur sel. Pada kasus yang lain, protein berfungsi sebagai

enzim yang berperan sebagai katalis dalam reaksi kimia tertentu. Namun, ada pula

beberapa protein yang hanya berfungsi untuk mengaktifkan gen lain sehingga terekspresi.

Protein ini berperan penting dalam jaringan regulatori genetik dan disebut sebagai faktor

transkripsi. Faktor transkripsi dapat pula menghambat terjadinya ekspresi suatu gen.

Setiap kali sel membelah, dua sel yang dihasilkan memiliki genom yang lengkap. Namun,

fungsi sel tersebut ditentukan oleh gen yang diaktifkan dan membentuk protein. Produk

yang dihasilkan dari ekspresi suatu gen pada sel dapat keluar dari sel dan melalui sel-sel

yang bersebelahan bergerak hingga mencapai suatu sel lain yang dituju untuk

mengaktifkan gen pada sel tersebut. Proses pengaktifan ini terjadi bila jumlah produk gen

yang dikirimkan melewati ambang tertentu.

II-19

2.5.2 Representasi

Jaringan regulatori genetik terdiri dari simpul-simpul yang berupa protein, mRNA yang

berkorespondensi dengan protein tersebut, dan senyawa yang terdiri dari ikatan protein-

protein. Sisi yang ada antara dua simpul dapat merepresentasikan reaksi molekular

individual, interaksi protein-protein, dan interaksi protein-mRNA yang pada akhirnya

menggambarkan bagaimana gen saling mempengaruhi satu sama lain. Pengaruh yang

disebabkan suatu gen pada gen lainnya dapat bersifat induktif maupun deduktif. Pengaruh

yang induktif berarti kenaikan level ekspresi suatu gen mengakibatkan naiknya level

ekspresi gen yang dipengaruhinya. Sebaliknya, pengaruh deduktif berarti kenaikan level

ekspresi gen mengakibatkan turunnya level ekspresi gen yang dipengaruhinya.

Sekumpulan sisi dapat membentuk rantai dependensi dengan siklus yang menggambarkan

adanya pengaruh balik. Struktur jaringan merupakan abstraksi dari dinamika kimia sistem

yang menggambarkan bagaimana suatu zat mempengaruhi zat-zat lainnya yang terkait.

Gambar II-3 Contoh Jaringan Regulatori Genetik

Contoh jaringan regulatori genetik dapat dilihat pada Gambar II-3. Pada jaringan

regulatori genetik, gen dapat dipandang sebagai simpul pada jaringan yang menerima

input berupa faktor transkripsi dan menghasilkan output berupa level ekspresi gen.

Simpul sendiri dapat dipandang sebagai suatu fungsi yang diperoleh dengan

mengkombinasikan fungsi-fungsi dasar pada input. Fungsi-fungsi ini telah

diinterpretasikan sebagai fungsi yang melakukan pemrosesan informasi dalam sel yang

membentuk perilaku sel. Cara kerja sel diatur oleh konsentrasi beberapa protein.

Konsentrasi beberapa protein inilah yang memberikan informasi spasial (lokasi dalam sel

atau jaringan) dan informasi temporal (siklus sel atau tahap pembangunannya) sel.

Setelah jaringan regulatori genetik dapat dipetakan, pekerjaan selanjutnya adalah

menentukan fungsi setiap simpul gen untuk membantu memahami perilaku sel.

II-20

Model matematis dari jaringan regulatori genetik telah dibangun agar perilaku sel yang

dimodelkan dapat dipelajari. Pada beberapa kasus, model dapat juga digunakan untuk

memprediksi kondisi sel pada suatu lingkungan percobaan tertentu. Beberapa model yang

sudah dibangun dapat memberikan prediksi kerja sel pada kondisi eksperimen yang

belum pernah dicoba secara riil. Setelah dilakukan percobaan riil, diketahui bahwa model

telah mampu memberikan prediksi yang akurat. Teknik pemodelan jaringan regulatori

genetik yang paling umum melibatkan penggunaan coupled ordinary differential

equations (coupled ODE). Beberapa teknik pemodelan lain yang dapat digunakan yaitu

Boolean network, jaringan Petri, Bayesian network, model grafis Gaussian, stokastik, dan

Process Calculi.

2.6 Penelitian Terkait

Pada bagian ini dipaparkan beberapa penelitian yang terkait dengan penggunaan Bayesian

network untuk jaringan regulatori genetik. Dari tinjauan pustaka yang dilakukan,

Bayesian network merupakan salah satu metode yang banyak digunakan untuk ranah

permasalahan jaringan regulatori genetik. Penggunaan Bayesian network pada ranah

permasalahan ini biasanya berkaitan dengan pemodelan dan simulasi jaringan regulatori

genetik.

Pemodelan jaringan regulatori genetik berkaitan dengan pembelajaran struktur jaringan

dari data ekspresi gen. Data ekspresi gen yang digunakan bisa dalam bentuk data

microarray ataupun dalam format arff. Pembelajaran struktur ini digunakan dengan

menggunakan algoritma pembelajaran Bayesian network. Metode Bayesian network juga

disukai untuk pemodelan jaringan regulatori genetik karena metode ini dapat dengan

mudah mengkombinasikan prior knowledge dengan struktur yang diperoleh dari hasil

pembelajaran. Sedangkan, untuk melakukan simulasi jaringan regulatori genetik,

digunakan algoritma inferensi Bayesian network seperti yang dikerjakan pada Tesis ini.

Berdasarkan tinjauan pustaka yang dilakukan, beberapa algoritma yang digunakan untuk

pembelajaran struktur jaringan regulatori genetik adalah FCI [SPI01] , GES [SPI01] , K2

with Bayesian scoring [COO92] , K2 with BIC scoring [COO92] , MWST [CHO68] , PC

[SPI01]. Dalam [NIE07] dilakukan perbandingan akurasi keenam algoritma tersebut

dalam melakukan pembelajaran struktur jaringan regulatori genetik dari data microarray.

Namun dari hasil eksperimen yang dilakukan, tidak ada algoritma yang dapat

direkomendasikan untuk melakukan pembelajaran struktur. [KHI07] melakukan

pembelajaran struktur jaringan regulatori genetik dengan algoritma Bayesian network

II-21

Metropolis-Hastings. Dari penelitian ini dapat disimpulkan bahwa algoritma Metropolis-

Hastings dapat direkomendasikan untuk pembelajaran struktur. Namun, dari sekian

banyak algoritma yang digunakan untuk pembelajaran struktur, dynamic Bayesian

network merupakan metode yang paling direkomendasikan. Hal ini disebabkan metode

ini dapat mengatasi relasi regulasi siklik yang ada pada jaringan regulatori genetik.

Dari tinjauan pustaka yang dilakukan, tidak banyak dijumpai penelitian yang

dipublikasikan yang memfokuskan pada pembelajaran Bayesian network untuk jaringan

regulatori genetik. Kebanyakan penelitian yang dipublikasikan memfokuskan

penelitiannya pada pembelajaran struktur jaringan regulatori genetik. Beberapa penelitian

yang membahas inferensi Bayesian network untuk jaringan regulatori genetik yaitu

[SUZ05] dan [WIL04].

Pada [SUZ05], untuk mensimulasikan jaringan regulatori genetik digunakan metode

Bayesian network dan neural network. Metode Bayesian network digunakan untuk

memperoleh confidence level nilai level ekspresi gen. Sedangkan nilai level ekspresi gen

dihitung dengan menggunakan neural network. Apabila simulasi hanya dilakukan dengan

menggunakan neural network saja, nilai level ekspresi gen yang dihasilkan dianggap

belum cukup prediktif. Namun, bila menggunakan Bayesian network saja, hanya dapat

diperoleh level ekspresi gen yang sudah dikuantisasi, bukan yang tepat. Oleh karena itu,

untuk memperoleh keduanya, digunakan teknik Bayesian network dan neural network

pada saat bersamaan. Pada [WIL04] digunakan teknik approximate inference untuk

melakukan inferensi pada graf Bayesian network dari jaringan regulatori genetik.

Algoritma yang digunakan untuk melakukan inferensi adalah algoritma dari kelompok

Markov Chain Monte Carlo. Namun, pembangunan dan kinerja sistem tidak dijelaskan

secara mendetail.