Carnegie Mellon University10 601Ahomework7_sol

10-601 Machine Learning: Homework 7 Due 5 p.m. Wednesday, April 22, 2015 Instructions • Late homework policy: Homework is worth full credit if submitted before the due date, half credit during the next 48 hours, and ...

10-601 Machine Learning: Homework 7 Due 5 p.m. Wednesday, April 22, 2015 Instructions • Late homework policy: Homework is worth full credit if submitted before the due date, half credit during the next 48 hours, and zero credit after that. You must turn in at least n-1 of the n homeworks to pass the class, even if for zero credit. • Collaboration policy: Homeworks must be done individually, except where otherwise noted in the assignments. \Individually" means each student must hand in their own answers, and each student must write and use their own code in the programming parts of the assignment. It is acceptable for students to collaborate in figuring out answers and to help each other solve the problems, though you must in the end write up your own solutions individually, and you must list the names of students you discussed this with. We will be assuming that, as participants in a graduate course, you will be taking the responsibility to make sure you personally understand the solution to any work arising from such collaboration. • Online submission: You must submit your solutions online on autolab. We recommend that you use LATEX to type your solutions to the written questions, but we will accept scanned solutions as well. On the Homework 7 autolab page, you can download the template, which is a tar archive containing a blank placeholder pdf for the written questions. Replace each pdf file with one that contains your solutions to the written questions. When you are ready to submit, create a new tar archive of the top-level directory and submit your archived solutions online by clicking the \Submit File" button. You should submit a single tar archive identical to the template, except with the blank pdfs replaced by your solutions for the written questions. You are free to submit as many times as you like. DO NOT change the name of any of the files or folders in the submission template. In other words, your submitted files should have exactly the same names as those in the submission template. Do not modify the directory structure. Problem 1: k-means Clustering [40 pt + 10 Extra Credit] Recall that in k-means clustering we attempt to find k cluster centers cj 2 Rd; j 2 f1; : : : ; kg such that the total distance between each datapoint and the nearest cluster center is minimized. In other words, we attempt to find c1; : : : ; ck that minimizes nXi =1 min j2f1;:::;kg kxi - cjk2; (1) where n is the number of data points. To do so, we iterate between assigning xi to the nearest cluster center and updating each cluster center cj to the average of all points assigned to the jth cluster. Choosing k is no easy matter 1. [10 pt] Instead of holding the number of clusters k fixed, one can think of minimizing (1) over both k and c. Show that this is a bad idea. Specifically, what is the minimum possible value of (1) ? what values of k and c result in this value ? Solution: The minimum objective value is 0. It is achieved when we have n clusters such that ci = xi. 1 k-means can be kernelized too ! k-means with Euclidean distance metric assumes that each pair of clusters is linearly separable. This may not be the case. A classical example is where we have two clusters corresponding to data points on two concentric circles in the R2 plane. We have seen that we can use kernels to obtain a non-linear version of an algorithm that is linear by nature and k-means is no exception. Recall that there are two main aspects of kernelized algorithms: (i) the solution is expressed as a linear combination of training examples, (ii) the algorithm relies only on inner products between data points rather than their explicit representation. We will show that these two aspects can be satisfied in k-means. 2. [5 pt] Let zij be an indicator that is equal to 1 if the xi is currently assigned to the jth cluster and 0 otherwise (1 ≤ i ≤ n and 1 ≤ j ≤ k). Show that the jth cluster center cj can be updated as Pn i=1 αijxi. Specifically, show how αij can be computed given all z’s. Solution: αij = zij= nX 0i =1 zi0j 3. [5 pt] Given two data points x1 and x2, show that the square distance kx1 - x2k2 can be computed using only (linear combinations of) inner products. Solution: kx1 - x2k2 = hx1; x1i + hx2; x2i - 2hx1; x2i 4. [5 pt] Given the results of parts 2 and 3, show how to compute the square distance kxi - cjk2 using only (linear combinations of) inner products between the data points x1; : : : ; xn. Note: This means that given a kernel K, we can run Lloyd’s algorithm. We begin with some initial data points as centers and use the answer to part 2 to find the closest center for each data point, giving us the initial zij’s. We then repeatedly use the answer to part 3 to reassign the points to centers and update the zij’s. Solution: kxi - cjk2 = hxi; xii + nX 0i =1 nX i00=1 αi0jαi00jhxi0; xi00i - 2 nX 0i =1 αi0jhxi; xi0i