Monday, December 11, 2006

Abstraction: Simon Funk's Netflix Prize SVD collaborative filtering algorithm explained

Key points:

• Netflix Prize dataset: 100M ratings, 500K users, 17K movies; goal is to minimize RMSE on held-out ratings in an 8.5B-cell sparse matrix
• Core model: rank-40 (or higher) matrix factorization — each user and movie represented by a feature vector; predicted rating = dot product of user and movie feature vectors
• Training via stochastic gradient descent on observed ratings only, with learning rate 0.001; one epoch over 100M ratings takes ~7.5 seconds on a laptop in C
• Key refinement: regularization ("decay") term penalizes feature magnitude to prevent overfitting sparse users/movies — equivalent to Tikhonov/ridge regularization, K~0.02
• Baseline model: per-movie average + per-user offset with Bayesian shrinkage toward global mean (equivalent to K=25 observations prior)
• Non-linear extensions tested: per-stage clipping to 1-5 range and piecewise-linear output function; beneficial only for first ~20 features

Connections: Netflix · Matrix Factorization · Collaborative Filtering · Recommendation Systems · Regularization

Source: https://sifter.org/~simon/journal/20061211.html