Artificial Intelligence

Kecerdasan Buatan/ Artificial Intelligence

Bayesian Network Imam Cholissodin, S.Si., M.Kom.

Pokok Bahasan 1. 2. 3. 4.

Syntax & Semantics Compact conditional distributions Efficient Inference Latihan Individu + Tugas Kelompok

Syntax & Semantics  Bayesian Network :  Notasi graf yang menyatakan conditional independence dalam suatu domain.  Node menyatakan sebuah random variable.  Arc (directed edge) menyatakan hubungan kausal langsung (direct influence). Arahnya dari variable “sebab” ke variable “akibat”.  Node sibling menyatakan variable yang conditionally independent karena parent-nya.  Conditional distribution untuk setiap node terhadap parent-nya: P(Xi | Parents(Xi))  Tidak ada cycle di dalam Bayesian Network.

Syntax & Semantics  Contoh kedokteran gigi :  Topologi sebuah Bayesian Network hubungan conditional independence :



menyatakan

Keterangan :  

Weather independent dari semua variable lain. Toothache dan Catch conditionally independent karena Cavity.

Syntax & Semantics  Contoh lain :  Anto sedang di kantor. Tetangganya, John, menelpon mengatakan alarm anti-perampoknya bunyi. Tetangganya, Mary, tidak menelpon. Kadang-kadang alarmnya nyala karena gempa bumi. Apakah ada perampok di rumah Anto?  Variable dalam domain : Burglar, Earthquake, Alarm, JohnCalls, MaryCalls  Hubungan sebab akibat :    

Perampok bisa membuat alarm nyala. Gempa bumi bisa membuat alarm nyala. Alarm bisa membuat John menelpon. Alarm bisa membuat Mary menelpon.

Syntax & Semantics  Contoh Bayesian Network :

Syntax & Semantics  Rekonstruksi full joint distribution :  Bayesian Network adalah deskripsi lengkap sebuah domain.  Full joint distribution bisa diperoleh dari local conditional distribution :

Px1,..., xn   i 1 Pxi | Parentsxi  n



Contoh: hitung probabilitas John menelpon, Mary menelpon, alarm nyala, tidak ada perampok, tidak ada gempa bumi. P (j ∧ m ∧ a ∧ ¬b ∧ ¬e) = P (j |a)P (m|a)P (a|¬b, ¬e)P (¬b)P (¬e) = 0.9 × 0.7 × 0.001 × 0.999 × 0.998 = 0.00062

Syntax & Semantics 

Membangun Bayesian Network :  Bagaimana membangun sebuah Bayesian Network?  Sebuah algoritma:.  Pilih ordering variable X1, . . . , Xn  For i = 1 to n o Tambahkan Xi ke network o Pilih parent dari X1, . . . , Xi−1 shg. P(Xi | Parents(Xi )) = P(Xi | X1, . . . , Xi−1)  Agar Bayesian Network sah.. Xi harus conditionally independent terhadap semua X1, . . . , Xi−1 yang bukan anggota Parents(Xi) karena Parents(Xi).

Syntax & Semantics 

Chain rule & conditional independence :  Algoritma di slide sebelumnya menggunakan chain rule : P(A, B, C, D) = P(A|B, C, D)P(B, C, D) = P(A|B, C, D)P(B|C, D)P(C, D) = P(A|B, C, D)P(B|C, D)P(C|D)P(D)  Ini spt. membangun Bayesian Network dengan urutan D, C, B, A tanpa conditional independence.  Bagaimana jika, mis: A conditionally independent thd. B karena C dan D B conditionally independent thd. C karena D: P(A, B, C, D) = P(A|C, D)P(B|D)P(C|D)P(D)

Syntax & Semantics 

Contoh membangun Bayesian Network :  Mis. kita pilih urutan : MaryCalls, JohnCalls, Alarm, Burglar, Earthquake.

P(J | M) = P(J)? Tidak P(A | J , M) = P(A | J)? P(A | J , M) = P(A)? Tidak P(B | A, J , M) = P(B | A)? Ya P(B | A, J , M) = P(B)? Tidak P(E | B, A, J , M) = P(E | A)? Tidak P(E | B, A, J , M) = P(E | A, B)? Ya

Syntax & Semantics 

Naive vs. paranoid... :  Naive Bayes model Semua variable akibat dianggap saling conditionally independent karena variable sebab.  Full joint distribution (paranoid?) Semua random variable dianggap saling mempengaruhi Yang kita cari: analisa domain-specific yang menghasilkan informasi conditional independence yang benar!

Syntax & Semantics 

Contoh yang lebih rumit... :  Diagnosa awal: mobil mogok!  Testable node: nilainya bisa diukur.  Fixable node: nilainya bisa diatur.  Hidden node: hanya untuk menyederhanakan network-nya.

struktur

Syntax & Semantics 

Contoh yang lebih rumit... :  Menentukan nilai asuransi mobil...

Compact conditional distributions 

Deterministic nodes :  Conditional distribution sebuah node dgn. k parent exponential dlm. k .  Ada beberapa representasi yang lebih efisien → canonical distribution.  Conditional distribution dari suatu deterministic node bisa dihitung sepenuhnya dari nilai parent-nya.  Dengan kata lain, nilai probabilitasnya bisa dinyatakan sebagai suatu fungsi : X = f(Parents(X))  Misalnya, “hidden” variable pada contoh mobil mogok: No_charging = Alternator_broken ∨ Fanbelt_broken Battery_flat = Battery_dead ∨ No_charging  Nilainya diperoleh dari truth table ∨

Compact conditional distributions 

Noisy-OR Distribution :  Noisy-OR distribution mirip ∨ dalam logic, tapi ada uncertainty : Berapakah ketidakpastian sebuah variable “gagal” mengakibatkan proposition bernilai true?  Contoh : P(¬fever | cold , ¬flu, ¬malaria) = 0.6 P(¬fever | ¬cold , flu, ¬malaria) = 0.2 P(¬fever | ¬cold , ¬flu, malaria) = 0.1

Compact conditional distributions 

Variable dengan nilai kontinyu :  Bagaimana kalau nilai variable kontinyu? Tabel?  Gunakan canonical distribution : fungsi dengan parameter.  Contoh :

Diskrit : Subsidy?, Buys? Kontinyu : Harvest, Cost

Compact conditional distributions 

Variable diskrit, parent kontinyu :  Probabilitas dari Buy? jika diketahui Cost adalah “soft threshold” :

Distribusi probit adalah integral dari fungsi Gaussian :

 x    N 0,1x dx x



P(Buys? = true | Cost = c) = Φ((−c + µ)/σ)

Compact conditional distributions 

Variable kontinyu :



Model Linear Gaussian sering dipakai : PCost  c | Harvest  h, Subsidy?  true  N at h  bt ,  t c  2       c  a h  b 1 1 t t     exp    2  t  2   

Efficient Inference 

Inference by enumeration :  Mis. hitung probabilitas ada perampok jika John dan Mary menelpon. Pb | j, m   e a PbPePa | b, eP j | a Pm | a   Pb e Pea Pa | b, eP j | a Pm | a 



Perhatikan bahwa P(j | a)P(m | a) dihitung untuk setiap nilai e. Gunakan dynamic programming : hitung sekali, simpan hasilnya!

Efficient Inference 

Approximate inference :  Pendekatan lain: jangan hitung nilai persis, tapi cukup disample (Monte Carlo).  Ide dasar :  



Ambil N sample dari distribusi Bayes Net. Estimasi posterior probability dari query event : Pˆ Berapa kali query event “terjadi” dari N kali sample? Dibagi N. lim N  Pˆ konvergen terhadap P.

Efficient Inference 

Contoh sampling :

a. P(C,S,R,W)=?

b. P(C,S,R,~W)=?

Latihan individu 

Perhatikan Bayesian Network di bawah ini.

Tentukan nilai Peluang : a. John menelpon, Mary menelpon, alarm nyala, ada perampok, tidak ada gempa bumi. P (j ∧ m ∧ a ∧ b ∧ ¬e). b. John menelpon, Mary tidak menelpon, alarm nyala, ada perampok, ada gempa bumi. P (j ∧ ¬ m ∧ a ∧ b ∧ e).

Tugas Kelompok 

Buatlah minimal 1 case study unik dan penyelesaiannya dengan Bayesian Network !



Buatlah program prolog jika diketahui fakta-fakta berikut! No

Judul Buku

ISBN

1

Beginning Ogre 3D 1.7

1-2345-678

2

Programming for Newbies

9-9972-784

3

Pro Android Games

4-7899-099

4

Pro Code Igniter

7-3788-123

5

Learn CCNA in 23 days

9-7889-900

Kategori Games Development

Penerbit

Rating

Apress

5

Programming

O’Reilly

4

Apress

4

Apress

3

Sams

2

Games Development Web Programming Network & Security

Kemudian buat query buku bagus / recommended jika rating-nya lebih dari 3 !

Selesai