Recommendation System

This is my personal notes taken for the course Machine learning by Standford. Feel free to check the assignments.
Also, if you want to read my other notes, feel free to check them at my blog.

I) Introduction

A recommender system or a recommendation system is a subclass of information filtering system that seeks to predict the "rating" or "preference" a user would give to an item.

Problem Formulation: (Predicting Movie Ratings case)

Let's define:

• $n_u$ = number of users.
• $n_m$ = number of movies.
• $r(i,j)=1$ if user
  $j$ has rated movie
  $i$.
• $y(i,j)$ is the rating given by user
  $j$ to the movie
  $i$, defined only if
  $r(i,j)=1$.

The objective of the recommender system is to use the rated movies by the users to predict the rating a user would give to a non-rated item.

To do so, 2 methods:

1. Content-based filtering.
2. Collaborative filtering.

II) Content-based filtering

Let's define:

• $x^{(i)}$ = feature vector for movie
  $i$. (in our case, it is the movie type : romance, action ...)
• ${\theta }^{(j)}$= parameter vector for user
  $j$. (user preferences : do they like more romance than action ?)
• $m^{(j)}$ = number of movies rated by user
  $j$.

The goal of this method is to predict the user rating on a non-rated movie based on movies characteristics. For example, when a friend asks you for a book recommendation, it's pretty natural to ask what kinds of books they have read and liked. From there, you could think of a few titles (books characteristics: fantasy, sci-fi ...) that are similar to the things they've read and liked in the past (user past books review).

So, in our case, it means that you need to have beforehand:

1. movies characteristics,
   $x^{(i)}$.
2. users past movie review,
   $y$.

With that, you can find user preference denoted as

$\theta$. Once you have user preference, it becomes easy to predict the user rating on a non-rated movie.

Suppose user

$j$ has rated

$m^{(j)}$ movies, then learning

${\theta }^{(j)}$ can be treated as linear regression problem. So, to learn

${\theta }^{(j)}$,

$$mi{n}_{{\theta }^{(j)}}\frac{1}{2}\sum _{i:r(i,j)=1}{[({\theta }^{(j)}{)}^T(x^{(i)})-y(i,j)]}^2+\frac{\lambda }{2}\sum _{k=1}^n({\theta }_k^{(j)}{)}^2$$

To get the parameters for all our users, we do the following:

$$\boxed{{\displaystyle mi{n}_{{\theta }^{(1)},\cdots ,{\theta }^{(n_u)}}\frac{1}{2}\sum _{j=1}^{n_u}\sum _{i:r(i,j)=1}{[({\theta }^{(j)}{)}^T(x^{(i)})-y(i,j)]}^2+\frac{\lambda }{2}\sum _{j=1}^{n_u}\sum _{k=1}^n({\theta }_k^{(j)}{)}^2}}$$

The cost function is then:

$$\boxed{{\displaystyle J({\theta }^{(1)},\cdots ,{\theta }^{(n_u)})=\frac{1}{2}\sum _{j=1}^{n_u}\sum _{i:r(i,j)=1}{[({\theta }^{(j)}{)}^T(x^{(i)})-y(i,j)]}^2+\frac{\lambda }{2}\sum _{j=1}^{n_u}\sum _{k=1}^n({\theta }_k^{(j)}{)}^2}}$$

The gradient descent update is then:

$$\boxed{{\displaystyle \begin{array}{ll}{\theta }_k^{(j)}& ={\theta }_k^{(j)}-\alpha \left(\sum _{i:r(i,j)=1}[({\theta }^{(j)}{)}^T{x}^{(i)}-y(i,j)]x_k^{(i)}\right)\text{, for k = 0 (bias/intercept term)}\\ {\theta }_k^{(j)}& ={\theta }_k^{(j)}-\alpha (\sum _{i:r(i,j)=1}[({\theta }^{(j)}{)}^T{x}^{(i)}-y(i,j)]x_k^{(i)}+\lambda {\theta }_k^{(j)})\text{, otherwise }\end{array}}}$$

Remark: The effectiveness of content based recommendation depends on identifying the features

$x^{(i)}$ properly, which is often not easy.

III) Collaborative filtering

Collaborative filtering has the intrinsic property of feature learning (it can learn by itself what features to use) which helps overcome drawbacks of content-based recommender systems.

Given the user past movie review

$y$ and the parameter vector

$\theta$, the algorithm learns the values for the features

$x^{(i)}$ by applying linear regression.

$$mi{n}_{x^{(i)}}\frac{1}{2}\sum _{j:r(i,j)=1}{[({\theta }^{(j)}{)}^T{x}^{(i)}-y(i,j)]}^2+\frac{\lambda }{2}\sum _{k=1}^n{\left(x_k^{(i)}\right)}^2$$

Intuitively this boils down to the scenario where given a movie and its ratings by various users (

$y$) and user preferences

$\theta$, the collaborative filitering algorithm tries to find the most optimal features to represent the movies such that the squared error between the two is minimized.

Since this is very similar to the linear regression problem, regularization term is introduced to prevent overfitting of the features learnt. Similarly by extending this, it is possible to learn all the features for all the movies

$i\in [1,n_m]$. Thus,

$$mi{n}_{x^{(1)},\cdots ,x^{(n_m)}}\frac{1}{2}\sum _{i=1}^{n_m}\sum _{j:r(i,j)=1}{[({\theta }^{(j)}{)}^T{x}^{(i)}-y(i,j)]}^2+\frac{\lambda }{2}\sum _{i=1}^{n_m}\sum _{k=1}^n{\left(x_k^{(i)}\right)}^2$$

where the gradient descent update on features is:

$$x_k^{(i)}:=x_k^{(i)}-\alpha (\sum _{j:r(i,j)=1}[({\theta }^{(j)}{)}^T{x}^{(i)}-y(i,j)]{\theta }_k^{(j)}+\lambda x_k^{(i)})$$

But it is also possible to solve for both

$\theta$ and

$x$ simultaneously, given by an update rule which is nothing but the combination of the earlier two update rules. Thus,

$$\boxed{{\displaystyle \begin{array}{ll}J(x^{(1)},\cdots ,x^{(n_m)},{\theta }^{(1)},\cdots ,{\theta }^{(n_u)})& =\frac{1}{2}\sum _{(i,j):r(i,j)=1}{[({\theta }^{(j)}{)}^T{x}^{(i)}-y(i,j)]}^2\\ & +\frac{\lambda }{2}\sum _{i=1}^{n_m}\sum _{k=1}^n(x_k^{(i)}{)}^2\\ & +\frac{\lambda }{2}\sum _{j=1}^{n_u}\sum _{k=1}^n({\theta }_k^{(j)}{)}^2\end{array}}}$$

$\sum _{(i,j):r(i,j)=1}$ is equivalent to looping through all the data where

$r(i,j)=1$.

And the minimization objective can be written as,

$$\boxed{{\displaystyle mi{n}_{x^{(1)},\cdots ,x^{(n_m)},{\theta }^{(1)},\cdots ,{\theta }^{(n_u)}}J(x^{(1)},\cdots ,x^{(n_m)},{\theta }^{(1)},\cdots ,{\theta }^{(n_u)})}}$$

Remark: Because the algorithm can learn feature by itself, the bias units where

$x_0=1$ and

${\theta }_0=1$ have been removed, therefore

$x\in {\mathbb{R}}^n$ and

$\theta \in {\mathbb{R}}^n$.

To summarize, the collaborative filtering algorithm has the following
steps:

1. Initialize
   $x^{(1)},\cdots ,x^{(n_m)},{\theta }^{(1)},\cdots ,{\theta }^{(n_u)}$ to small random values.
2. Minimize
   $J(x^{(1)},\cdots ,x^{(n_m)},{\theta }^{(1)},\cdots ,{\theta }^{(n_u)})$ using gradient descent or any other advance optimization algorithm. The update rules given below can be obtained by following the partial derivatives along
   $x$s and
   $\theta$s.
   $$\boxed{{\displaystyle \begin{array}{ll}{x}_k^{(i)}& =x_k^{(i)}-\alpha (\sum _{j:r(i,j)=1}[({\theta }^{(j)}{)}^T{x}^{(i)}-y(i,j)]{\theta }_k^{(j)}+\lambda x_k^{(i)})\\ {\theta }_k^{(j)}& ={\theta }_k^{(j)}-\alpha (\sum _{i:r(i,j)=1}[({\theta }^{(j)}{)}^T{x}^{(i)}-y(i,j)]x_k^{(i)}+\lambda {\theta }_k^{(j)})\end{array}}}$$
3. For a user with parameter
   $\theta$ and a movie with learned features
   $x$, the predicted star rating is given by
   ${\theta }^{T}x$.

Consequently, the matrix of all predicted ratings of all movies by all users

$Y$ can be written as:

$$Y=\left[\begin{array}{cccc}({\theta }^{(1)}{)}^T{x}^{(1)}& ({\theta }^{(2)}{)}^T{x}^{(1)}& \cdots & ({\theta }^{(n_u)}{)}^T{x}^{(1)}\\ ({\theta }^{(1)}{)}^T{x}^{(2)}& ({\theta }^{(2)}{)}^T{x}^{(2)}& \cdots & ({\theta }^{(n_u)}{)}^T{x}^{(2)}\\ ⋮& ⋮& \ddots & ⋮\\ ({\theta }^{(1)}{)}^T{x}^{(n_m)}& ({\theta }^{(2)}{)}^T{x}^{(n_m)}& \cdots & ({\theta }^{(n_u)}{)}^T{x}^{(n_m)}\end{array}\right]$$

where

$y(i,j)$ is the rating for movie

$i$ by user

$j$.

IV) Implementation detail

How to handle the case where a user has not rated any movies ?

The term in our cost function is

$\frac{1}{2}\sum _{(i,j):r(i,j)=1}{[({\theta }^{(j)}{)}^T{x}^{(i)}-y^{(i,j)}]}^2=0$ because the summation applies only if the user has rated a movie. Thus,

$$J(x^{(1)},\cdots ,x^{(n_m)},{\theta }^{(1)},\cdots ,{\theta }^{(n_u)})=\frac{\lambda }{2}\sum _{i=1}^{n_m}\sum _{k=1}^n(x_k^{(i)}{)}^2+\frac{\lambda }{2}\sum _{j=1}^{n_u}\sum _{k=1}^n({\theta }_k^{(j)}{)}^2$$

When minimizing our cost function, we will find

${\theta }^{(5)}$ equal to the 0 vector because the only term to pull away our regularization term on theta from 0 is equal to 0 (See above). Thus, when it comes to predict movies for Eve, it will all be equal to 0 (

${\theta }^{(5)}{x}^{(i)}=0$) which does not seem intuitively correct.

To prevent this, we will do mean normalization. Here is an example:

$$Y=\left[\begin{array}{cccc}5& 5& 0& 0\\ 4& ?& ?& 0\\ 0& 0& 5& 4\\ 0& 0& 5& 0\end{array}\right]\mu =\left[\begin{array}{c}2.5\\ 2\\ 2.25\\ 1.25\end{array}\right]$$

where

${\mu }_j=\frac{\sum _{j:r(i,j)=1}{Y}_{i,j}}{\sum _j{r}^{(i,j)}}$

Then, let's define

$Y^{\prime }=Y-\mu$

$$Y^{\prime }=\left[\begin{array}{cccc}2.5& 2.5& -2.5& -2.5\\ 2& ?& ?& -2\\ -.2.25& -2.25& 3.75& 1.25\\ -1.25& -1.25& 3.75& -1.25\end{array}\right]$$

Which means that in our cost function, we need to put

${\theta }^{(j)T}{x}^{(i)}+{\mu }_i$ without the summation condition

$j:r(i,j)=1$ instead of

${\theta }^{(j)T}{x}^{(i)}$

V) Content-based vs Collaborative filtering

Content-based recommendation engine works with existing profiles of users. A profile has information about a user and their taste. Taste is based on user rating for different items. Generally, whenever a user creates his profile, Recommendation engine does a user survey to get initial information about the user in order to avoid new user problem.

In the recommendation process, the engine compares the items that are already positively rated by the user with the items he didn't rate and looks for similarities. Items similar to the positively rated ones will be recommended to the user. Here, based on user’s taste and behavior a content-based model can be built by recommending articles relevant to user’s taste. This model is efficient and personalized yet it lacks something.

Let us understand this with an example. Assume there are four categories of news:

• Politics
• Sports
• Entertainment
• Technology

and there is a user A who has read articles related to Technology and Politics. The content-based recommendation engine will only recommend articles related to these categories and may never recommend anything in other categories as the user never viewed those articles before.

This problem can be solved using another variant of recommendation algorithm known as Collaborative Filtering.

The idea of collaborative filtering is finding users in a community that share appreciations. If two users have same or almost same rated items in common, then they have similar taste. Such users build a group or a so-called neighborhood. A user gets recommendations for those items that user hasn't rated before but was positively rated by users in his/her neighborhood.

Collaborative filtering has basically 2 approaches:

1. User Based Approach: In this approach, Items that are recommended to a user are based on an evaluation of items by users of the same neighborhood, with whom he/she shares common preferences. If the article was positively rated by the community, it will be recommended to the user. In the user-based approach, articles which are already rated by a user, play an important role in searching for a group that shares appreciations with him/her.
2. Item Based Approach: Referring to the fact that the taste of users remains constant or change very slightly, similar articles build neighborhoods based on appreciations of users. Afterwards, the system generates recommendations with articles in the neighborhood that a user might prefer.

Let's try to understand above picture. Let's say there are three users A, B and C.

1. In user-based approach, user A and C are similar because both of them like Strawberry and Watermelon. Now user A likes Grapes and Orange too. So user-based approach will recommend Grapes and Orange to user C.
2. In item-based approach, Grapes and Watermelon will form the similar items neighborhood which means irrespective of users, different items which are similar will form a neighborhood. So when user C likes Watermelon, the other item from the same neighborhood i.e Grapes will be recommended by item-based approach.