CSCI 4150: Introduction to Artificial Intelligence, 2014 Spring
Homework 1: Probability and Bayesian networks
(Due Feb 24 before class)
Total points: 100. Bonus points: 20.
We only accept electronic submission at Submitty. Please try to ask questions on Piazza. If Piazza is not helpful,
please contact the TAs.
1 CSP
Problem 1 (10 points.) Textbook problem 6.2 a-c (page 230 in the third edition).
2 Probability
Problem 2 (10 points.) Prove the chain rule. That is, for any probabilistic model composed of random variables
X1, . . . , Xn and any valuesx1, . . . , xn, we have:
p(x1, . . . , xn) =
n∏
i=1
p(xi|x1, . . . , xi−1)
Problem 3 (10 points.) Prove that the two definitions of conditional independence of random variables are equivalent.
Let X , Y , Z be random variables. The two definitions are:
Definition 1: X and Y are conditionally independent given Z if for any value x of X , any value y of Y , and
any value z of Z, the following holds: p(x, y|z) = p(x|z)× p(y|z).
Definition 2: X and Y are conditionally independent given Z if for any value x of X , any value y of Y , and
any value z of Z, the following holds: p(x|y, z) = p(x|z).
Problem 4 (bonus question 20 points.) Let X , Y , Z be random variables. Prove or disprove the following statements.
(That means, you need to either write down a formal proof, or give a counterexample.)
Statement 1. If X and Y are (unconditionally) independent, is it true that X and Y are conditionally independent
given Z?
Statement 2. If X and Y are conditionally independent given Z, is it true that X and Y are (unconditionally)
independent?
3 Bayesian networks
We are going to take the perspective of an instructor who wants to determine whether a student has understood the
material, based on the exam score. Figure 1 gives a Bayesian network for this. As you can see, whether the student
1
Intelligent Hardworking
Understands
material
high Exam
score
good Test
taker
P(+i) = .7
P(+t|+i) = .8
P(+t|-i) = .5
P(+h) = .6
P(+u|+i,+h) = .9
P(+u|+i,-h) = .3
P(+u|-i,+h) = .5
P(+u|-i,-h) = .1
P(+e|+t,+u) = .9
P(+e|+t,-u) = .5
P(+e|-t,+u) = .7
P(+e|-t,-u) = .3
Figure 1: A Bayesian network representing what influences an exam score.
scores high on the exam is influenced both by whether she is a good test taker, and whether she understood the
material. Both of those, in turn, are influenced by whether she is intelligent; whether she understood the material is
also influenced by whether she is a hard worker.
Problem 5 (40 points.)
For the above Bayesian network, label the following statements about conditional independence as true or false.
For this question, you should consider only the structure of the Bayesian network, not the specific probabilities.
Explain each of your answers. Specifically, when you claim conditional dependence, you must show an active
path.
1. T and U are independent.
2. T and U are conditionally independent given I , E, and H .
3. T and U are conditionally independent given I and H .
4. E and H are conditionally independent given U .
5. E and H are conditionally independent given U , I , and T .
6. I and H are conditionally independent given E.
7. I and H are conditionally independent given T .
8. T and H are independent.
9. T and H are conditionally independent given E.
10. T and H are conditionally independent given E and U .
Problem 6 (30 points).
2
Using variable elimination (by hand!), compute the probability that a student who did well on the test actually
understood the material, that is, compute P (+u|+ e).
3