practice_final

pdf

School

University of California, Los Angeles *

*We aren’t endorsed by this school

Course

M146

Subject

Computer Science

Date

Jan 9, 2024

Type

pdf

Pages

Uploaded by tachyonphantom

CS M146 Practice Final Exam 1 CS M146, Fall 2023 Practice Final Exam Instructions 1. This exam is worth 80 points. You have 3 hours to complete it. 2. You are allowed to consult 2 US Letter/A4 sized page (4 sides) of reference notes. 3. You can quote results from the lecture slides, HWs, discussion problems, and practice problems as part of your solutions to the exam problems. 4. No network access is allowed. 5. All answers must be justified. Unsupported answers will not receive credit. An incorrect answer supported by substantially correct calculations and explanations might still receive partial credit. Blank answers will receive zero credit. Good luck! I attest that I have not given or received aid in this examination, and that I have done my share and taken an active part in seeing to it that others as well as myself uphold the spirit and letter of the UCLA Honor Code. Name : UID : Signature : For instructor use Question Score 1 / 42 2 / 15 3 / 11 4 / 12 Total score: / 80

CS M146 Practice Final Exam 2 1. [42 points total] Short questions There are 5 sub-questions covering a few themes of the course. Each sub-question has 4-5 statements. For each of the 5x1+4x4=21 statements below, state True or False and provide a 1-2 line justification for your choice. 1 point for correct assertion and 1 point for explanation. (a) [10 points] General Machine Learning i. The complexity of a hypothesis class is equal to the number of unknown parameters. ii. Statistical generative models are trained to learn probability distributions that approximate the data distribution as closely as possible. iii. Pruning is used to mitigate underfitting in decision trees. iv. Both k NN and k -means do not need access to any labels for the input datapoints. v. SGD with momentum helps reduce the noise fluctuations in the gradient estimates.

CS M146 Practice Final Exam 3 (b) [8 points] Support Vector Machines i. Consider 2 hyperplanes with parameter vectors θ and 5 θ respectively. The margin of any datapoint x w.r.t. the second hyperplane is larger than its margin w.r.t. the first hyperplane. ii. The soft-margin SVM optimization problem has n constraints. iii. For a classifier f θ ( x ) = sign( θ T x ) with fixed parameter vector θ , the hinge loss at any training instance is always greater than or equal to the perceptron loss. iv. The hard margin SVM and the soft margin SVM with C = 0 will always have the same solution no matter how the data is distributed.

Your preview ends here

Eager to read complete document? Join bartleby learn and gain access to the full version

Access to all documents
Unlimited textbook solutions
24/7 expert homework help

CS M146 Practice Final Exam 4 (c) [8 points] Neural Networks and Deep Learning i. Dropout is a regularization technique for deep learning in which we randomly deactivate hidden neurons during training and testing. ii. A single filter in a convolutional layer applied over an input image always has the same number of weight parameters as a fully connected layer applied to the same input image (flattened to a vector). iii. Computations during the forward pass are never used for computing gradients during back- propagation. iv. In an autoregressive generative model for an object x ∈ R 3 , the joint distribution is factorized as: p ( x ) = p ( x 1 | x 2 , x 3 ) p ( x 2 | x 1 , x 3 ) p ( x 3 | x 1 , x 2 )

CS M146 Practice Final Exam 5 (d) [8 points] Ensemble Models i. In both bagging and boosting, the base models that are part of the ensemble have to be trained sequentially. ii. Bootstrap replicates create multiple copies of the training dataset by sampling training in- stances without replacement. iii. Ensembles will yield bad results if there is significant diversity in the predictions of the base models. iv. Suppose you are working on a binary classification problem and there are three base models each with 70% accuracy. Suppose you want to ensemble these models using the majority voting method. The maximum possible accuracy you can get is 100%.

CS M146 Practice Final Exam 6 (e) [8 points] General Unsupervised Learning i. For k -means clustering, we should set the number of clusters k = n so that we minimize the k -means inertia objective function on the training dataset. Here n is the number of datapoints in the training dataset. ii. k -means clustering always converges to the same clustering regardless of the initialization of the cluster centers. iii. In PCA, the smaller the eigenvalue λ i is, the less important the corresponding principal component v i . iv. In PCA, if we use d principal components to reconstruct a data point x ∈ R d , then, we will get a perfect reconstruction ˜ x , i.e. reconstruction ˜ x = x .

Your preview ends here

Eager to read complete document? Join bartleby learn and gain access to the full version

Access to all documents
Unlimited textbook solutions
24/7 expert homework help

CS M146 Practice Final Exam 7 2. [15 points total] AdaBoost Suppose we have a dataset with the following examples ( x 1 , x 2 ) ∈ R 2 in Table 1 ( i is the example index). The dataset is also visualized for convenience in Figure 1 . 1st iteration 2nd iteration final i x 1 x 2 Label w 1 ˆ y 1 w 2 ˆ y 2 ˆ y (1) (2) (3) (4) (5) (6) (7) (8) (9) 1 1 2 − 2 2 3 + 3 2 2 + 4 3 3 + 5 3 4 + 6 3 2 − 7 3 1 + 8 4 1 − Table 1: Dataset and results for AdaBoost Figure 1: Adaboost Dataset We would like to separate true and false classes with AdaBoost. Specifically, we will use two rounds of AdaBoost to learn a classifier, which chooses a weak learner in each round that minimizes the weighted error ϵ . The weak learners are linear separators with bias, i.e., h θ ( x 1 , x 2 ) = sign( θ T x ) = sign( θ 0 + θ 1 x 1 + θ 2 x 2 ) . Training error is 0-1 classification error with weights w i for iteration i . When using log, use base e. (a) [1 points] Start the first round with a uniform distribution w 1 , place the value of w 1 for each example in the 5th column of Table 1 .

CS M146 Practice Final Exam 8 (b) [3 points] Pick the base model h θ 1 from the following candidates that minimizes the training error ϵ 1 given data in Table 1 : i. h θ 1 ( x 1 , x 2 ) = sign( x 1 − 2 . 5) ii. h θ 1 ( x 1 , x 2 ) = sign( x 2 − 1 . 5) iii. h θ 1 ( x 1 , x 2 ) = sign( − x 1 + 2 x 2 + 0 . 5) iv. h θ 1 ( x 1 , x 2 ) = sign( − 3 x 1 + 2 x 2 + 4) Write down your formula of h θ 1 below. Then write down the predicted value of h θ 1 ( x 1 , x 2 ) = sign( θ T x ) for each example in the 6th column. (c) [2 points] Compute training error ϵ 1 and classifier weight β 1 for the best hypothesis h θ 1 ( x 1 , x 2 ) in 1st iteration below. (d) [2 points] Based on the prediction from the first iteration, derive w 2 for each example below and fill in the computed values in the 7th column. (e) [3 points] Pick the base model h θ 2 from the following candidates that minimizes the weighted training error (using weights w 2 ): i. h θ 2 ( x 1 , x 2 ) = sign( x 1 − 3 . 5) ii. h θ 2 ( x 1 , x 2 ) = sign( x 2 − 2 . 5) iii. h θ 2 ( x 1 , x 2 ) = sign( x 1 − 1 . 5) iv. h θ 2 ( x 1 , x 2 ) = sign( x 2 − 1 . 5) Write down your formula of h θ 2 below. Compute the predicted value of h θ 2 ( x 1 , x 2 ) for each example and fill in the 8th column.

CS M146 Practice Final Exam 9 (f) [2 points] Compute the weighted training error ϵ 2 (using weights w 2 ) and classifier weight β 2 for the best hypothesis h θ 2 ( x 1 , x 2 ) in 2nd iteration below. (g) [2 points] What is the final hypothesis H ( x 1 , x 2 ) produced by AdaBoost? Write down the final predictions in the 9th column.

Your preview ends here

Eager to read complete document? Join bartleby learn and gain access to the full version

Access to all documents
Unlimited textbook solutions
24/7 expert homework help

CS M146 Practice Final Exam 10 3. [11 points total] PCA You have the following 3-dimensional data: Data point # 1 2 3 4 5 x 1 0.4 -2.6 -0.6 1.4 1.4 x 2 0.2 -2.8 -0.8 2.2 1.2 x 3 -1.8 3.2 0.2 -3.8 2.2 Our goal is to reduce the dimensionality of the data from 3 to 2 using the principal component analysis (PCA) algorithm. The unsorted principal components are given as: p 1 = [ − 0 . 7173 , 0 . 6930 , 0 . 0722] T , p 2 = [0 . 5690 , 0 . 5228 , 0 . 6347] T , p 3 = [ − 0 . 4021 , − 0 . 4964 , 0 . 7694] T . [ Tip: Please provide formulas/workings for each answer. In the case your numerical workings are incorrect, it can help us provide partial credit.] (a) [1 points] What is the mean vector µ for the above dataset? (b) [4 points] Which are the leading two principal components based on the PCA algorithm? [ Hint: Recall from linear algebra, for any square matrix M , an eigenvector v is any non-zero vector such that M v = λ v . Here, λ denotes the eigenvalue corresponding to the eigenvector v .]

CS M146 Practice Final Exam 11 (c) [2 points] What are the explained variances for the leading two principal components? (d) [2 points] What is the reduced principal representation y (1) ∈ R 2 of the data x (1) ? (e) [2 points] What is the reconstruction ˜ x (1) ∈ R 3 given its principal representation y (1) ?

CS M146 Practice Final Exam 12 4. [12 points total] Neural Networks Suppose you have the following neural network f θ ( x ) described by the equations below: h 1 = ReLU( W 1 , (1 , 1) x 1 + W 1 , (1 , 2) x 2 + b 1 , 1 ) h 2 = ReLU( W 1 , (2 , 1) x 1 + W 1 , (2 , 2) x 2 + b 1 , 2 ) f θ ( x ) = σ ( w 2 , 1 h 1 + w 2 , 2 h 2 + b 2 ) , where ReLU( z ) = max(0 , z ) is the ReLU activation function, σ ( z ) = 1 1+ e − z is the sigmoid activation function, and • x = ( x 1 , x 2 ) T ∈ R 2 is the input to the network, • W 1 ∈ R 2 × 2 are the weights of the first layer, W 1 , ( i,j ) is the element of W 1 at row i , column j , where i, j ∈ { 1 , 2 } , • w 2 ∈ R 2 are the weights of the second layer, w 2 ,i is the i th element of w 2 , where i ∈ { 1 , 2 } , • b 1 ∈ R 2 is the bias vector for the first layer, b 1 ,i is the i th element of b 1 , where i ∈ { 1 , 2 } , • b 2 ∈ R is the bias for the second layer, and • θ refers to the set of all parameters (biases b 1 , b 2 and weights W 1 , w 2 ) in the network. The computation graph for the network is shown in Figure 2 . For this problem, use the following values: • x 1 = 1 , x 2 = 2, • W 1 , (1 , 1) = 1 , W 1 , (1 , 2) = − 2 , W 1 , (2 , 1) = 3 , W 1 , (2 , 2) = 1, • w 2 , 1 = − 3 , w 2 , 2 = − 1, • b 1 , 1 = 2 , b 1 , 2 = − 2, • b 2 = 3. For the following questions, you do not need to show any working beyond filling in all the blanks in Figure 2 . (a) [4 points] Compute the forward pass for f θ ( x ) by filling in the first blank for each outgoing edge in the computation graph (values that are given above have been filled in as examples). (b) [8 points] Compute the backward pass for f θ ( x ) by filling in the second blank for each outgoing edge in the computation graph.

Your preview ends here

Eager to read complete document? Join bartleby learn and gain access to the full version

Access to all documents
Unlimited textbook solutions
24/7 expert homework help

CS M146 Practice Final Exam 13 x 1 * W 1 , (1 , 1) b 1 , 1 + ReLU x 2 * * w 2 , 1 W 1 , (1 , 2) x 1 b 2 + σ f θ ( x ) * W 1 , (2 , 1) b 1 , 2 + ReLU x 2 * * w 2 , 2 W 1 , (2 , 2) 1, 1, 2, -2, , , 2, , , -3, , 3, , , 1 1, 3, 2, 1, , , -2, , , -1, , Figure 2: Computation graph for neural network. Nodes with ReLU refer to the ReLU activation function, i.e. ReLU( z ) = max(0 , z ). The node with σ refers to the sigmoid activation function, i.e. σ ( z ) = 1 1+ e − z . Fill in the blanks for each edge with values f, b where f, b are the forward pass (part a) and backward pass (part b) values for the edge. Values given in the problem have been indicated on the computation graph.

practice_final

Related Documents