COMP3314 Machine Learning Homework: Release date: April 18, 2020 Due date: 11:59pm, April 23, 2020 (20% deduction for every 24 hours after the due date) 1. Given a convolution function = (|) and the value of , perform one step convolution with weight tensor , zero padding set to 1 pixel and stride set to 1. (1) calculate the forward pass result (4 points); (2) calculate the Jacobian matrix (5 points); (3) assume is the final loss function and is given, calculate using chain rule (5 points). Note: is a 4×4 matrix, is a 4×4 matrix, w is 3×3 a matrix, is a 4×4 matrix, is a 16×9 matrix and is a 3×3 matrix. 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 2. Given a maxpooling function = (), perform one step maxpooling with pooling kernel size set to 3. (1) calculate the forward pass result (5 points); (2) assume is the final loss function and is given, calculate using chain rule (5 points). Note: (i). no padding is needed and the pooling stride is set to 1; (ii). is a 5×5 matrix, is a 3×3 matrix, is a 3×3 matrix and is a 5×5 matrix; (iii) when multiple max values exist in the kernel, select the one with the smallest index. example kernel index 3. Given the following dataset: 0.0625 0 0 0 0 0.0625 0 0 0 0 0 0.0625 0.0625 0.0625 0 0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 0.1111 -0.0007 0 0 0.1104 0.1111 0.1111 0.1111 0.1111 1 2 3 4 5 6 7 8 9 6 2 5 4 4 9 1 5 3 7 7 2 4 3 8 4 5 5 1 0 0 2 8 0 8 V W X Y 0 0 0 0 0 1 0 1 1 0 0 1 1 1 0 0 1 1 1 0 Your task is to build a decision tree for classifying variable . (You can think of the dataset as replicated many times, i.e. overfitting is not an issue here). 1) Compute the information gains (|), (|) and (|). Remember, information gain is defined as () = () – ∑ =1 () where () = 1 − ∑ (|) 2 =1 is the class number, and are the dataset of the parent and th child node. is gini impurity. is the total number of samples at the parent node and is the number of samples in the th child node (12 points). 2) Write down the entire decision tree with gini impurity(8 points). 4. Given the following dataset and the points information, use logistic regression classifier to solve the problem. In logistic regression classification, the initial decision boundary is defined as −2.7 − 2.2 + 15.2 = 0. Apparently, this boundary is not optimal and the initial accuracy with this boundary is 83.33%. Your task is to: (1). With this initial decision boundary, use Gradient Descent and Minibatch Gradient Descent to calculate a new decision boundary respectively. Note: in Minibatch Gradient Descent, the batch sampling order is fixed and defined as: = [6, 1, 4, 2, 5, 3] Number Var a Var b Label 1 2.5 3.0 1 2 3.0 2.0 1 3 3.5 3.0 1 4 5.0 3.5 0 5 4.0 4.5 0 6 4.0 4.0 0 Minibatch size is set to 2, learning rate is set to 0.01 and training iteration is set to 3. Write down the final decision boundary equation and the calculation steps required to calculate the boundary (including all variable gradients, cost value at each step) (12 points). (2). Suppose the decision boundary is −2.4 − 3.8 + 21.7 = 0 , predict the class of the following datapoints and write down corresponding probabilities (Sigmoid Function is used as the activation function, probability threshold is set to 0.5) (6 points). 5. Consider a classification problem: there is a feature vector ∈ × with N features and class label can be 1 or -1. Denote the weight for the slack variables is . There are samples in total and for each sample the corresponding annotations are , , respectively. Let equation of the decision boundary be + = 0 (1) We denote the standard QP form as: min 1 2 + s. t. ≤ , = Please derive the standard QP form variable P, q, z, G, h, A, b of a linear SVM by using variables , , , , , and other necessary constant variables. (8 points) (2) Let’s assume we have solve the quadratic programming problem, and the attained normalized direction of the decision hyper-plane ⃑ is [ 1 2 , 1 2 , 1 2 , 1 2 ]. There is a negative support vector at [0, 0, 0,0] and a positive support vector at [1, 2, 3,4]. What is the width of the margin (twice the distance from decision boundary to the closest training samples)? What is the weight and bias ? (12 points) (3) Let two positive samples at [1, 1, 1,1] and [[4, 4, 4,4]]. What is the slack variables for them? (4 points) 6. As a simple illustration of a k-means algorithm, consider the following data set consisting of the scores of two variables on each of 7 individuals: Number Var a Var b Label Prob 1 3.5 4.0 2 6.0 1.5 3 4.5 3.3 x y 1.0 1.0 0.3 0.4 1.0 1.5 3.0 0.2 3.5 -0.8 4.5 -0.6 3.5 -0.5 The dataset has roughly 2 clusters. And we set initial cluster centers to be [4.5,−1] and [3, 0] respectively. It is apparent two cluster center are initialized in the same cluster. Use Sum of Squared Error (SSE) as the distance metric: (1) What is the initial clustering result given these two initial cluster centers? (4 points) (2) What is the clustering result after 1 iteration? (5 points) (3) What is the clustering result after 4 iterations? (5 points)
