Probabilistic Reasoning: Exact Inference
CSci 5512: Artificial Intelligence II
Instructor:
January 31, 2022
Copyright By PowCoder代写 加微信 powcoder
Instructor:
Probabilistic Reasoning: Exact Inference
Announcements
Homework 1 will be posted tomorrow (Feb 1) and due Feb 10
Probabilistic Reasoning: Exact Inference
Instructor:
Bayesian networks
A simple, graphical notation for conditional independence assertions and hence for compact specification of full join distributions
A set of nodes, one per variable
A directed, acyclic graph (link implies direct influence)
A conditional distribution for each node given its parents
Conditional distributions
For each Xi, P(Xi|Parents(Xi))
In the form of a conditional probability table (CPT)
Distribution of Xi for each combination of parent values
Probabilistic Reasoning: Exact Inference
Instructor:
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, MaryCalls 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
Probabilistic Reasoning: Exact Inference
Instructor:
Example (cont.)
Instructor:
Probabilistic Reasoning: Exact Inference
Earthquake
TT TF FT FF
.95 .94 .29 .001
How can we compute P(b|j, m)?
Instructor:
Probabilistic Reasoning: Exact Inference
Inference by Enumeration
Simple query can be answered using the product rule
P(b|j, m) = P(b, j, m) P(j,m)
Each marginal can be obtained from the joint distribution
P(b,j,m) = P(b,E,A,j,m) EA
P(j,m) = P(B,E,A,j,m) BEA
Each term can be written as product of conditionals
P(b,E,A,j,m) = P(b)P(E)P(A|b,E)P(j|A)P(m|A) The complexity of the simple approach is O(n2n)
Probabilistic Reasoning: Exact Inference
Instructor:
Inference by Enumeration (cont.)
Complexity can be improved by a simple observation
P(b|j,m) = 1 P(b,E,A,j,m)
= 1 P(b)P(E)P(A|E,b)P(j|A)P(m|A)
1 = P(j,m)P(b) P(E) P(A|E,b)P(j|A)P(m|A)
Complexity is O(2n)
Some computations are repeated
Probabilistic Reasoning: Exact Inference
Instructor:
Burglary Network
Earthquake
TT TF FT FF
.95 .94 .29 .001
Instructor:
Probabilistic Reasoning: Exact Inference
Enumeration Tree
P( a|b, e)
Probabilistic Reasoning: Exact Inference
Instructor:
Enumeration Tree
P( a|b, e)
Enumeration Tree for P(b|j, m)
P(j|a)P(m|a) and P(j|¬a)P(m|¬a) are computed twice
Probabilistic Reasoning: Exact Inference
Instructor:
Variable Elimination
Queries can be written as sum-of-products Main idea
Sum over products to eliminate variables Storage required to prevent repeat computations
Burglary network
= 1 P(b) P(E) P(A|b,E)P(j|A)P(m|A)
P(j,m) E A
Have a factor for every variable
Probabilistic Reasoning: Exact Inference
Instructor:
Factors for Variable Elimination
Factor for M: fm(A) = [P(m|a) P(m|¬a)] Factor for J: fj(A) = [P(j|a) P(j|¬a)] Similarly, factors fA(B,E,A),fE(E),fB(B) Summing out to eliminate variables
fA ̄jm(B,E) = fA(B,E,A)fj(A)fm(A) A
fE ̄A ̄jm (B ) P (B |j , m)
= fE (E )fA ̄jm (B , E ) E
= 1 fB (B )fE ̄A ̄jm (B ) P(j,m)
Probabilistic Reasoning: Exact Inference
Instructor:
Variable Elimination: Basic Operations
Summing out a variable from a product of factors Pointwise products of (a pair of) factors
Sum out a variable from a product of factors
Pointwise product of factors f1(a, b) × f2(b, c) = f(a, b, c) In general
f1(x1,…,xj,y1,…,yk)×f2(y1,…,yk,z1,…,zl) = f(x1,…,xj,y1,…,yk,z1,…,zl)
Assuming f1,…,fi do not depend on X
f1 ×···×fk = f1 ×···×fi × fi+1 ×···×fk xX
= f1×···×fi×fX ̄
Probabilistic Reasoning: Exact Inference
Instructor:
Example: Pointwise Product of Factors
0.3 0.7 0.9 0.1
0.2 0.8 0.6 0.4
T T T T F F F F
T T F F T T F F
T F T F T F T F
0.3 × 0.2 0.3 × 0.8 0.7 × 0.6 0.7 × 0.4 0.9 × 0.2 0.9 × 0.8 0.1 × 0.6 0.1 × 0.4
Instructor:
Probabilistic Reasoning: Exact Inference
Complexity of Exact Inference
Singly connected networks (or polytrees)
Any two nodes are connected by at most one path Time and space cost of variable elimination are O(dkn)
d: size of variable domain (2 if boolean) k: max number of parents
Exact inference becomes intractable for large, multiply connect networks (exponential)
Must consider approximate inference methods (via stochastic simulations)
Probabilistic Reasoning: Exact Inference
Instructor:
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com