EECS189 Dis10 Solution

CS 189/289A Introduction to Machine Learning Fall 2023 Jennifer Listgarten, Jitendra Malik DIS10 1 Probabilistic Graphical Models Recall that we can represent joint probability distributions with directed acyclic graphs (DAGs). Let G be a DAG with vertices X 1 , ..., X k . If P is a (joint) distribution for X 1 , ..., X k with (joint) probability mass function p , we say that G represents P if p ( x 1 , · · · , x k ) = k ZZZZZZZ i = 1 P ( X i = x i | pa( X i )) , (1) where pa( X i ) denotes the parent nodes of X i . (Recall that in a DAG, node Z is a parent of node X i ff there is a directed edge going out of Z into X .) Consider the following DAG Z Y X S Figure 1: G , a DAG (a) Write down the joint factorization of P S , X , Y , Z ( s , x , y , z ) implied by the DAG G shown in Figure 1. Solution: P S , X , Y , Z ( s , x , y , z ) = P ( X = x ) P ( Z = z ) P ( Y = y | X = x , Z = z ) P ( S = s | X = x , Y = y ) . (b) Is S ⊥ Z | Y ? Solution: No. As a counterexample, consider the case where all nodes represent binary ran- dom variables, P ( X = 1) = P ( Z = 1) = 0 . 5, Y = X ⊗ Z , and S = X ⊗ Y , where ⊗ is the XOR operator. Then we can see that S = Z , whereas knowing Y does not fully determine S or Z . A version of these solutions from a previous semester erroneously said that this conditional independence did hold. As a result, you may have wrongly heard in section that this statement is true, via faulty algebraic manipulation and / or other algorithms such as the Bayes ball (d- separation). Running these algorithms correctly should show that S and Z are indeed not conditionally independent given Y . DIS10, © UCB CS 189 / 289A, Fall 2023. All Rights Reserved. This may not be publicly shared without explicit permission. 1

If X is fully removed from G , then we do indeed have S ⊥ Z | Y . This is left as an exercise in algebraic manipulation of probability distributions. (c) Is S ⊥ X | Y ? Solution: No. Consider the same example from above with binary random variables. Knowing Y does not determine S , but knowing both X and Y does. DIS10, © UCB CS 189 / 289A, Fall 2023. All Rights Reserved. This may not be publicly shared without explicit permission. 2

Compute state estimates for timesteps t at 1, 2, and 3; that is, calculate P ( S t | e 1: t ). Assume a prior on P ( s 0 ) that is consistent with the prior in the previous part; that is, P ( s 0 ) = 0 . 7. Solution: We can apply the filtering (forward computation) method. We walk through the computation step-by-step: P ( S 0 ) = ⟨ 0 . 7 , 0 . 3 ⟩ P ( S 1 ) = YYYYYYY s 0 P ( S 1 | s 0 ) P ( s 0 ) = ⟨ 0 . 8 , 0 . 2 ⟩ 0 . 7 + ⟨ 0 . 3 , 0 . 7 ⟩ 0 . 3 = ⟨ 0 . 65 , 0 . 35 ⟩ P ( S 1 | e 1 ) = α P ( e 1 | S 1 ) P ( S 1 ) = α ⟨ 0 . 8 ∗ 0 . 9 , 0 . 3 ∗ 0 . 7 ⟩⟨ 0 . 65 , 0 . 35 ⟩ After normalizing, we get the following (the rest of the solution(s) will normalize implicitly.) = ⟨ 0 . 8643 , 0 . 1357 ⟩ P ( S 2 | e 1 ) = YYYYYYY s 1 P ( S 2 | s 1 ) P ( s 1 | e 1 ) = ⟨ 0 . 7321 , 0 . 2679 ⟩ P ( S 2 | e 1 : e 2 ) = α P ( e 2 | S 2 ) P ( S 2 | e 1 ) = ⟨ 0 . 5010 , 0 . 4990 ⟩ P ( S 3 | e 1 : e 2 ) = YYYYYYY s 2 P ( S 3 | s 2 ) P ( s 1 | e 1 : e 2 ) = ⟨ 0 . 5505 , 0 . 4495 ⟩ P ( S 3 | e 1 : e 3 ) = α P ( e 3 | S 3 ) P ( S 3 | e 1 : e 2 ) = ⟨ 0 . 1045 , 0 . 8955 ⟩ (c) Compute smoothing estimates P ( S t | e 1:3 ) for each timestep, using the same evidence as the previous part. Solution: First, we do the backwards computations: P ( e 3 | S 3 ) = ⟨ 0 . 2 ∗ 0 . 1 , 0 . 7 ∗ 0 . 3 ⟩ = ⟨ 0 . 02 , 0 . 21 ⟩ P ( e 3 | S 2 ) = YYYYYYY s 3 P ( e 3 | s 3 ) P ( s 3 | S 2 ) = ⟨ 0 . 02 ∗ 0 . 8 + 0 . 21 ∗ 0 . 2 , 0 . 02 ∗ 0 . 3 + 0 . 21 ∗ 0 . 7 ⟩ = ⟨ 0 . 0588 , 0 . 153 ⟩ DIS10, © UCB CS 189 / 289A, Fall 2023. All Rights Reserved. This may not be publicly shared without explicit permission. 4

P ( e 2 : e 3 | S 1) = YYYYYYY s 2 P ( e 2 | s 2 ) P ( e 3 | s 2 ) P ( s 2 | S 1 ) = ⟨ 0 . 0233 , 0 . 0556 ⟩ Now, we can combine them with the forwards computation and normalize. P ( S 1 | e 1 : e 3 ) = α P ( S 1 | e 1 ) P ( e 2 : e 3 | S 1 ) = ⟨ 0 . 7277 , 0 . 2723 ⟩ P ( S 2 | e 1 : e 3 ) = α P ( S 2 | e 1 : e 2 ) P ( e 3 | S 2 ) = ⟨ 0 . 2757 , 0 . 7243 ⟩ P ( S 3 | e 1 : e 3 ) = ⟨ 0 . 1045 , 0 . 8955 ⟩ (d) Compare, in plain English, the filtered estimates you computed for timesteps 1 and 2 with the smoothed estimates. How do the two analyses di ff er? Solution: The smoothed analysis shows that the time the student started sleeping poorly is one timestep earlier than filtering only computation by incorporating future observations that indicated lack of sleep at the last step. DIS10, © UCB CS 189 / 289A, Fall 2023. All Rights Reserved. This may not be publicly shared without explicit permission. 5