-1X071018180046 e.g.PljAmAanA-e) Global semantics Global semantics For burglary net,++++2=10 numbers (vs.25-1 =31) glinearly()for the full joint distribution Compactness Q Q This chice of parents gurantees the: Constructing Bayesian networks Markoy blanket of its nondescendants given its paren Local semantics:each node is conditionally independen Local semantics P. Compactness A CPT for Boolean Xi with k Boolean parents has B E J A M 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(2 n ) for the full joint distribution For burglary net, 1 + 1 + 4 + 2 + 2 = 10 numbers (vs. 2 5 − 1 = 31) Chapter 14.1–3 7 Global semantics Global semantics defines the full joint distribution B E J A M as the product of the local conditional distributions: P(x1, . . . , xn) = Πi n = 1P(xi |parents(Xi)) e.g., P(j ∧ m ∧ a ∧ ¬b ∧ ¬e) = Chapter 14.1–3 8 Global semantics “Global” semantics defines the full joint distribution B E J A M as the product of the local conditional distributions: P(x1, . . . , xn) = Πi n = 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.00063 Chapter 14.1–3 9 Local semantics Local semantics: each node is conditionally independent of its nondescendants given its parents . . . . . . U1 X Um Yn Znj Y1 Z1j 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 X Um Yn Znj Y1 Z1j 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 |Parents(Xi)) = P(Xi |X1, . . . , Xi−1) This choice of parents guarantees the global semantics: P(X1, . . . , Xn) = Πi n = 1P(Xi |X1, . . . , Xi−1) (chain rule) = Πi n = 1P(Xi |Parents(Xi)) (by construction) Chapter 14.1–3 12