Regularization to Prevent Overfitting

When training a matrix factorization model with Stochastic Gradient Descent, the primary goal is to minimize the prediction error on the training data. While this sounds correct, pursuing this goal too aggressively can lead to a significant problem: overfitting. An overfit model learns the specific details and noise of the training data so well that it fails to generalize to new, unseen data.

In the context of matrix factorization, overfitting means the model generates latent factor vectors for users and items ($p_u$ and $q_i$) that are highly specialized to the ratings in the training set. These vectors often contain very large positive or negative values, which allows them to perfectly reconstruct the known ratings but results in poor, often extreme predictions for unknown ratings. The model effectively memorizes the training examples instead of learning the underlying patterns of user taste.

Penalizing Model Complexity

To combat overfitting, we can introduce a technique called regularization. The idea is to modify the cost function to penalize model complexity. For matrix factorization, complexity is associated with the magnitude of the values in the latent factor vectors. By adding a penalty for large factor values, we encourage the model to find a simpler solution that explains the data well without fitting the noise.

The most common method for this is L2 regularization. We add a penalty term to our original squared error cost function that is proportional to the sum of the squared values of all elements in our user-factor and item-factor matrices.

The updated cost function looks like this:

$$\text{Cost} = \sum_{(u,i) \in K} (r_{ui} - p_u^T q_i)^2 + \lambda \left( \sum_{u} ||p_u||^2 + \sum_{i} ||q_i||^2 \right)$$

Let's break down this new formula:

• The first term, $\sum_{(u,i) \in K} (r_{ui} - p_u^T q_i)^2$, is the same sum of squared errors we tried to minimize in the previous section. It pushes the model to make accurate predictions.
• The second term, $\lambda \left( \sum_{u} ||p_u||^2 + \sum_{i} ||q_i||^2 \right)$, is the L2 regularization penalty.
  • $||p_u||^2$ is the squared L2 norm of the user's latent vector, calculated as $\sum_{k=1}^{K} p_{uk}^2$. This is the sum of the squares of its elements.
  • $||q_i||^2$ is the squared L2 norm of the item's latent vector, calculated as $\sum_{k=1}^{K} q_{ik}^2$.
  • $\lambda$ (lambda) is a hyperparameter that controls the strength of the regularization. A higher $\lambda$ value results in a stronger penalty, forcing the latent factor values to be smaller and creating a simpler model. A $\lambda$ of 0 removes regularization entirely.

The optimization process now has to balance two objectives: minimizing the prediction error and keeping the latent factor vectors small.

Modifying the SGD Update Rules

This change to the cost function also modifies the gradients we use in our SGD update rules. When we calculate the partial derivatives with respect to $p_{uk}$ and $q_{ik}$, the regularization term adds a new component. The resulting update rules become:

For each rating $r_{ui}$ in the training set:

1. Calculate the prediction error: $e_{ui} = r_{ui} - p_u^T q_i$
2. Update the user vector $p_u$: $p_u \leftarrow p_u + \eta \cdot (e_{ui} \cdot q_i - \lambda \cdot p_u)$
3. Update the item vector $q_i$: $q_i \leftarrow q_i + \eta \cdot (e_{ui} \cdot p_u - \lambda \cdot q_i)$

Notice the new parts: $- \lambda \cdot p_u$ and $- \lambda \cdot q_i$. On every update, in addition to moving the vectors along the gradient of the error, we also shrink them slightly by a factor proportional to $\lambda$. This prevents any single element in the latent vectors from growing too large and dominating the dot product calculation, leading to a more stable and generalizable model.

Finding the Right Balance with Lambda

The choice of $\lambda$ is important for model performance. It controls the trade-off between fitting the training data and keeping the model simple.

• If $\lambda$ is too low: The regularization effect is weak, and the model may still overfit.
• If $\lambda$ is too high: The penalty for large vector values is severe. The model will produce very small latent factors, potentially becoming too simple and failing to capture the underlying patterns in the data, a problem known as underfitting.

The optimal value for $\lambda$ is typically found through experimentation. You would train models with different $\lambda$ values and evaluate their performance on a separate validation dataset (a portion of data not used for training). The value that yields the best performance on the validation set is chosen.

The relationship between regularization strength, training error, and validation error. As $\lambda$ increases, training error rises because the model is more constrained. Validation error typically decreases to a minimum point (the optimal $\lambda$) before rising again due to underfitting.

In practice, most recommendation system libraries, including the ones we will use shortly, provide parameters to easily control regularization, so you can focus on tuning its strength rather than implementing the update rules from scratch.