Spring 2023 Practice Midterm Solutions (2)

9. true/false : The use of ReLU activation functions completely removes the issue of vanishing gradients. Solution: False. The ReLU activation functions alleviate the problem with respect to, e.g., a sigmoidal activation function. However, the problem is still present because it is also due to the repeated multiplication of small numbers. 3

4 [6 points] Boosting 1. [3 points] It is possible to show that AdaBoost minimizes the exponential loss on the training set: L exp S ( f ) = 1 m ∑ m i =1 exp( − y i f ( x i )) , where y = +1 or − 1 is the class label, x is the data and f ( x ) is the weighted sum of the weak learners. Show that the loss function L exp S ( f ) is an upper bound on the 0/1 loss function: L 0 / 1 S ( f ) = 1 m ∑ m i =1 1 [ y i ̸ = sign( f ( x i ))] , where 1 [ x ] is 1 if x is true and 0 otherwise. Solution: Note that 1 [ y i ̸ = sign( f ( x i ))] is 0 if y i f ( x i ) ≥ 0 and 1 otherwise. So, it is enough to observe that exp( − x ) is non-negative when x ≥ 0 and greater or equal than 1 otherwise. 2. [3 points] Consider the training set in figure, where the ’x’ points are from class +1 and the ’o’ are from class -1. The figure illustrates the decision boundary (the black line) after the first iteration in an AdaBoost classifier with decision stumps as weak learner, where the points in the left semi-plane are classified as positive and the ones in the right semi-plane as negative. Draw (roughly) in a solid line the decision boundary at the second iteration. State your reasoning in 2-3 sentences. -0.8 -0.6 -0.4 -0.2 0 0.2 0.4 0.6 0.8 1 -1 -0.8 -0.6 -0.4 -0.2 0 0.2 0.4 0.6 0.8 1 Solution: -1 -0.5 0 0.5 1 -1 -0.8 -0.6 -0.4 -0.2 0 0.2 0.4 0.6 0.8 1 After the first round of boosting, there are two misclassified samples. So, in the second round these two points will have a bigger weight. Hence, the algorithm will look for a stump classifier 6

6 [6 points] Proof In the lecture on k -means, we used an alternating minimization approach to minimize the objective function. In particular, we rewrote the objective function as m X i =1 k X j =1 ϕ i,j ∥ x i − c j ∥ 2 2 where ϕ i,j = 1 { x i is assigned to cluster j } and each point is assigned to one cluster. We said that the algorithm uses two steps: 1. Minimize with respect to ϕ i,j for i = 1 , . . . , m and j = 1 , . . . , k , with c 1 , . . . , c m fixed; 2. Minimize with respect to c 1 , . . . , c m , with ϕ i,j fixed for i = 1 , . . . , m and j = 1 , . . . , k . [3 Points] We said that the first step is obtained assigning each point to its closest center. Why? Solution: First of all, we observe that the objective function is written as a sum over the samples and we can minimize ϕ i,j for each sample separately. So, we have to minimize ∑ k j =1 ϕ i,j ∥ x i − c j ∥ 2 2 where ϕ i,j is all zeros, exept for a ’1’. From the expression, we immediately have that for sample i we should put the ’1’ in the position j such that j = arg min n =1 ,...,k ∥ x i − c n ∥ 2 2 . [3 Points] We said that the second step is obtained by setting c j equal to the mean of the training points assigned to the cluster j . Why? Solution: Again, we observe that the objective function is written as a sum, this time over the clusters because I can swap the order of the two sums. So, we can minimize with respect to each c j separately, minimizing ∑ m i =1 ϕ i,j ∥ x i − c j ∥ 2 2 where ϕ i,j is fixed. We can calculate the gradient with respect to c j , put it equal to 0 and solve, obtaining that c j is the average of the points that have ϕ i,j = 1 , that is, all the points assigned to the cluster j . 9