CMPSC442-Wk8-Mtg24
Bayesian Inference
AIMA 13.3-13.5
CMPSC 442
Week 8, Meeting 24, Three Segments
Outline
● Exact Inference in Bayesian Networks
● Approximate Inference for Bayesian Networks
● Causal Networks
2Outline, Wk 8, Mtg 24
Bayesian Inference
AIMA 13.3-13.5
CMPSC 442
Week 8, Meeting 24, Segment 1 of 3: Exact Inference in
Bayesian Networks
General Motivation for Inference
● Compute the posterior probability distribution for a set of query variables,
given an observed event (evidence variables)
○ We have already seen this exemplified for the Wumpus world, where the agent asked for the
posterior P(P
1,3
) (mtg 20)
○ We consider here only a single query variable at a time, for inferences over more complex
networks
● Compute the most probable explanation for some observed evidence
○ For example, if the Wumpus world agent asked what event is the most probable event (out of
the 5 events) for the observations ¬B
1,1
∧B
1,2
∧ B
2,1
∧¬P
1,1
∧¬P
1,2
∧ ¬P
2,1
4Exact Inference
Querying a Bayesian Network
● A typical query: the posterior probability of X given the evidence
● EG:
5Exact InferenceExact Inference
Computation Tree for Summing over the Probabilities
6
● Evidence: j, m
● P(b|j,m)
Exact Inference
Inference by Enumeration
7Exact Inference
Algorithm: Depth First, Left-to-Right Recursion
8Exact Inference
Improving the Efficiency
● Enumeration algorithm sums over the full joint distribution, without explicitly
representing it
● Poor time complexity: O(2n)
● Efficiency can be improved
○ Note that the computation tree on slide 6 had repeated subpaths
■ P(j|a)P(m|a) occurs twice
■ P(j|¬a)P(m|¬a) occurs twice
● Given that there are repeated computations, dynamic programming can be
used to re-use previous computations
9Exact Inference
Variable Elimination
● Evaluate expressions that rely on the CPTs in right-to-left order, e.g.,
● Store intermediate results of factors that repeat
● Summations over each variable are done only on expressions that depend on
the variable
10Exact Inference
Variable Elimination
● Identify factors based on distinct variables that occur:
● Factors as vectors:
● Rewrite formula using factors (where × represents pointwise product)
11Exact Inference
Variable Elimination Pseudo Code
12Exact Inference
Complexity of Best Exact Inference Methods
● Inference in Bayesian Networks is NP-hard
● CSP satisfiability problems can be reduced to Bayesian Network inference
● Complexity of Bayesian Networks and CSP problems is similar
○ SAT-solving has been optimized for large-scale applications
○ SAT-solving algorithms can be applied to Bayesian Networks
13
Bayesian Inference
AIMA 13.3-13.5
CMPSC 442
Week 8, Meeting 24, Segment 2 of 3: Approximate
Inference for Bayesian Networks
Monte Carlo Algorithms for Bayesian Networks
● Randomized sampling algorithms (e.g., simulated annealing, Monte Carlo Tree
Search)
● Accuracy depends on the number of samples generated
○ Generate random samples based on the probabilities in the network
○ Sum over the randomly generated possibilities
● Two approaches for Bayesian Networks
○ Direct sampling
○ Markov chain sampling
15Approximate Inference
Direct Sampling Approach
● Given a source of random numbers r uniformly distributed in [0,1]
○ It is possible to sample any distribution for a single variable Xi
○ Construct the cumulative distribution for Xi and return the first value whose cumulative
probability exceeds r
16Approximate Inference
● Sample each variable in topological order
● The probability distribution from which a value is
sampled is thus conditioned on the values
already assigned to the parents
Example of Generating One Random Event
17Approximate Inference
Algorithm for Direct Sampling
18
● Guaranteed to be consistent with the axioms of probability:
Approximate Inference
Direct Sampling and Probability of Each Event
● Every randomly generated event will occur with a probability given by the
Bayesian Network
● Events where it was cloudy, the sprinkler didn’t go on, it did rain, and the grass
was wet occur 32.4% of the time
19Approximate Inference
Other Direct Sampling Methods
● Rejection sampling: can produce samples from a hard-to-sample distribution by
rejecting randomly generated samples that do not match the evidence
● Importance sampling: for P, use a simpler distribution Q to sample from, then
apply a correction factor P(x)/Q(x)
○ EG: Likelihood weighting (probabilities of evidence are called likelihoods, cf. slide 9, Mtg 22)
20Approximate Inference
Markov Chain Monte Carlo (MCMC)
● Markov Chain: a random process that generates a sequence of states
● In contrast to direct sampling methods, MCMC does not generate each sample
from scratch
● MCMC: makes a random change to the current example to generate a new
one
○ Current state: a value is specified for every variable
○ Next state: randomly change the current state, according to the probabilities given in the
Bayesian Network
21Approximate Inference
Two Best-Known MCMC Algorithms
● Gibbs sampling: Particularly well suited to Bayesian Networks
● Metropolis Hastings sampling: Allows greater flexibility in generating samples
● Both are widely used in probabilistic inference
22Approximate Inference
Bayesian Inference
AIMA 13.3-13.5
CMPSC 442
Week 8, Meeting 24, Segment 3 of 3: Causal Inference
Causal Networks
● Dilemma:
○ In a full joint probability distribution, two networks are equivalent that have opposite
conditioning contexts:
■ P(Smoke|Fire) = P(Smoke, Fire)/P(Fire) corresponding to Fire causes Smoke
■ P(Fire|Smoke) = P(Smoke,Fire)/P(Smoke) corresponding to Smoke causes Fire
● Causal Bayesian Networks capture the asymmetry in conditional probabilities
○ Bayesian Networks ask if Smoke and Fire are probabilistically dependent
○ Causal Networks ask whether Smoke is conditioned on Fire, or Fire on Smoke
24Causal Inference
Structural Equations
● The value xi of Xi is determined by an equation xi = fi(Other Variables)
○ If Xj is an argument of fi, then Xj → Xi
○ Else Xi is not conditioned on Xj
● The function fi is called a structural equation: it describes a stable mechanism
in nature that remains invariant to measurements and local changes in the
environment
25
Stability of Causal Bayesian Networks
● Left: Mary sometimes turns the sprinkler on when its cloudy
● Right: After Mary takes the action of turning the sprinkler on
● Note: If the sprinkler breaks, it can be removed from the network with no
change to the rest of the network
26
Interventions
● An intervention, by definition, compares two otherwise equal experiments,
holding all things equal apart from the intervention action (treatment)
○ Compares the outcome with and without the treatment (condition 1 and condition 2)
○ If the outcomes differ, it must be due to the treatment
● Causal networks support reasoning about interventions
● Correlation is not causation!
27
Summary – One
● A Bayesian network is a directed acyclic graph (DAG) whose nodes correspond to
random variables; each node as a CPT
● Bayesian networks concisely represent conditional independence
● Bayesian networks represent full joint probability distributions, and obey the axioms
of probability
● Inference in a Bayesian network means computing the posterior probability
distribution of a query variable (or set of query variables)
28Summary, Wk 8, Mtg 24
Summary – Two
● Exact inference algorithms, e.g., variable elimination, rely on dynamic
programming, but are still intractable for large numbers of variables
● Approximate inference techniques can be very accurate, given large samples
● Causal Networks are a specific type of Bayesian network to support causal
reasoning about interventions
○ Depend on structural equations that capture stable knowledge about the world
29Summary, Wk 8, Mtg 24