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