Matrix Factorization for Recommendation

Latent factors, regularization, and alternating least squares

Ben Dai

CUHK · Department of Statistics and Data Science

Why averages miss the match

Global, user, and item means describe overall tendencies. But two users with the same average can like opposite films.

FOUR OBSERVED RATINGS

Global mean = 3

THREE-MEAN BASELINE
\[\widehat r_{ui}=w_u\bar r_u+w_i\bar r_i+w_0\mu\]
Every pair gets the same prediction: 3

Each mean is 3. With weights summing to 1, the baseline misses who likes which film.

We need a user–item interaction: a model that can give \((0,0)\) a different prediction from \((1,0)\).

What the ratings matrix leaves blank

OBSERVED\(\Omega_{\mathrm{train}}\)

User–item pairs whose ratings are available for fitting.

TO PREDICT\(\widehat r_{ui}\)

Missing pairs are questions. A blank is not a zero rating.

Fit only the observed ratings. Then use the learned pattern to predict a new pair.

MF mattered in the Netflix Prize

Netflix challenged teams to predict held-out movie ratings from 100 million+ observed ratings.

2009 GRAND PRIZE WINNERBellKor’s
Pragmatic Chaos

The winning prediction was a blend of many models.

MF’S ROLEMultiple factorization models

The blend included several MF variants, alongside neighborhood models and other predictors.

Source: Koren, The BellKor Solution to the Netflix Grand Prize (2009), §§ I, IV.

The bias + dot-product model we will study is the starting point for this influential family. How can it learn to match users with films?

A shared space for users and films

To picture \(K=2\), imagine two possible tastes. Both user and film profiles use the same axes.

factor 1 · action-like factor 2 · romance-like
USER PROFILES\(p_u\): how much each taste matters to this user
User 0 action fan
1.00.2
User 1 romance fan
0.21.0
FILM PROFILES\(q_i\): positive or negative signals on the same axes
Item 0 action-heavy
1.5−1.5
Item 1 romance-heavy
−1.51.5

We chose these profile numbers for the picture. How could a real model find its own numbers from ratings?

Where do the profiles come from?

The previous slide used hand-picked profiles. In a real dataset we observe ratings, not profile coordinates; fitting must infer those coordinates.

WHAT WE OBSERVE Rating rows
userfilmrating
005
011
115

These are three known entries from the ratings matrix. There are no “action taste” columns.

FIT MF
→
AFTER FITTING Profiles inferred from ratings
User \(u\) \(p_u\in\mathbb R^K\)
Item \(i\) \(q_i\in\mathbb R^K\)

Fit also computes the global mean and learns user/item bias terms.

WE CHOOSE \(K\) BEFORE FITTINGFit the profile values to explain the ratings we have.

Latent means the factors are hidden from the input table, not unknowable. The model estimates them from ratings; “action / romance” are only teaching labels.

Baseline + dot product predicts a rating

For this calculation, reuse the hand-picked, not fitted profiles from “A shared space”: \(p_0=(1.0,0.2)\), \(q_0=(1.5,-1.5)\), and \(q_1=(-1.5,1.5)\).

BASELINE IN THIS TOY EXAMPLE\(\mu=3,\;a_u=b_i=0\)
FULL PREDICTION RULE\(\widehat r_{ui}=\mu+a_u+b_i+p_u^\top q_i\)
ITEM 0 · ACTION-HEAVY
1.0 × 1.5= 1.5
0.2 × (−1.5)= −0.3
3 + MATCH 1.2\(\widehat r_{0,0}=4.2\)
ITEM 1 · ROMANCE-HEAVY
1.0 × (−1.5)= −1.5
0.2 × 1.5= 0.3
3 + MATCH (−1.2)\(\widehat r_{0,1}=1.8\)

The baseline is 3 for both pairs; the interaction raises one prediction to 4.2 and lowers the other to 1.8. Fitting would adjust these example coordinates using the ratings.

Same rule, a different user

Keep the two item profiles and baseline \(3\). Change only to User 1’s illustrative profile: \(p_1=(0.2,1.0)\).

USER 1 × ITEM 0
\(p_1^\top q_0=0.2(1.5)+1.0(-1.5)=-1.2\)
\(\widehat r_{1,0}=3-1.2=\mathbf{1.8}\)
USER 1 × ITEM 1
\(p_1^\top q_1=0.2(-1.5)+1.0(1.5)=+1.2\)
\(\widehat r_{1,1}=3+1.2=\mathbf{4.2}\)

The baseline remains 3 for every pair. Changing the user changes the interaction: User 1 prefers Item 1, while User 0 preferred Item 0.

Four questions before writing the estimator

01
CUHK emblem

Model → hyperparameters → fitting criterion → learned parameters

1 · What is the model?

\[f_{\theta}(u,i)=\mu+a_u+b_i+p_u^\top q_i\]
PARAMETERS\(\theta=(\mu,a,b,P,Q)\)
BASELINE PARAMETERS\(\mu,\ a,\ b\)

\(\mu\) is one global value; \(a\in\mathbb R^n\) and \(b\in\mathbb R^m\) hold user and item biases.

INTERACTION PARAMETERS\(P,\ Q\)

\(P\in\mathbb R^{n\times K}\) and \(Q\in\mathbb R^{m\times K}\) hold the user and item profiles.

For input \((u,i)\), the rule uses \(a_u,b_i,p_u,q_i\) to predict one rating. Q4 will show their fitted values.

Which parameters does \((u,i)\) select?

Input: user ID 1, item ID 0. Each ID selects one position in a bias vector and one row in a factor matrix. We show \(K=2\) columns.

USER ID 1select row 1 in both

\(a\)parameter vector
\(n\times1\)
User Bias
0 \(a_0\)
1 \(a_1\)
2 \(a_2\)
\(P\)parameter matrix
\(n\times K\)
User factor 1 factor 2
0 \(p_{0,1}\) \(p_{0,2}\)
1 \(p_{1,1}\) \(p_{1,2}\)
2 \(p_{2,1}\) \(p_{2,2}\)

ITEM ID 0select row 0 in both

\(b\)parameter vector
\(m\times1\)
Item Bias
0 \(b_0\)
1 \(b_1\)
2 \(b_2\)
\(Q\)parameter matrix
\(m\times K\)
Item factor 1 factor 2
0 \(q_{0,1}\) \(q_{0,2}\)
1 \(q_{1,1}\) \(q_{1,2}\)
2 \(q_{2,1}\) \(q_{2,2}\)
LOOK UP FOUR VALUES, THEN PREDICT\(\widehat r_{1,0}=\mu+a_1+b_0+p_1^\top q_0\)

\(a,b,P,Q\) are learned during fit. At prediction time, the input contains only the two IDs.

How does \((u,i)\) become a prediction?

Use the hand-picked values from “A shared space” to see how stored parameters produce one prediction.

INPUT\((u,i)=(0,0)\)No rating is supplied
BASELINE TERMS
\(\mu=3,\quad a_0=0,\quad b_0=0\)

\(\mu+a_0+b_0=3\)

INTERACTION TERMS
\(p_0=(1.0,0.2)\)
\(q_0=(1.5,-1.5)\)

\(p_0^\top q_0=1.2\)

PREDICTED RATING\(\widehat r_{0,0}=3+1.2=4.2\)

The model uses the two IDs and its stored parameters. The observed rating is not supplied to predict.

2 · Which choices are hyperparameters?

NUMBER OF FACTORS\(K\in\{1,2,\ldots\}\)

Controls how much user–item structure the model can express.

REGULARIZATION STRENGTH\(\lambda\geq 0\)

Controls how strongly fitting discourages large factor values.

Choose \((K,\lambda)\) before each fit; compare candidate choices with held-out ratings.

3 · What criterion do we minimize?

First set \(\mu\) to the mean of the fitting ratings. Then learn the biases and factors:

\[\begin{aligned} \min_{a,b,P,Q}\;J &=\sum_{(u,i)\in\Omega_{\mathrm{train}}} \bigl(r_{ui}-\mu-a_u-b_i-p_u^\top q_i\bigr)^2\\ &\quad+\lambda\bigl(\|P\|_F^2+\|Q\|_F^2\bigr). \end{aligned}\]
FIT

Explain ratings the model was allowed to see.

CONTROL

Discourage large factors that may fit noise.

\(\mu\) is the fitting-fold mean. Ridge learns each bias as an unpenalized intercept; \(\lambda\) penalizes only the latent factors.

4 · What does fit learn?

BASELINE TERMS\(\widehat\mu,\ \widehat a,\ \widehat b\)

The fitting mean, one user bias per user, and one item bias per item.

LATENT FACTORS\(\widehat P,\ \widehat Q\)

One \(K\)-coordinate vector per user and per item.

\[\widehat r_{ui}=\widehat\mu+\widehat a_u+\widehat b_i+\widehat p_u^\top\widehat q_i\]

Learned from ratings: \(\mu,a,b,P,Q\). Chosen before fitting: \(K\) and \(\lambda\).

Two controls, two different effects

INCREASE \(K\)More factor coordinates

The model can represent richer interaction patterns. Training error can only improve or stay the same at a fixed \(\lambda=0\).

INCREASE \(\lambda\)Stronger shrinkage

Large factor values cost more in the fitting criterion. This can improve held-out predictions when an unregularized fit follows noise.

Neither “larger” nor “smaller” is automatically best. Choose with validation RMSE, as in ML II.

Select \(K\) and \(\lambda\) with CV

01Choose candidates

e.g. \(K\in\{2,5,10\}\) and \(\lambda\in\{0.1,1,10\}\)

→
02Fit on each training fold

Compute \(\mu\); learn new \(a,b,P,Q\) for every candidate and fold.

→
03Score held-out pairs

Average validation RMSE across folds.

Then refit the chosen settings on all development ratings, and evaluate once on the untouched test set.

The same sklearn estimator structure

SETTINGS__init__(K, lambda_, …)

Remember constructor choices.

→
LEARNINGfit(X, y)

Compute \(\mu\) and learn \(a,b,P,Q\) from rating rows.

→
PREDICTIONpredict(X)

Add baseline and interaction for each pair.

X: two columns [user ID, item ID]   ·   y: one-dimensional ratings

The class interface lets GridSearchCV repeat fit and predict. We still need an algorithm inside fit.

How can we fit the factors?

02
CUHK emblem

Alternating least squares updates biases and factors with Ridge regression.

A difficult joint problem, two familiar subproblems

JOINTLYLearn user and item terms

The interaction contains a product of unknowns, \(p_u^\top q_i\).

ONE BLOCK AT A TIMEHold one side fixed

Update an item bias with its factor vector, then a user bias with its factor vector.

\((a,P)\) fixed → update \((b,Q)\) → \((b,Q)\) fixed → update \((a,P)\)

This is alternating least squares (ALS). The global mean \(\mu\) stays fixed at the fitting-data mean while the two blocks alternate.

ALS follows the loss contours one block at a time

A schematic 2D view of the training objective \(J\): each contour joins points with the same loss.

Schematic loss contours with a zigzag ALS path. Purple vertical arrows update the item block while the user block is fixed; gold horizontal arrows update the user block while the item block is fixed. The path moves toward lower loss.

Fix \((a,P)\); update \((b,Q)\)Fix \((b,Q)\); update \((a,P)\)

Repeat the vertical and horizontal moves. Each axis represents a whole parameter block, not one scalar.

Fix the users; update one item

For item \(i\), let \(U_i\) be the users who rated it. Hold their \(a_u,p_u\) values fixed and fit \(b_i,q_i\) together.

\[\begin{aligned} (\widehat b_i,\widehat q_i)=\underset{b,q}{\arg\min}\;&\sum_{u\in U_i}\bigl[(r_{ui}-\mu-a_u)-(b+p_u^\top q)\bigr]^2\\ &+\lambda\|q\|_2^2. \end{aligned}\]
RIDGE INPUTS\(X_i=[p_u^\top]_{u\in U_i}\)
TARGETS\(y_i=[r_{ui}-\mu-a_u]_{u\in U_i}\)
RIDGE OUTPUT\(b_i\) = intercept_
\(q_i\) = coef_

Use fit_intercept=True: Ridge learns \(b_i\) as its intercept and regularizes \(q_i\) as its coefficients.

Fix the items; update one user

For user \(u\), let \(I_u\) be the items they rated. Hold their \(b_i,q_i\) values fixed and fit \(a_u,p_u\) together.

\[\begin{aligned} (\widehat a_u,\widehat p_u)=\underset{a,p}{\arg\min}\;&\sum_{i\in I_u}\bigl[(r_{ui}-\mu-b_i)-(a+q_i^\top p)\bigr]^2\\ &+\lambda\|p\|_2^2. \end{aligned}\]
RIDGE INPUTS\(X_u=[q_i^\top]_{i\in I_u}\)
TARGETS\(y_u=[r_{ui}-\mu-b_i]_{i\in I_u}\)
RIDGE OUTPUT\(a_u\) = intercept_
\(p_u\) = coef_

Same Ridge operation, with the roles of users and items reversed. The user bias is the intercept.

One complete ALS iteration

STARTInitialize \(\mu,a,b,P\)

Compute \(\mu\) from fitting ratings; set biases to zero and use small random factors.

ITEM UPDATEFit each \((b_i,q_i)\)

Ridge on the users who rated item \(i\).

USER UPDATEFit each \((a_u,p_u)\)

Ridge on the items rated by user \(u\).

REPEATCheck objective

Stop when improvement is small or the iteration limit is reached.

Each item or user update is a small independent Ridge problem within its block.

The Ridge call inside an item update

from sklearn.linear_model import Ridge

# User-side a and P are fixed; fit item bias and factors
user_ids = user_ids_for_item_i
X_item = P[user_ids]
y_item = ratings_for_item_i - mu - a[user_ids]

ridge = Ridge(alpha=lambda_, fit_intercept=True)
ridge.fit(X_item, y_item)
b[i] = ridge.intercept_
Q[i] = ridge.coef_

The Ridge intercept gives the item bias; its coefficients give the item factors. User updates work the same way.

Monitor the objective, not just the loop counter

AFTER ITEM UPDATES\(J_{\mathrm{item\ step}}\)
≥
AFTER USER UPDATES\(J_{\mathrm{user\ step}}\)
With exact block minimization, the training objective should not increase after either block update.
If it increases: check the user/item indexing, the Ridge penalty scale, and whether the objective uses the same ratings as the updates.

A new ID has no learned bias or factor

WARM STARTKnown user + known item

Use \(\widehat\mu+\widehat a_u+\widehat b_i+\widehat p_u^\top\widehat q_i\).

COLD STARTSome terms are unavailable

New user: use \(\widehat\mu+\widehat b_i\). New item: use \(\widehat\mu+\widehat a_u\). Both new: use \(\widehat\mu\).

When reporting RMSE, separate warm-start and cold-start cases if the split contains both. An MF dot product alone does not solve cold start.

Put the whole workflow together

MODELbiases + \(p_u^\top q_i\)
→
FITALS via Ridge
→
SELECTCV over \(K,\lambda\)
→
PREDICTtest pairs once
CHECK YOUR UNDERSTANDING

In MF, which quantities are chosen before fitting, which are learned by fit, and which ratings may be used to choose the final model?