CS计算机代考程序代写 chain Bayesian flex Bayesian network algorithm CMPSC442-Wk8-Mtg24

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