=== p1 ===
Introduction to 
Artificial Intelligence
Chapter 13
Probabilistic Reasoning
Wei-Ta Chu (朱威達)
1

=== p2 ===
• This chapter introduces Bayesian network. 
Representing Knowledge
2

=== p3 ===
• Recall the variables Toothache, Cavity, Catch, and Weather. We argued that 
Weather is independent of the other variables; we argued that Toothache and 
Catch are conditionally independent, given Cavity. 
• The conditional independence of Toothache and Catch, given Cavity, is 
indicated by the absence of a link between Toothache and Catch. 
Representing Knowledge
3

=== p4 ===
• You have a new burglar alarm (竊盜警報器) installed at home. It is fairly 
reliable at detecting a burglary, but also responds on occasion to minor 
earthquakes. 
• You also have two neighbors, John and Mary, who have promised to call you 
at work when they hear the alarm. John nearly always calls when he hears the 
alarm, but sometimes confuses the telephone ringing with the alarm and calls 
then, too. Mary, on the other hand, likes rather loud music and often misses the 
alarm altogether. 
Representing Knowledge
4

=== p5 ===
Representing Knowledge
5
[IMAGE-ONLY]

=== p6 ===
• The network structure shows that burglary and earthquakes directly affect the 
probability of the alarm’s going off, but whether John and Mary call depends 
only on the alarm. 
• The network thus represents our assumptions that they do not perceive 
burglaries directly, they do not notice minor earthquakes, and they do not 
confer (協商) before calling.
Representing Knowledge
6

=== p7 ===
• The conditional distributions are shown as a conditional probability table, or 
CPT. 
• A node with no parents has only one row, representing the prior probabilities
of each possible value of the variable. 
• The probabilities actually summarize a potentially infinite set of circumstances 
in which the alarm might fail to go off (high humidity, power failure, dead 
battery, cut wires, a dead mouse stuck inside the bell, etc.) or John or Mary 
might fail to call and report it (out to lunch, on vacation, temporarily deaf, 
passing helicopter, etc.). 
• In this way, a small agent can cope with a very large world, approximately.
Representing Knowledge
7

=== p8 ===
• We can calculate the probability that the alarm has sounded, but neither a 
burglary nor an earthquake has occurred, and both John and Mary call. 
Representing the full joint distribution
8

=== p9 ===
Representing the full joint distribution
9
• A method for constructing Bayesian networks

=== p10 ===
• Intuitively, the parents of node Xi should contain all those nodes in X1, . . . , 
Xi−1 that directly influence Xi. 
• Because each node is connected only to earlier nodes, this construction method 
guarantees that the network is acyclic. 
Representing the full joint distribution
10

=== p11 ===
• Compactness and node ordering
• One might object to our burglary network on the grounds that if there is an 
earthquake, then John and Mary would not call even if they heard the alarm, 
because they assume that the earthquake is the cause. 
• Whether to add the link from Earthquake to JohnCalls and MaryCalls (and 
thus enlarge the tables) depends on comparing the importance of getting more 
accurate probabilities with the cost of specifying the extra information.
Representing the full joint distribution
11

=== p12 ===
• Even in a locally structured domain, we will get a compact 
Bayesian network only if we choose the node ordering well. 
What happens if we happen to choose the wrong order? 
• Suppose we decide to add the nodes in the order MaryCalls, 
JohnCalls, Alarm, Burglary, Earthquake. We then get the 
somewhat more complicated network shown in Figure 14.3(a).
Representing the full joint distribution
12

=== p13 ===
Representing the full joint distribution
13

=== p14 ===
• The process goes as follows:
Representing the full joint distribution
14

=== p15 ===
• The resulting network has two more links than the original network in Figure 
14.2 and requires three more probabilities to be specified. What’s worse, some 
of the links represent tenuous (稀薄的) relationships that require difficult and 
unnatural probability judgments, such as assessing the probability of 
Earthquake, given Burglary and Alarm. 
Representing the full joint distribution
15

=== p16 ===
• The topological semantics specifies that each variable is conditionally 
independent of its non-descendants, given its parents (Figure 14.4(a)). 
• A node is conditionally independent of all other nodes in the network, given its 
parents, children, and children’s parents—that is, given its Markov blanket. 
Conditional independence relations in 
Bayesian networks
16

=== p17 ===
Conditional independence relations in 
Bayesian networks
17

=== p18 ===
• Many real-world problems involve continuous quantities. 
• By definition, continuous variables have an infinite number of possible values, 
so it is impossible to specify conditional probabilities explicitly for each value. 
• One possible way to handle continuous variables is using discretization—that 
is, dividing up the possible values into a fixed set of intervals. 
• For example, temperatures could be divided into (<0C), (0C−100C), and 
(>100C). Discretization is sometimes an adequate solution, but often results in 
a considerable loss of accuracy and very large CPTs.
Bayesian nets with continuous variables
24

=== p19 ===
• The most common solution is to define standard families of probability density 
functions that are specified by a finite number of parameters. For example, a 
Gaussian (or normal) distribution N(μ,σ2)(x) has the mean μ and the variance 
σ2 as parameters. 
• Yet another solution—sometimes called a nonparametric representation—is 
to define the conditional distribution implicitly with a collection of instances, 
each containing specific values of the parent and child variables. 
Bayesian nets with continuous variables
25

=== p20 ===
• A network with both discrete and continuous variables is called a hybrid 
Bayesian network. 
• Consider a customer buys some fruit depending on its cost, which depends in 
turn on the size of the harvest (收穫) and whether the government’s subsidy 
(補貼) scheme is operating. The variable Cost is continuous and has 
continuous and discrete parents; the variable Buys is discrete and has a 
continuous parent.
Bayesian nets with continuous variables
26

=== p21 ===
Bayesian nets with continuous variables
27

=== p22 ===
• For the Cost variable, we need to specify P(Cost | Harvest, Subsidy). The 
discrete parent is handled by enumeration—that is, by specifying both P(Cost | 
Harvest, subsidy) and P(Cost | Harvest, ¬subsidy). 
• To handle Harvest, we specify how the distribution over the cost c depends on 
the continuous value h of Harvest. In other words, we specify the parameters
of the cost distribution as a function of h. The most common choice is the 
linear Gaussian distribution, in which the child has a Gaussian distribution 
whose mean μ varies linearly with the value of the parent and whose standard 
deviation σ is fixed.
Bayesian nets with continuous variables
28

=== p23 ===
• We need two distributions, one for subsidy and one for ¬subsidy, with different 
parameters:
• For this example, then, the conditional distribution for Cost is specified by 
naming the linear Gaussian distribution and providing the parameters at, bt, σt, 
af, bf, and σf. Figures 14.6(a) and (b) show these two relationships. 
Bayesian nets with continuous variables
29

=== p24 ===
Bayesian nets with continuous variables
30

=== p25 ===
• Figure 14.6(c) shows the distribution P(c | h), averaging over the two possible 
values of Subsidy and assuming that each has prior probability 0.5. This shows 
that even with very simple models, quite interesting distributions can be 
represented.
Bayesian nets with continuous variables
31

=== p26 ===
• It seems reasonable to assume that the customer will buy if the cost is low and 
will not buy if it is high and that the probability of buying varies smoothly in 
some intermediate region. The conditional distribution is like a “soft” 
threshold function. One way to make soft thresholds is to use the integral of 
the standard normal distribution:
Bayesian nets with continuous variables
33

=== p27 ===
• Then the probability of Buys given Cost might be 
which means that the cost threshold occurs around μ, the width of the threshold 
region is proportional to σ, and the probability of buying decreases as cost 
increases. 
• This probit distribution (pronounced “pro-bit” and short for “probability 
unit”) is illustrated in Figure 14.7(b). 
Bayesian nets with continuous variables
34

=== p28 ===
Bayesian nets with continuous variables
35

=== p29 ===
• An alternative to the probit model is the logit distribution (pronounced “low-
jit”). It uses the logistic function 1/(1 + e−x) to produce a soft threshold: 
• This is illustrated in Figure 14.7(b). The two distributions look similar, but the 
logit actually has much longer “tails.” The probit is often a better fit to real 
situations, but the logit is sometimes easier to deal with mathematically. It is 
used widely in neural networks. 
Bayesian nets with continuous variables
36

=== p30 ===
• The basic task for any probabilistic inference system is to compute the 
posterior probability distribution for a set of query variables, given some 
observed event. 
• Let X denotes the query variable; E denotes the set of evidence variables 
E1 , . . . , Em , and e is a particular observed event; Y will denote the 
nonevidence, nonquery variables Y1, . . . , Yl (called the hidden variables). 
Thus, the complete set of variables is X = {X} ∪E ∪Y. A typical query asks 
for the posterior probability distribution P(X | e).
Exact Inference in Bayesian Networks
37

=== p31 ===
• In the burglary network, we might observe the event in which JohnCalls = 
true and MaryCalls = true. We could then ask for, say, the probability that a 
burglary has occurred:
Exact Inference in Bayesian Networks
38

=== p32 ===
• Any conditional probability can be computed by summing terms from the full 
joint distribution. 
• More specifically, Equation (14.2) shows that the terms P(x, e, y) in the joint 
distribution can be written as products of conditional probabilities from the 
network. Therefore, a query can be answered using a Bayesian network by 
computing sums of products of conditional probabilities from the network.
Inference by enumeration
39

=== p33 ===
• Consider the query P(Burglary | JohnCalls=true, MaryCalls=true). The hidden 
variables for this query are Earthquake and Alarm. Using initial letters for the 
variables to shorten the expressions, we have
• The semantics of Bayesian networks (Equation (14.2)) then gives us an 
expression in terms of CPT entries. For simplicity, we do this just for Burglary
= true:
Inference by enumeration
40

=== p34 ===
• To compute this expression, we have to add four terms, each computed by 
multiplying five numbers. In the worst case, where we have to sum out almost 
all the variables, the complexity of the algorithm for a network with n Boolean 
variables is O(n2n). 
• An improvement can be obtained from the following simple observations: the 
P(b) term is a constant and can be moved outside the summations over a and e, 
and the P(e) term can be moved outside the summation over a. Hence, we 
have
Inference by enumeration
41
(14.4)

=== p35 ===
• The structure of this computation is shown in Figure 14.8. Using the numbers 
from Figure 14.2, we obtain P(b | j, m) = α × 0.00059224. The corresponding 
computation for ¬b yields α × 0.0014919; hence, 
That is, the chance of a burglary, given calls from both neighbors, is about 
28%.
Inference by enumeration
42

=== p36 ===
Inference by enumeration
43
[IMAGE-ONLY]

=== p37 ===
•
The complexity of exact inference in Bayesian networks depends strongly on 
the structure of the network. 
•
The burglary network has at most one path between any two nodes. These are 
called singly connected networks or polytrees. The time and space 
complexity of exact inference in polytrees is linear in the size of the network. 
The complexity of exact inference
55

=== p38 ===
•
For multiply connected networks, such as that of Figure 14.12(a), variable 
elimination can have exponential time and space complexity in the worst case, 
even when the number of parents per node is bounded. In fact, it can be 
shown that the problem is an NP-hard problem. 
The complexity of exact inference
56

=== p39 ===
The complexity of exact inference
57
[IMAGE-ONLY]

=== p40 ===
•
Given the intractability of exact inference in large, multiply connected 
networks, it is essential to consider approximate inference methods. 
•
Monte Carlo algorithms provide approximate answers whose accuracy 
depends on the number of samples generated. 
•
Monte Carlo algorithms are used in many branches of science to estimate 
quantities that are difficult to calculate exactly. In this section, we describe 
two families of algorithms: direct sampling and Markov chain sampling. 
Approximate Inference in Bayesian Nets
60

=== p41 ===
•
The primitive element in any sampling algorithm is the generation of samples 
from a known probability distribution. For example, an unbiased coin can be 
thought of as a random variable Coin with values ⟨heads, tails⟩and a prior 
distribution P(Coin) = ⟨0.5,0.5⟩. 
•
Sampling from this distribution is exactly like flipping the coin: with 
probability 0.5 it will return heads, and with probability 0.5 it will return tails. 
•
Sample each variable in turn, in topological order. The probability distribution 
from which the value is sampled is conditioned on the values already assigned 
to the variable’s parents. 
Direct sampling methods
61

=== p42 ===
•
We can illustrate its operation on the network in Figure 14.12(a), assuming an 
ordering [Cloudy, Sprinkler, Rain, WetGrass]: 
•
In this case, PRIOR-SAMPLE returns the event [true, false, true, true].
Direct sampling methods
62

=== p43 ===
•
It is easy to see that PRIOR-SAMPLE generates samples from the prior joint 
distribution specified by the network. First, let SPS (x1, . . . , xn) be the 
probability that a specific event is generated by the PRIOR-SAMPLE 
algorithm. Just looking at the sampling process, we have 
because each sampling step depends only on the parent values.
Direct sampling methods
63

=== p44 ===
•
This expression should look familiar, because it is also the probability of the 
event according to the Bayesian net’s representation of the joint distribution, 
as stated in Equation (14.2). That is, we have
This simple fact makes it easy to answer questions by using samples.
Direct sampling methods
64

=== p45 ===
•
Suppose there are N total samples, and let NPS(x1, . . . , xn) be the number of 
times the specific event x1 , . . . , xn occurs in the set of samples. We expect 
this number, as a fraction of the total, to converge in the limit to its expected 
value according to the sampling probability:
For example, consider the event produced earlier: [true, false, true, true]. The 
sampling probability for this event is
in the limit of large N, we expect 32.4% of the samples to be of this event. 
Direct sampling methods
65

=== p46 ===
•
Whenever we use (“≈”), we mean that the estimated probability becomes 
exact in the large-sample limit. Such an estimate is called consistent. 
•
For example, one can produce a consistent estimate of the probability of any 
partially specified event x1 , . . . , xm, where m ≤ n, as follows: 
That is, the probability of the event can be estimated as the fraction of all 
complete events generated by the sampling process that match the partially 
specified event. For example, if we generate 1000 samples from the sprinkler 
network, and 511 of them have Rain = true, then the estimated probability of 
rain, written as P(Rain = true), is 0.511.
Direct sampling methods
66
(14.6)

=== p47 ===
•
Rejection sampling in Bayesian networks
•
Rejection sampling is a general method for producing samples from a hard-
to-sample distribution given an easy-to-sample distribution. In its simplest 
form, it can be used to compute conditional probabilities—that is, to 
determine P(X | e). 
•
The REJECTION-SAMPLING algorithm first generates samples from the 
prior distribution specified by the network. Then, it rejects all those that do 
not match the evidence. 
Finally, the estimate P(X = x | e) is obtained by counting how often X = x
occurs in the remaining samples.
Direct sampling methods
67

=== p48 ===
Direct sampling methods
69
[IMAGE-ONLY]

=== p49 ===
•
The true answer is ⟨0.3, 0.7⟩. As more samples are collected, the estimate will 
converge to the true answer. The standard deviation of the error in each 
probability will be proportional to           , where n is the number of samples 
used in the estimate.
•
The biggest problem with rejection sampling is that it rejects so many samples! 
The fraction of samples consistent with the evidence e drops exponentially as 
the number of evidence variables grows, so the procedure is simply unusable 
for complex problems.
Direct sampling methods
70

=== p50 ===
•
Markov chain Monte Carlo (MCMC) algorithms work quite differently 
from rejection sampling and likelihood weighting. Instead of generating each 
sample from scratch, MCMC algorithms generate each sample by making a 
random change to the preceding sample. 
•
Here we describe a particular form of MCMC called Gibbs sampling, which 
is especially well suited for Bayesian networks. 
Inference by Markov chain simulation
81

=== p51 ===
•
Gibbs sampling in Bayesian networks
•
The Gibbs sampling algorithm for Bayesian networks starts with an arbitrary 
state (with the evidence variables fixed at their observed values) and generates 
a next state by randomly sampling a value for one of the nonevidence 
variables Xi. The sampling for Xi is done conditioned on the current values of 
the variables in the Markov blanket of Xi. (Recall that the Markov blanket of a 
variable consists of its parents, children, and children’s parents.) The 
algorithm therefore flips one variable at a time, but keeping the evidence 
variables fixed.
Inference by Markov chain simulation
82

=== p52 ===
•
Consider the query P(Rain | Sprinkler = true, WetGrass = true) applied to the 
network in Figure 14.12(a). The evidence variables Sprinkler and WetGrass
are fixed to their observed values and the nonevidence variables Cloudy and 
Rain are initialized randomly— let us say to true and false respectively. Thus, 
the initial state is [true, true, false, true]. Now the nonevidence variables are 
sampled repeatedly in an arbitrary order.
Inference by Markov chain simulation
83
[Cloudy, Sprinkler, Rain, WetGrass]

=== p53 ===
Inference by Markov chain simulation
84
[IMAGE-ONLY]

=== p54 ===
Inference by Markov chain simulation
85
[IMAGE-ONLY]