Spring 2023 HW Solutions (6)

Solution: (a) See code. (b) See code. (c) See code. (d) See figure. The training error is guaranteed to reach zero with enough rounds of boosting only if the weak learners are successful. In this case, after a certain rounds of boosting, the weak learners will basically fail. Hence, the results do not contradict the theory. The k -Means algorithm Problem 6.2 We saw that the k -Means algorithm consists of the following steps: 1. Select k starting centers that are points from your data set. 2. Assign each data point to the cluster associated with the nearest of the k center points. 3. Re-calculate the centers as the mean vector of each cluster from (2). 4. Repeat steps (2) and (3) until convergence or the limit on the number of iterations is met. Here, we define convergence as no change in label assignment from one step to another. (a) (7 points) Implement the k -means algorithm as described above. The prototype should be [M,obj] = kmeans(X, k, T) where X is the input matrix and k the number of clusters, T the maximum number of iterations to use, M is the matrix containing the centers, and obj is the vector of the values of the objective function during the iterations. The initialization must be done through the k -means++ strategy we saw in class. Please count your iterations as follows: after 100 iterations, you should have assigned the points to the clusters 100 times. Hint: The matlab command repmat might help you to get a faster algorithm. (b) (1 point) Run the k -means algorithm on the training data of MNIST from Homework 5 with k = 10, T = 100. Plot the value of the objective function over the iterations. (This plot is mainly for you to debug your algorithm: the objective function has to decrease!) (c) (2 points) Run the k -means algorithm on the training data of MNIST from Homework 5 with T = 100. Record the objective function of k -means for k = 2, k = 4, k = 6, k = 8, k = 10, k = 12, and k = 14, repeat it for 10 random runs (because the initalization is random) and plot the average and standard deviations of the final value of the objective function for the different values of k . Comment the results: is it possible to have an objective function increasing with k ? Why? 3

6