Recommender Systems and Collaborative Filtering

Machine Learning Notes · recommenders 1 of 1 · Collaborative filtering ← Anomaly detection Reinforcement learning →

A recommender system starts from a table that is mostly empty. Users are the columns, items are the rows, and an entry exists only where somebody bothered to rate something. Every question worth asking is about the holes: what would Alice have said about a film she has never seen, and which film should be put in front of her next?

This is a different shape of problem from everything so far. There is no feature vector handed to you per example and no label column — there is one sparse matrix, and both the "features" and the "parameters" have to come out of it.

In one line. Predict user $j$'s rating of item $i$ as $\vec{w}^{(j)} \cdot \vec{x}^{(i)} + b^{(j)}$ — a linear regression per user. If the item features $\vec{x}^{(i)}$ are known, that is all it is. If they are not, learn them at the same time as the parameters by minimising the same squared-error cost over both: that is collaborative filtering, and the learned features are what make "related items" a distance computation.

Contents

A matrix full of holes

The example everyone uses

Four users, five films, ratings from 0 to 5 stars, and a question mark wherever the user has not rated the film:

Movie	Alice (1)	Bob (2)	Carol (3)	Dave (4)
Love at last	5	5	0	0
Romance forever	5	?	?	0
Cute puppies of love	?	4	0	?
Nonstop car chases	0	0	5	4
Swords vs. karate	0	0	5	?

Table 1: The ratings matrix. Five of the twenty entries are missing, and the missing ones are the entire point — a recommender exists to fill them in. Note the structure already visible by eye: Alice and Bob like the first three films and dislike the last two, and Carol and Dave are the exact opposite.

Notation

$n_u$ — the number of users; here $n_u = 4$.
$n_m$ — the number of items; here $n_m = 5$.
$r(i,j) = 1$ if user $j$ has rated item $i$, and $0$ otherwise. So $r(1,1) = 1$ (Alice rated Love at last) while $r(3,1) = 0$ (she has not rated Cute puppies of love).
$y^{(i,j)}$ — the rating user $j$ gave item $i$, defined only when $r(i,j) = 1$. Here $y^{(3,2)} = 4$: Bob gave Cute puppies of love four stars.
$m^{(j)}$ — how many items user $j$ has rated.

The distinction between $r$ and $y$ is the one piece of bookkeeping that matters. A missing rating is not a zero. Zero is a real, and very negative, opinion; missing means no opinion was expressed, and every sum below runs only over $i$ with $r(i,j) = 1$.

If we already had features

Suppose someone hands you two numbers per film — how much romance and how much action:

Movie	$x_1$ (romance)	$x_2$ (action)
Love at last	0.90	0.00
Romance forever	1.00	0.01
Cute puppies of love	0.99	0.00
Nonstop car chases	0.10	1.00
Swords vs. karate	0.00	0.90

Table 2: The same films with two given features. The three romances score high on $x_1$ and near zero on $x_2$; the two action films do the reverse. With these in hand, each user becomes an independent regression problem.

Figure 1: The five films placed by the two features they were handed. The catalogue splits into two tight clumps in opposite corners — three romances at $x_1 \approx 1$, $x_2 \approx 0$ and two action films at the reverse — and nothing sits in the middle. That separation is what lets four ratings per user pin down a taste vector: a user who scores the bottom-right corner high and the top-left corner low has already told you almost everything the model can represent.

Now give each user their own weight vector and bias, and predict their rating of item $i$ the obvious way:

$$ \hat{y}^{(i,j)} = \vec{w}^{(j)} \cdot \vec{x}^{(i)} + b^{(j)} . \tag{1} $$

Equation 1: The prediction rule. Every user gets their own $\vec{w}^{(j)}$ and $b^{(j)}$; the item contributes only through its feature vector. This is linear regression, one model per user, sharing the same inputs.

Ng's worked case: suppose Alice's parameters came out as $\vec{w}^{(1)} = \begin{bmatrix} 5 \ 0\end{bmatrix}$ and $b^{(1)} = 0$ — she cares about romance and is indifferent to action. Then her predicted rating for Cute puppies of love, $\vec{x}^{(3)} = \begin{bmatrix} 0.99 \ 0 \end{bmatrix}$, is

$$ \vec{w}^{(1)} \cdot \vec{x}^{(3)} + b^{(1)} = 5(0.99) + 0(0) + 0 = 4.95 , $$

which is the number that goes in the hole. This is just linear regression — the machinery of note 1 applied $n_u$ times over.

The cost function

For one user

Fit $\vec{w}^{(j)}, b^{(j)}$ on the items that user actually rated:

$$ \min_{\vec{w}^{(j)},\, b^{(j)}} \; J\left(\vec{w}^{(j)}, b^{(j)}\right) = \frac{1}{2m^{(j)}} \sum_{i \,:\, r(i,j)=1} \left(\vec{w}^{(j)} \cdot \vec{x}^{(i)} + b^{(j)} - y^{(i,j)}\right)^2 + \frac{\lambda}{2m^{(j)}} \sum_{k=1}^{n}\left(w_k^{(j)}\right)^2 . \tag{2} $$

Equation 2: The cost for a single user. The sum is over rated items only — that is what $i : r(i,j) = 1$ means — and the second term is the usual $L_2$ penalty over that user's $n$ weights.

The $m^{(j)}$ can go. Dividing by the number of items this user rated scales the whole objective by a constant, and a constant does not move the minimum. Ng crosses it out on the slide, and the convention from here on is to drop it — which matters in §3.2, where users who rated very different numbers of items are summed together.

For all users

Every user's problem is independent given the features, so the total cost is just the sum:

$$ J\left(\vec{w}^{(1)}, \ldots, \vec{w}^{(n_u)}, b^{(1)}, \ldots, b^{(n_u)}\right) = \frac{1}{2}\sum_{j=1}^{n_u} \sum_{i \,:\, r(i,j)=1} \left(\vec{w}^{(j)} \cdot \vec{x}^{(i)} + b^{(j)} - y^{(i,j)}\right)^2 + \frac{\lambda}{2}\sum_{j=1}^{n_u}\sum_{k=1}^{n}\left(w_k^{(j)}\right)^2 . \tag{3} $$

Equation 3: The cost over all users. The double sum visits every observed entry of the ratings matrix exactly once; the regularization runs over every weight of every user.

Minimising this by gradient descent is ordinary linear regression, run in parallel for $n_u$ users.

Fitting the four users

Doing exactly that on the table above — least squares on each user's rated films, with a light $\lambda = 0.01$ — gives four parameter sets and, with them, every missing entry:

	Alice	Bob	Carol	Dave
$\vec{w}^{(j)}$	$[\,2.36,\,-3.01\,]$	$[\,1.07,\,-3.68\,]$	$[-2.39,\,2.97\,]$	$[-1.56,\,2.65\,]$
$b^{(j)}$	$2.75$	$3.47$	$2.28$	$1.48$
Love at last	4.88	4.43	0.12	0.08
Romance forever	5.09	4.50 *	−0.08 *	−0.05
Cute puppies of love	5.09 *	4.52	−0.09	−0.06 *
Nonstop car chases	−0.02	−0.10	5.01	3.97
Swords vs. karate	0.05	0.16	4.95	3.87 *

Table 3: Parameters fitted per user from the given features, and the resulting predictions. Starred entries were missing from the data. Alice and Bob come out with a positive romance weight and a negative action weight; Carol and Dave come out with the signs reversed, which is the structure of the matrix expressed as numbers.

The recommendation for Alice is now readable straight off the column: Cute puppies of love at $5.09$. The predictions that fall slightly outside the $0$–$5$ range are a reminder that nothing in the model knows the scale is bounded — in production you clip them.

Where do the features come from?

Flipping the problem around

The whole of §2–§4 assumed somebody had labelled every film with a romance score and an action score. For a catalogue of five films that is plausible; for a million items it is not, and nobody agrees on what the axes should even be.

But notice the symmetry in $\vec{w}^{(j)} \cdot \vec{x}^{(i)}$. If the features are known, the users' parameters are a regression. If the users' parameters were known, the features would be a regression too — with $\vec{w}$ fixed, each $\vec{x}^{(i)}$ is chosen to make $\vec{w}^{(j)} \cdot \vec{x}^{(i)} + b^{(j)}$ land near $y^{(i,j)}$ for every user $j$ who rated item $i$.

Learning both at once

Neither is known, so minimise over both at the same time:

$$ J\left(\vec{w}, b, \vec{x}\right) = \frac{1}{2}\sum_{(i,j)\,:\, r(i,j)=1} \left(\vec{w}^{(j)} \cdot \vec{x}^{(i)} + b^{(j)} - y^{(i,j)}\right)^2 + \frac{\lambda}{2}\sum_{j=1}^{n_u}\sum_{k=1}^{n}\left(w_k^{(j)}\right)^2 + \frac{\lambda}{2}\sum_{i=1}^{n_m}\sum_{k=1}^{n}\left(x_k^{(i)}\right)^2 . \tag{4} $$

Equation 4: The collaborative filtering objective. The first term is unchanged — it visits every observed rating — and the only difference from the cost in section 3.2 is that the $\vec{x}$ are now variables to be minimised over, with their own penalty. Gradient descent updates $w$, $b$ and $x$ together.

The features are initialised randomly, like any other parameter, and descend with everything else. What comes out is not "romance" and "action" — it is whatever pair of axes best explains the ratings, which is why §7 opens by admitting the learned features are hard to interpret.

Why it is called collaborative

Nothing would work with a single user: one column of ratings cannot pin down both a feature vector per item and a taste vector for that user. It works because many users rate the same items. Alice's five stars and Bob's five stars for Love at last together push that film's feature vector somewhere that explains both, and that vector is then used to predict Carol's opinion of it. Each user's ratings help every other user, through the items they share — the collaboration is between users, mediated by items.

A real run

Running gradient descent on Equation 4 over the ratings table alone — no given features, $n = 2$, $\lambda = 1$, learning rate $0.01$, random initialization:

The cost coming down

Figure 2: Collaborative filtering converging on the five-by-five example. The cost falls from 80.6 to 9.8 within a hundred iterations and is flat by five hundred; the floor is not zero because $\lambda$ keeps the parameters small and fifteen observations cannot be fitted exactly by a rank-two model.

What it learned

Movie	learned $x_1$	learned $x_2$
Love at last	$1.237$	$-0.118$
Romance forever	$1.064$	$-0.102$
Cute puppies of love	$0.918$	$-0.088$
Nonstop car chases	$-1.640$	$0.157$
Swords vs. karate	$-1.578$	$0.151$

Table 4: The learned two-dimensional item features. Nobody told the algorithm about genre: the three romances came out with a positive first coordinate and the two action films with a negative one, purely because that is what makes the ratings reconstruct. The second coordinate is nearly a fixed multiple of the first — with $\lambda = 1$ the model used only the one axis the data actually supports.

The user parameters came out matched to them — Alice $\vec{w} = [\,1.59, -0.15\,]$, $b = 2.87$ against Carol $\vec{w} = [-1.61,\, 0.15\,]$, $b = 2.07$ — one taste vector pointing along the learned axis and one pointing against it.

Figure 3: What the algorithm actually learned, plotted in its own feature space. Read the axis ranges before the shape: $x_1$ spans 4 units and $x_2$ spans half of one, so the vertical scale is stretched about eightfold. Every film lands on the same dashed line through the origin — the ratio $x_2/x_1$ is $-0.0954$, $-0.0959$, $-0.0959$, $-0.0957$ and $-0.0957$ for the five of them — and so do both taste vectors. With $\lambda = 1$ the model was given two dimensions and used one, because one is all fifteen ratings support. The romances sit at positive $x_1$ and the action films at negative $x_1$, and Alice's and Carol's vectors point in exactly opposite directions along that single axis. Nobody supplied the word genre.

The filled-in matrix

Movie	Alice	Bob	Carol	Dave
Love at last	4.85	4.48	0.06	0.11
Romance forever	4.57	4.22 *	0.34 *	0.32
Cute puppies of love	4.34 *	4.01	0.57	0.50 *
Nonstop car chases	0.24	0.21	4.73	3.57
Swords vs. karate	0.34	0.30	4.63	3.49 *

Table 5: The ratings matrix reconstructed from the learned features and parameters. Starred entries were never observed. The observed entries are reproduced to within a few tenths, and the five holes are filled with values that agree with what the columns around them say.

Alice is again recommended Cute puppies of love — from ratings alone, with no genre labels anywhere in the pipeline.

Figure 4: Alice's column under both models. The grey bar is missing for Cute puppies of love — that is the hole being filled — and both models put it at the top of her list anyway, at 5.09 from the handed-over genre features and 4.34 from features learned out of ratings alone. The learned model is the looser fit of the two on the entries it can check (RMSE 0.33 against 0.21 over the fifteen observed ratings), which is the price of also having had to invent the axes; what matters for a recommendation is that the ordering is the same.

The learned $\vec{x}^{(i)}$ are hard to read one at a time, but they are perfectly usable compared to each other. Items that get similar ratings from the same people end up with similar feature vectors, so "related to item $i$" means "smallest distance from $\vec{x}^{(i)}$":

$$ \operatorname{dist}^2(i, k) = \sum_{\ell=1}^{n}\left(x^{(k)}_{\ell} - x^{(i)}_{\ell}\right)^2 = \left\lVert \vec{x}^{(k)} - \vec{x}^{(i)} \right\rVert^2 . \tag{5} $$

Equation 5: The similarity between items $i$ and $k$. As with k-means, the square root is optional — it does not change the ordering — so the squared form is what gets computed.

This is the machinery behind "people who liked this also liked…", and it costs one pass over the catalogue.

First the source's own toy example, with hand-chosen vectors — target $\vec{x}^{(i)} = [\,1.0,\, 0.9\,]$ against $\vec{x}^{(k_1)} = [\,1.1,\, 1.0\,]$ and $\vec{x}^{(k_2)} = [-0.5,\, 2.0\,]$:

$$ \begin{aligned} \operatorname{dist}^2(i, k_1) &= (1.1 - 1.0)^2 + (1.0 - 0.9)^2 = 0.01 + 0.01 = 0.02, &\quad \operatorname{dist} &\approx 0.1414, \[2pt] \operatorname{dist}^2(i, k_2) &= (-0.5 - 1.0)^2 + (2.0 - 0.9)^2 = 2.25 + 1.21 = 3.46, &\quad \operatorname{dist} &\approx 1.8601 . \end{aligned} $$

Since $0.02 < 3.46$, item $k_1$ is the related one.

And now the same computation on the features actually learned in §6, taking Love at last as the target:

Candidate	$\operatorname{dist}^2$	$\operatorname{dist}$
Romance forever	$0.0302$	$0.174$	closest
Cute puppies of love	$0.1024$	$0.320$	also close
Swords vs. karate	$7.9968$	$2.828$	far
Nonstop car chases	$8.3517$	$2.890$	furthest

Table 6: Related items computed from the learned vectors. The gap is not subtle — the two romances sit at squared distances of 0.03 and 0.10, the two action films at 8.35 and 8.00, a factor of roughly eighty. Nothing about genre was ever supplied; this ordering came out of five people's ratings.

Where this goes next

The source pages stop here, at the ratings matrix, the per-user regression, the cost, and related items. Three things a production recommender needs are worth naming, because each is a known gap in what is above:

New users and new items. A user who has rated nothing gets $\vec{w} = \vec{0}$ from the regularizer and is predicted to rate everything at $b$. The standard fix is mean normalization — subtract each item's average rating before fitting and add it back when predicting — so a brand-new user is at least told what everybody else thinks. The item-side version of the same problem is the cold start, and it is why real systems mix in content features (genre, cast, text) that exist before any rating does.
Ratings that are not numbers. Most real signals are binary — clicked or not, watched or not, bought or not. The same factorization applies with the squared error replaced by a logistic loss on $\sigma\left(\vec{w}^{(j)}\cdot\vec{x}^{(i)} + b^{(j)}\right)$, which makes it exactly the logistic regression of note 2 with learned inputs.
Content-based filtering. Rather than learning item vectors from ratings alone, compute a user vector and an item vector from known attributes with two neural networks and match them by dot product — which scales to catalogues where most items have no ratings at all.

Then the course changes subject entirely. Reinforcement learning has no dataset: an agent moves through states, actions have consequences, and the reward for a good decision may arrive many steps after the decision was made.

Backwards from here: linear regression is the regression this note runs once per user, clustering uses the same squared distance for a different purpose, and logistic regression is what the binary-label version becomes.