Description
1 Problem Description
In Homework 5, we implemented memory-based collaborative filtering. The goal of this homework is to
implement a model-based CF method. Specifically, please implement a matrix factorization based CF method
using gradient descent.
Assume that the rating matrix M ∈ R
m×n (m and n are the number of users and items, respectively.) is a
low-rank matrix. Intuitively, there is only a small number of factors (e.g, genre, director, main actor/actress,
released year, etc.) that determine the user preference. Define r as the number of factors, we need to learn a
user profile matrix U ∈ R
m×r and an item profile matrix V ∈ R
n×r
from the observed ratings. A rating can
be approximated by an inner product of two r-dimensional vectors, one for the user profile and the other for
the item profile. Mathematically, a rating of user u on movie i can be approximated by
Mu,i ≈
Xr
k=1
Uu,kVi,k. (1)
We want to learn U and V by minimizing reconstruction error over all observed ratings O. In other words,
we want to minimize the following objective function:
E(U, V ) = X
(u,i)∈O
(Mu,i − U
T
u Vi)
2 =
X
(u,i)∈O
(Mu,i −
Xr
k=1
Uu,kVi,k)
2
(2)
where Uu is the uth row of U and Vi
is the ith row of V .
As U and V are interrelated in (2), there is no closed form solution. We update each element of U and
V using gradient descent:
Uu,k ← Uu,k − µ
∂E(U, V )
∂Uu,k
, Vi,k ← Vi,k − µ
∂E(U, V )
∂Vi,k
, (3)
where µ is a user provided parameter determining the updating rate (a.k.a. learning rate). ∂E(U,V )
∂Uu,k
and
∂E(U,V )
∂Vi,k
are partial derivatives of E(U, V ) with respect to Uv,k and Vj,k, respectively.
2 Requirements
2.1 Equation Derivation (20%)
Derive the update equations in (3) by specifying the partial derivatives.
1
2.2 Equation Derivation (10%)
To avoid overfitting, it is common to add regularization terms that penalize large values in U and V . Derive
the update equations in (3) for the regularized objective function below:
E(U, V ) = X
(u,i)∈O
(Mu,i −
Xr
k=1
Uu,kVi,k)
2 + λ(
X
u,k
U
2
u,k +
X
i,k
V
2
i,k)
where λ is a user provided parameter controlling the effect of regularization.
2.3 Implementation (70%)
To use gradient descent to optimize an objective function, you need to update the variables repeatedly. To
start, you may need a random initial guess. To stop, you may need to set stopping criteria, based on either
reconstruction error or the maximum number of iterations. Usually, it is necessary to try several different
values for µ and λ to find the best model. To evaluate the model, we use RMSE (Root Mean Squared Error)
that, for testing ratings T , can be computed as follows:
X
(u,i)∈T
(Mu,i − f(u, i))2
where Mu,i ∈ T is the ground truth rating and f(u, i) is the estimated rating.
2.3.1 Code (40%)
Given a set of ratings (ratings.csv), you need to implement two functions: one for the basic regularized MF
and one for the cross-validation experiments based on regularized MF.
Basic Regularized MF For the basic regularized MF function, it should have the following input:
• O: the set of training ratings (ratings.csv)
• T : the set of testing ratings (toBeRated.csv)
• r: the number of latent factors (dimensions)
• µ: learning rate
• λ: regularization parameter
and output:
• result.csv, where each line is the rating correspoding to the (userID, movieID) pair in the toBeRated.csv
file.
Cross-Validation Regularized MF For the cross-validation function, it should have the following input:
• M: the set of ratings (ratings.csv)
• r: the number of latent factors (dimensions)
• µ: learning rate
• λ: regularization parameter
• D: the number of folds
and output:
• RMSE on the testing ratings averaged over M folds
2
2.3.2 Report (30%)
RMSE for CV Please report the results based on 10-fold cross-validation. Specifically, please fill in the
following Table 1, 2, 3 and 4 (please round RMSE to 4 decimals).
RMSE λ = 0.05 λ = 0.1 λ = 0.5
µ = 0.0001
µ = 0.0005
µ = 0.001
Table 1: RMSE for r = 1
RMSE λ = 0.05 λ = 0.1 λ = 0.5
µ = 0.0001
µ = 0.0005
µ = 0.001
Table 2: RMSE for r = 3
RMSE λ = 0.05 λ = 0.1 λ = 0.5
µ = 0.0001
µ = 0.0005
µ = 0.001
Table 3: RMSE for r = 5
Analysis Based on the RMSE results you have obtained, please answer the following questions:
1. What do you observe when you vary r? Why?
2. Which model is the best? Please describe the best model in Table 4 and explain your choice.
3. Suppose you are using regularized MF in real systems, how will you choose parameters? Why?
2.4 Submission
The folder structure of your submission should be as below.
|−− hw6 answer . pd f
|−− Recommender . py/Recommender . cpp /Recommender . j a v a
|−− Recommender CV . py/Recommender CV . cpp /Recommender CV . j a v a
|−− Readme . t x t
1. hw6 answer.pdf should contain all the tables and answers to the questions.
2. Recommender.py/Recommender.cpp/Recommender.java should be the function for basic regularized
MF. We should be able to run your code using, for example, python Recommender.py ratings.csv
toBeRated.csv 5 0.001 0.1
3. Recommender CV.py/Recommender CV.cpp/Recommender CV.java should be the function for CrossValidation MF. We should be able to run your code using, for example, python Recommender CV.py
ratings.csv 5 0.001 0.1 10
3
µ
λ
r
RMSE
Table 4: The Best Model
4. Readme.txt should show how to run your code to obtain the result.csv. (Don’t provide the result.csv
file, but show how we can create it using your code).
5. C++/Python/Java/Matlab is preferred. If you use other languages, please be prepared to show how
to run your code in person.
4
