6.825 Homework 3: Solutions

6.825 Homework 3: Solutions 1 Easy EM You are given the network structure shown in Figure 1 and the data in the following table, with actual observed values for A, B, and C, and expected counts for D. A 1 0 0 0 1 0 1 1 0 0 0 0 0 0 1 1 1 B 1 0 0 1 1 0 0 1 1 0 0 1 1 1 0 0 1 C 1 0 1 1 1 0 1 0 1 1 1 0 1 1 0 1 1 Pr(D|A, B, C) .6 .3 .7 .9 .6 .3 .5 .4 .9 .7 .7 .1 .9 .9 .2 .5 .6 A D B C Figure 1: Network Structure 1 F A B C D E G Figure 2: Network Structure 1. What are the maximum likelihood estimates for Pr(A), Pr(D|A), Pr(B|D), and Pr(C|D)? Solution: 7 17 = 0.412 Pr(D|A) = E#[D∧A] E#[A] = 3.4 7 = 0.486 Pr(B|D) = E#[B∧D] E#[D] = 5.9 9.8 = 0.602 Pr(C|D) = E#[C∧D] E#[D] = 8.5 9.8 = 0.867 Pr(A) = 2. What’s another way to represent this data in a table with only 8 entries? Solution: Use a table that tallies the occurrences of each data sample. A 0 0 0 0 1 1 1 1 2 B 0 0 1 1 0 0 1 1 C 0 1 0 1 0 1 0 1 Pr(D|a, b, c, d) .3 .7 .1 .9 .2 .5 .4 .6 Number of Occurrences 2 3 1 4 1 2 1 3 Harder EM Consider the Bayesian network structure shown in Figure 2. 1. Write down an expression for Pr(a, b, c, d, e, f, g) using only conditional probabilities that would be stored in that network structure. Solution: Pr(a, b, c, d, e, f, g) = Pr(f) Pr(a|f) Pr(b|f) Pr(c|a, b) Pr(d|c) Pr(e|c) Pr(g|e, d) 2 2. We’d like to use variable elimination to compute Pr(d|b). Which variables are irrelevant? Solution: Variables E and G are irrelevant. If we try to sum them out, we get factors that are identical to 1. 3. Using elimination order A, B, C, D, E, F, G to compute Pr(d|b), what factors get created? Solution: We’ve already established that we can ignore E and G. And since we’re naming specific values d and b in our query, we really only need to sum over A, C, and F. Summing over F gives us factor X Pr(f) Pr(a|f) Pr(b|f) . f1 (a, b) = F Summing over C gives us factor f2 (a, b, d) = X Pr(c|a, b) Pr(d|c) . C Summing over A gives us Pr(b, d) = X f1 (a, b)f2 (a, b, d) . A To get the conditional probability we want, we first need to compute X Pr(b) = Pr(b, d) ; D then Pr(d|b) = Pr(b, d)/ Pr(b). 4. Assume variables F and C are hidden. You have a data set consisting of vectors of values of the other variables: ha, b, d, e, gi. You start with an initial set of parameters, θ0 , that contains CPTs for the whole network. You decide to estimate Pr(f|a, b, d, e, g) and Pr(c|a, b, d, e, g) separately, for each row of the table, as shown. A 0 0 0 0 0 ... B 1 0 0 1 0 D 0 0 0 0 0 E 1 1 0 1 0 G 1 1 1 1 1 Pr(F|a, b, d, e, g) Pr(C|a, b, d, e, g) Is this justified? Why or why not? Solution: I should have said, above, “you decide to calculate” rather than “you decide to estimate” above, since we calculate these values directly from the data in each row and the model. 3 The answer is, in this case, yes, but not always. In particular, because F and C are independent given A and B, we can write Pr(F, C|a, b, d, e, g) = Pr(F|a, b) Pr(C|a, b, d, e) , and so it’s okay to fill in values for F and C independently given the other variables. (Note that we can save time by figuring out Pr(F|a, b) for every value of a and b, and using those values to fill in the whole column.) If, instead, we had A and B as the hidden variables, we would have to estimate their values jointly, since they are not independent given values of all the other variables. Thus, we’d have to make a table that looked something like: C 0 D 1 E 0 F 1 G 1 0 0 0 1 1 A 0 0 1 1 0 0 1 1 B 0 1 0 1 0 1 0 1 Pr(a, b|c, d, e, f, g) .4 .3 .2 .1 .05 .1 .05 .8 ... This table contains the conditional joint of A and B, for each actually observed data point. You could also make it more compact by collapsing all duplicate data points and counting them, as we did above. 5. Now you think of another shortcut: You decide to estimate Pr(G|d, e) directly from the data and leave G out of the EM computations all together. Is this justified? Solution: Yes. Pr(G|a, b, c, d, e, f) = Pr(G|d, e). EM starts with some values in the CPT, and then it loops for a while, alternately (a) estimating the counts for the missing data from the CPT, and then (b) re-estimating the CPT given the new estimated counts for the missing data. But, G’s CPT entry does not depend on the missing data, F and G; it only depends on D and E. So, it’s ok to calculate its CPT parameters once, and then leave them out of the EM loop. 3 Markov Chain Consider a 3-state Markov chain, where R(s1 ) = 1, R(s2 ) = 3, and R(s3 ) = −1. The transition probabilities are given by the table below, where the entry in row i, column j, is the probability of making a transition from si to sj . 4 s1 s2 s3 s1 0.8 0.2 0.9 s2 0.1 0.1 0.1 s3 0.1 0.7 0.0 1. Compute the values of each state, assuming a discount factor of γ = 0.9. 2. Compute the values with a discount factor of γ = 0.1. Solution: Writing out the full equation for the values of each state we get: v1 = 1 + 0.8 γ v1 + 0.1 γ v2 + 0.1 γ v3 v2 = 3 + 0.2 γ v1 + 0.1 γ v2 + 0.7 γ v3 v3 = −1 + 0.9 γ v1 + 0.1 γ v2 Or, in matrix form:       0.8 γ − 1 0.1 γ 0.1 γ v1 −1       0.1 γ − 1 0.7 γ  ·  v2  =  3   0.2 γ 0.9 γ 0.1 γ −1 v3 1 With γ = 0.9 and 0.1, respectively, we find: v1 = 9.26, 1.11 v2 = 10.27, 2.99 v3 = 7.42, −0.87 4 Markov Decision Process Now, consider a Markov decision process with the same states and rewards as in the previous problem. It has two actions. The first action is described by the transition matrix given above. The second action is described by the following transition matrix: s1 s2 s3 s1 0.1 0.7 0.9 s2 0.1 0.1 0.0 s3 0.8 0.2 0.1 Starting with a value function that is 0 for all states, perform value iteration for 10 iterations for γ = 0.9. Do it again for γ = 0.1. Can you see it converging faster in one case? If so, why? Can you see what the optimal policy is? How could you compute the values of the states under the optimal policy? Solution: The solution can be implemented in a few lines of matlab: 5 g = 0.9; %or 0.1 r = [1; 3; -1]; v = [0; 0; 0]; a1 = [0.8, 0.1, 0.1; 0.2, 0.1, 0.7; 0.9, 0.1, 0]; a2 = [0.1, 0.1, 0.8; 0.7, 0.1, 0.2; 0.9, 0.0, 0.1]; for i = 1:10, v = r + g*max(a1*v, a2*v); end, v With γ = 0.9 and 0.1, respectively, we find after ten iterations: v1 = 6.51, 1.11 v2 = 8.35, 3.09 v3 = 4.68, −0.87 We see that when γ = 0.1, the values for each state are greater than or equal to those found in problem 3. We should expect this, since value iteration finds a global optimum; the policy of always choosing the first action would give exactly the discounted rewards found in problem 3, and the optimal policy will perform better than or equal to that. So why isn’t this true when γ = 0.9? The algorithm hasn’t converged yet. Running for 1000 iterations, we find the values converge to: v1 = 10.0 v2 = 11.83 v3 = 8.16 These values are better than those found in problem 3 for γ = 0.9. Intuitively, the algorithm converges quickly with smaller values of γ because we are putting less of an emphasis on future rewards and so don’t have to consider as many time steps to get a good estimate. Concretely, the value of future rewards decays to zero much more rapidly when γ = 0.1. To compute the optimal policy, it is only necessary to see which action gives the highest expected value at each state once value iteration has converged. For this problem, the optimal actions are 1, 2, 1, for states s1 , s2 , and s3 respectively. So, to compute the optimal values exactly we can treat this problem as a Markov Chain with transition probabilities: s1 s2 s3 s1 0.8 0.7 0.9 s2 0.1 0.1 0.1 s3 0.1 0.2 0.0 Solving this system as in the previous problem will produce the same values as value iteration. 5 At the Races, again You go to the horse races, hoping to win some money. Your options are to: • Bet $2 on Moon. You think that he’ll win with probability 0.7. If he wins, you’ll get back $4. If he loses, you’ll get back nothing. 6 • Bet $2 on Jeb. You think that he’ll win with probability 0.2. If he wins, you’ll get back $22. If he loses, you’ll get back nothing. • Bet $1 on Moon and $1 on Jeb. With probability 0.7, Moon will win and you’ll get back $2. With probability 0.2, Jeb will win, and you’ll get back $11. If they both lose, you’ll get back nothing. 1. What’s the expected value of each bet? What action would a risk-neutral bettor choose? Solution: Expected Values: • Bet $2 on Moon: .7 · U(2) + .3 · U(−2) = 0.8 • Bet $2 on Jeb: .2 · U(20) + .8 · U(−2) = 2.4 • Bet $1 on Moon and $1 on Jeb: .7 · U(0) + .2 · U(9) + .1 · (−2) = 1.6 So a risk-neutral bettor would choose the second option, putting all their money on Jeb. 2. Now, consider a risk-averse bettor, whose utility function for money is √ U(x) = x + 20 . What are the expected utilities of each bet? What action would that person choose? Solution: Expected utilities: • Bet $2 on Moon: 4.56 • Bet $2 on Jeb: 4.66 • Bet $1 on Moon and $1 on Jeb: 4.63 This person would choose the second option, as well, but it’s very close to the other options. √ If we changed the utility function to be U(x) = x + 3, the values for the three bets are now 1.87, 1.76, and 2.01. So now, we’d prefer option 3. 3. How do the outcomes of the previous parts relate to investment strategy? Solution: Investment straegy should differ depending on a person’s utility function. It’s common to reduce risk by simultaneously betting on a variety of different options. This is called “hedging ones’ bets,” and it’s why, when we’re really risk averse (the last utility function simulates having only $3 in our pockets), we hedge. 7