DOC PREVIEW
Pitt CS 2710 - Inference in Bayesian networks

This preview shows page 1-2-3 out of 9 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 9 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 9 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 9 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 9 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

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

Pitt CS 2710 - Inference in Bayesian networks

Documents in this Course
Load more
Download Inference in Bayesian networks
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Inference in Bayesian networks and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Inference in Bayesian networks 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?