Collaborative filtering

Problem

A shop, a music app or a film site has millions of users and items and a log of who interacted with what: star ratings, plays, purchases, clicks. Arrange it as a matrix R with one row per user and one column per item. Nearly every cell is empty, because each user has touched a tiny fraction of the catalogue. The job is to fill in the empty cells well enough to rank, for each user, the items they haven't seen.

We often know nothing about the items' content, or don't trust it, and we have no labelled features about users. Collaborative filtering (CF) uses only the matrix: if two users rated the same items the same way, each is a good guide to what the other will like. The example used throughout this page is 5 users and 5 films, 20 of 25 cells known, plus two ratings we hide and try to predict:

The two cells marked ? are held out: their true ratings (in brackets) are hidden from every method below. Two tastes are visible by eye: Ana, Ben and Eli like the first three films, Cai and Dee like the last two.

Intuition

There are two families of CF, and they make the same bet in different ways:

• Neighbourhood methods keep the matrix as it is. To predict Ben's rating of Caper, find the users most similar to Ben (by how they rated the films both have seen) and average what they gave Caper. Item-based neighbourhoods do the same over columns: films that were rated alike are recommended alike.
• Latent factor models (matrix factorization) assume the matrix is close to low rank: a few hidden dimensions, such as "likes heists" and "likes horror", explain most of the ratings. Each user gets a short vector p_u, each item a vector q_i, and the predicted rating is their dot product. These vectors are embeddings learned from nothing but the matrix.

The crucial detail in both is that empty cells are unknown, not zero. A user who hasn't rated a film hasn't said they hate it. Fitting the factors only on observed cells is what lets the model predict the rest.

Mechanics

Neighbourhoods

Users rate on different scales: one person's 3 is another's 4. So centre each user's ratings on their own mean r̄_u first, then measure similarity with the cosine of the centred vectors over the items both rated (this is Pearson correlation restricted to co-rated items):

s(u, v) = Σ_{i ∈ Iuv} (r_ui − r̄_u)(r_vi − r̄_v) / ( ‖r_u − r̄_u‖ · ‖r_v − r̄_v‖ )

The prediction starts from the user's own mean and adds the similarity-weighted deviations of the k most similar users who rated the item:

r̂_ui = r̄_u + Σ_{v ∈ Nk(u, i)} s(u, v)(r_vi − r̄_v) / Σ_v |s(u, v)|

This needs no training, explains itself ("because Ana and Eli liked it"), and updates the moment a new rating arrives. It costs a similarity per pair of users, which is why large systems use item-item neighbourhoods (items are fewer and their similarities change slowly) and precompute them.

Matrix factorization and its loss

Give each user a vector p_u ∈ ℝ^k and each item q_i ∈ ℝ^k. With Ω the set of observed (user, item) pairs, minimize

L = Σ_{(u,i) ∈ Ω} (r_ui − μ − b_u − b_i − p_u · q_i)² + λ (‖p_u‖² + ‖q_i‖² + b_u² + b_i²)

μ is the global mean, b_u and b_i are a user's and an item's offsets from it (a generous rater, a beloved film), and the dot product carries the interaction: how this user feels about this item beyond those offsets. The L2 term λ is not optional. There are (users + items) · k parameters, often as many as there are ratings, so without it the factors simply memorize Ω.

Two ways to minimize it:

• SGD. For each observed rating, compute the error e = r − r̂ and step p_u += η(e q_i − λp_u), q_i += η(e p_u − λq_i). Simple, and what a PyTorch model with an embedding table does.
• Alternating least squares (ALS). The loss is not convex in (P, Q) together, but with Q fixed it is an independent ridge regression for every user: p_u = (Q_u^TQ_u + λI)⁻¹ Q_u^T r_u, where Q_u holds only the items user u rated. Then fix P and solve every item the same way. Each half-step can only lower L, the solves are embarrassingly parallel, and there is no learning rate.

Implicit feedback

Most real signals are not ratings but events: plays, views, purchases. There are no negatives, only "did" and "didn't (yet)". Hu, Koren and Volinsky turn each count r_ui into a binary preference p_ui = [r_ui > 0] and a confidence c_ui = 1 + α r_ui, then fit over all cells:

L = Σ_{u, i} c_ui (p_ui − x_u · y_i)² + λ (Σ‖x_u‖² + Σ‖y_i‖²)

Here zeros are in the loss, deliberately, but with confidence 1, while anything the user actually did weighs 1 + α times its count. Summing over every cell looks impossible at scale; the trick is that Y^TC_uY = Y^TY + Y^T(C_u − I)Y, where Y^TY is shared by all users and C_u − I is non-zero only on the items user u touched. Each ALS solve still costs only that user's interactions.

Cold start

A new user or a new item has no row or column to learn from, so neither family can say anything personal about it. The usual fallbacks: show new users popular or highly rated items (μ + b_i), ask a few onboarding questions, or switch to content features (genre, text, image embeddings) that exist from day one. Hybrid models, such as two-tower models with ID and content features in each tower, blend the two as interactions accumulate.

Non-negative matrix factorization

NMF factors a non-negative matrix X ≈ WH with W, H ≥ 0, which makes the factors additive parts (topics, tastes) that are easy to read. scikit-learn's NMF minimizes 0.5‖X − WH‖²_Fro plus L1/L2 penalties scaled by the matrix's dimensions. Its multiplicative update for the Frobenius loss is H ← H ⊙ (W^TX) / (W^TWH), and the mirror image for W. Each factor stays non-negative because it is only ever multiplied by a non-negative ratio.

The catch for recommendation: X is a whole matrix, sparse or dense, and every cell is in the loss. An unrated film is a stored or implicit zero, so NMF treats "hasn't seen it" as "rated it 0" and drags those predictions toward zero. That is fine for counts where absence really means zero, such as word counts in documents, and wrong for explicit ratings.

Worked example

User similarities

Centred cosine between every pair of users, over the films both rated:

The two taste groups fall out: similarities are positive within Ana, Ben, Eli and within Cai, Dee, and negative across. Cai and Eli come out at exactly -1.00: their co-rated films' centred ratings are mirror images.

Five ways to fill the two cells

The global mean is μ = 2.90. The bias baseline adds Ben's offset -0.15 and Caper's +0.10. The neighbourhood prediction uses k = 2 as in the diagram; for Dee only Cai is both similar and has rated Heist. Matrix factorization is rank 2 by ALS with λ = 0.1 on the 20 observed cells. NMF is rank 2, 300 multiplicative updates, on the matrix with blanks filled by 0.

The bias baseline is worse than the global mean here: Dee rates generously and Heist is popular, so biases alone predict a high rating for a user who dislikes heist films. Offsets can't see interaction; that is what the dot product is for. Both CF methods find the taste groups. NMF finds them too but has been told that Ben rated Caper 0, so its prediction of 2.57 is dragged far below the truth; its fit on the 20 real ratings (RMSE 0.87) is also worse than ALS's, because it spends capacity reproducing the fake zeros.

ALS, sweep by sweep

The objective falls at every sweep, because each half-step solves its ridge problems exactly. The RMSE on observed ratings levels off near 0.29 while the objective keeps creeping down: the later sweeps shrink the vectors' norms without changing the fit. The model has 20 factor numbers for 20 ratings, so with λ = 0 it could fit them almost perfectly and generalize badly.

One concrete solve: Ana rated 4 films. With the item vectors fixed, Ana's new vector is the 2 × 2 ridge solution over those four rows of Q, (2.60, 0.86).

Implicit confidence and scale

With α = 40 (the value Hu, Koren and Volinsky found worked), a film played once counts 41 times as much as an unplayed one. At production scale, 1,000,000 users and 100,000 items give 100,000,000,000 cells. Rank-64 factors are 70,400,000 numbers, about 282 MB in float32: the model is 1,420 times smaller than the matrix it predicts. For the cold-start user, the popularity order by μ + b_i is Heist, Caper, Sting, Drift, Haunt.

Implementation

Matrix factorization with biases in PyTorch: two nn.Embedding tables trained on (user, item, rating) triples, so only observed cells are ever in the loss. With sparse=True each step's gradient touches only the batch's rows, which needs one of the optimizers the docstring lists, such as SparseAdam:

import torch
from torch import nn

class MF(nn.Module):
    def __init__(self, n_users, n_items, k=64):
        super().__init__()
        self.p = nn.Embedding(n_users, k, sparse=True)
        self.q = nn.Embedding(n_items, k, sparse=True)
        self.bu = nn.Embedding(n_users, 1, sparse=True)
        self.bi = nn.Embedding(n_items, 1, sparse=True)
        for e in (self.p, self.q):
            nn.init.normal_(e.weight, std=0.01)   # default N(0, 1) is far too large
        for e in (self.bu, self.bi):
            nn.init.zeros_(e.weight)
        self.mu = nn.Parameter(torch.zeros(()))

    def forward(self, u, i):
        return (self.mu + self.bu(u).squeeze(-1) + self.bi(i).squeeze(-1)
                + (self.p(u) * self.q(i)).sum(-1))

model = MF(n_users, n_items)
model.mu.data.fill_(ratings.mean())
sparse = [model.p.weight, model.q.weight, model.bu.weight, model.bi.weight]
opt_sparse = torch.optim.SparseAdam(sparse, lr=1e-2)
opt_dense = torch.optim.Adam([model.mu], lr=1e-2)
lam = 1e-4

for u, i, r in loader:                     # observed triples only
    pred = model(u, i)
    reg = lam * (model.p(u).pow(2).sum() + model.q(i).pow(2).sum())
    loss = (pred - r).pow(2).mean() + reg / len(r)
    opt_sparse.zero_grad(); opt_dense.zero_grad()
    loss.backward()
    opt_sparse.step(); opt_dense.step()

The L2 term is applied to the rows in the batch, not via weight_decay, which would shrink every row on every step (and SparseAdam doesn't support it). For implicit data, use an ALS library built on the confidence trick, or train with sampled negatives as in two-tower models.

If you reach for scikit-learn, remember what NMF fits: a scipy.sparse rating matrix is accepted, but its missing entries are zeros in the loss. That suits counts (topics in a document-term matrix) and not explicit ratings.

from sklearn.decomposition import NMF

nmf = NMF(n_components=2, init="nndsvda", solver="mu", max_iter=300)
W = nmf.fit_transform(play_counts)   # [users, k]: zeros here mean "zero plays", which is true
H = nmf.components_                  # [k, items]

Tradeoffs

• Neighbourhoods vs factors. Neighbourhoods are explainable, training-free and instantly fresh, but noisy when users share few items, and quadratic in users or items. Factors generalize across the sparsity (two users need not share a single item to end up close in factor space) and serve as a fast dot product, but must be retrained or folded in for new data.
• ALS vs SGD. ALS has no learning rate, parallelizes per row and handles the all-cells implicit loss exactly. SGD is simpler, fits any differentiable model (side features, deep towers) and streams over huge logs.
• Rank k and λ. Larger k fits more taste dimensions and overfits faster; λ trades the two and must be tuned on held-out ratings, split by time if you can, since the future is what you'll predict.
• RMSE vs ranking. Predicting stars well is not the same as ranking the top 10 well. Many systems train on implicit data and evaluate with ranking metrics, and add a learning-to-rank stage on top.
• Popularity and feedback loops. CF recommends what similar people consumed, which over time amplifies what is already popular and starves new items; cold-start content features and some exploration counter it.
• NMF. Non-negative parts are interpretable, but the default scikit-learn implementation's zeros-are-observed loss makes it a poor fit for explicit ratings.

Connections

References

• Resnick, Iacovou, Suchak, Bergstrom and Riedl. GroupLens: An Open Architecture for Collaborative Filtering of Netnews. CSCW, 1994.
• Sarwar, Karypis, Konstan and Riedl. Item-Based Collaborative Filtering Recommendation Algorithms. WWW, 2001.
• Koren, Bell and Volinsky. Matrix Factorization Techniques for Recommender Systems. IEEE Computer, 2009.
• Hu, Koren and Volinsky. Collaborative Filtering for Implicit Feedback Datasets. ICDM, 2008.
• Lee and Seung. Algorithms for Non-negative Matrix Factorization. NeurIPS, 2000.
• scikit-learn 1.9.1: NMF, multiplicative updates, cosine_similarity.
• PyTorch v2.15.0: nn.Embedding, nn.EmbeddingBag, SparseAdam.