[AIMA] Russel, Stuart J., Peter Norvig, "Artificial Intelligence, A Modern Approach" 3rd Ed., Prentice Hall, New Jersey, 2010
KI091322 Kecerdasan Buatan Materi 13: Learning Probabilistic Models (Bayesian Network) Teknik Informatika, Fakultas Teknologi Informasi Institut Teknologi Sepuluh Nopember Surabaya 2012 Pengembangan Bahan Ajar sebagai Pendukung Student Centered-Learning (SCL) melalui e-Learning : Share ITS
Daftar Materi 1.
Pengenalan Intelligent Agents, Uninfomed Search (pencarian tanpa informasi tambahan) 2. Informed Search (Heuristics) 3. Local Search & Optimization (pencarian dengan optimasi) 4. Adversarial Search (pencarian dengan melihat status pihak lainnya) 5. Constraint Satisfaction Problems (pencarian dengan batasan kondisi) 6. Reasoning: propositional logic 7. Reasoning: predicate logic 8. Reasoning: first order logic 9. Reasoning: inference in first order logic (forward-backward chaining untuk inference) 10. Learning Probabilistic Models (1+2) 2
Latar Belakang • Learning Probabilistic Models = solusi yang diambil dari ketidakpastian kondisi • Kurangnya informasi di problem nyata • Solusi dari problem nyata dapat ditemukan jika ada pembelajaran kemungkinan kejadian • Langkah praktis: buat representasi problem nyata menjadi model dugaan berdasarkan probabilitas (probabilistic inference ) • Pendekatan dasar: teknik Bayesian 3
Ketidakpastian (Uncertainty) Didefinisikan At = ke bandara t menit sebelum penerbangan Apakah kejadian At membuat penumpang tidak terlambat? Permasalahan: jalan macet, ban bocor dan semacamnya Kemungkinan dugaan kejadian: “A25 memungkinkan penumpang tidak terlambat penerbangan JIKA tidak ada kecelakaan di jalan, tidak ada kemacetan, tidak ada hujan, tidak terjadi ban bocor, dll.” (A1440 juga memungkinkan tepat waktu tetapi harus bermalam hari sebelumnya di hotel bandara …)
Keputusan dengan Ketidakpastian Kondisi Semisal dugaan kemungkinan P(A25 jadi on time | …) P(A90 jadi on time | …) P(A120 jadi on time | …) P(A1440 jadi on time | …)
= 0.04 = 0.70 = 0.95 = 0.9999
Keputusan yang diambil bergantung pada preferences untuk missing flight vs. waktu tunggu di bandara, etc. – Utility theory is used to represent and infer preferences – Decision theory = probability theory + utility theory
Probabilitas • Probabilitas koin (bagian depan, head, dan belakang, tail)
1 P(COIN = tail) = 2 1 P(tail) = 2
6
Probabilitas • Probabilitas penderita kanker
P(has cancer) = 0.02 Þ P(Ø has cancer) = 0.98
7
Probabilitas Gabung, Joint Probability • Variasi kejadian (event): cancer, test result – Berdasarkan data di lapangan (misal 1000 pasien)
P(has cancer, test positive) Has cancer?
Test positive?
P(C,TP)
yes
yes
0.018
yes
no
0.002
no
yes
0.196
no
no
0.784
18 org + dari hasil tes
784 org - dari hasil tes
8
Probabilitas Bersyarat, Conditional Probability • Pertanyaan diagnosa: seberapa mungkin indikasi kanker ditemukan dengan tes?
P(has cancer | test positive) = ? Has cancer?
Test positive?
P(TP, C)
yes
yes
0.018
yes
no
0.002
no
yes
0.196
no
no
0.784
P(C | TP) = P(C, TP) / P(TP) = 0.018 / 0.214 = 0.084 9
Bayes Network (BN) vs Independence MODEL BN: P(cancer) and P(Test positive | cancer)
P(C, TP ) P(C) P(TP ) Independence
Bayes Network
PREDICTION BN: Hitung P(Test positive)
Cancer
DIAGNOSTIC REASONING BN: Hitung P(Cancer | test positive)
Cancer
versus
Test positive
Test positive 10
Notasi Grafik: Coin • N independent coin flips
X1
X2
Xn
• Tidak ada ketergantungan untuk setiap kejadian pelemparan: absolute independence 11
Example: Coin Flips X1
X2
Xn
h
0.5
h
0.5
h
0.5
t
0.5
t
0.5
t
0.5
Only distributions whose variables are absolutely independent can be represented by a Bayes’ net with no arcs. 12
Notasi Grafik: Traffic • Variables: – R: It rains – T: There is traffic
R
• Model 1: independence • Model 2 (better): rain causes traffic
T
• Model 2 lebih baik karena lebih sesuai dengan kondisi nyata 13
Example: Traffic R
+r
T r
+r
1/4
r
3/4
+t
3/4
t
1/4
+t
1/2
t
1/2
14
Independence • 2 variabel disebut independent jika: – Dengan kata lain:
– Tertulis :
15
Contoh: Independence • N pelemparan koin (fair, independent): h
0.5
h
0.5
h
0.5
t
0.5
t
0.5
t
0.5
16
Contoh Lain: Independence? T = temperature W = weather
T
P
warm
0.5
cold
0.5
T
W
P
T
W
P
warm
sun
0.4
warm
sun
0.3
warm
rain
0.1
warm
rain
0.2
cold
sun
0.2
cold
sun
0.3
cold
rain
0.3
cold
rain
0.2
W
P
sun
0.6
rain
0.4 17
Contoh Bayes Network: Sakit Gigi P(cavity) Cavity
P(catch | cavity)
1 parameter
P(toothache | cavity)
2 parameters
2 parameters
Catch
Headache
Versus: 23-1 = 7 parameters
P(toothache) = 0.108 + 0.012 + 0.016 + 0.064 = 0.2
18
Conditional Independence • P(Toothache, Cavity, Catch) has 23 – 1 = 7 independent entries • If I have a Toothache, a dental probe might be more likely to catch • But: if I have a cavity, the probability that the probe catches doesn't depend on whether I have a toothache: – P(+catch | +toothache, +cavity) = P(+catch | +cavity)
• The same independence holds if I don’t have a cavity: – P(+catch | +toothache, cavity) = P(+catch| cavity)
• Catch is conditionally independent of Toothache given Cavity: – P(Catch | Toothache, Cavity) = P(Catch | Cavity)
• Equivalent statements: – P(Toothache | Catch , Cavity) = P(Toothache | Cavity) – P(Toothache, Catch | Cavity) = P(Toothache | Cavity) P(Catch | Cavity) – One can be derived from the other easily
• Tertulis : 19
Contoh Bayes Network: Rumput & Air
20
Contoh Bayes Network: Rumput & Air • Apabila fakta bahwa kondisi rumput adalah basah, maka bagaimana kemungkinan terjadinya sprinkler menyala, dan kemungkinan terjadinya hujan. normalizing constant
kemungkinan
Contoh Bayes Network: Car
22
Contoh: Alarm Network • Variables – B: Burglary – A: Alarm goes off – M: Mary calls – J: John calls – E: Earthquake!
Earthquake
Burglary
Alarm
John calls
P(J | M) = P(J)? No P(A | J, M) = P(A | J)? P(A | J, M) = P(A)? No P(B | A, J, M) = P(B | A)? Yes P(B | A, J, M) = P(B)? No P(E | B, A ,J, M) = P(E | A)? No P(E | B, A, J, M) = P(E | A, B)? Yes
Mary calls
23
Example: Alarm Network B
P(B)
+b
0.001
b
0.999
Burglary
Earthqk
E
P(E)
+e
0.002
e
0.998
B
E
A
P(A|B,E)
+b
+e
+a
0.95
+b
+e
a
0.05
+b
e
+a
0.94
Alarm
John calls
Mary calls
A
J
P(J|A)
A
M
P(M|A)
+b
e
a
0.06
+a
+j
0.9
+a
+m
0.7
b
+e
+a
0.29
+a
j
0.1
+a
m
0.3
b
+e
a
0.71
a
+j
0.05
a
+m
0.01
b
e
+a
0.001
a
j
0.95
a
m
0.99
b
e
a
0.999
Bayes Net Semantics • A set of nodes, one per variable X
• A directed, acyclic graph
A1
An
• A conditional distribution for each node – A collection of distributions over X, one for each combination of parents’ values
X – CPT: conditional probability table – Description of a noisy “causal” process
A Bayes net = Topology (graph) + Local Conditional Probabilities 25
Probabilities in BNs • Bayes nets implicitly encode joint distributions – As a product of local conditional distributions – To see what probability a BN gives to a full assignment, multiply all the relevant conditionals together:
– Example:
• This lets us reconstruct any entry of the full joint • Not every BN can represent every joint distribution – The topology enforces certain conditional independencies 26
Bayes’ Nets • A Bayes’ net is an efficient encoding of a probabilistic model of a domain • Questions we can ask: – Inference: given a fixed BN, what is P(X | e)? – Representation: given a BN graph, what kinds of distributions can it encode? – Modeling: what BN is most appropriate for a given domain? 27
Causal Chains • This configuration is a “causal chain” X: Low pressure
X
Y
Z
Y: Rain
Z: Traffic
– Is X independent of Z given Y?
Yes! – Evidence along the chain “blocks” the influence 28
Common Cause • Another basic configuration: two effects of the same cause
Y
– Are X and Z independent? – Are X and Z independent given Y?
X
Z
Y: Alarm
X: John calls Z: Mary calls
Yes! – Observing the cause blocks influence between effects. 29
Common Effect • Last configuration: two causes of one effect (v-structures) – Are X and Z independent? • Yes: the ballgame and the rain cause traffic, but they are not correlated • Still need to prove they must be (try it!)
– Are X and Z independent given Y? • No: seeing traffic puts the rain and the ballgame in competition as explanation?
– This is backwards from the other cases
X
Z
Y X: Raining Z: Ballgame
Y: Traffic
• Observing an effect activates influence between possible causes. 30
The General Case • Any complex example can be analyzed using these three canonical cases • General question: in a given BN, are two variables independent (given evidence)? • Solution: analyze the graph
31
Reachability • Recipe: shade evidence nodes L
• Attempt 1: Remove shaded nodes. If two nodes are still connected by an undirected path, they are not conditionally independent
R
B
• Almost works, but not quite – Where does it break? – Answer: the v-structure at T doesn’t count as a link in a path unless “active”
D
T
32
Reachability (D-Separation) • Question: Are X and Y conditionally independent given evidence vars {Z}? – Yes, if X and Y “separated” by Z – Look for active paths from X to Y – No active paths = independence!
• A path is active if each triple is active:
– Causal chain A B C where B is unobserved (either direction) – Common cause A B C where B is unobserved – Common effect (aka v-structure) A B C where B or one of its descendents is observed
• All it takes to block a path is a single inactive segment
Active Triples
Inactive Triples
Example
Yes
R
B
T
T’
34
Example L Yes R
Yes
D
B
T
Yes T’ 35
Example • Variables: – R: Raining – T: Traffic – D: Roof drips – S: I’m sad
R
T
• Questions:
D
S Yes 36
Causality? • When Bayes’ nets reflect the true causal patterns: – Often simpler (nodes have fewer parents) – Often easier to think about – Often easier to elicit from experts
• BNs need not actually be causal – Sometimes no causal net exists over the domain – End up with arrows that reflect correlation, not causation
• What do the arrows really mean? – Topology may happen to encode causal structure – Topology only guaranteed to encode conditional independence
37
