Recommender systems

The learning to rank note ordered documents for a query, and every (query, document) pair came with features: text matches, link counts, embeddings. A recommender orders items for a person: the next film, the songs of a playlist, the products for a basket, the posts of a feed. The query is a user, and there is often nothing to describe the user except what they did: which items they rated, bought, played or skipped. That record is enough. People who agreed in the past tend to agree in the future, and items liked by the same people tend to be liked together. This note turns that observation into models, from neighbours in the user–item matrix to the low-rank factorization that won the Netflix Prize, adapts it to feedback without negatives, and spends as much time on evaluation as on fitting, because a recommender is unusually easy to evaluate wrongly.

Notation. There are $m$ users, indexed by $u$, and $n$ items, indexed by $i$. $r_{ui}$ is the feedback of user $u$ on item $i$: a rating of 1 to 5 stars, or for implicit feedback a count such as the number of plays. $\Omega$ is the set of pairs $(u, i)$ with known $r_{ui}$; $n_u$ and $n_i$ are the numbers of known entries of user $u$ and of item $i$. $R$ is the $m \times n$ matrix with the known entries filled in. A prediction is $\hat r_{ui}$. Latent factors are vectors $p_u, q_i \in \mathbb R^d$, the rows of matrices $P$ ($m \times d$) and $Q$ ($n \times d$); $\mu$, $b_u$, $b_i$ are the global mean and the user and item biases; $\lambda$ is a regularization strength.

The user–item matrix#

Everything a collaborative recommender knows sits in one matrix: a row per user, a column per item, an entry wherever the user left feedback. Three properties of that matrix shape every method below.

• It is almost empty. The Netflix Prize data held more than 100 million ratings by about 500,000 customers of more than 17,000 films (Koren, Bell and Volinsky, 2009): about 1% of the cells. The synthetic data of the Code section, 18,872 ratings of 400 items by 600 users, fill 7.9%.
• It is skewed. A few items collect most of the feedback and most items have little; in the synthetic data the 10% most popular items hold 53% of all ratings. Any average over ratings is dominated by the popular head.
• Its gaps are not random. A user rates the films they chose to watch, and they chose those because they expected to like them. So a missing entry is not a neutral unknown, but it is not a low rating either: whether a cell is empty depends on exposure, availability and the user’s choice, and absence alone does not show a low preference. Some models treat missing entries as weak negatives by convention, as in the section on implicit feedback below.

Explicit feedback, such as stars or thumbs, says how much a user liked an item, positive or negative, and is scarce. Implicit feedback, such as plays, purchases, clicks and watch time, is plentiful but has no negatives: not having watched a film may mean disliking it or never having heard of it. The first half of the note works with ratings, the second with implicit feedback.

The goal is rarely the rating itself. A product shows a user a short list, so the task is to rank the items the user has not seen, the problem of the previous note with users in place of queries. Predicting ratings is a means to that end, and evaluation must measure the list.

Content-based filtering#

The first approach does not need the matrix’s other users at all. Describe each item by features, a genre vector, the embedding of its description, the artists of a song, and fit for each user a model of their ratings as a function of those features. With a linear model this is one ridge regression per user:

$$\hat r_{ui} = w_u^\top \phi_i , \qquad w_u = \arg\min_w \sum_{i:\,(u, i) \in \Omega} (r_{ui} - w^\top \phi_i)^2 + \lambda \lVert w \rVert^2 ,$$

where $\phi_i$ is the feature vector of item $i$. Content-based filtering recommends a new item on the day it appears, as long as it has features, and it can explain itself (“because you liked other jazz records”). Its limits are those of the features. It cannot learn that people who like one particular director also like a particular composer if no feature records it, and it recommends more of the same: a user is only ever shown items close to what they already rated. Good features also have to be collected or engineered, which is expensive or impossible for many catalogues (Koren, Bell and Volinsky, 2009).

Collaborative filtering with neighbours#

Collaborative filtering uses no item features. It infers what a user will like from what similar users liked, or from how the user rated similar items, where similarity itself is computed from the matrix. The oldest methods do this with nearest neighbours.

User-based. Measure the similarity $w_{uv}$ of two users by the correlation of their ratings on the items both rated, find the users most similar to $u$ who rated item $i$, and average their ratings, each centred by its user’s mean so that a harsh critic and a generous one can be compared:

$$\hat r_{ui} = \bar r_u + \frac{\sum_v w_{uv} (r_{vi} - \bar r_v)}{\sum_v \lvert w_{uv} \rvert} .$$

Item-based. Turn it around: compute similarities between items from the users who rated both, and predict $u$‘s rating of $i$ from $u$‘s own ratings of the items most similar to $i$ (Sarwar et al., 2001). With the adjusted cosine similarity, each rating is first centred by its user’s mean, and

$$\hat r_{ui} = \bar r_u + \frac{\sum_j s_{ij} (r_{uj} - \bar r_u)}{\sum_j \lvert s_{ij} \rvert} ,$$

the sum running over items $j$ that $u$ rated. Item similarities change slowly and can be computed offline, a user’s history is short, and the recommendation comes with a reason (“because you watched…”). Amazon’s item-to-item recommender was built this way (Linden, Smith and York, 2003).

Worked example. Five users rated five films (· = not rated):

	film 1	film 2	film 3	film 4	film 5	mean
Ann	5	4	·	1	·	3.333
Ben	4	5	1	·	2	3
Cat	·	4	2	1	1	2
Dan	1	·	5	4	·	3.333
Eve	2	1	4	·	5	3

How will Ann rate film 3? Ben, Dan and Eve rated both films 3 and 1. Centred by their means, their ratings of film 3 are $(-2, 1.667, 1)$ and of film 1 $(1, -2.333, -1)$, so

$$s_{31} = \frac{-2 - 3.889 - 1}{\sqrt{7.778}\,\sqrt{7.444}} = \frac{-6.889}{7.609} = -0.905 .$$

The same computation gives $s_{32} = -0.775$ (from Ben, Cat and Eve) and $s_{34} = +0.555$ (from Cat and Dan). Ann’s centred ratings of films 1, 2 and 4 are $1.667$, $0.667$ and $-2.333$, so

$$\hat r_{\text{Ann},3} = 3.333 + \frac{-0.905 \cdot 1.667 - 0.775 \cdot 0.667 + 0.555 \cdot (-2.333)}{0.905 + 0.775 + 0.555} = 3.333 - 1.486 = 1.85 .$$

Ann likes the two films that film 3’s fans dislike and dislikes the one they like, and the prediction is low.

Neighbourhood methods are simple and transparent, and they struggle where the matrix is sparsest. Two users who share two rated items have a correlation of exactly $\pm 1$, and the similarities of rare items rest on a handful of people. Each similarity is estimated separately, so nothing ties them into a consistent picture of taste; and the choices of similarity, neighbourhood size and normalization are heuristics without an objective to optimize.

Matrix factorization#

A latent factor model explains every rating by a few hidden properties of the user and of the item. Each user gets a vector $p_u \in \mathbb R^d$ and each item a vector $q_i \in \mathbb R^d$, and the interaction of user and item is their dot product. One coordinate might come to measure how much a film is a comedy and how much a user likes comedies; nothing forces the coordinates to be interpretable, but $d$ of 20 to 100 is enough to describe much of the taste in a large catalogue (Koren, Bell and Volinsky, 2009). Before the interaction, a large part of every rating is explained by who rates and what is rated: some users rate everything high, some films are rated high by everyone. Those effects get their own parameters, the biases:

$$\hat r_{ui} = \mu + b_u + b_i + p_u^\top q_i$$

(Koren, Bell and Volinsky, 2009, Eq. 4). Toy example of the biases: with an average rating $\mu = 3.6$, a film rated $0.4$ above average and a user who rates $0.5$ below average, the baseline prediction is $3.6 + 0.4 - 0.5 = 3.5$, and the dot product adds or subtracts whatever this user’s taste says about this film.

The model is fitted to the known ratings only, with an $\ell_2$ penalty on every parameter each time it appears in a rating:

$$\min_{P, Q, b} \sum_{(u, i) \in \Omega} \Big[ (r_{ui} - \mu - b_u - b_i - p_u^\top q_i)^2 + \lambda \big( \lVert p_u \rVert^2 + \lVert q_i \rVert^2 + b_u^2 + b_i^2 \big) \Big]$$

(Eq. 5). Without biases, without the penalty and with every entry known, the problem is the best rank-$d$ approximation of a matrix, which the truncated SVD solves exactly; the penalty keeps the same singular vectors and shrinks the singular values toward zero. That is the same computation that gives PCA in the dimensionality reduction note. With 99% of the entries missing the SVD is not even defined, and filling the gaps with zeros or means would teach the model those made-up values. The penalty is what keeps the fit to the known entries from overfitting: a user with three ratings could otherwise get a vector that reproduces them exactly and predicts nonsense everywhere else.

Figure

A low-rank matrix recovered from 40% of its cells

The figure shows why the model works when its assumption nearly holds. Its true matrix is the constant 3 plus a rank-2 matrix, clipped to $[1, 5]$ in 35 of the 600 cells, so around that constant it is approximately, not exactly, of rank 2: its singular values are $18.3$ and $12.4$, then $1.8$. A matrix of rank 2 is fixed by $(20 + 30) \cdot 2 = 100$ numbers, fewer once the rescaling and rotation freedom is removed, not by 600, so 247 noisy cells are enough to pin it down, and the factorization fills the remaining 353 with an error close to the noise level. Real rating matrices are not exactly low-rank, but their main directions of taste are few, and that is what the factors capture.

Stochastic gradient descent#

The objective is a sum over known ratings, so it suits stochastic gradient descent: loop over the ratings in random order, compute the error $e_{ui} = r_{ui} - \hat r_{ui}$, and move each parameter of the rating a step $\eta$ against its gradient,

$$\begin{aligned} b_u &\leftarrow b_u + \eta\,(e_{ui} - \lambda b_u), & p_u &\leftarrow p_u + \eta\,(e_{ui}\, q_i - \lambda p_u),\\ b_i &\leftarrow b_i + \eta\,(e_{ui} - \lambda b_i), & q_i &\leftarrow q_i + \eta\,(e_{ui}\, p_u - \lambda q_i) \end{aligned}$$

(the factor 2 of the derivative is absorbed into $\eta$). The four updates are simultaneous: each uses the values from before the step, so $q_i$ moves with the old $p_u$, as in the Code section. Simon Funk’s version of this loop during the Netflix Prize made the method popular (Koren, Bell and Volinsky, 2009). Each step costs $O(d)$, and a pass over the data costs $O(d\,\lvert\Omega\rvert)$.

Alternating least squares#

The objective is not convex: $p_u^\top q_i$ is a product of unknowns, and any rescaling $p_u \to c\,p_u$, $q_i \to q_i / c$, or rotation of all vectors at once, leaves the predictions unchanged. But with all item vectors fixed, the problem for one user is a least squares problem with a ridge penalty, which has a closed-form solution. Ignoring the biases for clarity, with $Q_u$ the matrix whose rows are the vectors of the $n_u$ items $u$ rated and $r_u$ the vector of those ratings (after subtracting $\mu$ and the biases),

$$p_u = \big(Q_u^\top Q_u + \lambda n_u I\big)^{-1} Q_u^\top r_u ,$$

the factor $n_u$ coming from the penalty paid once per rating. Alternating least squares fixes the items and solves every user, then fixes the users and solves every item, and repeats. Each half-step solves its subproblem exactly, so the objective never increases (Koren, Bell and Volinsky, 2009). Biases fit into the same solve as an extra coordinate whose regressor is 1. ALS needs no learning rate, its users (and then its items) are independent problems that run in parallel, and it extends to the dense objective of implicit feedback, where SGD would have to visit every cell.

Worked example. A user rated two items whose vectors are $q_1 = (1, 0)$ and $q_2 = (1, 1)$, with centred ratings 2 and 1. With a penalty of $0.1$ on the solve,

$$Q_u^\top Q_u + 0.1\, I = \begin{pmatrix} 2.1 & 1 \\ 1 & 1.1 \end{pmatrix}, \qquad Q_u^\top r_u = \begin{pmatrix} 3 \\ 1 \end{pmatrix}, \qquad p_u = \begin{pmatrix} 1.756 \\ -0.687 \end{pmatrix},$$

which predicts $1.756$ and $1.069$ for the two items: close to 2 and 1, shrunk slightly by the penalty.

On the synthetic ratings of the Code section, split by time, the global mean predicts with a root mean squared error of 0.969, biases alone with 0.835, and factorization with $d = 3$ with 0.705, by ALS, or 0.702, by mini-batch SGD on the same objective: two optimizers, one answer. With $d = 10$ the error grows to 0.756. The data were generated with three factors, and the extra seven fit noise; $d$ is a capacity to choose by validation, like the degree of a polynomial.

Implicit feedback#

Plays, purchases and clicks change the problem in three ways (Hu, Koren and Volinsky, 2008, §1). There are no negatives, so the missing cells cannot be ignored: a model fitted to the observed cells only would see nothing but positive evidence and predict “likes it” everywhere. The signal is noisy: a show played once may have been on while the viewer slept. And the value of an entry measures confidence, not preference: a favourite film watched once and a series watched weekly are both liked, and the weekly count says only that the evidence is stronger.

Hu, Koren and Volinsky separate the two meanings. The preference is binary, $s_{ui} = 1$ if $r_{ui} > 0$ and 0 otherwise, and the confidence in it grows with the count, $c_{ui} = 1 + \alpha r_{ui}$. The model fits the preferences of all $m \cdot n$ cells, weighted by confidence:

$$\min_{P, Q} \sum_{u, i} c_{ui} \big( s_{ui} - p_u^\top q_i \big)^2 + \lambda \Big( \sum_u \lVert p_u \rVert^2 + \sum_i \lVert q_i \rVert^2 \Big)$$

(§4, Eq. 3). Every unobserved cell says “probably not”, with the minimum confidence 1; every observed cell says “probably yes”, more firmly the more often it happened. In probabilistic terms this is weighted least squares: a Gaussian model of $s_{ui}$ whose variance is $1/c_{ui}$, so that frequent interactions are treated as precise measurements and absent ones as vague.

The sum has $m \cdot n$ terms, billions in practice, which rules out SGD. ALS still works, and costs time linear in the number of observed cells thanks to one identity (§4, Eq. 4). The user solve is $p_u = (Q^\top C^u Q + \lambda I)^{-1} Q^\top C^u s_u$, where $C^u$ is the diagonal matrix of $u$‘s confidences, and

$$Q^\top C^u Q = Q^\top Q + Q^\top (C^u - I)\, Q .$$

$Q^\top Q$ is the same for every user and is computed once per sweep; $C^u - I$ is zero except on the $n_u$ items $u$ interacted with, so the user-specific part costs $O(d^2 n_u)$.

Worked example. A user who played a show 3 times has, with $\alpha = 2$, confidence $c = 1 + 2 \cdot 3 = 7$ in the preference 1: the fit cares about that cell as much as about seven unplayed shows. With $\alpha = 40$, the value Hu, Koren and Volinsky found good for their television data (§4), the same cell weighs as much as 121 unplayed ones.

The confidence scale is a hyperparameter that interacts with $\lambda$. In the simulation of the Code section the same 600 users play the items they like several times each and random items once, and one liked item per user is held out. Recommending the most popular unplayed items puts the held-out item in the top 10 for 19.8% of users. Implicit ALS with $\lambda$ chosen on a separate validation item reaches 32.7% with $\alpha = 0$, where every cell, played or not, weighs the same, 34.8% with $\alpha = 2$, and 28.5% with $\alpha = 40$, which trusts the counts too much for these data.

Pairwise alternatives. Instead of regressing all cells, one can train on pairs: for user $u$, an item $i$ they interacted with should be ranked above an item $j$ they did not. Bayesian personalized ranking (Rendle et al., 2009, §4.1) maximizes $\sum \log \sigma(\hat r_{ui} - \hat r_{uj})$ over all triples $(u, i, j)$ with $i$ observed and $j$ unobserved for $u$, with a Gaussian prior on the parameters. The triples are far too many to visit in turn, so the sum is optimized by stochastic gradient ascent on triples sampled at random (§4.2). Maximizing it minimizes the RankNet loss of the previous note plus a penalty, with a user in place of a query and unobserved items as the less relevant documents. Its per-user objective is a smooth version of the AUC over (observed, unobserved) pairs (§4.1.1).

Evaluating recommendations#

A recommender is easy to evaluate wrongly, and the errors all make it look better than it is.

Split by time. A random split of the ratings lets the model train on ratings made after the ones it is tested on: it learns which items will become popular and what each user will come to like, information it will not have when deployed. The honest split mirrors deployment: train on everything before a cutoff, test on what happened after. Hu, Koren and Volinsky trained on four weeks of viewing and tested on the following week (§6). In the synthetic data of the Code section, where item popularity drifts over time, the rank-3 model scores 0.670 on a random split and 0.705 on a time split; the random split overstates its accuracy, and it does so for every model. This is the time split of the validation note, and the leakage of the data and leakage note in one of its most common forms.

Measure the list. The root mean squared error of predicted ratings was the Netflix Prize metric, but users see a top-$k$ list. The metrics of the previous note apply per user: precision and recall at $k$ over the held-out items, hit rate (is at least one held-out item in the top $k$), MAP, NDCG. Already-seen items are removed from the candidates. Recommended items the user did not interact with in the test period are not known to be irrelevant, so precision underestimates the truth; with implicit data, recall-type metrics are the safer choice (Hu, Koren and Volinsky, 2008, §6).

Beat popularity. Recommending the most popular items is a strong baseline, especially for metrics averaged over interactions, which are dominated by popular items. A model that does not beat it by a clear margin has learned nothing personal.

Beyond accuracy. A list can be accurate and useless: ten nearly identical items, or only bestsellers a user would have found anyway. Coverage (the share of the catalogue that is ever recommended), diversity within a list, and novelty (how unknown the recommended items are to the user) are measured alongside accuracy (Shani and Gunawardana, 2011). Whether recommendations change behaviour, rather than predict what users would have done anyway, only an online experiment can tell: an A/B test on watch time, purchases or retention.

Cold start#

A new user has an empty row and a new item an empty column; collaborative filtering has nothing to work with. The remedies all bring in information from outside the matrix. Before any feedback, show popular or hand-picked items, or ask a new user to pick a few favourites. Use content features for new items and context (device, country, time) for new users, either through a separate content-based model or inside the factorization: Koren, Bell and Volinsky (2009, Eq. 6) add to the user vector the factor vectors of the items the user interacted with implicitly, summed and divided by the square root of their number, and the sum of the factor vectors of the user’s known attributes, so that a user with no ratings still gets a vector. In the ALS of the Code section, users with no training ratings before the cutoff get $p_u = 0$ and $b_u = 0$ and fall back to $\mu + b_i$, the item’s average rating corrected for the users who rated it.

Two-tower retrieval#

Matrix factorization can be read as two lookups and a dot product: the user’s id selects a row of $P$, the item’s id a row of $Q$, and the score is $p_u^\top q_i$. Two-tower models replace the lookups by neural networks. A user tower maps everything known about the user, their history, their context, their features, to a vector $u(x)$; an item tower maps the item’s id and content features to $v(y)$; the score is $\langle u(x), v(y)\rangle$ (Yi et al., 2019, §3). Because the item tower reads content, a new item gets a vector from its features alone, which addresses item cold start.

Training treats recommendation as classification over the catalogue: given the user, which item did they choose? The probability of item $y$ is a softmax over all items, approximated, since the catalogue has millions of items, by a softmax over the items of the mini-batch, the chosen item included, with the other items of the batch as negatives (Eqs. 1–3). Popular items appear in batches more often and would be penalized as negatives too often, so each logit is corrected by subtracting $\log p_j$, the log-probability that item $j$ is sampled into a batch, before the softmax (§3). At serving time the item vectors are precomputed and an approximate nearest-neighbour search in the dot-product space returns the few hundred best candidates out of millions in milliseconds (Covington, Adams and Sargin, 2016, §3). A feature-rich ranker, the learned rankers of the previous note, then orders those candidates. This is the cascade of retrieval and reranking once more, and the same architecture is the bi-encoder of the semantic search note, trained with the same in-batch softmax.

The factorization view reaches further. Word embeddings are factors of a word–context matrix: skip-gram with negative sampling implicitly factorizes the matrix of shifted pointwise mutual information, a weighted factorization in which frequent pairs count more (Levy and Goldberg, 2014, §3.1–3.2), and GloVe fits dot products plus two biases to log co-occurrence counts by weighted least squares, the explicit-feedback model above with words in place of users and items. The Word2Vec note and the GloVe note develop both.

What changed#

	Learning to rank	Recommender systems
Query	a text with features	a user, often known only by their history
Item description	query–document features	optional; collaborative filtering uses none
Signal	graded labels or clicks per (query, document)	a sparse user–item matrix: ratings or implicit counts
Model	a scoring function of features	neighbours in the matrix; low-rank factors $\mu + b_u + b_i + p_u^\top q_i$; two towers
Fitting	pointwise, pairwise or listwise losses	regularized least squares by ALS or SGD; confidence-weighted over all cells for implicit data
New items	scored by their features at once	cold start: need content features or a fallback
Evaluation	split by query	split by time; ranking metrics against a popularity baseline

Limitations#

• Feedback loops. A recommender learns from interactions with items it chose to show, so it reinforces its own past choices and popular items get more popular. Correcting for exposure needs the propensity ideas of the previous note or randomized exploration.
• Low rank is an approximation. Taste has a long tail of idiosyncrasies that a few factors cannot hold; production systems combine factorization with neighbours, features and boosted rankers.
• Ratings are not goals. A model that predicts stars or clicks optimizes those, which can diverge from what users value: clickbait gets clicks. Choosing the target is part of the design.
• Cold start and sparsity remain. New users and items, and the long tail of rare items, are exactly where collaborative signals are weakest.
• Offline metrics are proxies. Accuracy on held-out history measures how well a model predicts what users did under the old system, not how they will respond to the new one; only online experiments answer that.

What you should remember#

• The user–item matrix is sparse, skewed toward popular items, and missing not at random; the product needs a ranked list of unseen items.
• Content-based filtering regresses each user’s ratings on item features; collaborative filtering uses only the matrix, through neighbours (user- or item-based, with centred similarities) or latent factors.
• Matrix factorization: $\hat r_{ui} = \mu + b_u + b_i + p_u^\top q_i$, fitted to the known entries with an $\ell_2$ penalty, which is MAP under Gaussian noise and Gaussian priors.
• SGD updates the parameters of one rating at a time; ALS alternates closed-form ridge regressions for users and items, never increases the objective, and parallelizes.
• Implicit feedback: binary preference $s_{ui}$, confidence $c_{ui} = 1 + \alpha r_{ui}$, a weighted fit of all cells; ALS stays linear in the observed cells through $Q^\top C^u Q = Q^\top Q + Q^\top(C^u - I)Q$.
• Evaluate with a time split, ranking metrics and a popularity baseline; handle cold start with content, context or popularity.
• Two-tower models generalize factorization to features, are trained with an in-batch softmax, and retrieve candidates for a ranker by nearest-neighbour search.

Code#

Item-based neighbours and an ALS step on toy numbers, matrix factorization on synthetic ratings under a random and a time split, and implicit ALS on synthetic plays:

import numpy as np

# item-based neighbours on a toy matrix: five users, five films, nan = not rated
R = np.array([[5, 4, np.nan, 1, np.nan], [4, 5, 1, np.nan, 2], [np.nan, 4, 2, 1, 1],
              [1, np.nan, 5, 4, np.nan], [2, 1, 4, np.nan, 5]])
seen = ~np.isnan(R)
C = np.where(seen, R - np.nanmean(R, 1, keepdims=True), 0)            # centre each user's ratings
def sim(i, j):                                                         # adjusted cosine over the users who rated both
    both = seen[:, i] & seen[:, j]
    a, b = C[both, i], C[both, j]
    return a @ b / np.sqrt((a @ a) * (b @ b))
s = np.array([sim(2, j) for j in (0, 1, 3)])
print(s.round(3), (np.nanmean(R[0]) + s @ C[0, [0, 1, 3]] / np.abs(s).sum()).round(2))   # [-0.905 -0.775  0.555] 1.85

# one ALS step for one user: a ridge regression on the vectors of the items they rated
Qu, ru = np.array([[1.0, 0.0], [1.0, 1.0]]), np.array([2.0, 1.0])
pu = np.linalg.solve(Qu.T @ Qu + 0.1 * np.eye(2), Qu.T @ ru)
print(pu.round(3), (Qu @ pu).round(3))                                 # [ 1.756 -0.687] [1.756 1.069]

# synthetic ratings: biases + a rank-3 taste model + noise; item popularity drifts over time
rng = np.random.default_rng(0)
m, n = 600, 400
P0, Q0 = rng.normal(0, 0.6, (m, 3)), rng.normal(0, 0.6, (n, 3))
bu0, bi0, drift = rng.normal(0, 0.4, m), rng.normal(0, 0.5, n), rng.normal(0, 0.6, n)
pop = rng.zipf(1.6, n).clip(max=60).astype(float); pop /= pop.sum()    # a long tail of popularity
U = np.concatenate([np.full(k, u) for u, k in enumerate(rng.integers(5, 60, m))])
I = np.concatenate([rng.choice(n, (U == u).sum(), replace=False, p=pop) for u in range(m)])
T = rng.random(len(U))                                                  # the time of each rating, in [0, 1]
r = 3.6 + bu0[U] + bi0[I] + drift[I] * (T - 0.5) + (P0[U] * Q0[I]).sum(1) + rng.normal(0, 0.5, len(U))
r = np.clip(np.round(r), 1, 5)
print(len(r), round(len(r) / (m * n), 3), (np.sort(np.bincount(I, minlength=n))[::-1][:n // 10].sum() / len(r)).round(3))
# 18872 0.079 0.527

def als(u, i, r, d, lam=0.05, iters=10):     # alternate ridge regressions; column 0 of P and Q holds the biases
    mu, P, Q = r.mean(), np.zeros((m, d + 1)), rng.normal(0, 0.1, (n, d + 1))
    for _ in range(iters):
        for A, B, a_idx, b_idx in ((P, Q, u, i), (Q, P, i, u)):
            Z_all = B.copy(); Z_all[:, 0] = 1                           # regressors: 1 for the bias, then the other side's factors
            res = r - mu - B[b_idx, 0]
            order = np.argsort(a_idx); cuts = np.searchsorted(a_idx[order], np.arange(len(A) + 1))
            for a in range(len(A)):
                k = order[cuts[a]:cuts[a + 1]]
                Z = Z_all[b_idx[k]]
                A[a] = np.linalg.solve(Z.T @ Z + lam * max(len(k), 1) * np.eye(d + 1), Z.T @ res[k])
    return lambda uu, ii: mu + P[uu, 0] + Q[ii, 0] + (P[uu, 1:] * Q[ii, 1:]).sum(1)

def sgd(u, i, r, d=3, lam=0.05, lr=0.02, epochs=40, batch=64):       # the same objective, one mini-batch at a time
    mu, bu, bi = r.mean(), np.zeros(m), np.zeros(n)
    P, Q = rng.normal(0, 0.1, (m, d)), rng.normal(0, 0.1, (n, d))
    for _ in range(epochs):
        for k in np.array_split(rng.permutation(len(r)), len(r) // batch):
            e = r[k] - mu - bu[u[k]] - bi[i[k]] - (P[u[k]] * Q[i[k]]).sum(1)
            gP, gQ = e[:, None] * Q[i[k]] - lam * P[u[k]], e[:, None] * P[u[k]] - lam * Q[i[k]]
            np.add.at(bu, u[k], lr * (e - lam * bu[u[k]])); np.add.at(bi, i[k], lr * (e - lam * bi[i[k]]))
            np.add.at(P, u[k], lr * gP); np.add.at(Q, i[k], lr * gQ)
    return lambda uu, ii: mu + bu[uu] + bi[ii] + (P[uu] * Q[ii]).sum(1)

rmse = lambda f, k: np.sqrt(np.mean((f(U[k], I[k]) - r[k]) ** 2)).round(3)
for name, test in (('random split', rng.random(len(r)) < 0.2), ('time split', T > 0.8)):
    tr = ~test
    print(name, np.sqrt(np.mean((r[tr].mean() - r[test]) ** 2)).round(3),       # the global mean
          *[rmse(als(U[tr], I[tr], r[tr], d), test) for d in (0, 3, 10)])     # biases only, rank 3, rank 10
print('SGD, rank 3, time split', rmse(sgd(U[tr], I[tr], r[tr]), test))
# random split 0.966 0.8 0.67 0.732 | time split 0.969 0.835 0.705 0.756 | SGD, rank 3, time split 0.702

# implicit feedback: the same users and items seen through plays. Liked items are played again and again,
# random items once. Two liked items per user are held out: one for validation, one for the test.
taste = np.exp(np.log(pop) + 2 * P0 @ Q0.T); taste /= taste.sum(1, keepdims=True)
plays, held = np.zeros((m, n)), np.zeros((m, 2), int)
for u in range(m):
    liked = rng.choice(n, rng.integers(5, 30), replace=False, p=taste[u])
    plays[u, liked] = 1 + rng.poisson(3, len(liked))
    noise = rng.integers(0, n, rng.integers(5, 30))
    plays[u, noise] = np.maximum(plays[u, noise], 1)
    held[u] = rng.choice(liked, 2, replace=False); plays[u, held[u]] = 0
def hit_rate(S, col):                                                   # is the held-out item among the top 10 unplayed items?
    top = np.argsort(np.where(plays > 0, np.inf, -S), 1)[:, :10]
    return (top == held[:, [col]]).any(1).mean().round(3)
def ials(alpha, lam, d=8, iters=8):                                     # weights 1 + alpha * plays on every cell, zeros included
    s, c = (plays > 0).astype(float), 1 + alpha * plays
    X, Y = rng.normal(0, 0.1, (m, d)), rng.normal(0, 0.1, (n, d))
    for _ in range(iters):
        for A, B, cA, sA in ((X, Y, c, s), (Y, X, c.T, s.T)):
            BtB = B.T @ B                                               # computed once per sweep, shared by all rows
            for a in range(len(A)):
                k = np.flatnonzero(sA[a]); Bk = B[k]
                A[a] = np.linalg.solve(BtB + Bk.T @ ((cA[a, k] - 1)[:, None] * Bk) + lam * np.eye(d), Bk.T @ cA[a, k])
    return X @ Y.T
print('popularity', hit_rate(np.tile((plays > 0).sum(0), (m, 1)).astype(float), 1))   # popularity 0.198
for alpha in (0, 2, 40):
    fits = {lam: ials(alpha, lam) for lam in (10, 50, 200)}
    best = max(fits, key=lambda lam: hit_rate(fits[lam], 0))            # choose lambda on the validation item
    print('alpha', alpha, 'lambda', best, 'validation', hit_rate(fits[best], 0), 'test', hit_rate(fits[best], 1))
# alpha 0 lambda 10 validation 0.347 test 0.327 | alpha 2 lambda 50 validation 0.363 test 0.348
# alpha 40 lambda 200 validation 0.315 test 0.285

The course in one paragraph#

The course began with a promise and a danger: a program can learn a rule from examples, and a rule that fits the examples perfectly can still fail on the next one, so validation came before any model. Each method then answered a limitation of the previous one, until the last sections changed the task. Nearest neighbours lost their meaning in high dimension, and least squares gave global structure, read as the maximum likelihood of Gaussian noise; gradient descent fitted what has no closed form, and regularization stopped the fit from chasing noise, read as a prior. For classes, logistic regression replaced squared error by a Bernoulli likelihood, metrics counted the errors that matter, and margins and kernels bent the boundary. Trees expressed interactions, the bias–variance decomposition explained why averaging and boosting help, and neural networks learned the features themselves through backpropagation. Without labels, clustering, the EM algorithm, dimensionality reduction and anomaly detection found structure, and the last two notes turned scores into orders. Probability ran underneath all of it: many losses are negative log-likelihoods (the hinge loss of the SVM is not), penalties are priors, the target of regression is the conditional expectation, and a validation score is an average: the law of large numbers makes it consistent, the central limit theorem gives its approximately normal error, and concentration inequalities give explicit bounds under their assumptions. The same pieces carry into the next courses: logistic regression on bag-of-words features, softmax and cross-entropy in language models, backpropagation through recurrent networks, embeddings as factorized co-occurrences, and retrieval with reranking in RAG; and in generative modelling, PCA grows into autoencoders, EM into the VAE, kernels into the maximum mean discrepancy of the Kernel Inception Distance, and anomaly scores into energy-based models.

References#

• Y. Koren, R. Bell, C. Volinsky. Matrix Factorization Techniques for Recommender Systems. IEEE Computer, 42(8), 2009. Content and collaborative filtering, the basic model and its objective (Eqs. 1–2), SGD and ALS, biases (Eqs. 3–5), additional inputs for cold start (Eq. 6), confidence weights (Eq. 8), the Netflix Prize.
• Y. Hu, Y. Koren, C. Volinsky. Collaborative Filtering for Implicit Feedback Datasets. ICDM, 2008. Properties of implicit feedback (§1), preference and confidence, the objective (§4, Eq. 3), the ALS update and its speed-up (Eq. 4), evaluation on a following week (§6).
• R. Salakhutdinov, A. Mnih. Probabilistic Matrix Factorization. NeurIPS, 2008. Gaussian likelihood and priors, and the regularized objective (§2, Eqs. 1–4).
• B. Sarwar, G. Karypis, J. Konstan, J. Riedl. Item-Based Collaborative Filtering Recommendation Algorithms. WWW, 2001. Adjusted cosine similarity (§3.1.3), weighted-sum prediction (§3.2.1).
• G. Linden, B. Smith, J. York. Amazon.com Recommendations: Item-to-Item Collaborative Filtering. IEEE Internet Computing, 7(1), 2003.
• S. Rendle, C. Freudenthaler, Z. Gantner, L. Schmidt-Thieme. BPR: Bayesian Personalized Ranking from Implicit Feedback. UAI, 2009. The BPR criterion (§4.1), its relation to AUC (§4.1.1) and its optimization by SGD on sampled triples (§4.2).
• G. Shani, A. Gunawardana. Evaluating Recommendation Systems. In Recommender Systems Handbook, Springer, 2011. Accuracy, coverage, novelty and diversity.
• P. Covington, J. Adams, E. Sargin. Deep Neural Networks for YouTube Recommendations. RecSys, 2016. Candidate generation as extreme multiclass classification, served by nearest-neighbour search (§3).
• X. Yi, J. Yang, L. Hong, D. Z. Cheng, L. Heldt, A. Kumthekar, Z. Zhao, L. Wei, E. Chi. Sampling-Bias-Corrected Neural Modeling for Large Corpus Item Recommendations. RecSys, 2019. The two-tower model, the in-batch softmax and the log-probability correction (§3, Eqs. 1–4).
• O. Levy, Y. Goldberg. Neural Word Embedding as Implicit Matrix Factorization. NeurIPS, 2014. SGNS as factorization of the shifted PMI matrix (§3.1), as weighted matrix factorization (§3.2).
• E. Sokolov et al. Машинное обучение (HSE), lecture notes, lecture 19: recommender systems and lecture 20: recommender systems, evaluation, 2019.