final-bayes

CS 188 Summer 2023 Final Review Bayes Nets Q1. Bayes Nets: Representation D B A C Consider the Bayes net graph depicted above. (a) (i) Select all conditional independences that are enforced by this Bayes net graph. □ A ⊥⊥ B □ A ⊥⊥ C | B □ D ⊥⊥ C | A, B □ D ⊥⊥ C □ A ⊥⊥ C □ A ⊥⊥ C | D □ A ⊥⊥ C | B, D □ D ⊥⊥ C | B (ii) Because of these conditional independences, there are some distributions that cannot be represented by this Bayes net. What is the minimum set of edges that would need to be added such that the resulting Bayes net could represent any distribution? □ A → C □ C → A □ C → D □ D → C □ D → A □ D → B □ B → C □ B → A (b) For the rest of this Q2, we use the original, unmodified Bayes net depicted at the beginning of the problem statement. Here are some partially-filled conditional probability tables on A , B , C , and D . Note that these are not necessarily factors of the Bayes net. Fill in the six blank entries such that this distri- bution can be represented by the Bayes net. A C P ( C | A ) + a + c 0 . 8 + a − c 0 . 2 − a + c 0 . 8 − a − c 0 . 2 A B D P ( D | A, B ) + a + b + d 0 . 60 + a + b − d 0 . 40 + a − b + d 0 . 10 + a − b − d 0 . 90 − a + b + d 0 . 20 − a + b − d 0 . 80 − a − b + d 0 . 50 − a − b − d 0 . 50 A B C P ( C | A, B ) + a + b + c 0 . 50 + a + b − c 0 . 50 + a − b + c 0 . 20 + a − b − c 0 . 80 − a + b + c 0 . 90 − a + b − c 0 . 10 − a − b + c 0 . 40 − a − b − c 0 . 60 C P ( C ) + c (i) − c (ii) A B C D P ( D, C | A, B ) + a + b + c + d (iii) + a + b − c − d (iv) + a − b + c + d (v) + a − b − c − d (vi) . . . . . . . . . . . . . . . 1

Q2. Bayes Nets: Elimination (a) Consider running variable elimination on the Bayes Net shown below. A D B E F C G H J First, we eliminate D to create a factor f 1 Next, we eliminate E to create a factor f 2 Next, we eliminate H to create a factor f 3 From the list below, select all factors that remain after D , E and H have been eliminated. □ f 1 □ f 2 □ f 3 □ P ( A ) □ P ( A | F ) □ P ( B ) □ P ( B | A ) □ P ( B | C ) □ P ( C ) □ P ( C | B ) □ P ( D | A ) □ P ( D | A, F ) □ P ( E | B ) □ P ( E | C ) □ P ( E | B, C ) □ P ( F ) □ P ( F | A, B ) □ P ( F | G ) □ P ( G | C ) □ P ( G | C, F ) □ P ( H | F ) □ P ( H | C, F ) □ P ( H | J ) □ P ( J | C ) □ P ( J | F ) □ P ( J | H ) (b) Consider the Bayes Net shown below. Each variable in the Bayes Net can take on two possible values. A B D C E F You are given the query P ( C | F ), which you would like to answer using variable elimination. Please find a variable elimination ordering where the largest intermediate factor created during variable elimination is as small as possible. Elimination ordering: 2

Q3. Bayes Nets: Inference Consider the following Bayes Net, where we have observed that D = + d . P ( A ) + a 0 . 5 − a 0 . 5 P ( B | A ) + a + b 0 . 5 + a − b 0 . 5 − a + b 0 . 2 − a − b 0 . 8 P ( C | A, B ) + a + b + c 0 . 8 + a + b − c 0 . 2 + a − b + c 0 . 6 + a − b − c 0 . 4 − a + b + c 0 . 2 − a + b − c 0 . 8 − a − b + c 0 . 1 − a − b − c 0 . 9 P ( D | C ) + c + d 0 . 4 + c − d 0 . 6 − c + d 0 . 2 − c − d 0 . 8 (a) Below is a list of samples that were collected us- ing prior sampling. Mark the samples that would be rejected by rejection sampling. □ + a − b + c − d □ + a − b + c + d □ − a + b − c − d □ + a + b + c + d (b) To decouple from the previous part, you now re- ceive a new set of samples shown below: + a + b + c + d − a − b − c + d + a + b + c + d + a − b − c + d − a − b − c + d Estimate the probability P (+ a | + d ) if these new samples were collected using... (i) ... rejection sampling: (ii) ... likelihood weighting: (c) Instead of sampling, we now wish to use variable elimination to calculate P (+ a | + d ). We start with the factorized representation of the joint probability: P ( A, B, C, + d ) = P ( A ) P ( B | A ) P ( C | A, B ) P (+ d | C ) (i) We begin by eliminating the variable B , which creates a new factor f 1 . Complete the expression for the factor f 1 in terms of other factors. f 1 ( ) = (ii) After eliminating B to create a factor f 1 , we next eliminate C to create a factor f 2 . What are the remaining factors after both B and C are eliminated? □ p ( A ) □ p ( B | A ) □ p ( C | A, B ) □ p (+ d | C ) □ f 1 □ f 2 (iii) After eliminating both B and C , we are now ready to calculate P (+ a | + d ). Write an expression for P (+ a | + d ) in terms of the remaining factors. P (+ a | + d ) = 4