15-780: Graduate ArtificialIntelligenceBayesian networks: Construction andinferenceBayesian networks: NotationsLeLi SP(Lo) = 0.5P(Li | Lo) = 0.4P(Li | ¬Lo) = 0.7P(S | Lo) = 0.6P(S | ¬Lo) = 0.2Conditionalprobability tables(CPTs)ConditionaldependencyRandom variablesBayesian networks are directed acyclic graphs.Constructing a Bayesian network• How do we go about constructing a network for aspecific problem?• Step 1: Identify the random variables• Step 2: Determine the conditional dependencies• Step 3: Populate the CPTsCan be learned from observation data!A example problem• An alarm system B – Did a burglary occur? E – Did an earthquake occur? A – Did the alarm sound off? M – Mary calls J – John calls• How do we reconstruct the network for this problem?Factoring joint distributions• Using the chain rule we can always factor a jointdistribution as follows: P(A,B,E,J,M) = P(A | B,E,J,M) P(B,E,J,M) = P(A | B,E,J,M) P(B | E,J,M) P(E,J,M) = P(A | B,E,J,M) P(B | E, J,M) P(E | J,M) P(J,M) P(A | B,E,J,M) P(B | E, J,M) P(E | J,M)P(J | M)P(M)• This type of conditional dependencies can also berepresented graphically.A Bayesian networkEJ MA BNumber of parameters:A: 2^4B: 2^3E: 4J: 2M: 1A total of 31 parametersA better approach• An alarm system B – Did a burglary occur? E – Did an earthquake occur? A – Did the alarm sound off? M – Mary calls J – John calls• Lets use our knowledge of the domain!Reconstructing a networkAJ MB ENumber of parameters:A: 4B: 1E: 1J: 2M: 2A total of 10 parametersBy relying on domain knowledgewe saved 21 parameters!Constructing a Bayesian network:Revisited• Step 1: Identify the random variables• Step 2: Determine the conditional dependencies - Select on ordering of the variables - Add them one at a time - For each new variable X added select the minimal subset of nodesas parents such that X is independent from all other nodes in thecurrent network given its parents.• Step 3: Populate the CPTs - We will discuss this when we talk about density estimationsReconstructing a networkAJ MB ESuppose we wanted to adda new variable to thenetwork:R – Did the radio announcethat there was anearthquake?How should we insert it?RBayesian network: Inference• Once the network is constructed, we can use algorithmfor inferring the values of unobserved variables.• For example, in our previous network the only observedvariables are the phone call and the radioannouncement. However, what we are really interestedin is whether there was a burglary or not.• How can we determine that?Inference• Lets start with a simpler question - How can we compute a joint distribution from thenetwork? - For example, P(B,¬E,A,J, ¬M)?• Answer: - That’s easy, lets use the networkComputing: P(B,¬E,A,J, ¬M)AJ MB EP(B)=.05P(E)=.1P(A|B,E) )=.95P(A|B,¬E) = .85P(A| ¬ B,E) )=.5P(A| ¬ B, ¬ E) = .05P(J|A) )=.7P(J|¬A) = .05P(M|A) )=.8P(M|¬A) = .15P(B,¬E,A,J, ¬M) =P(B)P(¬E)P(A | B, ¬ E)P(J | A)P(¬M | A)= 0.05*0.9*.85*.7*.2= 0.005355Computing: P(B,¬E,A,J, ¬M)AJ MB EP(B)=.05P(E)=.1P(A|B,E) )=.95P(A|B,¬E) = .85P(A| ¬ B,E) )=.5P(A| ¬ B, ¬ E) = .05P(J|A) )=.7P(J|¬A) = .05P(M|A) )=.8P(M|¬A) = .15P(B,¬E,A,J, ¬M) =P(B)P(¬E)P(A | B, ¬ E)P(J | A)P(¬M | A)= 0.05*0.9*.85*.7*.2= 0.005355We can easily compute acomplete joint distribution.What about partialdistributions? Conditionaldistributions?Inference• We are interested in queries of the form: P(B | J,¬M)• This can also be written as a joint:• How do we compute the new joint?),,(),,(),,(),|(MJBPMJBPMJBPMJBP¬¬+¬¬=¬AJ MB EComputing partial joints),,(),,(),,(),|(MJBPMJBPMJBPMJBP¬¬+¬¬=¬Sum all instances with these settings (thesum is over the possible assignments to theother two variables, E and A)Computing: P(B,J, ¬M)AJ MB EP(B)=.05P(E)=.1P(A|B,E) )=.95P(A|B,¬E) = .85P(A| ¬ B,E) )=.5P(A| ¬ B, ¬ E) = .05P(J|A) )=.7P(J|¬A) = .05P(M|A) )=.8P(M|¬A) = .15P(B,J, ¬M) =P(B,J, ¬M,A,E)+P(B,J, ¬M, ¬ A,E) +P(B,J, ¬M,A, ¬ E) +P(B,J, ¬M, ¬ A, ¬ E) =0.0007+0.00001+0.005+0.0003 = 0.00601Computing partial joints),,(),,(),,(),|(MJBPMJBPMJBPMJBP¬¬+¬¬=¬Sum all instances with these settings (the sum is over thepossible assignments to the other two variables, E and A)• This method can be improved by re-using calculations(similar to dynamic programming)• Still, the number of possible assignments is exponential inthe unobserved variables?• That is, unfortunately, the best we can do. General queryingof Bayesian networks is NP-completeInference in Bayesian networks ifNP complete (sketch)• Reduction from 3SAT• Recall: 3SAT, find satisfying assignments to thefollowing problem: (a ∨ b ∨ c) ∧ (d ∨ ¬ b ∨ ¬ c) …P(xi=1) = 0.5P(xi=1) = (x1 ∨ x2 ∨ x3)P(Y=1) = (x1 ∧ x2 ∧ x3 ∧ x4)What is P(Y)?YOther inference methods• Convert network to a polytree - In a polytree no two nodes havemore than one path between them - We can convert arbitrary networks toa polytree by clustering (grouping)nodes. For such a graph there is aalgorithm which is linear in the numberof nodes - However, converting into a polytreecan result in an exponential increasein the size of the CPTsAJMBEAJMBEStochastic inference• We can easily sample the jointdistribution to obtain possibleinstances1. Sample the free variable2. For every other variable: - If all parents have been sampled, sample based on conditionaldistributionWe end up with a new set ofassignments for B,E,A,J and Mwhich are a random sample fromthe jointAJ MB EP(B)=.05P(E)=.1P(A|B,E) )=.95P(A|B,¬E) = .85P(A| ¬ B,E) )=.5P(A| ¬ B, ¬ E) = .05P(J|A) )=.7P(J|¬A) = .05P(M|A) )=.8P(M|¬A) = .15Stochastic inference• We can easily sample the jointdistribution to obtain possibleinstances1. Sample the free variable2. For every other variable: - If all parents have been sampled, sample based on conditionaldistributionAJ MB EP(B)=.05P(E)=.1P(A|B,E) )=.95P(A|B,¬E) = .85P(A| ¬ B,E) )=.5P(A| ¬ B, ¬ E) = .05P(J|A) )=.7P(J|¬A) = .05P(M|A) )=.8P(M|¬A) = .15Its always possible tocarry out this samplingprocedure, why?Using sampling for inference• Lets revisit our problem: Compute P(B | J,¬M)• Looking at the samples we can cound: - N: total number of samples - Nc : total number of samples in which the condition holds (J,¬M) - NB: total number of samples where the joint is true (B,J,¬M)• For a large enough N -