Last update: May 11, 2010Bayesian networksCMSC 421: Chapter 14.1–4CMSC 421: Chapter 14.1–4 1Outline♦ Syntax♦ Semantics♦ Parameterized distributionsCMSC 421: Chapter 14.1–4 2Bayesian networksGraphical network that encodes conditional independence assertions:♦ a set of nodes, one per variable♦ a directed, acyclic graph (link ≈ “directly influences”)♦ a conditional distribution P(Xi|P arents(Xi)) for each node XiWeatherCavityToothache CatchW eather is independent of the other variablesT oothache and Catch are conditionally independent given CavityFor each node Xi, P(Xi|P arents(Xi)) is represented as a conditional prob-ability table (CPT); we’ll have examples laterCMSC 421: Chapter 14.1–4 3ExampleExample from Judea Pearl at UCLA:I’m at work, neighbor John calls to say my alarm is ringing, but neighborMary doesn’t call. Sometimes it’s set off by minor earthquakes. Is there aburglar?Variables: Burglar, Earthquake, Alarm, JohnCalls, MaryCallsNetwork 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 callCMSC 421: Chapter 14.1–4 4Example, continued.001P(B).002P(E)AlarmEarthquakeMaryCallsJohnCallsBurglaryBTTFFETFTF.95.29.001.94P(A|B,E)ATF.90.05P(J|A)ATF.70.01P(M|A)CMSC 421: Chapter 14.1–4 5CompactnessFor a Boolean node Xiwith k Boolean parents, the CPT hasB EJAM2krows, one for each combination of parent valuesEach row requires one number p for Xi= true(the number for Xi= false is just 1 − p)If there are n variables and ifeach variable has no more than k parents,the complete network requires no more than n · 2knumbersI.e., grows linearly with n, vs. O(2n) for the full joint distributionHow many numbers for the burglary net?CMSC 421: Chapter 14.1–4 6CompactnessFor a Boolean node Xiwith k Boolean parents, the CPT hasB EJAM2krows, one for each combination of parent valuesEach row requires one number p for Xi= true(the number for Xi= false is just 1 − p)If there are n variables and ifeach variable has no more than k parents,the complete network requires no more than n · 2knumbersI.e., grows linearly with n, vs. O(2n) for the full joint distributionHow many numbers for the burglary net?1 + 1 + 4 + 2 + 2 = 10 numbers(vs. 25− 1 = 31 for the joint distribution)CMSC 421: Chapter 14.1–4 7Semantics of Bayesian netsIn general, semantics = “what things mean.”B EJAMHere, we’re interested in what a Bayesian net means.We’ll look at global and local semanticsCMSC 421: Chapter 14.1–4 8Global semanticsGlobal semantics defines the full joint distributionB EJAMas the product of the local conditional distributionsIf X1, . . . , Xnare all of the random variables,then by combining the chain rule and conditionalindependence, we getP (X1, . . . , Xn) = Πni = 1P (Xi|parents(Xi))e.g., P (j ∧ m ∧ a ∧ ¬b ∧ ¬e)=CMSC 421: Chapter 14.1–4 9Global semanticsGlobal semantics defines the full joint distributionB EJAMas the product of the local conditional distributionsIf X1, . . . , Xnare all of the random variables,then by combining the chain rule and conditionalindependence, we getP (X1, . . . , Xn) = Πni = 1P (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)= 0.9 × 0.7 × 0.001 × 0.999 × 0.998≈ 0.00063CMSC 421: Chapter 14.1–4 10Local semanticsLocal semantics: each node is conditionally independentof its nondescendants given its parents. . .. . .U1XUmYnZnjY1Z1jTheorem: Local semantics ⇔ global semanticsCMSC 421: Chapter 14.1–4 11Markov blanketEach node is conditionally independent of all others given itsMarkov blanket: parents + children + children’s parents. . .. . .U1XUmYnZnjY1Z1jCMSC 421: Chapter 14.1–4 12Constructing Bayesian networksGiven a set of random variables1. Choose an ordering X1, . . . , XnIn principle, any ordering will work2. For i = 1 to n, add Xito the network as follows:For P arents(Xi), choose a subset of {X1, . . . , Xi−1} such thatXiis conditionally independent of the other nodes in {X1, . . . , Xi−1},i.e., P(Xi|P arents(Xi)) = P(Xi|X1, . . . , Xi−1)This choice of parents guarantees the global semantics:P(X1, . . . , Xn) = Πni = 1P(Xi|X1, . . . , Xi−1) (chain rule)= Πni = 1P(Xi|P arents(Xi)) (by construction)CMSC 421: Chapter 14.1–4 13ExampleSuppose we choose the ordering M, J, A, B, EMaryCallsJohnCallsP (J|M) = P (J)?CMSC 421: Chapter 14.1–4 14ExampleSuppose we choose the ordering M, J, A, B, EMaryCallsAlarmJohnCallsP (J|M) = P (J)? NoP (A|J, M) = P (A|J)? P (A|J, M) = P (A)?CMSC 421: Chapter 14.1–4 15ExampleSuppose we choose the ordering M, J, A, B, EMaryCallsAlarmBurglaryJohnCallsP (J|M) = P (J)? NoP (A|J, M) = P (A|J)? P (A|J, M) = P (A)? NoP (B|A, J, M) = P (B|A)?P (B|A, J, M) = P (B)?CMSC 421: Chapter 14.1–4 16ExampleSuppose we choose the ordering M, J, A, B, EMaryCallsAlarmBurglaryEarthquakeJohnCallsP (J|M) = P (J)? NoP (A|J, M) = P (A|J)? P (A|J, M) = P (A)? NoP (B|A, J, M) = P (B|A)? YesP (B|A, J, M) = P (B)? NoP (E|B, A, J, M) = P (E|A)?P (E|B, A, J, M) = P (E|A, B)?CMSC 421: Chapter 14.1–4 17ExampleSuppose we choose the ordering M, J, A, B, EMaryCallsAlarmBurglaryEarthquakeJohnCallsP (J|M) = P (J)? NoP (A|J, M) = P (A|J)? P (A|J, M) = P (A)? NoP (B|A, J, M) = P (B|A)? YesP (B|A, J, M) = P (B)? NoP (E|B, A, J, M) = P (E|A)? NoP (E|B, A, J, M) = P (E|A, B)? YesCMSC 421: Chapter 14.1–4 18Example, continuedMaryCallsAlarmBurglaryEarthquakeJohnCallsDeciding conditional independence is hard in noncausal directionsAssessing conditional probabilities is hard in noncausal directionsNetwork is less compact: 1 + 2 + 4 + 2 + 4 = 13 numbers neededCMSC 421: Chapter 14.1–4 19Example: Car diagnosisInitial evidence: car won’t startTestable variables (green), “broken, so fix it” variables (orange)Hidden variables (gray) ensure sparse structure, reduce parameterslightsno oil no gasstarterbrokenbattery agealternator brokenfanbeltbrokenbattery deadno chargingbattery flatgas gaugefuel lineblockedoil lightbattery metercar won’t startdipstickCMSC 421: Chapter 14.1–4 20Compact conditional distributionsProblem: CPT grows exponentially with number of parents.Can overcome this if the causes don’t interact: use a Noisy-OR distribution1) Parents U1. . . Ukinclude all causes (can add leak node)2) Independent failure probability qifor each cause Uiby itself⇒ P (¬X|U1. . . Uj, ¬Uj+1. . . ¬Uk) = Πji =