Build a recommender end to end

Recommenders are the largest application of machine learning by revenue, and the first thing worth knowing is how good the trivial approaches are. This section builds one from interaction data: splitting by time so the model cannot learn from the future, establishing a popularity baseline that is harder to beat than it sounds, then matrix factorisation, then measuring with metrics that suit a ranked list of suggestions rather than a single prediction.

Data and split#

MovieLens, a public research dataset of film ratings, is the standard place to start. Treat any rating as an interaction. Split by time: train on everything before a date and test on what each user did after it. A random split lets the model learn from the future.

There are two time splits and they answer different questions. A global cutoff picks one date and puts everything before it in training, which is what production actually looks like: you train on Monday and serve on Tuesday. Leave-one-out holds back each user's single most recent interaction, which gives every user a test case including the ones who joined last week, and is what most papers report. The global split is harder and more honest. Use it, and if you also report leave-one-out, say which is which, because the two differ by a lot and a comparison across them is meaningless.

import numpy as np

rng = np.random.default_rng(0)
n_users, n_items = 400, 150

# A synthetic catalogue with three tastes, so there is real structure to find.
user_taste = rng.integers(0, 3, n_users)
item_taste = rng.integers(0, 3, n_items)
appeal = rng.beta(1.5, 4, n_items)                     # some items are widely liked
prob = 0.5 * (user_taste[:, None] == item_taste[None, :]) * appeal[None, :]
took = rng.random((n_users, n_items)) < prob

users, items = np.nonzero(took)
when = rng.random(len(users))                          # stands in for a timestamp
train = when < 0.8                                     # the cutoff date

R = np.zeros((n_users, n_items))
R[users[train], items[train]] = 1.0                    # what the model may see
future = [set() for _ in range(n_users)]
for u, i in zip(users[~train], items[~train]):
    future[u].add(i)                                   # what it must predict

print(int(took.sum()), "interactions,", int(train.sum()), "in training")
# 2887 interactions, 2356 in training

Popularity#

def recall_at_10(score_matrix):
    """One row of scores per user. Of everything a user took after the
    cutoff, what fraction did we put in their top ten?"""
    hits, users_scored = 0.0, 0
    for u in range(n_users):
        if not future[u]:
            continue
        s = score_matrix[u].copy()
        s[R[u] > 0] = -np.inf              # exclude what they already took
        top = np.argsort(-s)[:10]
        hits += len(set(top) & future[u]) / len(future[u])
        users_scored += 1
    return hits / users_scored

popularity = np.tile(R.sum(axis=0), (n_users, 1))   # same row for everyone
print("popularity     ", round(recall_at_10(popularity), 3))
print("random         ", round(recall_at_10(rng.random((n_users, n_items))), 3))

# popularity      0.173
# random          0.069

Recommending the most popular unseen items is embarrassingly strong. Every model must be compared with it, and many published models barely beat it once it is tuned. Tuned means at least three things: exclude what the user has already taken, restrict popularity to a recent window so last year's hit does not dominate forever, and condition it on whatever segment you cheaply know, such as country. Each of those is a line of code and each moves the baseline enough to sink a model that was about to be declared a success.

Matrix factorisation#

import torch, torch.nn as nn

class MF(nn.Module):
    def __init__(self, n_users, n_items, d=64):
        super().__init__()
        self.u = nn.Embedding(n_users, d)
        self.i = nn.Embedding(n_items, d)

    def forward(self, users, items):
        return (self.u(users) * self.i(items)).sum(-1)     # a score per pair

# Train with observed pairs as positives and random unobserved items as negatives,
# using a binary cross-entropy or pairwise ranking loss.

Each user and item gets a vector; the dot product scores how well they match. Items a user interacted with get pulled towards that user's vector. Negative sampling is needed because unobserved does not mean disliked, but you have to show the model something it should rank lower.

How you draw those negatives changes the model more than most hyperparameters do, and there are three choices with different consequences. Uniform sampling over the catalogue is easy and produces negatives that are trivially easy, because a random item from two million is obviously irrelevant and the model learns nothing from ranking it last. Sampling in proportion to popularity gives harder negatives, since a popular item the user did not take is genuine evidence of a preference, and it also corrects the bias that makes popular items score highly simply for appearing often. Sampling from the items that were actually shown and not clicked is the best signal available, and it needs impression logging that most systems only add after someone asks for it.

import numpy as np

def sample_negatives(rng, taken, n_items, k, popularity=None, alpha=0.75):
    """Draw k items the user did not take. alpha=0 is uniform, 1 is fully
    popularity-proportional; 0.75 is the usual compromise."""
    if popularity is None:
        weights = np.ones(n_items)
    else:
        weights = np.power(popularity, alpha)
    weights = weights.copy()
    weights[list(taken)] = 0.0                 # never sample a true positive
    weights /= weights.sum()
    return rng.choice(n_items, size=k, replace=False, p=weights)

rng = np.random.default_rng(0)
popularity = np.array([500.0, 300, 50, 20, 5, 2])
print(sorted(int(i) for i in sample_negatives(rng, {0}, 6, 3, popularity)))
print(sorted(int(i) for i in sample_negatives(rng, {0}, 6, 3)))

# [1, 2, 3]   popularity-weighted: it drew the two next-most-popular items
# [2, 4, 5]   uniform: it drew from the tail, where the model learns least

The simplest factorisation needs no training loop at all. A truncated singular value decomposition of the interaction matrix gives exactly the same thing — a vector per user, a vector per item, scores as their dot product — in one call, which makes it the right way to see the idea working before adding machinery.

U, sv, Vt = np.linalg.svd(R, full_matrices=False)

for k in (4, 8, 16, 32):
    mf = (U[:, :k] * sv[:k]) @ Vt[:k]                  # rank-k reconstruction
    print("factors", k, " ", round(recall_at_10(mf), 3))

# factors 4    0.432
# factors 8    0.365
# factors 16   0.381
# factors 32   0.339

That last line is the reason plain SVD is a teaching tool rather than the production answer. It treats every unobserved cell as a confident zero, so it spends capacity explaining absences. The implicit-feedback methods that replace it — alternating least squares with confidence weights, or the pairwise BPR loss — all encode the same correction: an observed interaction is evidence, an unobserved one is weak evidence at best, and they must not be weighted the same.

Measure ranking#

import numpy as np

def recall_at_k(recs, relevant, k=10):
    return len(set(recs[:k]) & relevant) / min(k, len(relevant))

def ndcg_at_k(recs, relevant, k=10):
    dcg = sum(1 / np.log2(i + 2) for i, r in enumerate(recs[:k]) if r in relevant)
    ideal = sum(1 / np.log2(i + 2) for i in range(min(k, len(relevant))))
    return dcg / ideal

Report the average by segment as well as overall, because the overall number is dominated by heavy users who have the most interactions and are the easiest to predict. The segment that decides whether the system is any good is users with fewer than twenty interactions, and it is routinely twice as bad as the headline while nobody looks.

                       recall@10   share of users
all users              0.43        100%
20+ interactions       0.58         31%
5 to 19 interactions   0.34         44%
under 5 interactions   0.11         25%

Two towers#

Matrix factorisation is a two-tower model with the simplest possible towers: a lookup table. Replace each lookup with a network that takes user features and item features, and new items with no history can still be embedded from their features. That is how large systems do retrieval over millions of items, with approximate nearest neighbour search over item vectors.