Recommendation system¶

$$ \newcommand{\eg}{{\it e.g.}} \newcommand{\ie}{{\it i.e.}} \newcommand{\argmin}{\operatornamewithlimits{argmin}} \newcommand{\mc}{\mathcal} \newcommand{\mb}{\mathbb} \newcommand{\mf}{\mathbf} \newcommand{\minimize}{{\text{minimize}}} \newcommand{\diag}{{\text{diag}}} \newcommand{\cond}{{\text{cond}}} \newcommand{\rank}{{\text{rank }}} \newcommand{\range}{{\mathcal{R}}} \newcommand{\null}{{\mathcal{N}}} \newcommand{\tr}{{\text{trace }}} \newcommand{\dom}{{\text{dom}}} \newcommand{\dist}{{\text{dist}}} \newcommand{\R}{\mathbf{R}} \newcommand{\B}{\mathbf{B}} \newcommand{\SM}{\mathbf{S}} \newcommand{\ball}{\mathcal{B}} \newcommand{\bmat}[1]{\begin{bmatrix}#1\end{bmatrix}} \newcommand{\loss}{\ell} \newcommand{\eloss}{\mc{L}} \newcommand{\abs}[1]{| #1 |} \newcommand{\norm}[1]{\| #1 \|} \newcommand{\tp}{T} $$

Jong-Han Kim (jonghank@khu.ac.kr)

The following cell downloads a csv file that contains the evaluation scores of 9,000+ movies rated by 600+ customers. It is made of 100,000+ rows where every row explains that the user userId gave rating points to the movie movieId.

Your job is to use the given data set to design a movie recommendation system that is able to suggest a specific user several movies that s/he has not watched and will probably like.

The first five rows:

and the last five rows:

For your information, the title of the movie corresponding to a specific movieId can be found from the following.

The first five rows,

and the last five.

Now we express the above rating information by a binary matrix $B\in\B^{m\times n}$ and a real matrix $R\in\R^{m\times n}$, where $m$ and $n$ represent the number of the users and the numer of the evaluated movies, respectively.

Each row in $B$ tells which movies the specific user has evaluated, and $R$ tells the evaluation scores for those combinations specified by $B$. So $B_{ij}=1$ when user $i$ gave the evaluation score $R_{ij}$ to the movie $j$,and $B_{ij}=0$ if the user $i$ did not evaluated the movie $j$.

In the code below, B and R contains $B$ and $R$. In addition, T contains the list of movie ID's. Those matrices contain 611 users' rating scores on 193,610 movies. So the rating matrix $R$ for the first 1,000 movieIDs looks like below.

The above image is extremely sparse and it contains lots of zero columns; there are actually a bunch of movies which did not receive any evaluation from anyone. So will cut the columns (movies) with few evaluations away, and similarly cut the rows (users) who marked few evaluations. This will reduce the size of the matrix, while conserving the dominant information.

The following removes the movies with less than 60 evaluations, and then removes the users who marked less than 40 evaluations. This leaves the reduced size $R$ and $B$ which represent rating information on 328 movies from 288 users. The selected user IDs are contained in selectedUserNumbers and the selected movie Titles are contained in selectedMovieTitles.

We now randomly erase ~10% of the evaluation data so that we can use them as a validation set. The remaining data will be used as a "training" set. This is shown below.

OK, now everything is ready. We have $B, R\in\R^{288\times 328}$ which represent the evaluation information on 328 movies from 288 users. Note the following observations:

• The rating matrix $R$ is quite sparse.
• A known entry $R_{ij}$ where $B_{ij}=1$ explains how much the user $i$ liked the movie $j$.
• If $B_{ij}=0$, user $i$'s preference on the movie $j$, $R_{ij}$, is unknown. If we can fill it in with some nice $\hat{R}_{ij}$, then we can use it as a prediction on how much the user $i$ will like the movie $j$, and finally we will be able to recommend the user $i$ with the movies in the order of high $\hat{R}_{ij}$'s.

So the problem is to find some preference matrix $\hat{R}$ such that $\hat{R}_{ij} = R_{ij}$ if $B_{ij}=1$. Then how? Another observation is here.

• The sparse rating matrix $R$ looks like a low rank matrix with some elements missing.
• The preference matrix, $\hat{R}$, which is a reconstruction from $R$, should be a low rank matrix since it is generally believed that a user's preference on movies is usually determined by a few dominant factors, such as user's age, sex, movie's genre, director, actress/actor, et cetera.

Now the problem boils down to finding a low rank matrix $\hat{R}$ such that $\hat{R}_{ij} = R_{ij}$ if $B_{ij}=1$, or

$$ \begin{aligned} \underset{P}{\minimize} \quad & \rank P \\ \text{subject to} \quad & P_{ij} = R_{ij}, \quad & \text{if }B_{ij}=0 \end{aligned} $$

The $\rank$ of a matrix is not a convex function. An obvious counterexample is with

$$ A=\bmat{1 & 0 \\ 0 & 0}, \quad B=\bmat{0 & 0 \\ 0 & 1} $$

where $\rank A = \rank B = 1$, but

$$ \rank\frac{A+B}{2} = 2 > \frac{1}{2}\left( \rank A + \rank B \right) = 1 $$

We relax the above nonconvex problem into convex one, by replacing the $\rank$ function by the nuclear norm. The nuclear norm of a matrix is defined by the sum of the nonzero singular values

$$ \|P\|_* = \sum_{i=1}^r \sigma_i(P) $$

where $r=\rank P$.

The intuition behind this is that $\|P\|_*$ is the convex envelope (the best pointwise convex approximation) of $\rank P$ for $\|P\|\le1$. Note the analogy with the cardinality function and the $\ell_1$ norm for vectors.

The $\ell_1$ norm of a vector:

• is the sum of the magnitude of nonzero elements
• is the convex envelope of the cardinality function, which deals with the sparsity

The nuclear norm of a matrix:

• is the sum of the nonzero singular values
• is the convex envelope of the rank function, which deals with the sparsity of the singular values.

So the relaxation is like solving the $\ell_1$-norm minimization when we wanted sparse solutions. Solve the relaxed problem, and we are good if the solution is (in many cases in practice) sparse. Now our problem is is cast as follows.

$$ \begin{aligned} \underset{P}{\minimize} \quad & \| P \|_* \\ \text{subject to} \quad & P_{ij} = R_{ij}, \qquad \text{if }B_{ij}=0 \end{aligned} $$

It turns out that the above is equivalent to

$$ \begin{aligned} \underset{P, X, Y}{\minimize} \quad & \frac{1}{2}\left( \tr X + \tr Y \right) \\ \text{subject to} \quad & \bmat{X & P \\ P^T & Y} \succeq 0,\\ \quad & P_{ij} = R_{ij}, \qquad \text{if }B_{ij}=0 \end{aligned} $$

(Problem 1) Use cvxpy to solve the above.

(Problem 2) Display the reconstructed preference matrix, $P$. Compare it with the rating table, $R$.

(Problem 3) Show the singular values of $P$, $X$, and $Y$. Report the number of dominant factors that contribute to an individual’s tastes or preferences on movies.

(Problem 4) Randomly choose 10 users, and compare the preference prediction ($P$) with the training data points (in $R$) and the validation data points (in $R_\text{true}-R$).

(Problem 5) Plot the histogram of the prediction error on the validation set. Compute the prediction RMSE on the validation set. Present a short interpretation on what you've observed.

This roughly implies that approximately 2/3 of the prediction error is less than 0.8.