Bayesian networks Chapter 14 1 3 Chapter 14 1 3 1 Outline Syntax Semantics Parameterized distributions Chapter 14 1 3 2 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 P arents 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 Chapter 14 1 3 3 Example Topology of network encodes conditional independence assertions Weather Cavity Toothache Catch W eather is independent of the other variables T oothache and Catch are conditionally independent given Cavity Chapter 14 1 3 4 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 Burglar Earthquake Alarm JohnCalls M aryCalls 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 Chapter 14 1 3 5 Example contd P E P B Burglary B E P A B E T T F F T F T F 95 94 29 001 JohnCalls Earthquake 001 002 Alarm A P J A T F 90 05 A P M A MaryCalls T F 70 01 Chapter 14 1 3 6 Compactness A CPT for Boolean Xi with k Boolean parents has 2k rows for the combinations of parent values Each row requires one number p for Xi true the number for Xi f alse is just 1 p B E A J M If each variable has no more than k parents the complete network requires O n 2k 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 Chapter 14 1 3 7 Global semantics Global semantics defines the full joint distribution as the product of the local conditional distributions B n P x1 xn i 1P xi parents Xi e g P j m a b e E A J M Chapter 14 1 3 8 Global semantics Global semantics defines the full joint distribution as the product of the local conditional distributions B n P x1 xn i 1P xi parents Xi e g P j m a b e E A J M 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 00063 Chapter 14 1 3 9 Local semantics Local semantics each node is conditionally independent of its nondescendants given its parents U1 Um X Z 1j Z nj Y1 Yn Theorem Local semantics global semantics Chapter 14 1 3 10 Markov blanket Each node is conditionally independent of all others given its Markov blanket parents children children s parents U1 Um X Z 1j Z nj Y1 Yn Chapter 14 1 3 11 Constructing Bayesian networks Need a method such that a series of locally testable assertions of conditional independence guarantees the required global semantics 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 P arents Xi P Xi X1 Xi 1 This choice of parents guarantees the global semantics n P X1 Xn i 1P Xi X1 Xi 1 chain rule n i 1P Xi P arents Xi by construction Chapter 14 1 3 12 Example Suppose we choose the ordering M J A B E MaryCalls JohnCalls P J M P J Chapter 14 1 3 13 Example Suppose we choose the ordering M J A B E MaryCalls JohnCalls Alarm P J M P J No P A J M P A J P A J M P A Chapter 14 1 3 14 Example Suppose we choose the ordering M J A B E MaryCalls JohnCalls Alarm Burglary P J M P J No P A J M P A J P A J M P A No P B A J M P B A P B A J M P B Chapter 14 1 3 15 Example Suppose we choose the ordering M J A B E MaryCalls JohnCalls Alarm Burglary Earthquake P J M P J No P A J M P A J P A J M P A No P B A J M P B A Yes P B A J M P B No P E B A J M P E A P E B A J M P E A B Chapter 14 1 3 16 Example Suppose we choose the ordering M J A B E MaryCalls JohnCalls Alarm Burglary Earthquake P J M P J No P A J M P A J P A J M P A No P B A J M P B A Yes P B A J M P B No P E B A J M P E A No P E B A J M P E A B Yes Chapter 14 1 3 17 Example contd MaryCalls JohnCalls Alarm Burglary Earthquake Deciding conditional independence is hard in noncausal directions Causal models and conditional independence seem hardwired for humans Assessing conditional probabilities is hard in noncausal directions Network is less compact 1 2 4 2 4 13 numbers needed Chapter 14 1 3 18 Example Car diagnosis Initial evidence car won t start Testable variables green broken so fix it variables orange Hidden variables gray ensure sparse structure reduce parameters battery age battery dead battery meter lights fanbelt broken alternator broken no charging battery flat oil light no oil gas gauge no gas car won t start fuel line blocked starter broken dipstick Chapter 14 1 3 19 Example Car insurance SocioEcon Age GoodStudent ExtraCar Mileage RiskAversion VehicleYear SeniorTrain MakeModel DrivingSkill DrivingHist Antilock DrivQuality Airbag Ruggedness CarValue HomeBase AntiTheft Accident Theft OwnDamage Cushioning MedicalCost OtherCost LiabilityCost OwnCost PropertyCost Chapter 14 1 3 20 Compact conditional distributions CPT grows exponentially with number of parents CPT becomes infinite with continuous valued parent or child Solution canonical distributions that are defined compactly Deterministic nodes are the simplest case X f P arents X for some function f E g Boolean functions N orthAmerican Canadian U S M exican E g numerical relationships among continuous variables Level inflow precipitation outflow evaporation t Chapter 14 1 3 21 Compact conditional distributions contd Noisy OR distributions model multiple noninteracting causes 1 Parents U1 Uk include all causes can add leak node 2 Independent failure probability qi for each cause alone j P X U1 Uj Uj 1 Uk 1 i 1qi Cold F F F F T T T T F lu F F T T F F T T M alaria F T F T F T F T P F ever 0 0 0 9 0 8 0 98 …