Description

Please read these instructions to ensure you receive full credit on your homework. Submit the written portion of your homework as a single PDF file through Courseworks (less than 5MB). In addition to your PDF write-up, submit all code written by you in their original extensions through Courseworks (e.g., .m, .r, .py, .c). Any coding language is acceptable, but do not submit notebooks, do not wrap your files in .rar, .zip, .tar and do not submit your write-up in .doc or other file type. Your grade will be based on the contents of one PDF file and the original source code. Additional files will be ignored. We will not run your code, so everything you are asked to show should be put in the PDF file. Show all work for full credit.
Problem 1 (K-means) – 20 points
Implement the K-means algorithm discussed in class. Generate 500 observations from a mixture of three
Gaussians on R2 with mixing weights π = [0.2,0.5,0.3] and means µ and covariances Σ,
.
b) For K = 3,5, plot the 500 data points and indicate the cluster of each for the final iteration by marking it with a color or a symbol.
Problem 2 (Matrix factorization) – 40 points
In this problem, you will implement the MAP inference algorithm for the matrix completion problem discussed in class. As a reminder, for users u ∈Rd and movies v ∈Rd, we have ui ∼ N(0,λ−1I), i = 1,…,N1, vj ∼ N(0,λ−1I), j = 1,…,N2.
We are given an N1× N2 matrix M with missing values. Given the set Ω = {(i,j) : Mij is measured}, for each (i,j) ∈ Ω we model Mij ∼ N(uTi vj,σ2).
You should run your code on the user-movie ratings dataset provided on Courseworks and the course website. For your algorithm, set σ2 = 0.25, d = 10 and λ = 1. Train the model on the larger training set for 100 iterations. For each user-movie pair in the test set, predict the rating using the relevant dot product. Note that the mean rating has been subtracted from the data and you do not need to round your prediction. Since the equations are in the slides, there’s no need to re-derive it.
a) Run your code 10 times. For each run, initialize your ui and vj vectors as N(0,I) random vectors. On a single plot, show the the log joint likelihood for iterations 2 to 100 for each run. In a table, show in each row the final value of the training objective function next to the RMSE on the testing set. Sort these rows according to decreasing value of the objective function.
b) For the run with the highest objective value, pick the movies “Star Wars” “My Fair Lady” and“Goodfellas” and for each movie find the 10 closest movies according to Euclidean distance using their respective locations vj. List the query movie, the ten nearest movies and their distances. A mapping from index to movie is provided with the data.