"algo-rec-mf"

Matrix Factorization

Overview

Matrix factorization decomposes the user-item interaction matrix R (m×n) into two low-rank matrices: U (m×k) and V (n×k), where k << min(m,n). Predicted rating: r̂ᵢⱼ = uᵢ · vⱼ. Trains in O(k × nnz × iterations) where nnz = non-zero entries.

When to Use

Trigger conditions:

• Scaling CF beyond pairwise similarity (millions of users/items)
• Discovering latent factors that explain user-item interactions
• Predicting ratings for unobserved user-item pairs

When NOT to use:

• When interaction data is extremely sparse (< 0.1% fill) — insufficient for learning
• When you need real-time updates (retraining is expensive)

Algorithm

IRON LAW: Rank k Controls Bias-Variance Trade-Off
- Too LOW k: underfits, misses nuanced preferences (high bias)
- Too HIGH k: overfits to noise, poor generalization (high variance)
- Typical k: 20-200. Select via cross-validation on held-out ratings.
- Always add regularization (λ) to prevent overfitting.

Phase 1: Input Validation

Load sparse interaction matrix. Split into train/validation/test. Check minimum density. Gate: Train matrix has sufficient entries per user and item.

Phase 2: Core Algorithm

ALS (Alternating Least Squares):

1. Initialize U, V randomly (or with SVD warm-start)
2. Fix V, solve for U: minimize ||R - UV^T||² + λ(||U||² + ||V||²)
3. Fix U, solve for V using same objective
4. Alternate until convergence (RMSE change < ε)

SGD alternative: Update u_i, v_j incrementally for each observed rating using gradient descent.

Phase 3: Verification

Compute RMSE on held-out validation set. Compare against baseline (global mean, user mean). Gate: Validation RMSE significantly below baseline.

Phase 4: Output

Return top-N predictions per user with predicted scores.

Output Format

{
  "recommendations": [{"user_id": "u1", "items": [{"item_id": "i5", "predicted_rating": 4.3}]}],
  "metadata": {"rank_k": 50, "regularization": 0.01, "iterations": 20, "train_rmse": 0.82, "val_rmse": 0.91}
}