IKI30320 Kuliah Nov Ruli Manurung. Syntax & Semantics. Compact conditional distributions. Efficient Inference

Outline IKI30320 Kuliah 18 28 Nov 2007

IKI30320 Kuliah 18 28 Nov 2007

Ruli Manurung

Ruli Manurung

IKI 30320: Sistem Cerdas Kuliah 18: Bayesian Networks

Syntax & Semantics Compact conditional distributions Efficient Inference

Ruli Manurung

Ringkasan

Syntax & Semantics Compact conditional distributions

1

Syntax & Semantics

2

Compact conditional distributions

3

Efficient Inference

4

Ringkasan

Efficient Inference Ringkasan

Fakultas Ilmu Komputer Universitas Indonesia

28 November 2007

Review

Bayesian Network



Ruli Manurung

Ruli Manurung

Notasi graf yang menyatakan conditional independence dalam suatu domain.

Syntax & Semantics

Syntax & Semantics

Node menyatakan sebuah random variable.


Arc (directed edge) menyatakan hubungan kausal langsung (direct influence). Arahnya dari variable “sebab” ke variable “akibat”.

Compact conditional distributions Efficient Inference Ringkasan

Probability theory merangkum ketidakpastian sbg. bilangan. Full joint probability distribution = inference as addition Efficiency: absolute & conditional independence Bayes Rule: inference dengan conditional probability


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 (d.k.l. directed acyclic graph atau DAG)

Contoh kedokteran gigi IKI30320 Kuliah 18 28 Nov 2007 Ruli Manurung

Contoh lain

Topologi sebuah Bayesian Network menyatakan hubungan conditional independence:

Syntax & Semantics

Ruli Manurung Syntax & Semantics

Cavity

Weather




Efficient Inference

Efficient Inference

Ringkasan

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

Ringkasan

Toothache

Hubungan sebab akibat:

Catch

Perampok bisa membuat alarm nyala. Gempa bumi bisa membuat alarm nyala. Weather independent dari semua variable lain.

Alarm bisa membuat John menelpon.

Toothache dan Catch conditionally independent karena Cavity .

Alarm bisa membuat Mary menelpon.

Bayesian Network = ringkas

Contoh Bayesian Network IKI30320 Kuliah 18 28 Nov 2007


Burglary Syntax & Semantics Compact conditional distributions Efficient Inference Ringkasan

P(E)

P(B)

Ruli Manurung

B

E

P(A|B,E)

T T F F

T F T F

.95 .94 .29 .001

JohnCalls

Earthquake

.001

Ruli Manurung

.002

B

E

Syntax & Semantics

A


Alarm

Efficient Inference

J

M

Ringkasan

A

P(J|A)

T F

.90 .05

A P(M|A)

MaryCalls

T F

.70 .01

Conditional probability sebuah node dgn. k parent = O(2k ). Untuk n buah variable: O(n × 2k ) Bandingkan dengan O(2n ) untuk full joint distribution.

Membangun Bayesian Network

Rekonstruksi full joint distribution IKI30320 Kuliah 18 28 Nov 2007 Ruli Manurung Syntax & Semantics Compact conditional distributions Efficient Inference Ringkasan


Bayesian Network adalah deskripsi lengkap sebuah domain. Full joint distribution bisa diperoleh dari local conditional distribution: n P(X1 , . . . , Xn ) =

Π

i = 1 P(Xi |Parents(Xi ))

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

Sebuah algoritma: Syntax & Semantics Compact conditional distributions Efficient Inference Ringkasan

Syntax & Semantics Compact conditional distributions Efficient Inference Ringkasan

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)

Pilih ordering variable X1 , . . . , Xn For i = 1 to n Tambahkan Xi ke network Pilih parent dari X1 , . . . , Xi−1 shg. P(Xi |Parents(Xi )) = P(Xi |X1 , . . . , Xi−1 )

Contoh membangun Bayesian Network

Ruli Manurung

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.

2

Xi harus conditionally independent terhadap semua X1 , . . . , Xi−1 yang bukan anggota Parents(Xi ) karena Parents(Xi ).


Ruli Manurung

1

Agar Bayesian Network sah...

Chain rule & conditional independence IKI30320 Kuliah 18 28 Nov 2007

Bagaimana membangun sebuah Bayesian Network?

Ruli Manurung

Mis. kita pilih urutan: MaryCalls, JohnCalls, Alarm, Burglar , Earthquake. MaryCalls JohnCalls


Alarm


Burglary 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

Naive vs. paranoid...

Mulailah dari penyebab



Ruli Manurung

Ruli Manurung

MaryCalls JohnCalls

Syntax & Semantics Compact conditional distributions Efficient Inference Ringkasan

Naive Bayes model

Syntax & Semantics

Semua variable akibat dianggap saling conditionally independent karena variable sebab.

Alarm


Burglary

Efficient Inference

Full joint distribution (paranoid?) Semua random variable dianggap saling mempengaruhi.

Earthquake

Ringkasan

Menentukan conditional independence sulit untuk arah non-causal.

Yang kita cari: analisa domain-specific yang menghasilkan informasi conditional independence yang benar!

Menghitung conditional probability sulit untuk arah non-causal. Ukuran Bayesian Network pun lebih besar: 1+2+4+2+4=13 nilai Conditional independence lebih intuitif pada causal model! Kesimpulan: mulai dari variable “sebab” dulu.

Contoh yang lebih rumit... IKI30320 Kuliah 18 28 Nov 2007 Ruli Manurung Syntax & Semantics Compact conditional distributions

Contoh yang LEBIH rumit...

Diagnosa awal: mobil mogok! Testable node: nilainya bisa diukur Fixable node: nilainya bisa diatur Hidden node: hanya untuk menyederhanakan struktur network-nya battery age


Ruli Manurung

battery meter

no oil

ExtraCar VehicleYear SeniorTrain MakeModel

DrivingSkill DrivingHist

Antilock DrivQuality

no gas

fuel line blocked

oil light

gas gauge

car won’t start

dipstick

Airbag

Ruggedness

starter broken

CarValue HomeBase

Accident Theft OwnDamage

Cushioning

lights

Mileage

RiskAversion

Ringkasan

no charging

battery flat

SocioEcon Age GoodStudent

Efficient Inference

battery dead

Menentukan nilai asuransi mobil...


fanbelt broken

alternator broken


MedicalCost

OtherCost

LiabilityCost

OwnCost

PropertyCost

AntiTheft

Deterministic nodes

Noisy-OR Distribution

IKI30320 Kuliah 18 28 Nov 2007 Ruli Manurung Syntax & Semantics Compact conditional distributions Efficient Inference Ringkasan


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. Dkl, nilai probabilitasnya bisa dinyatakan sebagai suatu fungsi: X = f (Parents(X ))

Ruli Manurung Syntax & Semantics Compact conditional distributions Efficient Inference Ringkasan

Misalnya, “hidden” variable pada contoh mobil mogok: No_charging = Alternator _broken ∨ Fanbelt_broken Battery _flat = Battery _dead ∨ No_charging Nilainya diperoleh dari truth table ∨

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 Cold F F F F T T T T

Flu F F T T F F T T

Malaria F T F T F T F T

P(Fever ) 0.0 0.9 0.8 0.98 0.4 0.94 0.88 0.988

P(¬Fever ) 1.0 0.1 0.2 0.02 = 0.2 × 0.1 0.6 0.06 = 0.6 × 0.1 0.12 = 0.6 × 0.2 0.012 = 0.6 × 0.2 × 0.1

Jumlah parameter linier thd. jumlah parent

Variable dengan nilai kontinyu

Ruli Manurung Syntax & Semantics Compact conditional distributions

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

Harvest

IKI30320 Kuliah 18 28 Nov 2007 Ruli Manurung

1


Efficient Inference

Efficient Inference

Ringkasan

Ringkasan

Cost

Buys?

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

Probabilitas dari Buy ? jika diketahui Cost adalah “soft threshold”:

0.8 P(buys | c)


Variable diskrit, parent kontinyu

0.6 0.4 0.2 0 0

2

4

6 Cost c

8

10

12

Distribusi R probit adalah integral dari fungsi Gaussian: Φ(x) = −∞ x N(0, 1)(x)dx P(Buys? = true | Cost = c) = Φ((−c + µ)/σ)

Variable kontinyu

Inference by enumeration




Ruli Manurung

P(c | h, subsidy) 0.4 0.35 0.3 0.25 0.2 0.15 0.1 12 0.05 10 0 8 6 0 2 4 4 6 2 Harvest h 8 10 Cost c 12 0

Mis. mau hitung probabilitas ada perampok jika John dan Mary menelpon. P P P(b|j, m) = α e Pa P(b)P(e)P(a|b, e)P(j|a)P(m|a) P = αP(b) e P(e) a P(a|b, e)P(j|a)P(m|a)

Syntax & Semantics

P(b) .001


P(e) .002

Efficient Inference

P( a|b,e) .05

P(a|b,e) .95

Ringkasan

Model Linear Gaussian sering dipakai:

P( e) .998

P(j|a) .90

P(j| .05

a)

P(m|a) .70

P(m| a) .01

P( a|b, e) .06

P(a|b, e) .94

P(j|a) .90

P(j| .05

a)

P(m|a) .70

P(m| .01

a)

P(Cost = c|Harvest = h, Subsidy ? = true) = =

N(at h + bt , σt )(c) 0 1 1 exp @− √ 2 σt 2π

c − (at h + bt ) σt

Perhatikan bahwa P(j|a)P(m|a) dihitung untuk setiap nilai e. Gunakan

!2 1 A

dynamic programming: hitung sekali, simpan hasilnya!

Approximate inference IKI30320 Kuliah 18 28 Nov 2007



Contoh sampling P(C) .50

Ruli Manurung

Pendekatan lain: jangan hitung nilai persis, tapi cukup di-sample (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. ˆ konvergen terhadap P limN→∞ P

Cloudy

Syntax & Semantics Compact conditional distributions Efficient Inference

C P(S|C) T .10 F .50

Rain

Sprinkler

Ringkasan

Wet Grass

S R P(W|S,R) T T F F

T F T F

.99 .90 .90 .01

C P(R|C) T .80 F .20

Contoh sampling

Contoh sampling


Efficient Inference

C P(S|C) T .10 F .50

Rain

Sprinkler

C P(R|C) T .80 F .20

Compact conditional distributions Efficient Inference

C P(S|C) T .10 F .50

Sprinkler

Rain

C P(R|C) T .80 F .20

Rain

C P(R|C) T .80 F .20

Ringkasan

Wet Grass

Wet Grass

S R P(W|S,R)

S R P(W|S,R)

T T F F

T T F F

T F T F

.99 .90 .90 .01

Contoh sampling IKI30320 Kuliah 18 28 Nov 2007

P(C) .50

Ruli Manurung

.99 .90 .90 .01

P(C) .50

Ruli Manurung

Cloudy

Syntax & Semantics

C P(S|C) T .10 F .50

T F T F

Contoh sampling


Efficient Inference

Cloudy

Syntax & Semantics

Ringkasan


P(C) .50

Ruli Manurung

Cloudy



P(C) .50

Rain

Sprinkler

Ringkasan

Cloudy

Syntax & Semantics

C P(R|C) T .80 F .20

Compact conditional distributions Efficient Inference

C P(S|C) T .10 F .50

Sprinkler

Ringkasan

Wet Grass

Wet Grass

S R P(W|S,R)

S R P(W|S,R)

T T F F

T T F F

T F T F

.99 .90 .90 .01

T F T F

.99 .90 .90 .01

Contoh sampling

Contoh sampling


Efficient Inference

C P(S|C) T .10 F .50

Rain

Sprinkler

C P(R|C) T .80 F .20

Rain

Sprinkler

Wet Grass

S R P(W|S,R)

S R P(W|S,R)

T T F F

T T F F

T F T F

.99 .90 .90 .01

Ruli Manurung

Ringkasan

Efficient Inference

C P(S|C) T .10 F .50

Ringkasan


Efficient Inference


Wet Grass

Ringkasan


Cloudy

Syntax & Semantics

Ringkasan

Syntax & Semantics

P(C) .50

Ruli Manurung

Cloudy



P(C) .50

Bayes Net cocok utk. representasi (causal) conditional independence Mulai dari variable penyebab, tambahkan variable akibat Compact conditional distribution dengan representasi canonical Exact inference bisa dipercepat dengan dynamic programming Approximate inference bisa dilakukan dengan sampling

T F T F

.99 .90 .90 .01

C P(R|C) T .80 F .20

IKI30320 Kuliah Nov Ruli Manurung. Syntax & Semantics. Compact conditional distributions. Efficient Inference

Recommend Documents