# 程序代写代做代考 chain Bayesian network Bayesian CSCI 4150: Introduction to Artificial Intelligence, 2014 Spring

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