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_...