Lecture 16: Recommender Systems

Recommender systems - introduction

Two motivations for talking about recommender systems

• Important application of ML systems
  • Many technology companies find recommender systems to be absolutely key.
  • Think about websites (Amazon, eBay, iTunes Genius):
    • Try and recommend new content for you based on past purchases.
    • Substantial part of Amazon's revenue generation.
  • Improvement in recommender system performance can bring in more income.
  • Kind of a funny problem:
    • In academic learning, recommender systems receive a small amount of attention.
    • But in industry, it's an absolutely crucial tool.
• Talk about the big ideas in machine learning
  • Not so much a technique, but an idea.
  • As seen, features are really important:
    • There's a big idea in machine learning that for some problems you can learn what a good set of features are (so not select those features, but learn them).
  • Recommender systems do this — try and identify the crucial and relevant features.

Example - predict movie ratings

• You're a company who sells movies:
  • You let users rate movies using a 1–5 star rating (to make the example nicer, allow 0–5; makes math easier).
• You have five movies and four users.
• Admittedly, business isn't going well, but you're optimistic about the future as a result of your truly outstanding (if limited) inventory.

• To introduce some notation:
  • $n_u$ — Number of users (called $n_u$ occasionally as we can't subscript in superscript)
  • $n_m$ — Number of movies
  • $r(i, j) = 1$ if user $j$ has rated movie $i$ (i.e. bitmap)
  • $y^{(i,j)}$ — rating given by user $j$ to movie $i$ (defined only if $r(i,j) = 1$)
• So for this example:
  • $n_u = 4$
  • $n_m = 5$
• Summary of scoring:
  • Alice and Bob gave good ratings to rom coms, but low scores to action films.
  • Carol and Dave gave good ratings for action films, but low ratings for rom coms.
• We have the data given above.
• The problem is as follows:
  • Given $r(i,j)$ and $y^{(i,j)}$, go through and try and predict missing values (?s).
  • Come up with a learning algorithm that can fill in these missing values.

---

Content based recommendation

Using our example above, how do we predict?

• For each movie we have a feature vector which measures the degree to which a movie is a romantic movie ($x_1$) or an action movie ($x_2$).

• If we have features like these, each film can be represented by a feature vector.
• Add an extra feature $x_0 = 1$ (bias unit):
  • So for each film we have a $3 \times 1$ vector, which for film number 1 ("Love at Last") would be:

• We'll explain later how we derived these values, but for now just take it that we have a feature vector $x^{(i)}$ associated with movie $i$:
  • For movie 1: $x^{(1)} = \begin{bmatrix} 1 \\ 0.9 \\ 0 \end{bmatrix}$
  • For movie 2: $x^{(2)} = \begin{bmatrix} 1 \\ 1.0 \\ 0.01 \end{bmatrix}$
  • For movie 3: $x^{(3)} = \begin{bmatrix} 1 \\ 0.99 \\ 0 \end{bmatrix}$
  • For movie 4: $x^{(4)} = \begin{bmatrix} 1 \\ 0.1 \\ 1.0 \end{bmatrix}$
  • For movie 5: $x^{(5)} = \begin{bmatrix} 1 \\ 0 \\ 0.9 \end{bmatrix}$

• So here $n = 2$ (number of features, not counting $x_0$).
• For each user $j$, we can learn a parameter vector $\theta^{(j)} \in \mathbb{R}^{n+1}$.
• Predict user $j$'s rating for movie $i$ as:

• Predicted rating = $(\theta^{(j)})^T x^{(i)}$ stars.

• Detailed Example: User 1 (Alice)

  • Suppose Alice has parameter vector $\theta^{(1)} = \begin{bmatrix} 0 \\ 5 \\ 0 \end{bmatrix}$.
  • For Movie 3 ("Cute Puppies of Love"), $x^{(3)} = \begin{bmatrix} 1 \\ 0.99 \\ 0 \end{bmatrix}$.
  • Predicted rating: $(\theta^{(1)})^T x^{(3)} = 0(1) + 5(0.99) + 0(0) = 4.95$ stars.
  • This fits with Alice's known preferences!

How do we learn $(\theta^{(j)})$?

• To learn $\theta^{(j)}$ (parameter for user $j$):
  • Create parameters which give values as close as those seen in the data when applied.
  • Sum over all movies rated by user $j$:

$\min_{\theta^{(j)}} \frac{1}{2 m^{(j)}} \sum_{i:r(i,j)=1} \left( (\theta^{(j)})^T x^{(i)} - y^{(i,j)} \right)^2 + \frac{\lambda}{2 m^{(j)}} \sum_{k=1}^n (\theta^{(j)}_k)^2$

• Where $m^{(j)}$ is the number of movies rated by user $j$.
• To make this a little bit clearer, you can get rid of the $m^{(j)}$ term (it's just a constant so shouldn't affect the optimal $\theta^{(j)}$ value):

$\min_{\theta^{(j)}} \frac{1}{2} \sum_{i:r(i,j)=1} \left( (\theta^{(j)})^T x^{(i)} - y^{(i,j)} \right)^2 + \frac{\lambda}{2} \sum_{k=1}^n (\theta^{(j)}_k)^2$

• So to learn $\theta^{(j)}$ for a single user $j$:

• To learn parameter vectors for all users ($\theta^{(1)}, \theta^{(2)}, \dots, \theta^{(n_u)}$):

$J(\theta^{(1)}, \dots, \theta^{(n_u)}) = \frac{1}{2} \sum_{j=1}^{n_u} \sum_{i:r(i,j)=1} \left( (\theta^{(j)})^T x^{(i)} - y^{(i,j)} \right)^2 + \frac{\lambda}{2} \sum_{j=1}^{n_u} \sum_{k=1}^n (\theta^{(j)}_k)^2$

• Gradient Descent Update Rules
  • In order to do the minimization, we use the following gradient descent updates:

• For $k = 0$ (bias term, no regularization): $\theta_0^{(j)} := \theta_0^{(j)} - \alpha \sum_{i:r(i,j)=1} \left( (\theta^{(j)})^T x^{(i)} - y^{(i,j)} \right) x_0^{(i)}$

• For $k \neq 0$ (with regularization): $\theta_k^{(j)} := \theta_k^{(j)} - \alpha \left( \sum_{i:r(i,j)=1} \left( (\theta^{(j)})^T x^{(i)} - y^{(i,j)} \right) x_k^{(i)} + \lambda \theta_k^{(j)} \right)$

• We can define the error derivative term as:

• This algorithm is called content-based recommendation because we assume we have features available for our content (movies) that describe their features (e.g. romance, action).

---

Collaborative filtering - overview

• The collaborative filtering algorithm has a very interesting property — it does feature learning, i.e. it can learn what features to use by itself!

• So — let's change the problem and pretend we have a dataset where we don't know any of the features associated with the movies (i.e. $x_1$ and $x_2$ are unknown).
• BUT suppose we have collected parameters $\theta^{(1)}, \theta^{(2)}, \theta^{(3)}, \theta^{(4)}$ from our users:

• $\theta^{(1)} = \begin{bmatrix} 0 \\ 5 \\ 0 \end{bmatrix}$ (Alice likes romance)

• $\theta^{(2)} = \begin{bmatrix} 0 \\ 5 \\ 0 \end{bmatrix}$ (Bob likes romance)

• $\theta^{(3)} = \begin{bmatrix} 0 \\ 0 \\ 5 \end{bmatrix}$ (Carol likes action)

• $\theta^{(4)} = \begin{bmatrix} 0 \\ 0 \\ 5 \end{bmatrix}$ (Dave likes action)

• Given these user parameters, can we infer the feature vector $x^{(i)}$ for movie $i$?

• Consider Movie 1 ("Love at Last"):

  • Alice and Bob gave it 5 stars.
  • Carol and Dave gave it 0 stars.
  • We want $(\theta^{(1)})^T x^{(1)} \approx 5$, $(\theta^{(2)})^T x^{(1)} \approx 5$, $(\theta^{(3)})^T x^{(1)} \approx 0$, $(\theta^{(4)})^T x^{(1)} \approx 0$.
  • From this, we can infer $x^{(1)} = \begin{bmatrix} 1 \\ 1.0 \\ 0.0 \end{bmatrix}$, meaning Movie 1 is a strong romantic movie with zero action content!

Formalizing the collaborative filtering problem

• Given $(\theta^{(1)}, \dots, \theta^{(n_u)})$, we want to learn features $x^{(i)}$ for movie $i$:

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

• To learn all features $(x^{(1)}, \dots, x^{(n_m)})$: $\min_{x^{(1)}, \dots, x^{(n_m)}} \frac{1}{2} \sum_{i=1}^{n_m} \sum_{j:r(i,j)=1} \left( (\theta^{(j)})^T x^{(i)} - y^{(i,j)} \right)^2 + \frac{\lambda}{2} \sum_{i=1}^{n_m} \sum_{k=1}^n (x_k^{(i)})^2$

How does this work with the previous recommendation system?

• Content-based recommendation systems:
  • Given movie features $x^{(1)}, \dots, x^{(n_m)}$, we can learn user parameters $\theta^{(1)}, \dots, \theta^{(n_u)}$.
• Feature learning (given parameters):
  • Given user parameters $\theta^{(1)}, \dots, \theta^{(n_u)}$, we can learn movie features $x^{(1)}, \dots, x^{(n_m)}$.
• This is a chicken-and-egg problem:
  • Which comes first, $\theta$ or $x$?
  • We can actually iterate back and forth!
  • Randomly initialize $\theta \rightarrow$ Learn $x \rightarrow$ Learn $\theta \rightarrow$ Learn $x \rightarrow \dots$
  • This converges to a good set of features and parameters!

---

Collaborative filtering Algorithm

• Here we combine both ideas into a single joint optimization objective to solve for $\theta$ and $x$ simultaneously.

• We can write a single joint cost function $J(x^{(1)}, \dots, x^{(n_m)}, \theta^{(1)}, \dots, \theta^{(n_u)})$:

$J(x, \theta) = \frac{1}{2} \sum_{(i,j):r(i,j)=1} \left( (\theta^{(j)})^T x^{(i)} - y^{(i,j)} \right)^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$

Understanding this optimization objective

• The squared error term sums over all pairs $(i,j)$ for which $r(i,j) = 1$ (all user-movie pairs with ratings).

• Notice that in collaborative filtering, we eliminate the bias term $x_0 = 1$ and $\theta_0 = 0$. Thus $x \in \mathbb{R}^n$ and $\theta \in \mathbb{R}^n$. If the algorithm needs a constant feature, it can learn $x_1 = 1$ automatically!

Algorithm Structure

1. Initialize $x^{(1)}, \dots, x^{(n_m)}$ and $\theta^{(1)}, \dots, \theta^{(n_u)}$ to small random values (similar to neural network weight initialization; breaks symmetry).
2. Minimize $J(x, \theta)$ using gradient descent (or advanced optimization algorithms like Conjugate Gradient, L-BFGS):

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

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

3. For a user $j$ with parameters $\theta^{(j)}$ and a movie $i$ with learned features $x^{(i)}$, predict rating as: $\text{Predicted Rating} = (\theta^{(j)})^T x^{(i)}$

---

Vectorization: Low rank matrix factorization

• Now let's look at how to vectorize collaborative filtering calculations.

• Group all ratings into a rating matrix $Y$ of dimension $n_m \times n_u$ ($5 \times 4$ in our example):

$$Y = \begin{bmatrix} 5 & 5 & 0 & 0 \\ 5 & \text{?} & 0 & 0 \\ \text{?} & 4 & 0 & 0 \\ 0 & 0 & 5 & 4 \\ 0 & 0 & 5 & 0 \end{bmatrix}$$

• We can vectorize the predicted ratings matrix as:

• Define movie feature matrix $X$:

$$X = \begin{bmatrix} \text{---} & (x^{(1)})^T & \text{---} \\ \text{---} & (x^{(2)})^T & \text{---} \\ & \vdots & \\ \text{---} & (x^{(n_m)})^T & \text{---} \end{bmatrix} \quad (n_m \times n)$$

• Define user parameter matrix $\Theta$:

$$\Theta = \begin{bmatrix} \text{---} & (\theta^{(1)})^T & \text{---} \\ \text{---} & (\theta^{(2)})^T & \text{---} \\ & \vdots & \\ \text{---} & (\theta^{(n_u)})^T & \text{---} \end{bmatrix} \quad (n_u \times n)$$

• Then the matrix of predicted ratings is given by: $\text{Predicted Ratings} = X \Theta^T$

• This vectorized algorithm is also called Low Rank Matrix Factorization because $X \Theta^T$ is a low-rank matrix approximation of $Y$.

Recommending new movies to a user

• How can we find movies related to a movie $i$?
• For each movie $i$, we learn a feature vector $x^{(i)} \in \mathbb{R}^n$.
• If a user is looking at movie $i$, how do we find a movie $j$ that is most similar to movie $i$?
• Find movie $j$ such that the distance $\|x^{(i)} - x^{(j)}\|$ is small!

---

Implementation detail: Mean Normalization

• Let's look at one final implementation detail to make the collaborative filtering algorithm work much better for users with no ratings.

• Problem Case: Consider user 5 ("Eve") who has not rated any movies.
  • What does the algorithm predict for Eve?
  • Let's look at Eve's parameter vector $\theta^{(5)}$ (for $n=2$):

• For Eve, $r(i, 5) = 0$ for all movies $i$.
• Thus, the first term in $J(x, \theta)$ has no terms involving $\theta^{(5)}$!
• The only term involving $\theta^{(5)}$ is the regularization term:

$\min_{\theta^{(5)}} \frac{\lambda}{2} \sum_{k=1}^n (\theta_k^{(5)})^2$

• The value of $\theta^{(5)}$ that minimizes this is $\theta^{(5)} = \begin{bmatrix} 0 \\ 0 \end{bmatrix}$.
• If $\theta^{(5)} = \begin{bmatrix} 0 \\ 0 \end{bmatrix}$, then for any movie $i$, predicted rating is: $(\theta^{(5)})^T x^{(i)} = 0$
• We predict 0 stars for every movie for Eve! That is useless — we can't make any meaningful recommendations to her.

How does mean normalization work?

• Group all ratings into matrix $Y$ (with a column of ?s for Eve):

• Compute average rating for each movie $i$ into vector $\mu \in \mathbb{R}^{n_m}$:

$$\mu = \begin{bmatrix} 2.5 \\ 2.5 \\ 2.0 \\ 2.25 \\ 1.25 \end{bmatrix}$$

• Subtract off the mean ratings from $Y$ to get normalized matrix $Y$:

$Y := Y - \mu$

• Now every movie has an average rating of 0 in the normalized matrix.

• Train collaborative filtering on normalized matrix $Y$ to learn $x^{(i)}$ and $\theta^{(j)}$.

• For user $j$ and movie $i$, predict rating as: $\text{Predicted Rating} = (\theta^{(j)})^T x^{(i)} + \mu_i$

• For user 5 (Eve), $\theta^{(5)} = \begin{bmatrix} 0 \\ 0 \end{bmatrix}$ (since no ratings):

$\text{Predicted Rating for Eve on Movie } i = (\theta^{(5)})^T x^{(i)} + \mu_i = 0 + \mu_i = \mu_i$

• Now, for a user who has rated no movies, we predict the average rating $\mu_i$ for movie $i$! This is logical and provides a reasonable baseline for recommendations.

• Summary / Aside:

  • Mean normalization allows the system to handle new users with zero ratings gracefully by predicting average item ratings.
  • (Similarly, column-wise normalization can handle brand new unrated movies, though usually unrated movies shouldn't be recommended until evaluated).