CIS 4190/5190 Final Exam

Instructions

. Write your answers on paper with a pen. Write your name, section number (4190 or 5190), and exam version (shown above) prominently on the first page of your answers at the top left.

.  No devices or cheat sheet(s) are allowed.

.  The exam contains 11 questions, with 80 points total.  Questions 1-7 are short answer, and 8-11 are more involved.

. Each point should take approximately 1-2 minutes; if you find yourself spending too much time on one problem, move on and come back to it.

. At the end of 2 hours, you will put down your pens and submit your exam.

Good luck!

1.  (12 pts) Consider the following 2D binary classification datasets:

Note that in (C), the points lie on aline. Suppose we run PCA, take only the top principal component, and use it to compress the data.

(a)  (1 pt) Which dataset will have the highest reconstruction error?

(b)  (1 pts) Which dataset will have the lowest reconstruction error?

(c)  (2 pts) For your answer to part (b), what is its reconstruction error?

(b)  (1 pt) Assuming we use L2  regularization, the magnitude of λ (recall that the regu- larization term is λ · ∥β∥2(2), where β are the logistic regression parameters)

(c)  (1 pt) The number of training examples n (i.e., the training dataset is {(xi , yi (d)  (1 pt) The number of features d (i.e., each feature vector is ϕ(x) ∈ Rd )

6.  (4 pts) For which of the following algorithms is optimization perfect—i.e., the standard optimizer is guaranteed to find the model that globally minimizes the loss function?

(a)  (1 pt) Logistic regression, if the loss is the NLL (a.k.a.  cross-entropy loss) (b)  (1 pt) Logistic regression, if the loss is the accuracy

(c)  (1 pt) Neural network with one hidden layer, if the loss is the NLL

(d)  (1 pt) k-means clustering, if the loss is the squared distance to the centroid repre- senting each point, averaged over points

7.  (4 pts) Consider a logistic regression model, which has likelihood function

where σ(z) = is the sigmoid function.  Suppose we have already fit the parameters θ , and we want torescale the predicted probabilities. One strategy for doing so is temperature scaling, where we introduce an additional real-valued parameter β ∈ R, and consider

(a)  (2 pts) What happens to the classification boundary if we take β  → 0  (i.e.,  very small but not quite zero)?  What happens to the predicted probabilities (i.e., what values can they take)?

(b)  (2 pts) What happens to the  classification boundary if we take β  → ∞?   What happens to the predicted probabilities?

8.  (10 pts) Consider a neural network with one hidden layer:

where σ(z) is some nonlinear function.

(a)  (4 pts) What is the gradient ∇W fW (x)?  In particular, compute each partial deriva- tive fW (x); then, the gradient is

You can leave your answer in terms of σ(z) and σ′ (z) = σ(z).

(b)  (2 pts) What is the gradient ΔW L(W;x,y) of the loss L(W;x,y) = (fW (x) — y)2 ? You do not need to expand fW (x) (but you should expand ΔW fW (x)).

(c)  (2 pts) Suppose the parameters satisfy W11  = W21   and W12  = W22.  After one step gradient descent (with learning rate η), do theseequalities still hold?  In other words, recalling that the gradient descent update rule is

W′ — W — η · ΔW L(W;x,y),

where η e R>0  is the learning rate, show that W1(′)1  = W2(′)1  and W1(′)2  = W2(′)2 .

(d)  (2 pts) Based on your answer, briefly explain why initializing the weight matrix to

zero (i.e., W11  = W12  = W21  = W22  = 0) is a bad idea.

9.  (10 pts) Consider two binary random variables X1 , X2 .

(a)  (3 pts) There are three possible Bayesian networks over these two random variables; draw all three of them.

(b)  (3 pt) For each possible Bayesian network, indicate whether it can represent joint distributions of the form p(X1  = x1 , X2  = x2 ) = p(X1  = x1 )p(X2  = x2 ).

(c)  (3  pt)  For  each possible Bayesian network,  indicate whether it  can represent an arbitrary joint distribution p(X1  = x1 , X2  = x2 ).

(d)  (1 pt) We say two  Bayesian networks are  equivalent  if they can represent exactly the same class (a.k.a. subset) of possible joint distributions. Indicate which pairs of Bayesian networks you drew are equivalent.

10.  (10 pts)  In class, we learned that recurrent neural networks (RNNs) can be viewed as reusing the same parameter across layers.  In this problem, we will examine the gradients of RNNs via a toy example.

(a)  (4 pts) Consider a neural network y = fθ (x), where x e R, y e R, and θ e R2 , where

fθ (x) = θ2 σ(θ1 x),

for some nonlinear function σ(z). What is the gradient Δθ fθ fθ (x) fθ (x)]⊤ ? You can leave your answer in terms of σ and σ′ , where σ′ (z) = (z).

(b)  (4 pts) Consider a neural network y = hβ (x), where x e R, y e R, and β e R, where

hβ (x) = βσ(βx),

with σ is as before. What is the gradient Δβ hβ (x) = hβ (x)?

(c)  (2 pts) Note that letting θ  =lβ   β]⊤ , then we have hβ (x)  = fθ (x).   Using this fact, express the gradient Δβ hβ (x) in terms of Δθ fθ (x).  [Hint:  Use the chain rule to compute f[β  β]⊤ (x).]  Check to make sure your answer is consistent with the previous parts!

11.  (10 pts) Consider the following Markov decision process with states  S = {s1 , s2 ,..., sn } and actions

A = {a1  = move left, a2  = move right}.

The transitions are deterministic:  Suppose the agent is currently in state si.  Then, taking action a1  transitions the agent to state si−1   (unless i = 1, in which case it stays in s1 ), and taking a2  transitions it to si+1   (unless i = n, in which case it stays in sn ).  Finally, the rewards are