CS 188 Spring 2020 Introduction to Artificial Intelligence Written HW 3 Sol. Solutions for HW 3 (Written)

Document Content and Description Below

CS 188 Spring 2020 Introduction to Artificial Intelligence Written HW 3 Sol. Solutions for HW 3 (Written) 1Q1. [30 pts] Quadcopter: Spectator Flying a quadcopter can be modeled using a Bayes Net... with the following variables: • W (weather) 2 fclear, cloudy, rainyg • S (signal strength) 2 fstrong, medium, weakg • P (true position) = (x; y; z; θ) where x; y; z each can take on values 2 f0; 1; 2; 3; 4g and θ can take on values 2 f0°; 90°; 180°; 270°g • R (reading of the position) = (x; y; z; θ) where x; y; z each can take on values 2 f0; 1; 2; 3; 4g and θ can take on values 2 f0°; 90°; 180°; 270°g • C (control from the pilot) 2 fforward, backward, rotate left, rotate right, ascend, descendg (6 controls in total) • A (smart alarm to warn pilot if that control could cause a collision) 2 fbad, goodg (a) Representation (i) [2 pts] What is Np, where Np is the domain size of the variable P? Please explain your answer. Answer: N p = 500 Explanation: 5 * 5 * 5 * 4 = 500 (ii) [2 pts] Please list all of the Conditional Probability Tables that are needed in order to represent the Bayes Net above. P(W); P(SjW); P(P); P(RjS; P); P(CjR); P(AjC; P) (iii) [1 pt] What is the size of the Conditional Probability Table for R? You may use Np in your answer. P(RjS; P) has size 750000 or 3 ∗ (Np)2 Now, assume that we look at this setup from the perspective of Spencer { a spectator who can observe A and W. Spencer observes A=bad and W=clear, and he now wants to infer the signal strength. In BN terminology, he wants to calculate P(SjA = bad; W = clear). (b) [5 pts] Inference by Enumeration If Spencer chooses to solve for this quantity using inference by enumeration, what is the biggest factor that must be calculated along the way, and what is its size? You may use Np in your answer. Please show your work. 2Biggest factor: f(W = clear; S; P; R; C; A = bad) Size of factor: Size is 1 ∗ 3 ∗ N p ∗ Np ∗ 6 ∗ 1 = 18(Np)2 (c) [5 pts] Inference by Variable Elimination: Order 1 Spencer chooses to solve for this quantity by performing variable elimination in the order of R−P −C. Answer the following prompts to work your way through this procedure. (1a) First, we need to eliminate R. Which factors (from the 6 CPTs above) are involved? P(RjS; P); P(CjR) (1b) Show the multiplication of those factors and eliminate the variable of interest. What conditional probability factor results from this step? eliminating r out of P(rjS; P) ∗ P(Cjr) results in f(CjS; P) (2a) Second, we need to eliminate P. Which factors are involved? P(A = badjC; P); P(P); f(CjS; P) (2b) Show the multiplication of those factors and eliminate the variable of interest. What conditional probability factor results from this step? eliminating p out of P(A = badjC; p) ∗ P(p) ∗ f(CjS; P) results in f(A = bad; CjS) (3a) Third, we need to eliminate C. Which factor/s are involved? f(A = bad; CjS) (3b) Show the multiplication of those factors and eliminate the variable of interest. What conditional probability factor results from this step? eliminating c out of f(A = bad; CjS) results in f(A = badjS) (4) List the 3 conditional probability factors that you calculated as a result of the 3 elimination steps above, along with their domain sizes. Which factor is the biggest? Is this bigger or smaller than the biggest factor from the \inference by enumeration" approach? f(CjS; P); f(A = bad; CjS); f(A = badjS): Biggest is f(CjS; P), whose size is 6 ∗ 3 ∗ Np = 18 ∗ Np. This is smaller than the biggest factor from inference by enumeration. (5) List the 1 unused conditional probability factor from the 3 that you calculated above, and also list the 2 unused conditional probability factors from the 6 original CPTs. f(A = badjS); P(SjW = clear); P(W = clear) (6) Finally, let’s solve for the original quantity of interest: P(SjA = bad; W = clear). After writing the equations to show how to use the factors from (5) in order to solve for f(SjA = bad; W = clear), don’t forget to write how to turn that into a probability P(SjA = bad; W = clear). Hint: use Bayes Rule, and use the 3 unused factors that you listed in the previous question. By Bayes rule, P(SjA = bad; W = clear) = PP(A(A==bad;S;W bad;W ==clear clear)) where f(A = badjS)P(SjW = clear)P(W = clear) gives the joint f(A = bad; S; W = clear), and eliminating s out of that joint gives f(A = bad; W = clear). Just normalize the whole thing at the end. (d) [5 pts] Inference by Variable Elimination: Order 2 Spencer chooses to solve for this quantity by performing variable elimination, but this time, he wants to do elimination in the order of P − C − R. Answer the following prompts to work your way through this procedure. (1a) First, we need to eliminate P. Which factors (from the 6 CPTs above) are involved? [Show More]

Last updated: 1 year ago

Preview 1 out of 11 pages