1Bayesian NetworksBayesian NetworksRussell and Norvig: Chapter 14CMCS424 Fall 2003based on material from Jean-ClaudeLatombe, Daphne Koller and Nir FriedmanProbabilistic AgentProbabilistic Agentenvironmentagent?sensorsactuatorsI believe that the sunwill still exist tomorrowwith probability 0.999999and that it will be a sunnywith probability 0.6ProblemProblemAt a certain time t, the KB of an agent is some collection of beliefsAt time t the agent’s sensors make an observation that changes the strength of one of its beliefsHow should the agent update the strength of its other beliefs?Purpose of Bayesian NetworksPurpose of Bayesian NetworksFacilitate the description of a collection of beliefs by making explicit causality relations and conditional independence among beliefsProvide a more efficient way (than by using joint distribution tables) to update belief strengths when new evidence is observedOther NamesOther NamesBelief networksProbabilistic networksCausal networksBayesian NetworksA simple, graphical notation for conditional independence assertions resulting in a compact representation for the full joint distributionSyntax: a set of nodes, one per variable a directed, acyclic graph (link = ‘direct influences’) a conditional distribution for each node given its parents: P(Xi|Parents(Xi))2ExampleCavityToothache CatchWeatherTopology of network encodes conditional independence assertions:Weather is independent of other variablesToothache and Catch are independent given CavityExampleI’m at work, neighbor John calls to say my alarm isringing, but neighbor Mary doesn’t call. Sometime it’s set off by a minor earthquake. Is there a burglar? 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 callVariables: Burglar, Earthquake, Alarm, JohnCalls, MaryCallsA Simple Belief NetworkA Simple Belief NetworkBurglary EarthquakeAlarmMaryCallsJohnCallscauseseffectsDirected acyclicgraph (DAG)Intuitive meaning of arrowfrom x to y: “x has direct influence on y”Nodes are random variablesAssigning Probabilities to RootsAssigning Probabilities to RootsBurglary EarthquakeAlarmMaryCallsJohnCalls0.001P(B)0.002P(E)Conditional Probability TablesConditional Probability Tables0.950.940.290.001TFTFTTFFP(A|B,E)EBBurglary EarthquakeAlarmMaryCallsJohnCalls0.001P(B)0.002P(E)Size of the CPT for a node with k parents: ?Conditional Probability TablesConditional Probability Tables0.950.940.290.001TFTFTTFFP(A|B,E)EBBurglary EarthquakeAlarmMaryCallsJohnCalls0.001P(B)0.002P(E)0.900.05TFP(J|A)A0.700.01TFP(M|A)A3What the BN MeansWhat the BN Means0.950.940.290.001TFTFTTFFP(A|…)EBBurglary EarthquakeAlarmMaryCallsJohnCalls0.001P(B)0.002P(E)0.900.05TFP(J|A)A0.700.01TFP(M|A)AP(x1,x2,…,xn) = Πi=1,…,nP(xi|Parents(Xi))Calculation of Joint ProbabilityCalculation of Joint Probability0.950.940.290.001TFTFTTFFP(A|…)EBBurglary EarthquakeAlarmMaryCallsJohnCalls0.001P(B)0.002P(E)0.900.05TFP(J|…)A0.700.01TFP(M|…)AP(J∧M∧A∧¬B∧¬E)= P(J|A)P(M|A)P(A|¬B,¬E)P(¬B)P(¬E)= 0.9 x 0.7 x 0.001 x 0.999 x 0.998= 0.00062What The BN EncodesWhat The BN EncodesEach of the beliefs JohnCalls and MaryCallsis independent of Burglary and Earthquake given Alarm or ¬AlarmThe beliefs JohnCallsand MaryCalls are independent given Alarm or ¬AlarmBurglary EarthquakeAlarmMaryCallsJohnCallsFor example, John doesnot observe any burglariesdirectlyWhat The BN EncodesWhat The BN EncodesEach of the beliefs JohnCalls and MaryCallsis independent of Burglary and Earthquake given Alarm or ¬AlarmThe beliefs JohnCallsand MaryCalls are independent given Alarm or ¬AlarmBurglary EarthquakeAlarmMaryCallsJohnCallsFor instance, the reasons why John and Mary may not call if there is an alarm are unrelated Note that these reasons couldbe other beliefs in the network.The probabilities summarize thesenon-explicit beliefsStructure of BNStructure of BNThe relation:P(x1,x2,…,xn) = Πi=1,…,nP(xi|Parents(Xi))means that each belief is independent of its predecessors in the BN given its parentsSaid otherwise, the parents of a belief Xiare all the beliefs that “directly influence” XiUsually (but not always) the parents of Xiare its causes and Xiis the effect of these causesE.g., JohnCalls is influenced by Burglary, but not directly. JohnCalls is directly influenced by AlarmConstruction of BNConstruction of BNChoose the relevant sentences (random variables) that describe the domainSelect an ordering X1,…,Xn, so that all the beliefs that directly influence Xiare before XiFor j=1,…,n do: Add a node in the network labeled by Xj Connect the node of its parents to Xj Define the CPT of Xj• The ordering guarantees that the BNwill have no cycles4Markov AssumptionWe now make this independence assumption more precise for directed acyclic graphs (DAGs)Each random variable X, is independent of its non-descendents, given its parents Pa(X)Formally,I(X; NonDesc(X) | Pa(X))DescendentAncestorParentNon-descendentXY1Y2Non-descendentSet E of evidence variables that are observed, e.g., {JohnCalls,MaryCalls}Query variable X, e.g., Burglary, for which we would like to know the posterior probability distribution P(X|E)Distribution conditional to the observations madeInference In BNInference In BN?TTP(B|…)MJInference PatternsInference PatternsBurglary EarthquakeAlarmMaryCallsJohnCallsDiagnosticBurglary EarthquakeAlarmMaryCallsJohnCallsCausalBurglary EarthquakeAlarmMaryCallsJohnCallsIntercausalBurglary EarthquakeAlarmMaryCallsJohnCallsMixed• Basic use of a BN: Given newobservations, compute the newstrengths of some (or all) beliefs• Other use: Given the strength ofa belief, which observation shouldwe gather to make the greatestchange in this belief’s strengthSingly Connected BNSingly Connected BNA BN is singly connected if there is at most one undirected path between any two nodesBurglary EarthquakeAlarmMaryCallsJohnCallsis singly connectedis not singly connectedis singly connectedTypes Of Nodes On A PathTypes Of Nodes On A PathRadioBatterySparkPlugsStartsGasMoveslinearconvergingdivergingIndependence Relations In BNIndependence Relations In BNRadioBatterySparkPlugsStartsGasMoveslinearconvergingdivergingGiven a set E of evidence nodes, two beliefs connected by an undirected path are independent if one of the following three conditions holds:1. A node on the path is linear and in E2. A node on the path is