Matrix Factorization · Recommender Systems

01 · Invent the attributes

Latent factors

If we knew each user’s taste and each item’s make-up, a rating would be a dot product.

Suppose we knew, for each user, how much they like each actor, and for each film, how strongly each actor features in it. Then a user’s rating of a film would be the dot product of her taste vector with the film’s actor vector. We don’t have those tables — so MF’s leap is to stop needing them: assume $K$ hidden latent factors (also called embeddings) drive behaviour, and learn them from the URM alone. Each user gets a vector $x_u\in\mathbb{R}^K$ and each item a vector $y_i\in\mathbb{R}^K$ ; the prediction is $\hat r_{ui} = x_u\cdot y_i = \sum_{k=1}^{K} x_{uk}\,y_{ki}$ .

Content-based (Ch. 4)

Item features are given (the ICM: genres, actors). Interpretable, but someone must tag everything.

Matrix factorization (Ch. 8)

Item features are discovered from ratings. No tagging — but the factors are abstract, not labelled “Action” or “Romance.”

key

The factors organise themselves

Nobody tells MF that “action” and “romance” exist — yet after training, the action fans and films land in one region of the latent space and the romance crowd in another (you’ll see it in §8.3). MF rediscovers the catalogue’s taste structure as geometry, purely from who rated what.

02 · R ≈ X · Y

Factorizing the rating matrix

Two skinny matrices, one MSE objective, and a single knob: the number of factors K.

Stack the user vectors into a user–feature matrix $X$ ( $N\times K$ ) and the item vectors into a feature–item matrix $Y$ ( $K\times M$ ). Their product reconstructs the whole rating matrix at once, $\hat R = X\,Y$ , and we choose $X,Y$ to minimise the squared error on the observed ratings — the same MSE objective as SLIM, now over two factor matrices.

Hands-on

R ≈ X·Y · slide the number of factors K

The reconstruction R̂ = X·Y. Each cell is the predicted rating. Raise K and the predictions snap onto the real ratings — but the parameter count grows and large K memorises noise.

Latent factors K2params 28 · RMSE 0.28

TopGunMIInterMartianNottingLoveActAvengLaLaAlice4.64.14.94.30.05.04.11.0Bob4.44.74.13.2-5.71.04.7-4.5Carla4.94.25.24.71.15.94.22.0Dan0.6-0.21.11.35.13.9-0.24.9Eva1.50.82.02.14.14.40.84.3Finn1.50.62.02.14.74.60.64.8

TakeawayMF has only K(N+M) parameters — far fewer than item-CF's M² similarity matrix. At K=1 the model collapses toward Top-Popular; K is tuned on validation (an inverted-U, like K in KNN).

This model has only $NK + KM = K(N+M)$ parameters — for a real catalogue, far fewer than item-based CF’s $M^2$ similarity matrix. The single hyperparameter $K$ (commonly 10–200) controls everything: at $K=1$ the model collapses toward Top-Popular; too large and it overfits and stops scaling.

!

More factors is not more accurate

A large $K$ drives training error toward zero but overfits (and scales badly); a tiny $K$ under-personalises and tilts toward popular items. $K$ is tuned on validation (Ch. 3) — the sweet spot is an inverted-U, exactly like $K$ in KNN.

Formal Definition 8.1 — objective & parameters

MF objective

R \approx X\,Y,\quad X\in\mathbb{R}^{N\times K},\ Y\in\mathbb{R}^{K\times M}, \qquad X,Y = \arg\min_{X,Y} \sum_{(u,i)\in R^{+}} \big(r_{ui}-x_u\cdot y_i\big)^2 + \lambda\lVert X\rVert^2 + \mu\lVert Y\rVert^2.

Parameter count $= NK + KM = K(N+M)$ , controlled by $K$ .

03 · Two coupled gradients

Learning the factors

The error is bilinear in X and Y, so we descend on both, alternately or together.

The objective can’t be solved in closed form — it’s degree-4 in the parameters. So we use gradient descent: sample an observed rating $(u,i)$ , compute the error $e_{ui}=r_{ui}-\hat r_{ui}$ , and nudge both factor vectors. The two gradients are coupled — the update to $x_u$ uses $y_i$ and vice versa — which is the whole reason the problem is non-convex.

Hands-on

Train MF (K=2) · watch the latent space organise

The two gradients are coupled — the update to x_u uses y_i and vice versa — so the problem is non-convex. Slide the iterations and watch the loss fall and the clusters emerge.

Iterations300MSE 0.08

MSE loss over training

2-D latent space (factor 1 × factor 2)

■ action cluster (Alice, Bob, Carla + their films) · ■ romance cluster (Dan, Eva, Finn)

TakeawayALS fixes one matrix and solves the convex least-squares for the other, alternating; SGD steps both at once. Either way, MF rediscovers the catalogue's taste structure as geometry.

Two ways to run this descent. Alternating Least Squares fixes $X$ and solves for $Y$ (now a convex least-squares problem), then fixes $Y$ and solves for $X$ , back and forth. Plain SGD just steps both at once on sampled ratings. Either way, regularization $\lambda,\mu$ keeps the factors from exploding.

Formal Definition 8.2 — gradients & update

For an observed rating $(u,i)$ with error $e_{ui}=r_{ui}-\hat r_{ui}$ :

MF update

\frac{\partial E}{\partial x_{uk}} = -2\,e_{ui}\,y_{ki} + 2\lambda\,x_{uk}, \qquad \frac{\partial E}{\partial y_{ki}} = -2\,e_{ui}\,x_{uk} + 2\mu\,y_{ki},

x_{uk} \leftarrow x_{uk} - \gamma\,\frac{\partial E}{\partial x_{uk}}, \qquad y_{ki} \leftarrow y_{ki} - \gamma\,\frac{\partial E}{\partial y_{ki}}.

Each gradient depends on the other matrix — that coupling is what makes the problem non-convex.

04 · One idea, several models

Funk SVD, SVD++ & Asymmetric SVD

The same factorization, three refinements — and a recurring honesty about missing data.

The classic recipe is Funk SVD (Simon Funk, 2006 — and, the slides insist, it has nothing to do with the Singular Value Decomposition). It minimises the error on the observed ratings only — the missing-as-random assumption.

Hands-on

Funk SVD recommender · scores from learned factors

Unseen items scored by the dot product of the user's taste vector with each item's feature vector. More factors sharpen the personalization.

Latent factors K2

Bob rated: TopGun (4), MI (5), Inter (4), LoveAct (1), Aveng (5)

1Martian3.20

2LaLa-4.53

3Notting-5.73

TakeawayFunk SVD fits only the observed cells (missing-as-random) — great for rating prediction, weaker for Top-N, where the un-rated items are exactly what we must rank. That gap is what BPR attacks.

Two evolutions build on it. SVD++ adds the global effects from Chapter 2 — $\hat r_{ui}=\mu+b_u+b_i+x_u\cdot y_i$ — so the factors model only what’s left after the average, the user’s generosity and the item’s popularity are removed. It was a centrepiece of the Netflix-Prize-winning ensemble, yet never shipped: it optimises MSE under missing-as-random, poor for Top-N. Funk SVD and SVD++ share a flaw: they are not model-based — a brand-new user has no factor row until you retrain. Asymmetric SVD fixes this by defining the user’s factors as a function of the items they interacted with, $x_u=\sum_j r_{uj}\,z_j$ . It’s called “asymmetric” because the product $Z^\top Y$ behaves like a non-symmetric item–item similarity matrix — quietly turning MF back into an item-based model in the spirit of SLIM.

!

Missing-as-random is MF's Achilles' heel

By fitting only the observed cells, Funk SVD / SVD++ never learn that an un-interacted item should probably score low. They’re great at rating prediction but weak at Top-N, where the un-rated items are exactly what we must rank. This is the gap BPR (Ch. 7) and PureSVD (next) attack from opposite directions.

Formal Definition 8.3 — SVD++ & Asymmetric SVD

SVD++ / Asymmetric

\hat r_{ui} = \mu + b_u + b_i + x_u\cdot y_i \quad\text{(SVD++)}, \qquad \hat r_{ui} = \Big(\textstyle\sum_{j} r_{uj}\,z_j\Big)\cdot y_i,\quad Z^\top Y \approx \text{item–item } S \quad\text{(Asymmetric)}.

05 · The one that really is SVD

PureSVD & the unifying view

A truncated SVD of the URM — and the punchline that ties this whole part together.

PureSVD is the one method here that genuinely uses the Singular Value Decomposition, $R = U\Sigma V^\top$ . The trick is to truncate it to the $k$ largest singular values: by the Eckart-Young–Mirsky theorem, the truncated SVD is the best possible rank- $k$ approximation of $R$ under the Frobenius norm. We set $X=U_k$ and $Y=\Sigma_k V_k^\top$ — user and item factors, for free.

Why truncate? A full-rank SVD reconstructs $R$ exactly — missing entries and all — which is useless overfitting, the same trap as SLIM’s $S=I$ . The approximation error of a truncated SVD is what forces the model to generalise. Because the Frobenius norm sums over every cell, PureSVD treats the blanks as zeros — the missing-as-negative assumption, the opposite of Funk SVD.

key

All roads lead to R·S

By “folding in,” PureSVD is equivalent to item-based CF with $S = V_k V_k^\top$ : the prediction is $\hat R = R\,V_k V_k^\top$ . So PureSVD (Ch. 8), Asymmetric SVD (Ch. 8), SLIM (Ch. 6) and neighbourhood item-CF (Ch. 5) are all the same model — $\hat R = R\,S$ — differing only in how they obtain $S$ : a cosine, a regression, or a low-rank projection. Matrix factorization is just another way to learn that $S$ .

Formal Definition 8.4 — PureSVD & folding-in

PureSVD

R \approx U_k\,\Sigma_k\,V_k^\top,\quad X=U_k,\ Y=\Sigma_k V_k^\top, \qquad \hat R = R\,V_k V_k^\top \Longrightarrow S = V_k V_k^\top.

Eckart–Young–Mirsky: the truncation is optimal, with error equal to the next singular value $\lVert R-R_k\rVert_F=\sigma_{k+1}$ .

06 · Exam intel

What the exam tests

Write the MF prediction and objective; count parameters; compute a gradient step; and distinguish Funk SVD (missing-as-random, observed only) from PureSVD (missing-as-negative, real truncated SVD, $S=V_kV_k^\top$ ).

Q

Worked question — predict, step, count

A user factor is $x_u=[0.5,\,1.0]$ and an item factor is $y_i=[2.0,\,0.5]$ . (a) Predict the rating; (b) the true rating is 3 — with pure MSE, one gradient step on $x_{u1}$ at $\gamma=0.1$ ; (c) parameters for $N=6, M=8, K=2$ .

(a) $\hat r_{ui}=0.5\cdot 2.0 + 1.0\cdot 0.5 = 1.5$ .
(b) error $e=3-1.5=1.5$ ; gradient $=-2e\,y_{i1}=-2(1.5)(2.0)=-6$ ; update $x_{u1}\leftarrow 0.5-0.1(-6)=1.1$ (it rises — the prediction was too low and the item loads on feature 1).
(c) $K(N+M)=2(6+8)=28$ parameters.

Traps: thinking Funk SVD is the SVD (a misnomer); saying bigger $K$ is always better (it overfits); forgetting the gradients are coupled, or that $K=1 \approx$ Top-Popular.

07 · Exam · past papers

Past-paper questions

Past paper Practice Exam 1 · MF idea, learning, regularization

Q. The idea behind MF; how parameters are learned with a loss like MSE; how regularization prevents overfitting and its impact.

Model answer. Idea. Approximate the URM by $R \approx P\,Q^\top$ , where $p_u\in\mathbb R^k$ is a user’s latent vector and $q_i\in\mathbb R^k$ an item’s; score $\hat r_{ui}=p_u\cdot q_i$ . Learning. Fit only the observed entries $\Omega$ : $\min_{P,Q}\sum_{(u,i)\in\Omega}(r_{ui}-p_u\cdot q_i)^2 + \lambda(\lVert p_u\rVert^2+\lVert q_i\rVert^2)$ , via SGD or ALS. Regularization. The $\lambda$ term penalises large factor norms (users/items with few ratings would otherwise overfit). It shrinks magnitudes — it does not sparsify the dense factor matrices.

Past paper Practice Exam 4 · Funk SVD vs full SVD, and ALS

Q. Funk SVD’s main idea and how it differs from full SVD; its missing-data assumption; iterative training via ALS.

Model answer. Funk SVD vs full SVD. Full SVD needs a complete matrix and is expensive; on a sparse URM you’d have to impute the blanks (biasing the result). Funk SVD instead learns $P,Q$ directly by gradient descent on the observed ratings only — “SVD-like” but optimisation-based, not an exact decomposition. Missing data. It treats blanks as unknown, not 0: the loss sums only over observed $(u,i)\in\Omega$ , so unrated items exert no pull toward zero. ALS. The objective is bi-convex: with $Q$ fixed, each $p_u$ is a regularised least-squares solve with a closed form; then fix $P$ and solve each $q_i$ . Alternate until convergence; each half-step is exact and parallelises.

08 · Self-check

Three questions before you move on

In matrix factorization, the latent factors are:

A matrix factorization model with N users, M items and K factors has how many parameters?

Which statement about Funk SVD vs PureSVD is correct?

09 · Recap

One-screen summary

Chapter 08 — load-bearing ideas

Factorize: $R\approx X\,Y$ , $\hat r_{ui}=x_u\cdot y_i$ . The $K$ latent features are learned, not given; $K(N+M)$ parameters.
Learn by gradient descent: minimise MSE over observed ratings with coupled gradients (ALS or SGD) + L2 regularization; $K$ is the capacity knob.
A family, one core: Funk SVD (observed only), SVD++ (+global effects), Asymmetric & PureSVD — all reduce to $\hat R=R\,S$ , differing only in how $S$ is found.
Missing-as-random (Funk SVD) vs missing-as-negative (PureSVD); $K=1 \approx$ Top-Popular.