‘Movies recommended for you’ – Netflix

‘Videos recommended for you’ – YouTube

‘Restaurants recommended for you’ – Some smart restaurant finder app

Notice a trend? Your favorite apps ‘know’ you (or at least they think they do). They gradually learn your preferences over time (or in a matter of hours) and suggest new products which they think you’ll love.

How is this done? I can’t speak for how Netflix *actually* makes movie recommendations, but the fundamentals are largely intuitive, actually.

If you keep ‘five staring’ Stoner Comedy movies like the whole ‘Harold and Kumar’ series on Netflix, it makes sense for Netflix to assume that you may also enjoy ‘Ted’, or any other Stoner Comedy film on Netflix.

To make recommendations in a real world application, let’s take our intuition and apply it to a machine learning algorithm called Collaborative Filtering.

The following guide will be done in the ‘Octave’ programming language, so we can properly understand what is going on *under the hood* of collaborative filtering. Let’s get started.

**Step 1 – Initialize The Movie Ratings**

Simple but scalable scenario

- 10 movies
- 5 users
- 3 features (we’ll discuss this in Step 3)

Here is an example diagram of movie ratings. Our rating system is from 1-10:

Let’s initialize a 10 X 5 matrix called ‘ratings’; this matrix holds all the ratings given by all users, for all movies. **Note: Not all users may have rated all movies, and this is okay.**

Note 2: I simply made up some data for ‘ratings’. The point of this step is to simply start off with a dataset that we can work with.

This matrix below contains the same ratings data you saw in the picture above. Here is how we declare it in Octave:

ratings = [ 8 4 0 0 4; 0 0 8 10 4; 8 10 0 0 6; 10 10 8 10 10; 0 0 0 0 0; 2 0 4 0 6; 8 6 4 0 0; 0 0 6 4 0; 0 6 0 4 10; 0 4 6 8 8]; |

**Learner’s check:**

- Each column represents all the movies rated by a single user
- Each row represents all the ratings (from different users) received by a single movie

Recall that our rating system is from 1-10. Notice how there are 0’s to denote that no rating has been given.

**Step 2 – Determine Whether a User Rated a Movie**

To make our life easier, let’s also declare a **binary** matrix (0’s and 1’s) to denote whether a user rated a movie.

1 = the user rated the movie.

0 = the user did not rate the movie.

Let’s call this matrix **‘did_rate’**. Note it has the same dimensions as ‘ratings’, 10 X 5:

did_rate = ratings ~= 0; |

This above command should give you the following binary matrix:

did_rate = 1 1 0 0 1 0 0 1 1 1 1 1 0 0 1 1 1 1 1 1 0 0 0 0 0 1 0 1 0 1 1 1 1 0 0 0 0 1 1 0 0 1 0 1 1 0 1 1 1 1 |

**Learner’s check:**

- did_rate(2, 3) = 1: This means the 3rd user
*did*rate the 2nd movie - did_rate(6, 4) = 0: This means the 4th user
*did not*rate the 6th movie

**Step 3 – User Preferences and Movie Features/Characteristics**

This is where it gets interesting. In order for us to build a robust recommendation engine, we need to know user preferences and movie features (characteristics). After all, a good recommendation is based off of knowing this key user and movie information.

For example, a user preference could be how much the user likes comedy movies, on a scale of 1-5. A movie characteristic could be to what degree is the movie considered a comedy, on a scale of 0-1.

**Example 1: User preferences -> Sample preferences for a single user Chelsea**

**Example 2: Movie features -> Sample features for a single movie Bad Boys**

**Note**: The user preferences are the exact same as the movie features; in other words, we can **map** each user preference to a movie feature. This makes sense; if a user has a huge preference for a comedy, we’d like to recommend a movie with a high degree of comedy. If we have add a new preference for the user, for ‘romantic-comedy’, we should also add this as a new feature for a movie, so that our recommendation algorithm can fully use this feature/preference when making a prediction.

**Note 2**: We can use these numbers that I purposely came up with to ‘predict’ ratings for movies. For example, let’s predict what Chelsea would rate Bad Boys, below:

Chelsea's (C) rating (R) of Bad Boys (BB): R |

**5 big problems:** This seems great, but:

- Who has time to sit down and come up with a list of features for users and movies?
- It would be very time consuming to come up with a value for each feature, for each and every user and movie.
- Why did I pick 1-10 as the range for user preferences and 0-1 as the range for movie features? It seems a bit forced.
- How does the product (multiplication) of user_prefs and movie_features magically give us a predicted rating?
- Why did I pick ‘comedy’, ‘romance’ and ‘action’ as the features? This seems manual and forced. There must be a better way to generate features

**The solution: **

Before we dive deep into the collaborative filtering solution to answer our 4 big problems, let’s quickly introduce some key matrixes that we’ll be needing.

The user features (preferences) can be represented by a matrix** ‘user_prefs’**. In our example, we have 5 users and 3 features. So, ‘user_prefs’ is a 5 X 3 matrix.

Here is an ** example** diagram to help

*the data ‘user_prefs’ contains:*

**visualize**The movie features can also be represented by a matrix **‘movie_features’.** In our example, we have 10 movies and 3 features. So, ‘movie_features’ is a 10 X 3 matrix.

Here is an ** example** diagram to help

*the data ‘movie_features’ contains:*

**visualize****Step 4: Let’s Rate Some Movies**

I have a list of 10 movies here, in a text file:

1 Harold and Kumar Escape From Guantanamo Bay (2008) 2 Ted (2012) 3 Straight Outta Compton (2015) 4 A Very Harold and Kumar Christmas (2011) 5 Notorious (2009) 6 Get Rich Or Die Tryin' (2005) 7 Frozen (2013) 8 Tangled (2010) 9 Cinderella (2015) 10 Toy Story 3 (2010) |

Now, let’s rate some movies. Our ratings can be represented by a 10 X 1 column vector **my_ratings**. Let’s initialize it to 0’s and make some ratings:

my_ratings = zeros(10, 1); my_ratings(1) = 7; my_ratings(5) = 8; my_ratings(8)= 3; |

**Learner’s check:**

- I gave Harold and Kumar Escape From Guantanamo Bay a 7
- I gave Notorious an 8
- I gave Tangled a 3

Let’s update **ratings** and **did_rate** with the our ratings **my_ratings**:

ratings = [my_ratings ratings]; did_rate = [(my_ratings ~= 0) did_rate]; |

**Learner’s check**:

- ‘ratings’ is now a 10 X 6 matrix
- ‘did_rate’ is now a 10 X 6 matrix

**Step 5: Mean Normalize All The Ratings**

Once we get to Step 7: Minimize The Cost Function, you may see why mean normalizing the ‘**ratings**‘ matrix is necessary.

**What is mean normalization?**

It is much easier to understand the ‘what’ if we understand the **why. **Why normalize the ‘ratings’ matrix?

Consider the following scenario:

A user (Christie) rated 0 movies. Our collaborative filtering algorithm that we are about to build will then go on to predict that Christie will rate all movies as 0. You may see why in the further steps when we cover the cost function and gradient descent. Don’t worry about it for now.

This is no good, because then we won’t be able to suggest Christie anything. **After all, a recommendation is simply based off of what movie(s) we predict the user to rate the highest. **

So how do recommend a movie to a user who has never placed a rating?

We simply suggest the highest average rated movie. That’s the best we can do, since we know nothing about the user. This is made possible because of mean normalization.

**What is mean normalization?**

Mean normalization, in our case, is the process of making the average rating received by each movie equal to 0.

Take a look at our Step 1 *example* the ‘ratings’ matrix, again:

Each row represents **all** the ratings received by **one** movie. Here’s how to normalize a matrix:

- Find the average of the 1st row. In other words, find the average rating received by the first movie ‘Harold and Kumar Go To Guantanamo Bay’
- Subtract this average from each rating (entry) in the 1st row
- The first row has now been normalized. This row now has an average of 0.
- Repeat steps 1 & 2 for all rows.

Here is the implementation for mean normalization in Octave:

function [ratings_norm, ratings_mean] = normalizeRatings(ratings, did_rate) [m, n] = size(ratings); ratings_mean = zeros(m, 1); ratings_norm = zeros(size(ratings)); for i = 1:m % all the indexes where there is a 1 idx = find(did_rate(i, :) == 1); %only finding the mean for which the user has rated ratings_mean(i) = mean(ratings(i, idx)); ratings_norm(i, idx) = ratings(i, idx) - ratings_mean(i); end end |

We can call this function and store the results into a 1 X 2 row vector.

[ratings, ratings_mean] = normalizeRatings(ratings, did_rate); |

**Learner’s check:**

‘ratings’ contains the normalized ‘ratings’ matrix. Of course, it’s still a 10 X 6 matrix. Here it is below:

ratings = 1.25000 2.25000 -1.75000 0.00000 0.00000 -1.75000 0.00000 0.00000 0.00000 0.66667 2.66667 -3.33333 0.00000 0.00000 2.00000 0.00000 0.00000 -2.00000 0.00000 0.40000 0.40000 -1.60000 0.40000 0.40000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 -2.00000 0.00000 0.00000 0.00000 2.00000 0.00000 2.00000 0.00000 -2.00000 0.00000 0.00000 -1.33333 0.00000 0.00000 1.66667 -0.33333 0.00000 0.00000 0.00000 -0.66667 0.00000 -2.66667 3.33333 0.00000 0.00000 -2.50000 -0.50000 1.50000 1.50000 |

‘ratings_mean’ is a 10 X 1 column vector whose *ith* row contains the average rating of the *ith* movie. Here it is below:

ratings_mean = 5.7500 7.3333 8.0000 9.6000 8.0000 4.0000 6.0000 4.3333 6.6667 6.5000 |

**Step 6: Collaborative Filtering via Linear Regression**

If you are unfamiliar with how a linear regression works, these links should be helpful.

The *simplest* way to think about it is that we are simply fitting a line, (i.e) learning from to a scatter plot (in the case of a *uni-linear *regression):

In our case, we face a multi-linear regression problem. But don’t worry, we’ll briefly cover the intuition in a few seconds.

**Helpful intuition **: A user’s *big* preference for comedy movies (i.e 4.5/5) paired with a *high* movie’s ‘level of comedy’ (i.e 0.8/1) tends to be *positively* correlated with the user’s rating for that movie. For the most part, this correlation is *continuos. *

**Conversely**, a user’s *hate* for* *comedy (1/5), still paired with a *high* movie’s ‘level of comedy’ (i.e 0.8/1) tends to be *negatively* correlated with the user’s rating for that movie. This is another reason for mean normalization. If you notice in the ‘ratings’ matrix above, there are some negative ratings. These ratings are negative because they have been rated below average.

If you are familiar with a linear regression, you may know that the goal of a linear regression is to **minimize the sum of squared errors** (absolute difference between our predicted values and observed values), in order to come up with the best learning algorithm for predicting new outputs, or in the case of a uni-linear regression, the *best* ‘line of best fit’.

**Note**: In our case, we face a *multi-linear regression* problem, since we have many more than 1 feature.

A linear regression is associated with some cost function; our goal is to minimize this cost function (Step 7), and thus minimize the sum of squared errors.

A vectorized implementation of a linear regression is as follows:

Y = X * θ |

**Learner’s check:**

- θ is our parameter (user preferences, in our case) vector
- X is our vector of features (movie features, in our case)

To fit our example, we can rename the variables as such:

ratings = movie_features * user_prefs |

We want to *simultaneously* find optimal values of movie_features and user_prefs such that the sum of squared errors (cost function) is minimized. How can we do this?

**Step 7: Minimize The Cost Function**

We will allow our collaborative filtering algorithm to simultaneously come up with the appropriate values of ‘movie_features’ and ‘user_prefs’, by minimizing the sum of squared errors, through a process called gradient descent. For our case, the gradient descent algorithm (function) we’ll be using in Octave is fmincg.

**Note:** If you are unfamiliar with gradient descent, worry not. All you need to understand is that gradient descent is an iterative algorithm that helps us minimize, in our specific case, the sum of squared errors. Consequently, we will have ‘learned’ the appropriate values of ‘user_prefs’ and ‘movie_features’ to make accurate predictions on movie ratings for every user.

We need to provide our fmincg function with 2 things: A cost function and it’s gradients (the slopes/ partial derivatives of cost function).

Here is my cost function, with regularization (to prevent overfitting, i.e high variance):

predictions = X * Theta'; difference = predictions - Y; J = sum(difference(R==1) .^ 2) / 2; thetaReg = sum(sum(Theta .^ 2)) * (lambda / 2); xReg = sum(sum(X .^ 2)) * (lambda / 2); J = J + thetaReg + xReg; |

**Learner’s check:**

- Remember, this code is inside of a function. So when this function is executed and it returns its matrix(s), the X matrix will hold the learned data (numbers) for ‘movie_features’ and the Theta matrix will hold the learned data (numbers) for ‘user_prefs’. You will see this shortly, if you are confused

Here is my gradient code:

for i = 1 : num_movies withoutReg = ((X(i, :) * Theta' - Y(i, :)) .* R(i, :) * Theta); reg = lambda * X(i, :); X_grad(i, :) = withoutReg + reg; end; for j = 1 : num_users withoutReg = ((X * Theta(j, :)' - Y(:, j)) .* R(:, j))' * X; reg = lambda * Theta(j, :); Theta_grad(j, :) = withoutReg + reg; end; |

And here is the full implementation of the *entire function* (calculating cost and its gradients):

function [J, grad] = costFunc(params, Y, R, num_users, num_movies, ... num_features, lambda) X = reshape(params(1:num_movies*num_features), num_movies, num_features); Theta = reshape(params(num_movies*num_features+1:end), ... num_users, num_features); J = 0; % cost (sum of squared differences) X_grad = zeros(size(X)); % (partial derviates of J with respect to X (movie_features)) Theta_grad = zeros(size(Theta)); % (partial derviates of J with respect to Theta (user_prefs)) % Cost function with regularization predictions = X * Theta'; difference = predictions - Y; J = sum(difference(R==1) .^ 2) / 2; thetaReg = sum(sum(Theta .^ 2)) * (lambda / 2); xReg = sum(sum(X .^ 2)) * (lambda / 2); J = J + thetaReg + xReg; % gradients for i = 1 : num_movies withoutReg = ((X(i, :) * Theta' - Y(i, :)) .* R(i, :) * Theta); reg = lambda * X(i, :); X_grad(i, :) = withoutReg + reg; end; for j = 1 : num_users withoutReg = ((X * Theta(j, :)' - Y(:, j)) .* R(:, j))' * X; reg = lambda * Theta(j, :); Theta_grad(j, :) = withoutReg + reg; end; grad = [X_grad(:); Theta_grad(:)]; end |

Before we actually execute this function, we need to initialize our parameters user_prefs (Theta) and movie_features (X) to *random small numbers*. To do this in Octave, I have used the randn function. This function returns a matrix of random elements that are normally distributed, with a mean of 0 and a variance of 1:

num_users = size(ratings, 2); num_movies = size(ratings, 1); num_features = 5; % Initialize Parameters Theta (user_prefs), X (movie_features) movie_features = randn(num_movies, num_features); user_prefs = randn(num_users, num_features); initial_parameters = [movie_features(:); user_prefs(:)]; |

Now, let’s set some options for our cost minimizing fmincg function:

options = optimset('GradObj', 'on', 'MaxIter', 100); |

Finally, let’s run fmincg, which will consequently run costFunc 100 times. Notice, fmincg takes our costFunc function as an argument. This is what fmincg needs to minimize our cost function and calculate the best learning algorithm for predicting movie ratings:

lambda = 10; % regularization weight/parameter optimal_prefs_and_features = fmincg (@(t)(costFunc(t, ratings, did_rate, num_users, num_movies, ... num_features, lambda)), ... initial_parameters, options); |

**Learner’s check**:

- If you are unfamiliar with regularization, you don’t need to worry about what lambda means.
**optimal_prefs_and_features**is the column vector returned from fmincg. It contains optimal values for user preferences and movie features that minimize our cost function

We need to extract ‘user_prefs’ and ‘movie_features’ from optimal_prefs_and_features, so we can start making some predictions:

movie_features = reshape(optimal_prefs_and_features(1:num_movies*num_features), num_movies, num_features); user_prefs = reshape(optimal_prefs_and_features(num_movies*num_features+1:end), ... num_users, num_features); |

**Step 8: Make Movie Predictions!…Finally**

Recall Step 4: Let’s Rate Some Movies. We rated some movies. Now, let’s use our learning algorithm we just built to predict ratings that we would give movies, based on our learning algorithm, and our ‘my_ratings’ row vector:

all_predictions = movie_features * user_prefs'; my_predictions = all_predictions(:,1) + ratings_mean; |

‘my_predictions’ is a 10 X 1 column vector:

my_predictions = 5.7500 7.3333 8.0000 9.6000 8.0000 4.0000 6.0000 4.3333 6.6667 6.5000 |

**Learner’s check**:

- Recall in Step 5 where we mean normalized all the ‘ratings’. Since we subtracted the mean of the movie’s ratings from each rating for that movie, we added back ‘ratings_mean’ to our predicted ratings.

Let’s display our predictions:

[r, ix] = sort(my_predictions, 'descend'); fprintf('nTop recommendations for you:n'); for i=1:10 j = ix(i); fprintf('Predicting rating %.1f for movie %sn', my_predictions(j), ... movieList{j}); end fprintf('nnOriginal ratings provided:n'); for i = 1:length(my_ratings) if my_ratings(i) > 0 fprintf('Rated %d for %sn', my_ratings(i), ... movieList{i}); end end |

The result looks as follows:

Top recommendations for you: Predicting rating 9.6 for movie Straight Outta Compton (2015) Predicting rating 8.0 for movie A Very Harold and Kumar Christmas (2011) Predicting rating 8.0 for movie Notorious (2009) Predicting rating 7.3 for movie Ted (2012) Predicting rating 6.7 for movie Cinderella (2015) Predicting rating 6.5 for movie Toy Story 3 (2010) Predicting rating 6.0 for movie Frozen (2013) Predicting rating 5.8 for movie Harold and Kumar Escape From Guantanamo Bay (2008) Predicting rating 4.3 for movie Tangled (2010) Predicting rating 4.0 for movie Get Rich Or Die Tryin' (2005) Original ratings provided: Rated 7 for Harold and Kumar Escape From Guantanamo Bay (2008) Rated 8 for Notorious (2009) Rated 3 for Tangled (2010) |

**Step 9: Take It Further**

You should try to build your own recommendation engine. Perhaps not just for movies, but for anything else you can think of. We can’t always find what are looking for by ourselves. Sometimes a good recommendation is all we need.

Perhaps you can implement a **clustering** algorithm such as k-means or DBSCAN to group users with similar features together, and thereby recommend the same movies to users belonging to the same cluster.

In our example, the more you rate movie movies, the more ‘personalized’ (and possibly accurate) your recommendations will be. This is because you are giving the recommendation engine (learning algorithm) more of your data to observe and learn from.

So, maybe if you* actually* ‘Netflix and chill’ed more often, Netflix will know you better and make better movie recommendations for you 😉

Nikhil Bhaskar

*Original post here*