11 · Learning factors with SGD (Funk SVD)
SVD-on-imputed-data is biased by the fill value. Funk SVD fixes it: learn P and Q directly on the OBSERVED ratings with SGD, regularized, plus user/item biases.
Don't impute. Learn P and Q by minimizing regularized squared error over the OBSERVED entries only, with SGD: for each known rating, predict p·q, take the error, and nudge p and q in the gradient direction. Add user/item biases for the part of a rating that's just 'this user rates high' or 'this item is loved'.
Without this:
This is the workhorse of explicit-feedback recsys — Simon Funk's blog post that reshaped the Netflix Prize. It scales to hundreds of millions of ratings because each SGD step touches only one user vector and one item vector.
Truncated SVD had a real flaw: it must fill the missing entries first, then treats those invented values as ground truth. With a 99%-sparse matrix, the decomposition mostly fits your imputation, not real ratings.
Funk SVD (Simon Funk, 2006) fixes this with a beautifully simple idea: only ever look at the ratings you actually observed. Define the loss over the observed set K:
L = Σ_(u,i)∈K ( r_ui − p_u·q_i )² + λ ( ‖p_u‖² + ‖q_i‖² )
The second term is L2 regularization — it keeps the factors small so they don't overfit users/items with few ratings. We minimize L with stochastic gradient descent: shuffle the observed ratings, and for each (u,i,r):
err = r − p_u · q_i
p_u += lr · ( err · q_i − λ · p_u )
q_i += lr · ( err · p_u − λ · q_i )
That's it — two vector updates per observed rating. Crucially, the missing cells contribute nothing to the loss, so there's no imputation bias.
Real models add biases: r_ui ≈ μ + b_u + b_i + p_u·q_i. Here μ is the global mean, b_u captures 'Ana rates everything high', and b_i captures 'this movie is universally loved'. The factors then only have to model the interaction — the personalized part left over after the easy averages.
An alternative optimizer is ALS (Alternating Least Squares): fix Q, solve for every P row in closed form (a ridge regression), then fix P and solve for Q, and repeat. ALS parallelizes beautifully and is the default for implicit feedback at scale (Spark's MLlib uses it). SGD is simpler and shines for explicit ratings.
Below we implement Funk SVD from scratch and watch the train RMSE fall epoch by epoch.
Python (in browser)
Funk SVD from scratch: SGD over observed ratings only, with L2 regularization and user/item biases. Watch the train RMSE drop each epoch.
Python runs entirely in your browser via Pyodide (~6 MB on first Run, cached after).
The same model via the Surprise library's SVD (explicit) and a note on implicit ALS (read-along; not executed here).
What is the key advantage of Funk SVD (SGD over observed entries) over running plain SVD on a mean-imputed matrix?
- Funk SVD minimizes regularized squared error over OBSERVED entries only — no imputation, so no fill-value bias.
- Each SGD step: err = r − p·q, then nudge p and q (and biases) by lr·(err·other − λ·self). Two cheap vector updates per rating.
- Add global mean + user/item biases (μ + b_u + b_i + p·q); ALS is the alternating closed-form alternative, the default for implicit feedback at scale.
Funk SVD with biases is the canonical explicit-feedback recommender (the Surprise library's SVD); ALS powers Spark MLlib and the implicit library used across industry.
If you remove it: Without learning factors on observed entries, you're stuck with imputation-biased SVD or non-scaling memory-based CF — neither competitive on real sparse data.