《Artificial Intelligence：A Modern Approach》教学资源（PPT课件，英文版）Chapter 14-Bayesian networks

Bayesian networks Chapter 14 Section 1 -2

Bayesian networks Chapter 14 Section 1 – 2

Outline 。 Syntax Semantics

Outline • Syntax • Semantics

Bayesian networks A simple,graphical notation for conditional independence assertions and hence for compact specification of full joint distributions ·Syntax: -a set of nodes,one per variable a directed,acyclic graph(link~"directly influences") a conditional distribution for each node given its parents: P(X|Parents(Xi)) In the simplest case,conditional distribution represented as a conditional probability table (CPT)giving the distribution over X;for each combination of parent values

Bayesian networks • A simple, graphical notation for conditional independence assertions and hence for compact specification of full joint distributions • Syntax: – a set of nodes, one per variable – – a directed, acyclic graph (link ≈ "directly influences") – a conditional distribution for each node given its parents: P (Xi | Parents (Xi )) • In the simplest case, conditional distribution represented as a conditional probability table (CPT) giving the distribution over Xi for each combination of parent values

Example Topology of network encodes conditional independence assertions: Weather Cavity Toothache Catch Weatheris independent of the other variables Toothache and Catch are conditionally independent given Cavity

Example • Topology of network encodes conditional independence assertions: • Weather is independent of the other variables • Toothache and Catch are conditionally independent given Cavity

Example I'm at work,neighbor John calls to say my alarm is ringing,but neighbor Mary doesn't call.Sometimes it's set off by minor earthquakes.Is there a burglar? Variables:Burglary,Earthquake,Alarm,JohnCalls,MaryCalls Network topology reflects "causal"knowledge: A burglar can set the alarm off An earthquake can set the alarm off The alarm can cause Mary to call The alarm can cause John to call

Example • I'm at work, neighbor John calls to say my alarm is ringing, but neighbor Mary doesn't call. Sometimes it's set off by minor earthquakes. Is there a burglar? • Variables: Burglary, Earthquake, Alarm, JohnCalls, MaryCalls • Network topology reflects "causal" knowledge: – A burglar can set the alarm off – An earthquake can set the alarm off – The alarm can cause Mary to call – The alarm can cause John to call

Example contd. P(B) PE) Burglary 001 Earthquake 002 B E P(AIB,E) T T .95 T F .94 Alarm F T .29 F F .001 A P(JIA) A PMIA) JohnCalls T .90 MaryCalls T .70 .05 F .01

Example contd

Compactness A CPT for Boolean X;with k Boolean parents has 2k rows for the combinations of parent values B Each row requires one number p for X;=true (the number for X;=false is just 1-p) M If each variable has no more than k parents,the complete network requires O(n·2 numbers .l.e.,grows linearly with n,vs.O(2)for the full joint distribution For burglary net,1+1+4+2+2=10 numbers (vs.25-1 =31)

Compactness • A CPT for Boolean Xi with k Boolean parents has 2 k rows for the combinations of parent values • Each row requires one number p for Xi = true (the number for Xi = false is just 1-p) • If each variable has no more than k parents, the complete network requires O(n ·2 k ) numbers • I.e., grows linearly with n, vs. O(2n ) for the full joint distribution • For burglary net, 1 + 1 + 4 + 2 + 2 = 10 numbers (vs. 25 -1 = 31)

Semantics The full joint distribution is defined as the product of the local conditional distributions: n P(X1,..,Xn)=TTi=1P (Xil Parents(X)) e.g.,P(inmnan-bn-e) =P(jl a)P(m l a)P (al-b,-e)P(-b)P(-e)

Semantics The full joint distribution is defined as the product of the local conditional distributions: P (X1 , … ,Xn ) = πi = 1 P (Xi | Parents(Xi )) e.g., P(j  m  a  b  e) = P (j | a) P (m | a) P (a | b, e) P (b) P (e) n

Constructing Bayesian networks 1.Choose an ordering of variables X1,...,Xn 2.For i=1 to n add X;to the network select parents from X1,...,X such that P(Xil Parents(X))=P(XilX1,...Xi-1) This choice of parerits guarantees: P (X1....Xn)=Ti=1P(XilX1:....Xi-1) (chain rule) =mi=P(Xil Parents(X》 (by construction)

Constructing Bayesian networks • 1. Choose an ordering of variables X1 , … ,Xn • 2. For i = 1 to n – add Xi to the network – – select parents from X1 , … ,Xi-1 such that P (Xi | Parents(Xi )) = P (Xi | X1 , ... Xi-1 ) This choice of parents guarantees: P (X1 , … ,Xn ) = πi =1 P (Xi | X1 , … , Xi-1 ) (chain rule) = πi =1P (Xi | Parents(Xi )) (by construction) n n

Example Suppose we choose the ordering M,J,A,B,E MaryCalls JohnCalls P(J M)=P(J)?

• Suppose we choose the ordering M, J, A, B, E • P(J | M) = P(J)? Example