ppt - CSE, IIT Bombay

Download Report

Transcript ppt - CSE, IIT Bombay

CS621/CS449
Artificial Intelligence
Lecture Notes
Set 7: 29/10/2004
Instructor: Prof. Pushpak Bhattacharyya
13/08/2004
CS-621/CS-449 Lecture Notes
Outline
• Bayesian Belief Networks
• Example BBN
29/10/2004
CS-621/CS-449 Lecture Notes
Prof. Pushpak Bhattacharyya
IIT Bombay
Bayesian Belief Networks
• BBNs : Data Structures for probabilistic
inferencing
• Example (from Russel & Norvik)
A’s house has a burglar alarm. The alarm goes
off when a burglar visits; but, it also goes off
when an earthquake occurs. B & C are
neighbours. B always calls A when the alarm
goes off, but also calls A sometimes wrongly,
when the doorbell rings. C sometimes misses
calling A, since he cannot hear the alarm, his
TV being too loud.
29/10/2004
CS-621/CS-449 Lecture Notes
Prof. Pushpak Bhattacharyya
IIT Bombay
Random variables
• We need to model the situation.
• Note that B makes +ve mistakes and C makes
–ve mistakes
• Random variables (all Boolean variables) :
T
 Burglar visit : B
F
 Earthquake occurs : E
 Alarm goes off : A
 B calls A : BA
 C calls A : CA
29/10/2004
CS-621/CS-449 Lecture Notes
Prof. Pushpak Bhattacharyya
IIT Bombay
Definition of BBN
• A BBN is a DAG (Directed Acyclic Graph) where each
node represents a random variable along with its CPT
(Conditional Probability Table). An edge from X to Y
depends on X. X is called the parent and Y is called
the child.
• CPT: If a node Y has parents X1, X2, … Xm, then each
row in the CPT records the values of Xis and the final
column gives the value of P(Y| X1, X2, … Xm).
• For the Boolean case, the CPT of Y will have 2m rows.
29/10/2004
CS-621/CS-449 Lecture Notes
Prof. Pushpak Bhattacharyya
IIT Bombay
Features of BBNs
• Topology of BBN – captures dependencies
• Models the most obvious dependencies, intuitively
seen from the data.
• Not all factors & events recorded.
– Influences of these captured in CPT
– Hidden nodes in BBNs
• No edge b/w 2 nodes  Independent events
• CPT row sum = 1
29/10/2004
CS-621/CS-449 Lecture Notes
Prof. Pushpak Bhattacharyya
IIT Bombay
Example BBN Topology
P(B)
0.6
A
T
F
0.4
P(BA)
1.0
0.03
positive
mistakes
29/10/2004
P(E)
P(~B)
E
B
P(~BA)
0.0
0.97
BA
A
CA
P(~E)
0.002 0.998
B
T
T
E
T
F
P(A)
0.95
0.94
P(~A)
0.05
0.06
F
F
T
F
0.2
0.001
0.8
0.999
A P(CA) P(~CA)
T 0.95
F 0.0
CS-621/CS-449 Lecture Notes
0.05
1.0
Prof. Pushpak Bhattacharyya
IIT Bombay