"Is There Anything On?"¶

A Movie Recommendation System¶

In this exercise, we implement a collaborative filtering learning algorithm and apply it to a dataset of movie ratings$^{*}$. The objective of collaborative filtering is to predict movie ratings for the movies that users have not yet rated. This allows us to recommend movies with a high predicted rating to the user.

$^{*}$MovieLens 100k Dataset from GroupLens Research.

We begin by importing standard machine learning libraries, as well as both loading and converting our data from MATLAB to a more python friendly format.

The code below loads the dataset ex8_movies.mat, which contains the matrices $Y$ and $R$. The matrix $Y$ (a $num\_movies \text{ x } num\_users$ matrix) stores the ratings $y^{(i,j)}$ (from 1 to 5). Restated, the data consist of ratings on a scale of 1 to 5, information on $n_u = 943$ users, and data on $n_m = 1682$ movies. The matrix $R$ is a binary-valued indicator matrix in which $R(i,j) = 1$, if user $j$ gave a rating to movie $i$ and $R(i,j) = 0$ otherwise.

Below is a slice of the matrix $Y$. As we can see, it contains ratings from 1 to 5. The zeros represent movies that users did not rate.

The code below presents us with a window into the matrix $R$. The contents reflect what was stated above: user-rated movies are coded with a 1, while unrated movies are coded with a zero.

Throughout this part of the exercise, we will also be working with the matrices $X$ and $\theta$. In the cell that follows, we load the MATLAB data file containing these matrices.

The $i-$th row of $X$ corresponds to the feature vector $x^{(i)}$ for the $i$-th movie, and the $j$-th row of $\theta$ corresponds to one parameter vector $\theta^{(j)}$ for the $j$-th user. Both $x^{(i)}$ and $\theta^{(j)}$ are $n$-dimensional vectors. For our purposes, we will use $n=100$. Thus, $x^{(i)} \in\mathbb{R}^{100}$ and $\theta^{(j)} \in\mathbb{R}^{100}$. This implies $X$ is a $n_m\times 100$ matrix and Theta is a $n_u\times 100$ matrix.

As one can see, the MATLAB file we imported contains more information than simply the contents of two more matrices.

Using matrix R to index into matrix Y allows us to obtain an average rating for our first movie, "Toy Story."

Below, we visualize the rankings in our matrix. It's clear that some movies are rated more often than others, while many are not rated at all. This may be attributed to movie popularity and/or user reluctance to participate in the rating system.

Now, we will implement the collaborative filtering learning algorithm. We start by implementing the cost function. The collaborative filtering algorithm when used in movie recommendation considers a set of n-dimensional parameter vectors $x^{(1)},\ldots,x^{(n_m)}$ and $\theta^{(1)},\ldots, \theta^{(n_u)}$, where the model predicts the rating for movie $i$ by user $j$ as $y^{(i,j)} = (\theta^{(j)})^T x^{(i)}$. Given a dataset that consists of a set of ratings produced by some users on some movies, we wish to learn the parameter vectors $x^{(1)},\ldots,x^{(n_m)},\;\theta^{(1)},\ldots,\theta^{(n_u)}$ that produce the best fit (minimizes the squared error).

We will complete the code in cofi_cost_func.py to compute the cost function and gradient needed for collaborative filtering. Note that the parameters to the function (i.e., the values we are trying to learn) are $X$ and Theta. In order to use an off-the-shelf minimizer like fmincg, the cost function has been set up to unroll the parameters into a single vector "params."

The collaborative filtering cost function (without regularization) is as follows: $J\left(x^{(i)},\ldots,x^{(n_m)},\;\theta^{(1)},\ldots,\theta^{(n_u)}\right) =\frac{1}{2}\sum_{(i,j):r(i,j)=1}\left((\theta^{(j)})^Tx^{(i)}-y^{(i,j)}\right)^2$. We display the cost function below. Note, we modified it to return the cost in the variable $J$. Furthermore, we accumulate the cost for user $j$ and movie $i$ only if $R(i,j) = 1$.

We'll test our cost function on a data set of reduced size, so as to accelerate the testing process.

Below we test our cost function. The outcome is approximately 22.22, which is consistent with our expectations.

We now turn our attention to implementing the gradient. Specically, we complete the code in cofi_cost_func.py to calculate the variables X_grad and Theta_grad. Note that X_grad is a matrix of the same size as $X$. Similarly, Theta_grad is a matrix of the same size as Theta. The gradients of the cost function are given by:

$\frac{\partial J}{\partial x_k^{(i)}} = \sum_{j:r(i,j)=1}\left((\theta^{(j)})^T x^{(i)} -y^{(i,j)}\right)\theta_k^{(j)}$

$\frac{\partial J}{\partial \theta_k^{(j)}} = \sum_{i:r(i,j)=1}\left((\theta^{(j)})^T x^{(i)} -y^{(i,j)}\right) x_k^{(i)}$

Our function returns the gradient for both sets of variables by unrolling them into a single vector. After we complete the code to compute the gradients, we will check our gradient implementation using finite difference methods. If our code is correct, we will see that the analytical and numerical gradients match up closely.

As the function signature suggests, this routine is responsible for calculating the finite differences between the analytical and numerical gradients. The differences should be small.

The check_cost_function calls our gradient check function and provides the output we need to discern whether or not our gradient calculations are reasonable.

As one can easily see, our gradient calculations pass muster.

Below, we introduce regularization to our cost function. Though we left room for a regularization term, $\lambda$, in our function signature in the code above, that code lacked the machinery to implement regularization. The cost function for collaborative filtering with regularization is given by:

$J\left(x^{(i)},\ldots,x^{(n_m)},\;\theta^{(1)},\ldots,\theta^{(n_u)}\right) =\\ \qquad\qquad \frac{1}{2}\sum_{(i,j):r(i,j)=1}\left((\theta^{(j)})^Tx^{(i)}-y^{(i,j)}\right)^2 +\left(\frac{\lambda}{2}\sum_{j=1}^{n_u}{\sum_{k=1}^{n}{(\theta_k^{(j)})^2}}\right) +\left(\frac{\lambda}{2}\sum_{i=1}^{n_m}{\sum_{k=1}^{n}{(x_k^{(i)})^2}}\right)$

Our cost function with regularization should produce a cost of about 31.34.

As expected, our cost function with regularization ($\lambda = 1.5$) yielded a value of approximately 31.344.

As with our unregularized cost function, we will check our numerical gradient calculations against their analytical counterparts.

Presented below are gradient calculations produced by our function with regularization. The difference between the numerical and analyticall gradient calculations is miniscule.

Having finished implementing our cost function and gradient, we can finally start training our algorithm to make movie recommendations for ourselves. In the code below, we enter our own movie preferences, so that later we can get our personalized movie recommendations!

In the following cells, we load a list of movies and assign ratings to a fraction of them.

Below, we review the movies we rated and the ratings assigned thereto.

Next, the code below will proceed to train the collaborative filtering model. Restated, it will learn the parameters X and Theta.

Having added our preferences to our list of films and pre-existing user ratings, we normalize the data to ensure that no single rating or subset of ratings dominate our calculations.

Here, we retrieve pertinent data used in training our model.

The above data are used to initialize matrices $X$ and $\theta$.

We're now ready to minimize our cost function with regularization.

After reshaping our data, we are ready to make predictions concerning which films, if any, we might enjoy. The recommendations look reasonable and definitely fit squarely in the set of films we'd enjoy watching!