Homework 1CS 6347: Statistical methods in AI/MLInstructor: Vibhav [email protected] date: Monday Feb. 14, 2022 via elearning[ Key: AD: Book by Adnan Darwiche, KF: Koller Friedman]• WARNING: Start early. Some problems are quite hard (e.g., Problems 8 and 10).• Each problem is worth 10 pointsProblem 1: Propositional logic [Problems 2.6 to 2.9 from AD]• Prove the Refutation theorem, namely α |= β iff α ∧ ¬β is inconsistent.• Prove the Deduction theorem, namely α |= β iff α ⇒ β is valid.• Prove that if α |= β then α ∧ β is equivalent to α.• Prove that if α |= β then α ∨ β is equivalent to β.Problem 2: Probability theory• Prove that the following two definitions of conditional independence are equivalent.1. Pr(α|β ∧ γ) = Pr(α|γ)2. Pr(α ∧ β|γ) = Pr(α|γ) Pr(β|γ)[Hint: Derive one using the other using laws of probability.]1Problem 3: Probability theory (Exercise 2.10 from Koller & Friedman)The question investigates the way in which conditional independence relationships af-fect the amount of information needed for probabilistic calculations. Let α, β, and γ bethree propositional variables.• Suppose we wish to calculate Pr(α|β, γ) and we have no conditional independenceinformation. Which of the following sets of numbers is sufficient for the calculation?1. Pr(α, β), Pr(α), Pr(β|α) and Pr(γ|α).2. Pr(β, γ), Pr(α) and Pr(β, γ|α)3. Pr(β|α), Pr(γ|α) and Pr(α).For each case, justify your response either by showing how to calculate the desiredanswer or by explaining why this is not possible.• Suppose we know that β and γ are conditionally independent given α. Now whichof the preceeding three sets is sufficient. Justify your response as before.Problem 4: Independence relations• Prove that Weak Union and Contraction hold for any probability distribution Pr.• Provide a counter-example to the intersection property. (You cannot use the counterexample given in AD, you have to make your own.)Problem 5: Bayesian networks (AD Exercise 4.1)2Consider the Bayesian network given above.1. List the Markovian assumptions asserted by the DAG.2. Express Pr(a, b, c, d, e, f, g, h) in terms of network parameters.3. Compute Pr(A = 0, B = 0) and Pr(E = 1|A = 1). Justify your answers.4. True or false? Why?(a) dsep(A, BH, E)(b) dsep(G, D, E)(c) dsep(AB, F, GH)3Problem 6: Bayesian networks (AD Exercise 4.12)Construct two distinct DAGs over variables A, B, C, and D. Each DAG must haveexactly four edges and the DAGs must agree on d-separation.Problem 7: Bayesian networks (AD Exercise 4.15)Identify a DAG that is a D-MAP for all distributions Pr over variables X. Similarly,identify another DAG that is an I-MAP for all distributions Pr over variables X.Problem 8: Sensitivity Analysis. Consider two Bayesian networks B1and B2that haveidentical graph structure G and identical conditional probability tables everywhere exceptat node Z. When can we guarantee that PB1(X|Y) = PB2(X|Y)? Note that Z may be thesame as X and may also belong to Y.Note: Your criterion should be stated purely in terms of the network structure and must besound.Problem 9: Bayesian networks (AD Exercise 4.17)Prove that for strictly positive distributions, if B1and B2are Markov blankets for somevariable X, then B1∩B2is also a Markov blanket for X. [Hint: Appeal to the intersectionaxiom.]Problem 10: Node Elimination. Define an algorithm that transforms the structure ofthe BN into BN’ such that one of the nodes Xiin the BN is not in BN’ and BN’ is anI-map of the marginal distribution over the remaining variables is defined by