CS188: Artificial Intelligence, Spring 2009Written Assignment 3: Probabilistic ModelsDue: April 16 (extended!)You can work on this in groups, but everyone should turn in his/her own work.Don’t forget your name and login.Name:Login:GSI:Section Time:1 Question 1: Bayes Net InferenceDr. A. Gent, an armchair climatologist, wants to predict whether or not it’s going to (R)ain. When it’s(C)loudy, it tends to (R)ain unless it’s (W)indy. From her armchair, Dr. Gent can observe the clouds (C)but not the wind. However, if it’s (W)indy, then the tree outside tends to (S)way, which she can observed.Sometimes the tree (S)ways even when it’s not windy. Squirrels, perhaps?(S)waying(C)loudy(W)indy(R)ainP (C)C P (C)c 0.4P (W )W P (W )w 0.6P (R|C, W )C W R P (R = r|C, W )c w r 0.40c ¬w r 0.80¬c w r 0.10¬c ¬w r 0.20P (S|W )W S P (S = s|W )w s 0.9¬w s 0.3Note: the tables above are abbreviated, but fully specified, e.g., P (¬r|c, w) = 1 − P (r|c, w) = 0.6.a) What is the probability of perfect weather, P (¬c, ¬r, ¬w)?P (C)C P (C)c 0.4P (W )W P (W )w 0.6P (R|C, W )C W R P (R = r|C, W )c w r 0.40c ¬w r 0.80¬c w r 0.10¬c ¬w r 0.20P (S|W )W S P (S = s|W )w s 0.9¬w s 0.3Conditional probability tables (CPTs) are repeated for convenience.b) A dangling node is a leaf node that is unobserved in a query. When computing P (C, R, W ), S isdangling. Show that the probabilities in the CPT for P (S|W ) cannot affec t P (C, R, W ) for this network,regardless of the values in the CPTs above.c) Can the CPT of a dangling leaf node for a query ever affect the outcome of that query? If so, when? Ifnot, what preprocessing step does this fact suggest for variable elimination?d) Compute P(R) using the variable elimination algorithm, perhaps modified by your answer to (c). Writedown the intermediate factors after summing out each hidden variable. Hint: you can answer this questionwith one intermediate factor, in addition to P (R).e) Now, approximate P (R|C = ¬c, S = ¬s) using each of the two sets of samples be low.Prior samples (rejection sampling):c, ¬w, s, r ¬c, w, s, ¬r c, w, s, ¬r ¬c, ¬w, ¬s, ¬r¬c, w, s, ¬r ¬c, w, ¬s, ¬r c, ¬w, ¬s, ¬r c, w, s, r¬c, w, s, r c, ¬w, ¬s, r ¬c, w, s, ¬r ¬c, w, s, ¬r¬c, ¬w, ¬s, ¬r ¬c, w, s, ¬r c, w, s, ¬r ¬c, ¬w, s, rP (R = r|C = ¬c, S = ¬s) ≈Weighted samples (likeliho od weighting):¬c, w, ¬s, ¬r ¬c, w, ¬s, r¬c, ¬w, ¬s, ¬r ¬c, w, ¬s, ¬rP (R = r|C = ¬c, S = ¬s) ≈22 Question 2: Conditional Independence ReviewConsider the following Bayes’ nets.A(i)SFRHVA(ii)SFRHVA(iii)SFRHVA(iv)SFRHVFor each of the following conditional independence properties, circle the number of each network forwhich the statement is guaranteed to be true.F ⊥⊥ R (i) (ii) (iii) (iv)F ⊥⊥ A (i) (ii) (iii) (iv)V ⊥⊥ A | F (i) (ii) (iii) (iv)V ⊥⊥ A | R (i) (ii) (iii) (iv)F ⊥⊥ R | S (i) (ii) (iii) (iv)A ⊥⊥ R | V (i) (ii) (iii) (iv)33 Question 3: The Captain’s TreasureYou are searching for the treasure of Captain Long Beard, lost for fifty years. You’ve narrowed down thesearch to four sites on the corners of Dinghy Island. Here is what you know:i. The treasure is in one of four locations: the North-East, North-West, South-East, or South-West. Youassign equal probability to each. Let L ∈ {ne, nw, se, sw} be the (unknown) location of the treasure.ii. You can only dig in one of the four locations. Let A ∈ {ne, nw, se, sw} indicate where you dig.iii. The North of the island is rocky, and the South sandy. If the treasure is in the North and you dig inthe correct location, you retrieve the treasure with probability 0.5, whilst if the treasure is in the Southand you dig in the correct place, you retrieve it with probability 0.9. Let T ∈ {t, f } be the variablerecording whether you retrieve the treasure.iv. The town’s guard claims to have seen w hether Long Beard took the road to the North or to the Southof the island when burying his treasure. The guard is willing to (honestly) tell you what he remembers,but his memory is shaky and biases Northward. If the Captain went North, the guard would remember.If the Captain went South, the guard has a14chance of remembering North anyway. Let G ∈ {n, s} bethe variable indicating whether the guard remembers the Captain burying the treasure in the Northor the South of the island.v. Your utility U is measured in dollars. The treasure chest is filled with gold, worth $1000. The East ofthe island is reachable only by river, so if you dig there you must buy a raft for $40.a) Draw the decision network for this problem and fill in the conditional probability tables for each variableand the utility function table.L P (L)nenwseswL A T P (T |L, A)ne ne tnw nw tse se tsw sw tL 6= A tL G P (G|L)ne nnw nse nsw nA T U (A, T )ne tne fnw tnw fse tse fsw tsw f4b) What is the best place to dig if you do not know what the town guard remembers. What is the expectedutility of this action?c) Supp ose the guard tells you that he remembers the Captain going North. Now what is the best placeto dig, and what is the expected utility of this action? Hint: first compute the distribution P (L | G = n).d) Now suppose the guard tells you that he remembers the Captain going South instead. What is the bestplace to dig based on this information, and what is the expected utility of this action?e) What is the value of the guard telling you what he remembers (assuming you don’t already know)?f) The guard will only tell you the information if you promise to dig in the East (his wife sells rafts). Howmuch money do you exp e ct to gain (or lose) by accepting his offer, versus digging without his information?54 Question 4: Playing PokerYou are playing poker against a friend. Over the years, you’ve collected data about her tendency to bluff(as opposed to playing her cards straight up) and decide to model her habits with the following HMM.State P (X1)bluff 0.2straight up 0.8Previous State Current State P (Xt|Xt−1)bluff bluff 0.2bluff straight up 0.8straight up bluff 0.6straight up straight up 0.4State Observation P (Ot|Xt)bluff rolls eyes 0.6bluff scratches shoulder 0.4straight up rolls eyes 0.3straight up scratches shoulder 0.7a) On the first hand, your friend rolls her eyes. What is the posterior probability that she is bluffing onthe first hand?b) You observe two consecutive eye rolls on hands 1 and 2. What’s the probability that she is bluffing onthe second hand?c) You confirm that s he was in fact bluffing on
View Full Document
Unlocking...