Scribd
Upload
133 views18 pages

CMPT 410/726 Spring 2024 Final Exam

sfu 24 fall cmpt 410 final

Uploaded by

lilacleejiayi
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
133 views18 pages

CMPT 410/726 Spring 2024 Final Exam

sfu 24 fall cmpt 410 final

Uploaded by

lilacleejiayi
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

CMPT 410/726: Final Exam (Spring 2024) Instructor: Mo Chen

CMPT 410/726 Final Exam


Spring 2024

1
CMPT 410/726: Final Exam (Spring 2024) Instructor: Mo Chen

Instructions

• Place your student ID on the desk.

• Write down your first name, last name, and student number on every page, and on the
Scantron sheet.

• Write your answers legibly.

• Use the Scantron sheet to answer the multiple choice questions. Any multiple choice
answers written directly on the exam will be ignored!

• If you write your answer on the back of any page, clearly indicate where your answers are
written.

• You may not use any electronic devices, including phones and calculators.

• The university policy on academic dishonesty (cheating) will be taken very seriously in this
course.

2
CMPT 410/726: Final Exam (Spring 2024) Instructor: Mo Chen

Useful Information
#»
Gradient of a function f ( #»
x ) : Rn → R and Jacobian of a function f ( #»
x ) : Rn → Rm :
 ∂f   ∂f1 ∂f2
· · · ∂f m

∂x1
#» ∂x1 ∂x1 ∂x1
 ∂f  ∂ f ( #»
∂f1 ∂f2 ∂fm 
∂f  ∂x2  x)   ∂x2 ∂x2 · · · ∂x2 
= , = (1)
∂ #»
x  ...  ∂ #»
x  ... .. .. .. 
  
. . . 
∂f ∂f1 ∂f2 ∂fm
∂xn ∂xn ∂xn
··· ∂xn

Derivative rules:
#» #»
∂( f ( #»
x )⊤ #»
g ( #»
x )) ∂ f ( #»
x ) #» #» ∂ #»
g ( #»
x ) #» #»
#» = #» g ( x ) + #» f (x) (2a)
∂x ∂x ∂x
#» #» #»
∂ f ( #»
y 1 ( #»
x ), #»
y 2 ( #»
x )) ∂ #»
y1 ∂f ∂ #»
y2 ∂f
= #» #» + #» #» (2b)
∂ #»
x ∂x ∂y1 ∂x ∂y2
Common derivatives:
∂( #»
a ⊤ #»
x) ∂(A #»
x) ∂( #»
x ⊤ A #»
x)
#» = #»
a, #» = A⊤ , #» = (A + A⊤ ) #»
x (3)
∂x ∂x ∂x
Common distributions:
x ∼ Categorical({pi }ni=1 ) ⇒ p(xi ) = pi , ∀i ∈ {1, . . . , n} (4a)
n!
x ∼ Binomial(n, p) ⇒ p(x = k) = pk (1 − p)n−k (4b)
k!(n − k)!
Ridge regression and maximum a posteriori estimation:

N n
#»∗ = arg min #» ⊤ #» 2
∥ #» #» 2 + λ∥ w∥
#» 2
X X
w #»
(yi − w x i ) + λ wi2 = arg min
#»
y − X w∥ 2 2 (5a)
w w
i=1 i=1
p {xi , yi }N #» #» = (X ⊤ X + λI)−1 X ⊤ #»
= arg max
#» i=1 | w p( w) y (5b)
w

Support vector machine:


1 #» 2
minimize
#»
∥ w∥2 (6a)
w,b 2
#»⊤ #»
subject to yi ( w x i − b) ≥ 1, ∀i (6b)

N N N
1 XX
λi λj yi yj #» #»
X
maximize
#»
λi − x⊤ j xi (7a)
λ
i=1
2 i=1 j=1
N
X
subject to λi y i = 0 (7b)
i=1
λi ≥ 0 ∀i (7c)

3
CMPT 410/726: Final Exam (Spring 2024) Instructor: Mo Chen

Linear Regression

x i , yi )}ni=1 , where #»
Suppose we are given a data set D = {( #» x i ∈ Rn , yi ∈ R. We would like to use
#» ⊤ #» #»
the model ŷ = w x to predict, given any input x , the label y.

a) Suppose we’d like to penalize large component magnitudes of w by minimizing the L2


#» = ∥ #»
regularized square loss L( w) #» 2 + λ∥ w∥
y − X w∥ #» 2 for some constant λ.
2 2
#»
∂L( w) #»∗ such that
Derive an expression for #» , and an expression for the value of w
∂w L2
#»∗ )
∂L( w
∂w#»
L2
= 0. Show all your steps.

b) Suppose X is an orthonormal matrix.


∗
Simplify the above expression for wL2 as much as possible.

c) Alternatively, we can also penalize large component magnitudes of w #» by minimizing the L1


regularized square loss L( w) #» = ∥ #»
y − X w∥ #» . This loss function can be written as
#» 2 + λ∥ w∥
2 1
#» =
L( w)
P n
f (w ), where w denotes the ith component #»
of w.
i=1 i i i

Derive an expression for fi (wi ) assuming X is orthonormal. Simplify your expression


using the fact that X is orthonormal and show all your steps.
(Hints: Your answer may include expressions such as xi , yi , X, #»
y , λ; and you may write
⊤ #» ⊤ #»
expressions such as (X y ) to denote the ith component of X y without expanding out
i
the expression.)

d) Suppose again that X is orthonormal.


∗
Derive an expression for wL1,i , the ith component of
#» ∗ #» #» 2
w L1 = arg min w#» ∥ y − X w∥2 + λ∥ w∥ #» . Hint: Make use of the form L( w)
#» = Pn f (w ).
1 i=1 i i

Linear regression solution

4
CMPT 410/726: Final Exam (Spring 2024) Instructor: Mo Chen

Linear regression solution cont’d

5
CMPT 410/726: Final Exam (Spring 2024) Instructor: Mo Chen

Linear regression solution cont’d

6
CMPT 410/726: Final Exam (Spring 2024) Instructor: Mo Chen

Linear regression solution cont’d

7
CMPT 410/726: Final Exam (Spring 2024) Instructor: Mo Chen

𝑥1 𝑥ො1
𝑤0,11 𝑤1,11
ℎ1

𝑥2 𝑥ො2

ℎ2

𝑤0,23 𝑤1,32
𝑥3 𝑥ො3

Figure 1: A depiction of a simple neural network.

Neural Networks

Consider a fully connected neural network (NN) with one hidden layer, shown in Fig. 1. An NN
with this architecture is called a multi-layer perceptron (MLP). This particular NN takes #»
x ∈ R3
#» 2
as input, and first maps it to the hidden layer h ∈ R . We can interpret this mapping as encoding
#» #»
the input into some “code”, represented by h . Then, the NN attempts to decode h back into
#x
ˆ» ∈ R3 , which should be as close to the original input #»
x as possible.
The network parameters are the weight matrices W := {W0 , W1 }; a few of their components,
w0,11 , w0,23 , w1,11 , w1,23 , are labeled in Fig. 1. Assume that there are no biases in the weight
matrices. The hidden layer uses ReLU(·) = max(0, ·) as the activation function, and the input and
output layers do not use any activation function. The loss function for training the network is
L(W ) = ∥ #» x − #xˆ»∥2 .
2

a) What are the dimensions of W0 and W1 ?

b) Write #x
ˆ» as a function of #»
x , in terms of W0 , W1 , and ReLU(·).
∂L
c) Derive an expression for #» .
∂h
What are the dimensions of your answer?
#»⊤ is the second row of W . What are the
d) Derive an expression for ∂ w#»∂L⊤ , where w 0,2· 0
0,2·
dimensions of your answer?

e) In general, it is not possible to perfectly reconstruct all #»x ∈ R3 ; however, it is possible to


do so if all data lies in the span of {(1, 0, 0), (0, 1, 0)}, with all elements of each data point
being non-negative.
In this case, what are the optimal weights W0 , W1 ?

f) Perfect reconstruction is still possible under the broader condition that all data #»
x is
generated by a1 #»
v 1 + a2 #»
v 2 , where a1 , a2 ≥ 0 and #»
v 1 , #»
v 2 are orthonormal.
In this case, what are the optimal weights W0 , W1 ?

8
CMPT 410/726: Final Exam (Spring 2024) Instructor: Mo Chen

Neural networks solution

9
CMPT 410/726: Final Exam (Spring 2024) Instructor: Mo Chen

Neural networks solution cont’d

10
CMPT 410/726: Final Exam (Spring 2024) Instructor: Mo Chen

Neural networks solution cont’d

11
CMPT 410/726: Final Exam (Spring 2024) Instructor: Mo Chen

Support Vector Machine

Consider a data set containing the following two data points:


 
D = { (1, 3), 1 , (−1, −3), −1 } (8)

#» = (1, 0), b = 10 a feasible solution of the primal SVM problem (6)?


a) Is w 1 1

#»∗ , b∗ ) to the primal SVM problem (6). You may use a


b) Determine the optimal solution ( w
geometric argument. What is the corresponding objective value?

c) What is the optimal objective value of the SVM dual problem (7)?

d) Determine the optimal solution (λ1 , λ2 ) to the dual SVM problem (7).

e) Write down the generalized Lagrangian L( w,#» b, λ , λ ) of the SVM primal problem (6).
1 2
There is no need to simplify the expression.
#» b) = max #»
f) Let Φ( w, λ1 ,λ2 ≥0 L( w, b, λ1 , λ2 ).

#» , b )?
i. What is the value of Φ( w 1 1
#»∗ , b∗ )?
ii. What is the value of Φ( w

Support vector machine solution

12
CMPT 410/726: Final Exam (Spring 2024) Instructor: Mo Chen

Support vector machine solution cont’d

13
CMPT 410/726: Final Exam (Spring 2024) Instructor: Mo Chen

Support vector machine solution cont’d

14
CMPT 410/726: Final Exam (Spring 2024) Instructor: Mo Chen

Support vector machine solution cont’d

15
CMPT 410/726: Final Exam (Spring 2024) Instructor: Mo Chen

Multiple Choice

Select the (one and only) correct choice for each question. Mark your responses on the scantron
sheet.

1. All critical points are global maxima for which of the following class of functions?

(a) linear functions


(b) convex functions
(c) concave functions
(d) lipschitz functions

2. The Hessian of a convex function f ( #»


x)

(a) never has any negative eigenvalues at every #»


x.
(b) is always positive definite at every #»
x.
(c) is always negative definite at every #»
x.
#»
(d) is always dependent on x .

3. Which of the following can lead to overfitting?

(a) stopping training too early when using iterative gradient-based optimization
algorithms
(b) using too much regularization
(c) using a model that is lacking in expressivity
(d) not having enough data for the chosen model

4. Which of the following is a symptom of overfitting?

(a) having a large training loss


(b) having a small validation loss and a large training loss
(c) having high variance in model parameters when training using different data sets
(d) having large validation and training losses

5. The entropy is the highest for which of the following?

(a) a Categorical distribution with n choices, where every outcome has equal probability
(b) a Categorical distribution with n choices, where one of the choices has 100%
probability
(c) a Binomial distribution (number of total successful outcomes in n trials) where the
probability of success of each outcome is 50%
(d) a Binomial distribution (number of total successful outcomes in n trials) where the
probability of success of each outcome is 100%

16
CMPT 410/726: Final Exam (Spring 2024) Instructor: Mo Chen

6. Which of the following does not necessarily characterize a Gaussian distribution?

(a) the marginal distribution of a Gaussian


(b) the conditional distribution of a Gaussian
(c) the sum of two Gaussians
(d) the distribution whose pdf is obtained from the product of two Gaussian pdf’s

7. A zero-mean isotropic Gaussian prior on the parameter of a linear model for regression
corresponds to which of the following?

(a) L2 regularization
(b) square loss function
(c) assuming Gaussian noise in a probabilistic model
(d) penalizing small components of the parameter vector

8. Which of the following is likely to cause vanishing gradients when training multi-layer
perceptrons using iterative gradient-based optimization?

(a) using too few layers or neurons per layer


(b) using momentum-based optimization methods such as Adam
(c) using an activation function that does not saturate on one side, like softplus
(d) using an activation function that saturates on both sides, like tanh

9. Gradient clipping is most useful for

(a) alleviating the problem of overfitting for neural networks with many layers
(b) ensuring that gradients vanish during training
(c) potentially increasing the rate of convergence
(d) mitigating unnecessarily large changes in the weights after each training iteration

10. In a classification problem in which the data set is linearly separable,

(a) the optimal margin is larger for hard-margin SVM compared to soft-margin SVM
(b) the Kernel trick is needed to improve computational efficiency so that a good solution
can be found quickly
(c) the optimal slack variables in soft-margin SVM have a value of 0
(d) there is no advantage in using the hinge loss compared to using the square loss

17
CMPT 410/726: Final Exam (Spring 2024) Instructor: Mo Chen

Extra Space

18

Common questions

Powered by AI

A zero-mean isotropic Gaussian prior on linear model parameters corresponds to L2 regularization, as both impose a preference for smaller coefficients, equivalent to penalizing large parameter magnitudes in the model .

The optimal solution \( (\mathbf{w}^*, b^*) \) is determined by maximizing the margin while keeping the constraint \( y_i(\mathbf{w}^T\mathbf{x}_i - b) \ge 1 \) for all data points. Geometrically, this requires finding the hyperplane that ensures maximum distance between data points of different classes .

L1 regularization often leads to sparse solutions, providing model interpretability and feature selection by driving coefficients of less important features to zero. L2 regularization, on the other hand, provides smooth solutions that can better handle multicollinearity, but it does not inherently perform feature selection .

In a neural network with input \( \mathbf{x} \in \mathbb{R}^3 \) and hidden layer \( \mathbf{h} \in \mathbb{R}^2 \), the weight matrix \( W_0 \) has dimensions \( 2 \times 3 \) and \( W_1 \) has dimensions \( 3 \times 2 \).

Perfect reconstruction is possible because the data spans a subspace formed by orthogonal vectors, allowing the network to learn a basis that precisely maps inputs and reconstructs them without loss, under certain constraints like non-negativity .

The derivative of the L2-regularized square loss function \( L(\mathbf{w}) = ||\mathbf{y} - X\mathbf{w}||^2_2 + \lambda||\mathbf{w}||^2_2 \) with respect to \( \mathbf{w} \) is given by \( \frac{\partial L}{\partial \mathbf{w}} = -2X^T(\mathbf{y} - X\mathbf{w}) + 2\lambda\mathbf{w} \).

In linearly separable datasets, hard-margin SVM aims to maximize the margin without allowing for any misclassification, leading to a larger margin compared to soft-margin SVM, which allows for some misclassification with slack variables to handle noise or outliers .

When \( X \) is an orthonormal matrix, the optimal \( \mathbf{w}^* \) for L2 regularization simplifies to \( \mathbf{w}^* = X^T\mathbf{y} \) due to the property that \( X^TX = I \), which simplifies the regularization term .

Entropy is maximal for a distribution when outcomes are equally likely, such as in a Categorical distribution where every choice is equally probable or in a Binomial distribution where the success probability is 0.5, maximizing uncertainty .

Gradient clipping is useful to prevent overly large updates during backpropagation, which can stabilize training by limiting the norm of the gradient, especially in models where large updates can cause divergence .

You might also like