RecSys Part II · Candidate generation · chapter 6 of 19
Matrix factorisation, ALS and fold-in
The same collaborative signal, but the generalisation works in a fundamentally different way: not through direct co-occurrences but through compression into a few coordinates. Because of this, factorisation sees links where neighbours see emptiness — and breaks where neighbours work. We take the mechanism apart with numbers, derive ALS, and separately look at how to give a vector to a user who was not in training.
- Factorisation is a method inside collaborative filtering, not an alternative to it. And «learned» does not mean «factorised»: EASE is trained too, but makes no attempt to decompose anything.
- Generalisation goes through a narrow bottleneck. Items that co-occurred 12 times out of 20 000 get a cosine of 0.04 from neighbours and 0.98 from a rank-2 factorisation.
- Rank is a hypothesis that «any taste is a mixture of \(d\) archetypes». At \(d = 6\) on a 30×40 matrix there are more parameters than observations.
- A new user needs no retraining. Fold-in is the solution of one \(d \times d\) system, that is, the same ridge regression that sits inside ALS.
1. Where factorisation sits among the rest
The terms get confused constantly, so let us place them at once.
We approximate the interaction matrix \(R\) of size \(|U| \times |I|\) by a product of two thin ones:
$$ R \;\approx\; P Q^{\top}, \qquad P \in \mathbb{R}^{|U| \times d},\ \ Q \in \mathbb{R}^{|I| \times d}, \qquad \hat r_{ui} = p_u^{\top} q_i $$Every user and every item is assigned a vector of \(d\) numbers, and the prediction is their inner product. We train only on the observed cells:
$$ \min_{P,Q} \sum_{(u,i) \in \Omega} \bigl(r_{ui} - p_u^{\top}q_i\bigr)^2 \;+\; \lambda\bigl(\lVert P\rVert^2 + \lVert Q\rVert^2\bigr) $$The sum over \(\Omega\) rather than over all pairs is essential: a missing entry is an unknown, not a zero.
A real singular value decomposition requires a complete matrix. Ours has holes, and filling them with zeros is not allowed, for the reason given in the chapter on data.
What has been called SVD since the Netflix Prize is Simon Funk's gradient descent over the observed cells. The name stuck; the method is a different one. Clarifying this distinction in an interview is a cheap way to show that you understand the setup rather than having memorised an acronym.
2. How this differs from neighbours
The main difference is not in the formula but in where the generalisation comes from.
Synthetic data: two items A and C load on the same latent taste, but both are rare, so they hardly ever occur together. B is a frequent item of the same taste, E an item of a different taste.
| sim(A, C) | sim(A, B) | sim(A, E) | |
|---|---|---|---|
| co-occurrence | A and C together — 12 times out of 20 000 | ||
| neighbours, cosine | 0.0396 | 0.1256 | — |
| factorisation, rank 2 | +0.980 | +0.889 | −0.622 |
The numbers are reproduced by the script _tools/mf_demo.py in this repository.
The neighbours consider A and C almost unrelated and put B three times closer to A. Factorisation recovers that A and C are practically duplicates in taste, having twelve co-occurrences to work with.
The mechanism: compression into two coordinates leaves the model no room to store every item separately. To explain the data it has to find shared axes — and on those axes A and C end up next to each other, because they are linked to the same third items.
Take substitute items: their audiences do not overlap at all, not a single joint interaction.
| neighbours | sim(A,C) = 0.000 | «no data» |
| factorisation | sim(A,C) = −1.000 | «opposites» |
These are different statements, and the second is one neighbours cannot express in principle. A zero from kNN means an absence of information; a minus one from factorisation is a substantive conclusion about the relationship.
Hence the practical division: neighbours are good where there is plenty of signal and explainability is needed, factorisation where you have to reach links that direct co-occurrences do not contain.
3. How it is trained
SGD: the derivation in two lines
For a single observation the error is \(e_{ui} = r_{ui} - p_u^{\top}q_i\) and the loss is \(L = e_{ui}^2 + \lambda(\lVert p_u\rVert^2 + \lVert q_i\rVert^2)\). Differentiating:
$$ \frac{\partial L}{\partial p_u} = -2e_{ui}q_i + 2\lambda p_u, \qquad \frac{\partial L}{\partial q_i} = -2e_{ui}p_u + 2\lambda q_i $$The descent step (with the two absorbed into \(\eta\)):
$$ p_u \leftarrow p_u + \eta\,(e_{ui}\,q_i - \lambda\,p_u), \qquad q_i \leftarrow q_i + \eta\,(e_{ui}\,p_u - \lambda\,q_i) $$It reads in plain words: move the user vector towards the item vector in proportion to the error, and symmetrically.
ALS: why production likes it
The problem is not convex in \((P, Q)\) jointly, but it is convex in each matrix separately. Fix \(Q\) — then for a user \(u\) what remains is an ordinary ridge regression. Setting the derivative to zero:
$$ \bigl(Q_u^{\top}Q_u + \lambda I\bigr)\,p_u = Q_u^{\top} r_u \quad\Longrightarrow\quad p_u = \bigl(Q_u^{\top}Q_u + \lambda I\bigr)^{-1} Q_u^{\top} r_u $$where \(Q_u\) are the rows of the items \(u\) interacted with. Then symmetrically fix \(P\) and solve for the items. Repeat.
Three reasons this is convenient in production:
- every \(p_u\) is computed independently of the others — it parallelises perfectly over users;
- there is no learning rate to tune;
- it converges in a dozen iterations rather than dozens of epochs.
Note the size of the system: \(d \times d\), where \(d\) is the rank, usually tens. The matrix being inverted is the size of the rank, not of the catalogue.
Rank is a hypothesis, not a hyperparameter
The word «rank» here is not a metaphor. The product of two matrices of width \(d\) has rank at most \(d\) — a fact of linear algebra. By choosing \(d\) we are literally asserting: any taste is a mixture of \(d\) archetypes.
At \(d = 2\) the hypothesis is strict, at \(d = 50\) it commits to almost nothing. And it has a measurable price.
The number of trainable parameters is \((|U| + |I|)\cdot d\). For a 30×40 matrix filled to 45%, with a third held out for validation — about 378 training observations:
| Rank \(d\) | Parameters | Per observation |
|---|---|---|
| 1 | 70 | 0.19 |
| 2 | 140 | 0.37 |
| 4 | 280 | 0.74 |
| 6 | 420 | 1.11 — more than there is data |
The numbers are reproduced by the script _tools/mf_demo.py.
At \(d = 6\) the model can fit the training data almost exactly while learning nothing. That is overfitting — and it is visible only on the held-out set, because the training error falls all the while.
The two roles of regularisation
In the loss \(\lambda\) is a penalty on the length of the vectors; in the ALS solution it turns into \(\lambda I\) on the diagonal. Usually only the first role gets named.
For a user with a single rating it pays to produce an enormous vector that hits that rating perfectly. The penalty on length makes that unprofitable, the vector stays short — and a short vector gives a prediction close to the average.
That is, \(\lambda\) makes the model say «I do not know» where there is little data, instead of inventing confidently.
The second role is purely computational and gets forgotten. The matrix \(Q_u^{\top}Q_u\) for a user with two or three interactions is singular: its rank is less than \(d\), and no inverse exists.
Adding \(\lambda I\) makes it invertible always. So in ALS regularisation is not an option but a condition of the thing working at all: at \(\lambda = 0\) the solution for a rare user simply does not compute.
- Move the rank and watch both errors. The training error falls monotonically, the held-out one has a minimum — and it sits near the true rank of the data.
- Increase the rank past the minimum: the training error keeps falling, the held-out one grows. That is exactly the «more parameters than observations» arithmetic from the table above.
- Raise \(\lambda\): the minimum over rank shifts to the right. Regularisation lets you keep a larger rank without overfitting — at the cost of using each coordinate more cautiously.
What to say in an interview: «Rank is a hypothesis about the number of latent factors. It is chosen on a held-out set rather than on the training one: the training error falls monotonically and tells you nothing».
4. iALS: what to do when there are no negatives
Everything above assumed \(r_{ui}\) is a rating. In implicit data there is no rating: we see «listened», we do not see «did not like it». And if we learn only from the observed pairs, then all of them are positive, and the trivial solution is to predict one everywhere.
The solution of Hu, Koren and Volinsky: learn from all pairs, but with different weights.
$$ \min_{P,Q}\; \sum_{u,i} c_{ui}\bigl(\mathbb{1}[r_{ui} > 0] - p_u^{\top}q_i\bigr)^2 \;+\; \lambda\bigl(\lVert P\rVert^2 + \lVert Q\rVert^2\bigr), \qquad c_{ui} = 1 + \alpha\, r_{ui} $$Two things that are fused together in explicit feedback are separated here:
- the target — a binary «there is a preference or there is not»;
- the weight \(c_{ui}\) — how confident we are of that: listened a hundred times or once.
Unobserved pairs enter with a weight of 1 — these are soft negatives: the model assumes an absence of interest, but weakly, and a single observation overturns that assumption.
The parameter \(\alpha\) is a hyperparameter, and it is not one: in the original work sensible values are of the order of tens. It sets how many times more an observation weighs than a missing entry.
Naively a sum over \(|U|\times|I|\) is unaffordable. But in the ALS solution it decomposes:
$$ Q^{\top}C_u Q \;=\; Q^{\top}Q \;+\; Q^{\top}(C_u - I)Q $$The first term does not depend on the user and is computed once per iteration. The second is a sum only over the items where \(c_{ui} \ne 1\), that is, over the observed ones, of which there are few.
It is precisely this trick that made iALS practical. Without it, «learn from all pairs» would have remained a theoretical proposal.
5. A new user: fold-in
A user arrives, watches a few things, and the model was trained yesterday. Retraining the whole of ALS for them is not an option. And it is not necessary.
The item vectors \(Q\) are already trained and change slowly. So for a new user it is enough to solve exactly the ALS step responsible for users:
$$ p_{\text{new}} = \bigl(Q_s^{\top}Q_s + \lambda I\bigr)^{-1} Q_s^{\top} r_s $$where \(Q_s\) are the vectors of the items the person has already interacted with. This is a \(d \times d\) system: at rank 8, eight by eight, microseconds.
A check on synthetic data: a catalogue of 300, rank 8, a new user with 25 interactions whose vectors were not in training at all.
The top-25 prediction matches their real interests in 17 cases out of 25 — and that is with the model seeing them for the first time and solving one 8×8 system.
The numbers are reproduced by the script _tools/mf_demo.py.
Hence the practical conclusion: cold start for users is solved cheaply if there is even a little history. Cold start for items is not: a new item has no vector \(q_i\), and without one it takes part in no score at all.
6. Where factorisation hits its limits
| Limitation | What it consists of |
|---|---|
| Cold start for items | a new item is not in \(Q\); the model does not accept content features by construction |
| No context | no time of day, no device, nothing about what the person is doing right now |
| The order of the history is ignored | \(p_u\) is learned from a set of interactions; «yesterday» and «two years ago» are indistinguishable |
| Only one form of interaction | an inner product. Anything not expressible by it the model cannot express |
| Popularity bias in the geometry | the norm \(\lVert q_i\rVert\) grows with popularity and MIPS does not cancel it — see the chapter on biases |
The first three limitations are removed by one and the same move: replace the learned item vector with one computed from features. That is the next big line of the textbook — from matrix factorisation to two-tower models.
Interview questions
How does matrix factorisation differ from collaborative filtering?
They are not alternatives: factorisation is a method inside collaborative filtering. CF splits into neighbour-based approaches (kNN, item-item — similarities computed straight from the matrix) and learned ones, which include factorisation as well as EASE and SLIM. And «learned» and «factorised» are different properties: EASE is trained but does not decompose its matrix.
The substantive difference is in the mechanism of generalisation. Neighbours generalise through direct co-occurrences, factorisation through compression into \(d\) coordinates. So it finds links where there are hardly any co-occurrences: in the example, items that co-occurred 12 times out of 20 000 get a cosine of 0.04 from neighbours and 0.98 from a rank-2 factorisation.
And the converse: for mutually exclusive items neighbours give 0 («no data»), factorisation −1 («opposites»). The second statement is unavailable to neighbours.
Why is «SVD» in recommenders not SVD?
A real singular value decomposition requires a complete matrix. Ours is sparse, and filling the gaps with zeros is not allowed: a gap means «it was not shown», not «it was not liked».
What came to be called SVD after the Netflix Prize is Simon Funk's gradient descent over the observed cells, that is, minimising the error only on known pairs with regularisation. The name stuck; the method is a different one.
Why is ALS preferred to SGD in production?
The problem is not convex in \((P,Q)\) jointly but is convex in each matrix separately. Fixing \(Q\), for each user we get an ordinary ridge regression with the solution \(p_u = (Q_u^\top Q_u + \lambda I)^{-1} Q_u^\top r_u\).
Hence three advantages: every \(p_u\) is computed independently and the task parallelises perfectly; there is no learning rate to tune; convergence takes a dozen iterations. And the system is of size \(d \times d\) — the size of the rank, not of the catalogue.
SGD wins when the matrix is very sparse and online updating is needed, and also when the loss is not quadratic — for BPR or a logistic loss you cannot derive ALS.
What is rank and how do you choose it?
Rank is the number of coordinates in each vector, and it is a substantive hypothesis: «any taste is a mixture of \(d\) archetypes». A product of matrices of width \(d\) has rank at most \(d\), so the choice of \(d\) limits what the model is able to express at all.
The price is measurable: the number of parameters is \((|U| + |I|)\cdot d\). On a 30×40 matrix with 378 training observations, rank 6 gives 420 parameters — more than there is data, and the model will fit the training set while learning nothing.
It is chosen on a held-out set. The training error falls monotonically with rank and suggests nothing; only the held-out error has a minimum.
Why is regularisation needed in ALS — name both roles.
The first, the usual one: shrinkage towards zero. For a user with a single rating it pays to produce an enormous vector that hits it perfectly; the penalty on length makes that unprofitable, and the model says «I do not know» instead of inventing confidently.
The second, the one people forget: conditioning. The matrix \(Q_u^\top Q_u\) for a user with two or three interactions is singular — its rank is less than \(d\) and no inverse exists. Adding \(\lambda I\) makes it invertible always, so at \(\lambda = 0\) the solution for a rare user simply will not compute.
How does iALS work with implicit feedback?
It separates the target from the confidence. The target is binary — «there is a preference» — while the weight \(c_{ui} = 1 + \alpha r_{ui}\) says how confident we are of that: listened a hundred times or once. We learn from all pairs rather than only the observed ones, and the unobserved enter with a weight of 1 — soft negatives that a single observation overturns.
The sum over all pairs does not explode because of the decomposition \(Q^\top C_u Q = Q^\top Q + Q^\top(C_u - I)Q\): the first term does not depend on the user and is computed once per iteration, the second is a sum only over the observed items, of which there are few.
And \(\alpha\) is a genuine hyperparameter, not one: sensible values are of the order of tens.
How do you serve recommendations to a user who was not in training?
Fold-in. The item vectors are already trained and change slowly, so it is enough to solve exactly the ALS step responsible for users: \(p_{\text{new}} = (Q_s^\top Q_s + \lambda I)^{-1} Q_s^\top r_s\), where \(Q_s\) are the vectors of what the person interacted with.
This is a \(d \times d\) system — at rank 8, microseconds, and no retraining. On synthetic data with a catalogue of 300 and 25 interactions the top 25 matches the real interests in 17 cases out of 25.
What matters is that the converse does not work: cold start for items is not treated this way. A new item has no vector and there is nowhere to take one from — that needs content features, that is, a different architecture.
One-screen cheat sheet
The place
MF is a method inside CF. «Learned» ≠ «factorised»: EASE learns but does not decompose.
Generalisation
Through a narrow bottleneck, not through co-occurrences. 12 co-occurrences out of 20 000 → cosine 0.04 from neighbours, 0.98 from MF.
ALS
\(p_u = (Q_u^\top Q_u + \lambda I)^{-1} Q_u^\top r_u\). Parallelises, no learning rate, a dozen iterations.
Rank
A hypothesis about the number of archetypes. Parameters \((|U|+|I|)d\); chosen on a held-out set.
iALS
Binary target, weight \(c = 1 + \alpha r\). Missing entries are soft negatives. \(\alpha\) of the order of tens.
Fold-in
A \(d\times d\) system, no retraining needed. Works for users, does not work for items.
Primary sources
- Y. Koren, R. Bell, C. Volinsky. Matrix Factorization Techniques for Recommender Systems, IEEE Computer 2009 — the canonical summary after the Netflix Prize.
- Y. Hu, Y. Koren, C. Volinsky. Collaborative Filtering for Implicit Feedback Datasets, ICDM 2008 — iALS, confidence instead of a rating, and the decomposition that makes the problem affordable.
- S. Rendle, C. Freudenthaler et al. BPR: Bayesian Personalized Ranking from Implicit Feedback, UAI 2009 — the pairwise alternative to a quadratic loss.
- S. Rendle, W. Krichene et al. Neural Collaborative Filtering vs. Matrix Factorization Revisited, RecSys 2020 — why the inner product is still hard to beat.
- The numbers in this chapter:
_tools/mf_demo.pyin this repository.