Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit

CSCI-567 Summer 2022 Exam 1

1    Short Answer

Here are the multiple choice and true false questions.  Please indicate your solutions by clearly circling the appropriate letter or T/F answer. Question 1-11 are multiple choice questions with a single correct answer.

1.  (2 points) Consider a univariate regression yˆ = wx where w ∈ R, and x ∈ R1 ×m .  The cost function is the squared-error cost J =  ∥yˆ − y∥2 . Which of the following equations is true?

(a)   =  (yˆ y)xT

(b)   =  (yˆ − y)xT

(c)   =  (yˆ y)x

(d)   =  (yˆ y)x

2.  (2 points) How does the bias-variance decomposition of a ridge regression estimator compare with that of ordinary least squares regression?

(a)  Ridge has larger bias, smaller variance

(b)  Ridge has larger bias, larger variance

(c)  Ridge has smaller bias, larger variance

(d)  Ridge has smaller bias, smaller variance

3.  (2 points) Which of the following is true about Support Vector Machine (SVM)?

(a)  SVM needs to store all the training samples for making predictions.

(b) If data is not linearly separable, hard margin SVM will not have a feasible solution.

(c)  SVM can always fit training data perfectly.

(d) While training SVM, we solve a non-convex optimization problem.

4.  (2 points) Which of the following penalty cannot be a good idea to regularize model complexity?

(a)  R(w) = exp{Pi |wi |}

(b)  R(w) = exp{−Pi |wi |}

(c)  R(w) = − Pi log(|wi | 1)

(d)  R(w) =Pi exp{|wi |}

5.  (2 points) Which of the following is not a true statement about Lagrangian duality?

(a)  The Lagrangian function is convex.

(b)  Duality formulates constrained optimization problems.

(c) If strong duality holds we may have found an easier approach to our primal problem.

(d) In the dual version of SVM, the Lagrangian is maximized.

6.  (2 points) Why can SVMs train quickly?

(a)  They can be solved with convex optimization.

(b)  They can leverage the kernel trick.

(c)  They can be optimized in the dual space.

(d)  All of the above.

7.  (2 points) Which of the following surrogate losses is not an upper bound of the 0-1 loss?

(a)  Perceptron loss: max(0, z)

(b)  Hinge loss: max(0, 1 − z)

(c)  Logistic loss: log(1 + exp( z))

(d)  Exponential loss: exp( z)

8.  (2 points) If a soft margin SVM model is underfitting. Which one of the following adjustment on the hyperparameter C will help?

(a) Increase C

(b)  Decrease C

(c)  Adjusting C will not help

9.  (2 points) Suppose you have a fully convolutional neural network (network containing only convolu- tional layers) for images with size 400 × 400. Later you decided to apply the same architecture to the images with size 800 × 800. By what factor does the number of parameters (of the network) increase?

(a)  1 (the networks parameters do not increase)

(b)  2

(c)  3

(d) 4

10.  (2 points) A ML model is called non-parametric if it has

(a)  No parameters

(b) Infinitely many parameters

(c)  Finitely many parameters

(d)  No hyperparameters

11.  (2 points) Increasing K in K-nearest neighbor models will:

(a) Increase bias, increase variance

(b) Increase bias, decrease variance

(c)  Decrease bias, increase variance

(d)  Decrease bias, decrease variance

Questions 12-19 are true/false type questions.

12.  (1 point) (T/F) Kernel function must be symmetric, that is, k(x,x) = k(x,x)

13.  (1 point)(T/F) The backpropagated gradient through a tanh non-linearity is always smaller or equal in magnitude than the upstream gradient.  (Recall: if z = tanh(x) then  = 1 − z2 )

14.  (1 point)(T/F) After training a neural network, you observe a large gap between the training accuracy (100%) and the test accuracy (42%). RMSprop optimizer is commonly used to reduce this gap.

15.  (1 point)(T/F) Consider a trained logistic regression.  Its weight vector is W and its test accuracy on a given data set is A. Assuming there is no bias, dividing W by 2 won’t change the test accuracy.

16.  (1 point) (T/F) Decision tree can be trained using gradient descent.

17.  (1 point) (T/F) Soft-margin SVM works for data that is not linearly separable.

18.  (1 point) (T/F) Neural Networks optimize a convex cost function.

19.  (1 point) (T/F) Gradient descent always reaches the global minimum solution.

2    Regularization                                                                    (15 points)

2.1

Ridge regression is actually a special case of a more general form of regularization where instead of minimizing the L2  norm of w, we minimize ∥Γw∥2(2)  where Γ is some matrix in RD×D . Note: We can get ridge regression by setting Γ = λI . Derive the optimal solution w for the following objective functions:

Show

your work.

ε(w) = Xw y2(2) + Γw2(2)

(10 points)

2.2

The Hessian is a square matrix of second-order partial derivatives of a scalar-valued function. Calculate the Hessian of ε(w). Prove that it is positive semi-definite. What does this tell you about the nature of optima? Is it a maxima, minima or a saddle point.                                                                                          (5 points)

3    Duality                                                                                 (20 points)

We are given N samples:  {(x1 ,y1 ) ... (xN ,yN )}, xi  ∈ X,yi  ∈ {−1, 1} ∀i ∈ {1 . . . N}.  We want to find a separating hyperplane w by maximizing the following objective function

N

f(w) =Xyiwxi

i=1

(1)

Note that f(w) can be arbitrarily maximized by increasing the magnitude of w once we have found a vector w such that f(w) > 0. Therefore, we add an additional constraint that ∥w∥2(2)  ≤ 1.

3.1

Suppose we use a transformation function ϕ : X RM  to transform inputs.  Write down the constraint minimization problem for this setup.                                                                                                  (3 points)

3.2

Write down the dual of the above optimization problem. Show all the steps.                                 (7 points)

3.3

Rewrite the dual optimization problem using the kernel function k(x, x) = ϕ(x)T ϕ(x).              (5 points)

3.4

Rewrite the prediction using the kernel function k(x, x) = ϕ(x)T ϕ(x).                                         (5 points)

4    Maximum Likelihood Arrivals                                        (20 points)

You are employed by a big road management firm to estimate the arrival of vehicles every hour in a day. They also provide you with some empirical observations over past N days. You decide to model the number of arrivals (X) in fixed intervals in a day as follows:

λx

x!

where λ is some parameter of the distribution that is to be estimated from the data and x ≥ 0, x is integer.

4.1

Assuming that the observations {x1 . . . xN } are mutually independent P(x1 . . . xn ) = Q P(xi ), compute the

maximum likelihood estimate (MLE) of the parameter λ .                                                              (10 points)


4.2

You present your model to the firm and they provide you more information about the parameter λ .  In particular, they tell you that prior over λ is:

λa e −bλ

Z(a,b)

where Z(a,b) is some normalizing constant. What is the maximum of λ given the observations {x1 . . . xN }?

Hints:  find the  λ that maximizes conditional probability  P(λ|x1 . . . xn ).   Use Bayes’ theorem.   Assume independence of {x1 . . . xN } as in 4.1.  Note, that P(x1 . . . xn ) is a constant, and P(xi |λ) is defined by (2).

(10 points)

5    Convolutional Neural Networks                                     (15 points)

You want to train a neural network to drive a car.  Your training data consists of grayscale 64  × 64 pixel images.   The training labels include the human driver’s steering wheel angle in degrees and the human driver’s speed in miles per hour. Your neural network consists of an input layer with 64 × 64 = 4,096 units, a hidden layer with 2,048 units, and an output layer with 2 units (one for steering angle, one for speed). You use the ReLU activation function for the hidden units and no activation function for the outputs (or inputs).

5.1

Calculate the number of parameters (weights) in this network. You can leave your answer as an expression. Be sure to account for the bias terms.                                                                                                (3 points)

5.2

You come up with a CNN classifier to recognize traffic.  For each layer, calculate the number of weights, number of biases and the size of the associated feature maps.  Fill in the shape of the output volume and the number of parameters at each layer. You can write the shapes in the numpy format (e.g.  (128,128,3)).

(12 points)

Layer

Activation Volume Dimensions

Number of parameters

Input

(32, 32, 1)

0

CONV5-10

 

 

POOL2

 

 

CONV5-10

 

 

POOL2

 

 

FC10

 

 

Notation:

1.  CONV5-N denotes a convolutional layer with N filters with height and width equal to 5.  Padding is 2, and stride is 1.

2.  POOL2 denotes a 2x2 max-pooling layer with stride of 2 and 0 padding.

3.  FC-N denotes a fully-connected layer with N neurons