Inference in Bayesian networksChapter 14.4Chapter 14.4 1Outline♦ Exact inference by enumeration♦ Exact inference by variable eliminationChapter 14.4 2Inference tasksSimple qu eries: compute posterior marginal P(Xi|E = e)e.g., P (NoGas|Gauge = empty, Lights = on, Starts = false)Conjunctive qu eries: P(Xi, Xj|E = e) = P(Xi|E = e)P(Xj|Xi, E = e)Optimal decisions: decision networks includ e utility information;probabilistic inference required forP (outcome|action, evidence)Value of information: which eviden ce to seek next?Sensitivity analysis: which probab ility values are most critical?Explanation: why do I need a new starter motor?Chapter 14.4 3Inference by enumerationSlightly intelligent way to sum out variables f rom the joint without actuallyconstructing its explicit representationSimple qu ery on the burglary network:BEJAMP(B|j, m)= P(B, j, m)/P (j, m)= αP(B, j, m)= α ΣeΣaP(B, e, a, j, m)Rewrite full joint entries usin g product of CPT entries:P(B|j, m)= α ΣeΣaP(B)P (e)P(a|B, e)P (j|a)P(m|a)= αP(B) ΣeP (e) ΣaP(a|B, e)P (j|a)P (m|a)Recursive d epth-first enumeration: O(n) space, O(dn) timeChapter 14.4 4Evaluation treeP(j|a).90P(m|a).70 .01P(m| a).05P(j| a)P(j|a).90P(m|a).70 .01P(m| a).05P(j| a)P(b).001P(e).002P( e).998P(a|b,e).95.06P( a|b, e).05P( a|b,e).94P(a|b, e)Enumeration is inefficient: repeated computatione.g., computesP (j|a)P (m|a) for each value of eChapter 14.4 5Inference by variable eliminationVariable elimination: car ry out summations right-to-left,storing intermediate results (factors) to avoid recomputationP(B|j, m)= α P(B)|{z }BΣeP (e)|{z }EΣaP(a|B, e)|{z }AP (j|a)|{z }JP (m|a)|{z }M= αP(B)ΣeP (e)ΣaP(a|B, e)P (j|a)fM(a)= αP(B)ΣeP (e)ΣaP(a|B, e)fJ(a)fM(a)= αP(B)ΣeP (e)ΣafA(a, b, e)fJ(a)fM(a)= αP(B)ΣeP (e)f¯AJM(b, e)(sum out A)= αP(B)f¯E¯AJM(b)(sum out E)= αfB(b) × f¯E¯AJM(b)Chapter 14.4 6Variable elimination: Basic operationsSumming out a variable from a prod uct of factors:move any constant factors outside the summationadd up submatrices in pointwise product of remaining factor sΣxf1× · · · × fk= f1× · · · × fiΣxfi+1× · · · × fk= f1× · · · × fi× f¯Xassuming f1, . . . , fido not depend on XPointwise product of factors f1and f2:f1(x1, . . . , xj, y1, . . . , yk) × f2(y1, . . . , yk, z1, . . . , zl)= f(x1, . . . , xj, y1, . . . , yk, z1, . . . , zl)E.g., f1(a, b) × f2(b, c) = f(a, b, c)Chapter 14.4 7Irrelevant variablesConsider the qu ery P (JohnCalls|Burglary = true)B EJAMP (J|b) = αP (b)XeP (e)XaP (a|b, e)P (J|a)XmP (m|a)Sum over m is identically 1; M is irrelevant to the queryThm 1:Y is irrelevant unless Y ∈ Ancestors({X} ∪ E)Here, X = Jo hnCalls, E = {Burglary}, andAncestors({X} ∪ E) = {Alarm, Earthquake}so MaryCalls is irrelevant(Compare this to ba ckward chain ing from the query in Horn clau se KBs)Chapter 14.4 8SummaryExact inference by variable elimination:– NP-hard on general graphsApproximate inference - see 14.5Chapter 14.4
View Full Document