New version page

Berkeley CS 188 - Exam Prep 6 Solutions

This preview shows page 1 out of 4 pages.

View Full Document
View Full Document

End of preview. Want to read all 4 pages?

Upload your study docs or become a GradeBuddy member to access this document.

View Full Document
Unformatted text preview:

CS 188Fall 2019 Exam Prep 6 SolutionsQ1. Probability and Bayes Nets(a) A, B, and C are random variables with binary domains. How many entries are in the following probabilitytables and what is the sum of the values in each table? Write a “?” in the box if there is not enoughinformation given.Table Size SumP (A, B|C) 8 2P (A| + b, +c) 2 1P (+a|B) 2 ?(b) Circle true if the following probability equalities are valid and circle false if they are invalid (leave it blankif you don’t wish to risk a guess). Each True/False question is worth 1 points. Leaving a question blankis worth 0 points. Answering incorrectly is worth −1 points.No independence assumptions are made.(i) [true or false] P (A, B) = P (A|B)P (A)False. P (A, B) = P (A|B)P (B) would be a valid example.(ii) [true or false] P (A|B)P (C|B) = P (A, C|B)False. This assumes that A and C are conditionally independent given B.(iii) [true or false] P (B, C) =Pa∈AP (B, C|A)False. P (B, C) =Pa∈AP (A, B, C) would be a valid example.(iv) [true or false] P (A, B, C, D) = P (C)P (D|C)P (A|C, D)P (B|A, C, D)True. This is a valid application of the chain rule.(c) Space Complexity of Bayes NetsConsider a joint distribution over N variables. Let k be the domain size for all of these variables, and letd be the maximum indegree of any node in a Bayes net that encodes this distribution.(i) What is the space complexity of storing the entire joint distribution? Give an answer of the formO(·).O(kN) was the intended answer. Because of the potentially misleading wording, we also allowedO(Nkd+1), one possible bound on the space complexity of storing the Bayes net (O((N − d)kd+1) isan asymptotically tighter bound, but this requires considerably more effort to prove).(ii) Draw an example of a Bayes net over four binary variables such that it takes less space to store theBayes net than to store the joint distribution.A simple Markov chain works. Size 2 + 4 + 4 + 4 = 14, which is less than 24= 16. Less edges, lessinbound edges (v-shape), or no edges would work too.(iii) Draw an example of a Bayes net over four binary variables such that it takes more space to store theBayes net than to store the joint distribution.Size 2 + 2 + 2 + 24= 22, which is more than 24= 16. Other configurations could work too, especiallyany with a node with indegree 3.12Q2. Probability(a) For the following questions, you will be given a set of probability tables and a set of conditional inde-pendence assumptions. Given these tables and independence assumptions, write an expression for therequested probability tables. Keep in mind that your expressions cannot contain any probabilities otherthan the given probability tables. If it is not possible, mark “Not possible.”(i) Using probability tables P(A), P(A | C), P(B | C), P(C | A, B) and no conditional independenceassumptions, write an expression to calculate the table P(A, B | C).P(A, B | C) = Not possible.(ii) Using probability tables P(A), P(A | C), P(B | A), P(C | A, B) and no conditional independenceassumptions, write an expression to calculate the table P(B | A, C).P(B | A, C) =P (A) P (B|A) P (C|A,B)PbP (A) P (B|A) P (C|A,B)# Not possible.(iii) Using probability tables P(A | B), P(B), P(B | A, C), P(C | A) and conditional independence as-sumption A ⊥⊥ B, write an expression to calculate the table P(C).P(C) =PaP (A | B) P (C | A) # Not possible.(iv) Using probability tables P(A | B, C), P(B), P(B | A, C), P(C | B, A) and conditional independenceassumption A ⊥⊥ B | C, write an expression for P(A, B, C).P(A, B, C) = Not possible.(b) For each of the following equations, select the minimal set of conditional independence assumptionsnecessary for the equation to be true.(i) P(A, C) = P(A | B) P(C) A ⊥⊥ B A ⊥⊥ B | C A ⊥⊥ C A ⊥⊥ C | B B ⊥⊥ C B ⊥⊥ C | A No independence assumptions needed.Alternatively, A ⊥⊥ B | C and A ⊥⊥ C | B can be selected.(ii) P(A | B, C) =P(A) P(B|A) P(C|A)P(B|C) P(C) A ⊥⊥ B A ⊥⊥ B | C A ⊥⊥ C A ⊥⊥ C | B B ⊥⊥ C B ⊥⊥ C | A No independence assumptions needed.(iii) P(A, B) =PcP(A | B, c) P(B | c) P(c) A ⊥⊥ B A ⊥⊥ B | C A ⊥⊥ C A ⊥⊥ C | B B ⊥⊥ C B ⊥⊥ C | A No independence assumptions needed.3(iv) P(A, B | C, D) = P(A | C, D) P(B | A, C, D) A ⊥⊥ B A ⊥⊥ B | C A ⊥⊥ B | D C ⊥⊥ D C ⊥⊥ D | A C ⊥⊥ D | B No independence assumptions needed.(c) (i) Mark all expressions that are equal to P(A | B), given no independence assumptions. PcP (A | B, c)PcP (A, c | B) P (B|A) P (A|C)PcP (B,c)PcP (A,B,c)PcP (B,c) P (A,C|B)P (C|B) P (A|C,B) P (C|A,B)P (C|B) None of the provided options.(ii) Mark all expressions that are equal to P(A, B, C), given that A ⊥⊥ B. P (A | C) P (C | B) P (B) P (A) P (B) P (C | A, B) P (C) P (A | C) P (B | C) P (A) P (C | A) P (B | C) P (A) P (B | A) P (C | A, B) P (A, C) P (B | A, C) None of the provided options.(iii) Mark all expressions that are equal to P(A, B | C), given that A ⊥⊥ B | C. P (A | C) P (B | C) P (A) P (B|A) P (C|A,B)PcP (A,B,c) P (A | B) P (B | C) P (C) P (B|C) P (A|C)P (C|A,B) PcP (A,B,c)P (C)P (C,A|B) P (B)P (C) None of the provided


View Full Document
Loading Unlocking...
Login

Join to view Exam Prep 6 Solutions and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Exam Prep 6 Solutions and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?